On Mon, 13 Apr 2009 01:45:00 -0400, bearophile <[email protected]>
wrote:
dsimcha:
What if the key is a long?
At the moment an AA like this:
byte[long] aa;
allocates 16 or more bytes/pair, so it needs the same memory as:
long[long] aa;
A built-in set can of course use only about 8 bytes (plus few empty
cells in the hash) for a:
HashSet!(long)
Bye,
bearophile
The AA node types are currently implemented as a binary tree for collision
resolution, so each node also needs at least 2 pointers for the child
nodes. Possibly a parent pointer, but I don't think so.
So T[long] aa will be 16 bytes + sizeof(T) for each node, assuming a
pointer is 4 bytes.
But technically, there is always going to be cases where waste occurs,
even without the void hack, depending on the resulting size of your
nodes. Imagine a 33 byte node, which will use up 64 bytes of space per
node. This is one of the reasons Tango and Dcollections have chunk
allocators where a large chunk of nodes is allocated at once from the GC
(or from malloc for non-GC types).
-Steve
