Array, AA Implementations

[Andrei Alexandrescu]

dsimcha wrote:
> Since there has been a lot of discussion here lately about how AAs and
> ArrayBuilders should be implemented, we should set up a website where people
> can contribute different candidate implementations and comment on them.  It's
> much easier to know whether something is a good idea when you have a working
> implementation of it than when you're discussing it in the abstract.  Also,
> the act of actually implementing something forces you to think of details that
> get missed when talking about it in the abstract.
> 
> Especially for AAs, I think the best thing to do would be for everyone who has
> a good idea to post their code in some central place for comment.  If
> containers are to be added to Phobos, we could even post AA types that are
> meant to handle some special case and aren't intended to be general
> implementations.
> 
> I already have three AA implementations that I've been prototyping and would
> like to have reviewed, and I'm sure others have more:
> 
> 1.  An open-addressed linear chaining AA that's designed for pure speed in the
> common cases.  Somewhat similar to the current implementation but sacrifices
> worst-case performance to allow lazy range-based iteration with no additional
> allocations and more space efficiency and speed in the common cases.
> 2.  An implementation that uses linear congruential randomized probing,
> designed with conservative GC and space efficiency in mind.
> 3.  An implementation I call StaticAA, which does not allow the addition or
> removal of keys after it is constructed, but in exchange has almost zero space
> overhead and is very GC-efficient.  It works by maintaining sorted parallel
> arrays and using binary search.

That's a great idea. I suggest you to find some comprehensive benchmarks 
against which the performance of AAs can be evaluated.


Andrei