Associative Arrays and Interior Pointers

[dsimcha]

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?