Python dictionary inspired hash table implementation

[Moritz Warning]

On Fri, 04 Jul 2008 19:45:47 +0000, Manfred_Nowak wrote:

> Moritz Warning wrote:
> 
>> The tests for the build-in AA had to be started ten times since the
>> test loop causes out of memory problems. The effect on the test result
>> should be negligible.
> 
> No. You should reduce the number of operations to 7_500_000.
> 
> Sorrily the PyDict seems to be bad suited for adresses out of the 2G-
> range. My tests show, that the builtin AA only needs 45% of the time of
> PyDict.
> 
> To verify this on your machine set
> 
>   ttotal= 512*1024*1024; // 512 MB
> 
> and replace "rand()" by "rand() << 2",
> 
> which effectively gives 4 byte alligned adresses out of the 2G range.
> 
> -manfred

With these changes, I get these results:

PyDict:7.73s
AA: 9.76s
HashMap: 7.36s

PyDict decreases in performance for this case.
But I can't see any significant speedup for AA.



Btw.: I had the 4x table grow for small tables changed to 2x in PyDict 
for all previous tests, since there wasn't any speed decrease to measure.