Associative Arrays and Interior Pointers

[bearophile]

dsimcha:

I can see you are working a lot to try to improve the implementation of the language. Thank you for this.

> 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.

The built-in AAs have to be flexible and not too much bad for most purposes.
This implementation of yours has different trade offs compared to the built-in one. One way to answer what implementation is to prefer is to collect some amount of typical D1 code, and benchmark it with the two different AA implementations, and keep the AA implementation that leads to an average smaller total running time.
Then one or more different implementations may be added to Phobos for special usages (even Python has a second kind of associative array in the std lib, named defaultdict(), it's based on the same hashing machinery, but has some differences).


> 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.

Improving current things in a gradual way like this seems a good starting point (this is essentially the same answer I have given to Don regarding complex numbers).

Bye,
bearophile