storing the hash multiplier instead of the hash value

[Andrei Alexandrescu]

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