storing the hash multiplier instead of the hash value

[Michael Rynn]

On Mon, 22 Mar 2010 16:59:36 -0500, Andrei Alexandrescu wrote:

> On 03/22/2010 04:03 PM, Andrei Alexandrescu wrote:
>> On 03/22/2010 03:36 PM, Walter Bright wrote:
>>> Andrei Alexandrescu wrote:
>>>> Better suggestions are always welcome. For integrals I'm unclear on
>>>> what we could use to make things better. (Clearly we could and should
>>>> get rid of the extraneous field.)
>>>
>>> Unfortunately, it won't be much of a win. Memory allocation is done in
>>> buckets of size 16, 32, 64, etc. Reducing the node size for a
>>> uint[uint] from 16 to 12 saves no memory at all.
>>
>> As we discussed, if nodes are allocated in bunches, you could store 5
>> nodes in a 64-byte block instead of 4. That's more than a 25% increase
>> in effectiveness because the per-block bookkeeping is also slashed by
>> 5.
>>
>> Andrei
> 
> One more idea before I forget: the bunches approach requires using a
> freelist for nodes that are available but not used. (Freelists are a
> good idea whether or not bunches are used.)
> 
> One good possibility is to store the head of the freelist in a static
> variable, such that e.g. all int[string] instances use the same
> freelist. And there's no thread contention issue because each thread has
> its own freelist.
> 
> 
> Andrei

I just committed a aaA.d version that uses some heap node memory 
management, although its on a per class instance basis. Also it dispences 
with a separate hash storage for keys <= size_t.  Sharing would mean some 
working out of which classes share the same sized node blocks. 
Much easier to implement class sharing using templates.

See the code here : http://www.dsource.org/projects/aa/browser/trunk/
druntime/aaA.d

See the benchmarks and comments here : http://www.dsource.org/projects/aa/
wiki/DrunTimeAA.

The result squeezes some extra performance for integer or less sized keys
(about 20% faster for lookups).


For the druntime, the generic C interface constrains the kinds of 
specialized AA versions that can be instantiated using run-time TypeInfo 
and var-arged calls. Maybe a class / interface direct calls would work 
better. Just imagine at runtime looking at the TypeInfo_AssociatedArray 
and trying to work out exactly which template is going to be instantiated.

And having a low code size, one or few versions fit  all approach, that 
performance sacrifice is unavoidable in a basic runtime libary.

But in template land , options and combinations and gains abound.
---
Michael Rynn