[Mono-devel-list] CoreLib's HashTable CalcPrime() new code
Paolo Molaro
lupus at ximian.com
Tue Sep 2 05:49:50 EDT 2003
On 09/01/03 Yuri Astrakhan wrote:
> I have rewritten CalcPrime() in the
> mcs\class\corlib\System.Collections\Hashtable.cs to fix several bugs (ie
> 15 was shown as a prime and the result was sometimes below the original
> value) The speed has been improved almost 4.5 times according to the
> 30 second tests, by skipping numbers divisible by 2 and 3. There is some
> bits magic, but code is, hopefully, clear / enough commented. TestPrime()
> is no longer needed and should be removed.
I would just remove both CalcPrime and TestPrime and extend the
precomputed size array, instead. There's no point computing the size
at runtime when we can easily do it offline.
> Also, there is a hardcoded prime number's table being used in
> ToPrime(), which waistes lots of resources (IMHO) because it skips most
> of the primes and new hash tables become overbloated. Why not use the
The point of the table is not only to find a prime number, but to also
allow the table to grow fast enough when it is filled without an
exponential factor in it. For example, if you just select each next
prime number the complexity is going to be O(n2) and we want it to
stay O(n) for insertion.
Thanks.
lupus
--
-----------------------------------------------------------------
lupus at debian.org debian/rules
lupus at ximian.com Monkeys do it better
More information about the Mono-devel-list
mailing list