GC-less Hash-Tables (AA)

[H. S. Teoh via Digitalmars-d-learn]

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