Array, AA Implementations

[Yigal Chripun]

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