• dsimcha (17/17) Mar 15 2009 Following up on a discussion from yesterday, it's become increasingly cl...

dsimcha <dsimcha yahoo.com> writes:

Following up on a discussion from yesterday, it's become increasingly clear to
me that the current associative array implementation interacts poorly with
conservative garbage collection and D's memory allocator.  In the current
design, we have a struct that holds two pointers, the hash, the key and the
value.  This means the hash, the key and the value can all be false pointers.
 Furthermore, we have a system that requires a separate memory allocation
every time an element is added to an AA, killing multithreaded code performance.

A scheme that would interact better with conservative GC and D's memory
management might be coalesced hashing
(http://en.wikipedia.org/wiki/Coalesced_hashing) or quadratic probing
(http://en.wikipedia.org/wiki/Quadratic_probing), in either case using
parallel arrays instead of structs.  This would allow each type to live in its
own GC block and the non-pointer types to not be scanned by the GC.

Has anyone else besides me been having problems with the interaction between
AAs and the GC, or am I just hitting corner cases?  Is there enough interest
in this that it would be worth it for me to prototype some of these AA
implementations for druntime that would interact better with the GC?