AA performance again

[Steven Schveighoffer]

"bearophile" wrote
> Steven Schveighoffer:
>> On my box (don't have python installed), 10m inserts took 15.3s, and the
>> memory usage was 290MB (I think :) )
>
> If you want, there are "mobile" versions of Python that doesn't require an 
> installation.
> I may want to ask you what's your CPU/clock.

CPU is dual-core Xeon 1.6GHz, only using one core of course.

To give you an idea of the speedup, the builtin AA's take 40.5 seconds to do 
10m inserts on my system.

>> Of course, the python numbers are much better, but the issue basically 
>> comes
>> down to when you allocate more memory, the GC tries to run and free some 
>> up
>> too often.  There's not a lot I can do about that.
>
> I don't think it's just a matter of memory allocator (but I have no proof 
> of this), there are many different macro and subtle ways to implement an 
> hash map in C.

At least in D, that seems to be the bottleneck.  This is why I get such a 
huge speedup using a custom allocator.  You might find this interesting, 
print out the time it takes for each million inserts :)

> Two more things:
> - In my blog post I have added a third Python version that's better, it 
> creates a true dict (AA):
> dict.fromkeys(xrange(20000000), 0)
> - I have used D longs because Python ints are like that (Python 2.5 uses 
> multiprecision numbers later), but Python integers are objects (so they 
> are "boxed"). Inside sets and dicts their memory usage for Python 2.5 is:
> set(int): 28.2 byte/element
> dict(int:None): 36.2 byte/element

You might also want to try setting the value of each element differently. 
I'm not sure it will make a difference, but perhaps python is doing 
something clever if all the values are 0.  The times you quote seem awfully 
fast, but the complexity of the issues is really beyond my understanding.

-Steve