https://issues.dlang.org/show_bug.cgi?id=10009

hsteoh@quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hsteoh@quickfur.ath.cx

--- Comment #12 from hsteoh@quickfur.ath.cx ---
It *is* possible to implement a reverse traversal in AA's. I'm just not sure it's a good idea (it'd need to allocate memory in order to traverse the linked-lists in reverse order).

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #13 from bearophile_hugs@eml.cc ---
(In reply to hsteoh from comment #12)
> It *is* possible to implement a reverse traversal in AA's. I'm just not sure it's a good idea (it'd need to allocate memory in order to traverse the linked-lists in reverse order).

Associative array pairs have a deterministic but undefined order. So what's the reverse of an undefined order? A simple solution is to turn foreach_reverse on an associative array in a compile-time error.

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #14 from yebblies <yebblies@gmail.com> ---
(In reply to bearophile_hugs from comment #13)
> 
> Associative array pairs have a deterministic but undefined order. So what's the reverse of an undefined order?

I'd love for the built-in AAs to use a linked hash map and guarantee iteration in insertion order...  It does have a performance hit on insertion and deletion, but it is a really nice property for a default AA that isn't super-optimized for any particular use case.

> A simple solution is to turn
> foreach_reverse on an associative array in a compile-time error.

Yeah, that fits with the error we added for foreach_reverse on a delegate.  AAs are special-cased in the compiler, should be easy enough to special-case an error for them.

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #15 from bearophile_hugs@eml.cc ---
(In reply to yebblies from comment #14)

> I'd love for the built-in AAs to use a linked hash map and guarantee iteration in insertion order...  It does have a performance hit on insertion and deletion, but it is a really nice property for a default AA that isn't super-optimized for any particular use case.

In my opinion built-in data structures should be first of all very flexible (and keeping the insertion order is a guaranteed that makes them more useful). But in engineering as usual you have trade-offs. So how much is going to increase the memory and how much is going to decrease the performance with that added feature?

In Python the built-in dict is fast, and there is an ordered dict in its standard library: https://docs.python.org/2/library/collections.html#collections.OrderedDict

With a druntime function added I think you can implement ordered AAs for Phobos (based on the built-in ones) in an efficient way and a small amount of code, see Issue 10733

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #16 from Steven Schveighoffer <schveiguy@yahoo.com> ---
(In reply to hsteoh from comment #12)
> It *is* possible to implement a reverse traversal in AA's. I'm just not sure it's a good idea (it'd need to allocate memory in order to traverse the linked-lists in reverse order).

Or you could recurse :)

Either way, you need memory.

I think we have two legitimate options:

1. Fix foreach_reverse .byKey so it does the same thing as foreach 2. Make foreach_reverse illegal on all cases of aa.

I lean towards 2.

The goal should be consistency. Making the thing actually work in reverse I think is not possible.

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #17 from yebblies <yebblies@gmail.com> ---
(In reply to Steven Schveighoffer from comment #16)
> (In reply to hsteoh from comment #12)
> > It *is* possible to implement a reverse traversal in AA's. I'm just not sure it's a good idea (it'd need to allocate memory in order to traverse the linked-lists in reverse order).
> 
> Or you could recurse :)
> 
> Either way, you need memory.
> 
> I think we have two legitimate options:
> 
> 1. Fix foreach_reverse .byKey so it does the same thing as foreach 2. Make foreach_reverse illegal on all cases of aa.
> 
> I lean towards 2.
> 
> The goal should be consistency. Making the thing actually work in reverse I think is not possible.

2 is absolutely the answer.  Basically copy-paste the error from the delegate foreach_reverse.  The check should be the same, just in the Taarray block.

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #18 from hsteoh@quickfur.ath.cx ---
+1 for 2. :-)

Implementing reverse traversal for what's essentially an arbitrary order is meaningless at best, and gives a false sense of a non-existent fixed ordering.

I think retaining insertion order is a needless overhead; if you needed such a thing, it should be implemented in the library instead.

--

https://issues.dlang.org/show_bug.cgi?id=10009

Ketmar Dark <ketmar@ketmar.no-ip.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ketmar@ketmar.no-ip.org

--- Comment #19 from Ketmar Dark <ketmar@ketmar.no-ip.org> ---
(In reply to yebblies from comment #14)
> I'd love for the built-in AAs to use a linked hash map and guarantee iteration in insertion order...
but you can implement your own AAs that does exactly this. built-in AAs aren't *that* special, just some sugar here and there, plus some D code in druntime.

actually, retaining insertion order will not be *that* slow, but you'll need two more pointers for each inserted element. this will even make some use cases faster (aa.byKey.first, for example, which is awfully slow now).

yet i'm not sure that everyone are ready to pay 8/64 bytes per AA element for this feature.

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #20 from yebblies <yebblies@gmail.com> ---
(In reply to hsteoh from comment #18)
> 
> I think retaining insertion order is a needless overhead; if you needed such a thing, it should be implemented in the library instead.

Sure, but sometimes it's really handy.  I've mostly wanted it when writing tests that accidentally relied on AA iteration order, which is perfectly stable unless you run the tests on different architectures.  It's not a big deal but it's a nice user-friendliness thing.  Anyone looking for high performance in the built-in AAs is on the wrong track.

(In reply to Ketmar Dark from comment #19)
> but you can implement your own AAs that does exactly this. built-in AAs aren't *that* special, just some sugar here and there, plus some D code in druntime.

Sure, but I tend to think of the builtin AAs as convenient but not necessarily high performance.

> actually, retaining insertion order will not be *that* slow, but you'll need two more pointers for each inserted element. this will even make some use cases faster (aa.byKey.first, for example, which is awfully slow now).
> 
> yet i'm not sure that everyone are ready to pay 8/64 bytes per AA element for this feature.

Maybe not.

--

https://issues.dlang.org/show_bug.cgi?id=10009

--- Comment #21 from Ketmar Dark <ketmar@ketmar.no-ip.org> ---
(In reply to yebblies from comment #20)
> Anyone looking for high performance in the built-in AAs is on the wrong track.
but why? it's wrong to assume that AA has any defined order of items for iteration. this is *really* wrong. but there is nothing wrong with fast and memory-effective built-in AAs. why include language feature that is known to be slow when it can be reasonably fast?

built-in AAs are very handy. and if they known to be slow, people will start to roll their own AA implementations virtually each time they want to use AA. and then we can just kill built-in AAs altogether.

> Sure, but I tend to think of the builtin AAs as convenient but not necessarily high performance.
i believe that built-in AAs should be fast, but not necessarily featurefull. and AAs with more features can be implemented in Phobos.

> > yet i'm not sure that everyone are ready to pay 8/64 bytes per AA element for this feature.
> Maybe not.
i certainly don't want that overhead. i done some work on faster byKey.first though, see https://issues.dlang.org/show_bug.cgi?id=13410

--