digitalmars.D - Associative Arrays and GC
- dsimcha <dsimcha yahoo.com> Mar 15 2009
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?
Mar 15 2009