www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Array, AA Implementations

reply dsimcha <dsimcha yahoo.com> writes:
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.
Oct 19 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 19 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 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.

against which the performance of AAs can be evaluated. Andrei

I'll work on it. I don't know much about how/where to host a such a website (my web programming skills are lacking), so I'll ask for volunteers to set this up. As far as the benchmark, so far the obvious ones seem to be speed and space efficiency under the following combinations of attributes: key size/hashing cost: small vs. large size of AA: Small (<100 elements), medium (100-10,000), large(10,000-1,000,000), enormous(1,000,000+) hashing performance: well-behaved/near uniform vs. poorly behaved/worst-case usage: insert/remove-heavy vs. read-heavy 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. 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.
Oct 19 2009
parent reply Jerry Quinn <jlquinn optonline.net> writes:
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.
 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'd also like to see a way to allow the user to implement a custom AA for some uses and still be able take advantage of the nice syntactic sugar the language provides.
Oct 19 2009
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Jerry Quinn (jlquinn 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.


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

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.


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).
Oct 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
On 19/10/2009 21:20, dsimcha wrote:
 == Quote from Jerry Quinn (jlquinn 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.


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

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.


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
Oct 19 2009
next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Yigal Chripun (yigal100 gmail.com)'s article
 On 19/10/2009 21:20, dsimcha wrote:
 == Quote from Jerry Quinn (jlquinn 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.


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

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




 hash tables when it makes sense, make this the default builtin AA, and




 of the underlying implementations in std.containers for when the user wants
more
 control over the details rather than DWIM.


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).

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.
Oct 19 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Yigal Chripun wrote:
 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html

This is a solid framework, unlike Java's containers which are a joke. I disagree with some of Gobo's abstractions (e.g. I believe all containers must be traversable and that primitives such as count() have no place in a general container) but generally the framework seems to be very well put together. It's a great source of inspiration for Phobos. Thanks very much for the link. Andrei
Oct 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
On 19/10/2009 23:42, Andrei Alexandrescu wrote:
 Yigal Chripun wrote:
 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html

This is a solid framework, unlike Java's containers which are a joke. I disagree with some of Gobo's abstractions (e.g. I believe all containers must be traversable and that primitives such as count() have no place in a general container) but generally the framework seems to be very well put together. It's a great source of inspiration for Phobos. Thanks very much for the link. Andrei

My understanding of this design is that they identified all the orthogonal properties relevant to containers and that specific containers are a composition of a specific set of such properties. Eiffel has MI (different from the c++ implementation) which is helpful if you already have suitable default implementations for these properties. regarding "traversable" property: what if I want a container for a non-ordered type? an example would be a container of complex numbers, how would you traverse it? what about hash tables?
Oct 21 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Yigal Chripun wrote:
 On 19/10/2009 23:42, Andrei Alexandrescu wrote:
 Yigal Chripun wrote:
 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html

This is a solid framework, unlike Java's containers which are a joke. I disagree with some of Gobo's abstractions (e.g. I believe all containers must be traversable and that primitives such as count() have no place in a general container) but generally the framework seems to be very well put together. It's a great source of inspiration for Phobos. Thanks very much for the link. Andrei

My understanding of this design is that they identified all the orthogonal properties relevant to containers and that specific containers are a composition of a specific set of such properties. Eiffel has MI (different from the c++ implementation) which is helpful if you already have suitable default implementations for these properties. regarding "traversable" property: what if I want a container for a non-ordered type? an example would be a container of complex numbers, how would you traverse it? what about hash tables?

Well as others mentioned, a hash table is traversable, just not in a particularly ordered manner. IMHO any container must offer at the very least (I'll use stylized signatures): 1. Got any? bool empty(); 2. Iterate using at least a one-pass range OnePassRange!E opSlice(); 3. Remove some element from the container and give it to me E removeAny(); 4. Add an element to the container is possible bool add(E); 5. Nuke void clear(); I think any container must support these primitives in O(1), and I find it difficult to think of a significant category of containers that can't support them (but then there may as well be, so please join me in thinking of that). A lot of stuff can be done with only these few methods. Note that even though length() is not part of the interface (as is in Gobo's library), it can be computed through iteration with a generic algorithm. The idea is to not force containers to write that themselves or ungainly cache the length. Please let me know of any thoughts. Andrei
Oct 21 2009
next sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
Andrei Alexandrescu wrote:
 IMHO any container must offer at the very least (I'll use stylized
 signatures):
 
 2. Iterate using at least a one-pass range
 
 OnePassRange!E opSlice();

Requiring this to be O(1) seems silly, since the actual iteration will never be O(1) and can't even be guaranteed to be O(n).
 3. Remove some element from the container and give it to me
 
 E removeAny();

IIRC, C++ had a good reason (related to exception safety) for separating retrieval and removal operations.
 Note that even though length() is not part of the interface (as is in
 Gobo's library), it can be computed through iteration with a generic
 algorithm. The idea is to not force containers to write that themselves
 or ungainly cache the length.

If the length is often needed, caching is much more efficient than recalculating from scratch. -- Rainer Deyke - rainerd eldwood.com
Oct 21 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Rainer Deyke wrote:
 Andrei Alexandrescu wrote:
 IMHO any container must offer at the very least (I'll use stylized
 signatures):

 2. Iterate using at least a one-pass range

 OnePassRange!E opSlice();

Requiring this to be O(1) seems silly, since the actual iteration will never be O(1) and can't even be guaranteed to be O(n).

The idea is that the cost of creating the iterator should not be significant. The cost of the iteration should be O(n) (not greater).
 3. Remove some element from the container and give it to me

 E removeAny();

IIRC, C++ had a good reason (related to exception safety) for separating retrieval and removal operations.

C++ does not have D's latitude to relocate objects.
 Note that even though length() is not part of the interface (as is in
 Gobo's library), it can be computed through iteration with a generic
 algorithm. The idea is to not force containers to write that themselves
 or ungainly cache the length.

If the length is often needed, caching is much more efficient than recalculating from scratch.

Yah, client code or a refined container may cache it. This has been a long discussion in the C++ community. Short version: you can't reasonably require O(1) length. Andrei
Oct 21 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bill Baxter wrote:
 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:
 
 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);

 I think any container must support these primitives in O(1), and I find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in thinking
 of that). A lot of stuff can be done with only these few methods.

I think balanced trees generally take O(lg N) to add and remove elements.

Good point, thanks. Logarithmic of better. Andrei
Oct 21 2009
parent reply Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);

 I think any container must support these primitives in O(1), and I 
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in 
 thinking
 of that). A lot of stuff can be done with only these few methods.

I think balanced trees generally take O(lg N) to add and remove elements.

Good point, thanks. Logarithmic of better. Andrei

Oct 22 2009
next sibling parent =?ISO-8859-1?Q?Pelle_M=E5nsson?= <pelle.mansson gmail.com> writes:
Don wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);

 I think any container must support these primitives in O(1), and I 
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in 
 thinking
 of that). A lot of stuff can be done with only these few methods.

