[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