On Wed, Sep 17, 2014 at 10:44:17PM +0000, "Nordlöw" via Digitalmars-d-learn wrote: > On Wednesday, 17 September 2014 at 22:36:55 UTC, H. S. Teoh via > Digitalmars-d-learn wrote: > >So you would use malloc/free? > > Yes, with GC-free I mean *not* involving D's automatic garbage > collector for the individual allocations of the AA *keys* and > *values*. > > How are these normally allocated in a hash-table?...as individual heap > allocations?
Assuming you're talking about the built-in AA's, the current implementation is as follows. There is the hashtable itself, which is just an array of pointers to individual buckets. The buckets are implemented as a linked-list of Slots, which are just structs containing a next pointer, the hash value, and a copy of the key and value. Obviously, individual allocations of Slots come from the GC heap, but in theory it could come from any allocator, potentially even malloc/free, since the lifetime of the Slots is well-defined (user code generally does not have direct access to them; so the AA always knows when a Slot is going out of scope). It does *not* perform separate allocations for keys and values. This means that if your keys and values are value-types, then there is no additional allocation besides the Slots themselves. For reference types, only the reference is stored (this is one of the sources of currently-open AA bugs where unexpected behaviour happens when non-immutable reference-type keys are used in AA's: somebody else changes the key after it's hashed, and this breaks the AA's ability to find that key/value again). No additional allocation is done unless the key/value type itself has a postblit that performs additional allocations. T -- I think Debian's doing something wrong, `apt-get install pesticide', doesn't seem to remove the bugs on my system! -- Mike Dresser