I think balanced trees generally take O(lg N) to add and remove elements.

Good point, thanks. Logarithmic of better. Andrei


Amortized logarithmic is equivalent to logarithmic.
Oct 22 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Don wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);

 I think any container must support these primitives in O(1), and I 
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in 
 thinking
 of that). A lot of stuff can be done with only these few methods.

I think balanced trees generally take O(lg N) to add and remove elements.

Good point, thanks. Logarithmic of better. Andrei


Don't see why not. Also, it turns out that iteration over a tree may cost O(log n) per step. Andrei
Oct 22 2009
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Thu, 22 Oct 2009 01:35:49 +0400, Yigal Chripun <yigal100 gmail.com>  
wrote:

 On 19/10/2009 23:42, Andrei Alexandrescu wrote:
 Yigal Chripun wrote:
 here's an example of a well designed, consistent API:
 http://www.gobosoft.com/eiffel/gobo/structure/index.html

This is a solid framework, unlike Java's containers which are a joke. I disagree with some of Gobo's abstractions (e.g. I believe all containers must be traversable and that primitives such as count() have no place in a general container) but generally the framework seems to be very well put together. It's a great source of inspiration for Phobos. Thanks very much for the link. Andrei

My understanding of this design is that they identified all the orthogonal properties relevant to containers and that specific containers are a composition of a specific set of such properties. Eiffel has MI (different from the c++ implementation) which is helpful if you already have suitable default implementations for these properties. regarding "traversable" property: what if I want a container for a non-ordered type? an example would be a container of complex numbers, how would you traverse it? what about hash tables?

What's wrong with iterating over a hash table? An order is just unreliable (but still deterministic).
Oct 21 2009
prev sibling next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:

 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);

 I think any container must support these primitives in O(1), and I find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in thinking
 of that). A lot of stuff can be done with only these few methods.

I think balanced trees generally take O(lg N) to add and remove elements. --bb
Oct 21 2009
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 22 Oct 2009 09:07:47 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 Don wrote:
 Andrei Alexandrescu wrote:
 Bill Baxter wrote:
 On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> wrote:

 3. Remove some element from the container and give it to me

 E removeAny();

 4. Add an element to the container is possible

 bool add(E);

 I think any container must support these primitives in O(1), and I  
 find it
 difficult to think of a significant category of containers that can't
 support them (but then there may as well be, so please join me in  
 thinking
 of that). A lot of stuff can be done with only these few methods.

I think balanced trees generally take O(lg N) to add and remove elements.

Good point, thanks. Logarithmic of better. Andrei


Don't see why not. Also, it turns out that iteration over a tree may cost O(log n) per step.

Yes, but it's actually O(n) to traverse the entire tree, because you traverse 2n edges in the tree (one left and one right) twice (once to go down, and once to go back). -Steve
Oct 22 2009
prev sibling parent reply Piotrek <starpit tlen.pl> writes:
dsimcha pisze:
 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.

Can immutable attribute be used for it? I mean for determine when create StaticAA like array. Cheers Piotrek
Oct 19 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Piotrek (starpit tlen.pl)'s article
 dsimcha pisze:
 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.

StaticAA like array. Cheers Piotrek

I thought of that, but no, because immutable is transitive. StaticAA would be strictly a niche library type. Not even sure, it may be too niche for the std. lib., but it's incredibly useful specifically for the type of work I do.
Oct 19 2009