Array, AA Implementations

dsimcha dsimcha at yahoo.com
Mon Oct 19 10:31:56 PDT 2009


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.



More information about the Digitalmars-d mailing list