Array, AA Implementations

[dsimcha]

== Quote from Jerry Quinn (jlquinn at optonline.net)'s article
> dsimcha Wrote:
> > If anyone can think of any more, please let me know.  Also, just thought of this
> > now:  I wonder if it would make sense to use some polymorphism tricks (AA
> > operations are slow enough that an extra pointer dereference or virtual function
> > call isn't going to make or break their performance) to allow implementations to
> > be automatically and dynamically changed depending on some of the attributes
> > listed above.
> This is not necessarily true.  If you are hammering a map of int to int,
function call overhead will matter a great deal and you would like the compiler to
be able to inline it.  Size will also matter for huge AA tables.
> On the other hand, perhaps you're willing to say that built-in AA's will not be
suitable for every case.

Yes.  The builtin should handle the most common 90-95% of cases, "special" AA
types in Phobos can handle another few percent, and for the last 1-2%, your
problem is so specialized that you understand it way better than the language/std.
lib designer that you should probably just roll your own or use some
hyper-specialized 3rd party lib.

> > For example, maybe binary trees are fastest for small N.  (Hypothetical, haven't
> > tested it.)  Obviously for sufficiently large N hash tables will be fastest.  We
> > could create an abstract AA type that automatically switches from binary trees to
> > hash tables when it makes sense, make this the default builtin AA, and expose both
> > of the underlying implementations in std.containers for when the user wants more
> > control over the details rather than DWIM.
> One thing I think is important is to codify the interface to the AA
implementation, so that files built with different compilers could be linked
together..

I was thinking define an interface (a runtime, OO interface, the kind you can
inherit from), and then define a bunch of final classes that implement that
interface.  This way, you can have either polymorphism (use the interface) or
speed (instantiate one of the final classes directly).