I've been playing around with associative array and it's led to two pretty interesting questions for other D users:
1. I have a prototype associative array implementation that's designed with D's GC implementation in mind. It is much easier on the GC (allocates much less frequently, causes almost no false pointers) than the current implementation. However, this comes at the price of worse cache performance that can cause lookups to take up to twice as long as the current implementation for large AAs. On the other hand, building these large AAs is an order of magnitude faster. Furthermore, my implementation only allocates occasionally, meaning in multithreaded mode, inserting an element will seldom require a lock. Therefore, the question is, how much cache/lookup performance are you willing to give up for an implementation that's more GC friendly, allows faster insertions, and requires less locking? Also, in your opinion, should D's builtin AA be designed around the GC implementation, or is this kind of coupling unacceptable? 2. Other than its abysmal interaction with the current GC and the lack of ability to iterate using ranges, the current AA implementation actually seems pretty good. One way to remedy a large portion of the GC issues without a massive overhaul of the GC would be to introduce a feature into the GC where a block of memory can be flagged as NO_INTERIOR. This would mean that it could only be kept alive by pointers to the base address. If this feature were implemented and used in memory blocks allocated by the current AA implementation, it would drastically reduce the false pointer issue. (What seems to happen is, first of all, the current implementation generates a lot of false pointers, and secondly, it allocates so many blocks of memory that a few of them are guaranteed to be kept around by false pointers, leading to massive heap fragmentation.) I've submitted a patch that implements this NO_INTERIOR feature. (See bugzilla 2927). Do you believe that this patch belongs in the GC?
