Array, AA Implementations

[dsimcha]

== Quote from Yigal Chripun (yigal100 at gmail.com)'s article
> On 19/10/2009 21:20, dsimcha wrote:
> > == 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).
> this is a good idea, but shouldn't such an API be designed as part of a
> collections API for phobos?
> here's an example of a well designed, consistent API:
> http://www.gobosoft.com/eiffel/gobo/structure/index.html

Well, we've got ranges for iteration.  Other than that, AAs don't have much in
common with any other collection, so I don't see much need to standardize and do a
big design up front.