Bug 10009 – AA.byKey/byValue should be bidirectional ranges

void main() { auto aa = [1 : 2, 2 : 3]; foreach_reverse (e; aa.byKey()) { } } ----- test.d(4): Error: invalid foreach aggregate aa.byKey().state ----- foreach works like a charm.

I think foreach_reverse was only ever meant to be used with arrays (and is scheduled for deprecations), for ranges you can use retro() from std.algorithm.

(In reply to comment #1) > I think foreach_reverse was only ever meant to be used with arrays (and is > scheduled for deprecations), for ranges you can use retro() from std.algorithm. I have hundreds of usages of foreach_reverse in my D2 codebase. You aren't going to deprecate it. retro() is not nearly as efficient for arrays.

(In reply to comment #2) > I have hundreds of usages of foreach_reverse in my D2 codebase. You aren't > going to deprecate it. retro() is not nearly as efficient for arrays. Sorry, my brain was switched off. And the usages are probably under one hundred. ----------------- (In reply to comment #1) > I think foreach_reverse was only ever meant to be used with arrays (and is > scheduled for deprecations), for ranges you can use retro() from std.algorithm. Maybe the compiler can rewrite this: foreach_reverse(x; someRange) as: foreach(x; someRange.retro) But I don't know what problems this causes.

(In reply to comment #2) > (In reply to comment #1) > > I think foreach_reverse was only ever meant to be used with arrays (and is > > scheduled for deprecations), for ranges you can use retro() from std.algorithm. > > I have hundreds of usages of foreach_reverse in my D2 codebase. You aren't > going to deprecate it. retro() is not nearly as efficient for arrays. Why is retro less efficient though?

> Why is retro less efficient though? Probably something to do with how the decoding is done and/or some extra steps which can be skipped. I don't think that I ever investigated it in detail, but I know that I used foreach_reverse in some functions in std.string because it was definitely faster according to the benchmarks that I did, much as I would prefer to never use it.

Well we better decide whether or not foreach_reverse is actually scheduled for deprecation. If it is then we shouldn't add more features to it.

Leave foreach_reverse alone!

The problem I see with removing foreach_reverse is that the compiler actually rewrites it directly instead of calling a function. Requiring to use retro when it is in std.range is not good for modularity. In addition, foreach_reverse(x..y) is nice to use instead of some combination of ranges. However, I don't think foreach_reverse is valid for this use case. An AA is only forward-traversable. foreach_reverse is not possible, as buckets are stored as singly-linked lists. If you want that, you need to first capture it as an array.

(In reply to comment #8) > However, I don't think foreach_reverse is valid for this use case. An AA is > only forward-traversable. foreach_reverse is not possible, as buckets are > stored as singly-linked lists. If you want that, you need to first capture it > as an array. Yet this compiles: import std.stdio: writeln; void main() { auto aa = [1: 2, 2: 3]; foreach (k, v; aa) writeln(k, " ", v); foreach_reverse (k, v; aa) writeln(k, " ", v); } And outputs: 1 2 2 3 1 2 2 3 The foreach seems to give the same sequence as the foreach_reverse :-)

> The foreach seems to give the same sequence as the foreach_reverse Which is essentially the same problem as bug# 6251.

(In reply to comment #10) > Which is essentially the same problem as bug# 6251. Not exactly. AA is a type, not a delegate. It is allowed to define opApplyReverse. A delegate cannot possibly be valid with foreach_reverse (and that bug should be killed with prejudice). Even if opApplyReverse is defined for AAs, the implementation will be wrong (as bearophile described) because it's built from singly linked lists.

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

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

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

(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

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

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

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

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

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

(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

(In reply to Ketmar Dark from comment #21) > (In reply to yebblies from comment #20) > > Anyone looking for high performance in the built-in AAs is on the wrong track. > but why? Because AAs can be optimized for different usage patterns, but builtin AAs cannot. I'm not saying we shouldn't care at all about their performance, just that usability is more important concern as their performance is less likely to be critical. > it's wrong to assume that AA has any defined order of items for > iteration. this is *really* wrong. Yes, it's wrong, but it's convenient. Deterministic behavior is always nice to have. > 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? It's a trade-off. > 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. People rolling their own specialized AAs into phobos would be a great thing. Slightly slower AAs would be just fine for scripting and prototyping. > i believe that built-in AAs should be fast, but not necessarily featurefull. > and AAs with more features can be implemented in Phobos. With hindsight, I don't think AAs belong in a language as powerful as D. They should be done in the library. The dedicated syntax is nice, but minor. > > > 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 Yeah, that's a similar tradeoff.

Built-in AA's was one of the things that initially drew me to D. Though, admittedly, I would've been OK with a library type that sported convenient syntax. But as they say, hindsight is always 20/20. In the early days, D simply wasn't powerful enough for a library type to be able to emulate what built-in AA's do. Today, of course, the tables have turned, and a library type may in fact be superior to the built-in type if given proper compiler support. (One thing that comes to mind is using templates and compile-time introspection to optimize AA operations, that today have to rely on passing typeinfo's around and thereby being handicapped when it comes to dealing with things like @disabled ctors, non-trivial opAssign's, and so on. A library type would have no such problem.)

(In reply to Ketmar Dark from comment #21) > it's wrong to assume that AA has any defined order of items for > iteration. It's not wrong, it's a handy feature, just as in Python the default sort is stable. Ordered dict is handy for unittesting and in other situations. And it's handy to use built-in data structures in unittesting. > why include language feature that is known to > be slow when it can be reasonably fast? Tracking the insertion order is not that slow...

(In reply to bearophile_hugs from comment #24) > Tracking the insertion order is not that slow... it's either slow or memory-consuming. as for me it's unacceptable deal.

(In reply to Ketmar Dark from comment #25) > it's either slow or memory-consuming. as for me it's unacceptable deal. Why? Have you created benchmarks, have you tested it already?

(In reply to bearophile_hugs from comment #26) > (In reply to Ketmar Dark from comment #25) > > it's either slow or memory-consuming. as for me it's unacceptable deal. > > Why? Have you created benchmarks, have you tested it already? The code to handle multiple parallel linked lists is not fun. I'm not saying it shouldn't be done, but I think adding 2 more pointers to every item is quite an increase in overhead. If you are storing an int key and int value, on a 64-bit machine, this means you have an extra overhead of 16 bytes, + current overhead of 8 bytes for pointer and 8 bytes for hash. This means the overhead is 80%, vs now where the overhead is only 66%. But let's also consider that current rules require each allocation fit into a power of 2. This means you don't get 40 bytes from the GC, you get 64! So really, the overhead is almost 90%, or 56 bytes of overhead per 8 bytes of value. Using same methodology, the current overhead is only 24 bytes, or 75%. We have to consider also the benefit of having some ordering to traversability. If you NEVER use your AA for traversing, you have wasted all that space/time. I think in a templated library solution, we can give that decision of tradeoff to the user, and when builtin AA's are templates, we will have that. Wait until then.

Yeah, built-in AA types should not introduce overhead for features user code may never even use. What we really need, is a nice, well-optimized sorted dictionary container in std.container that overloads the AA operators. Once Igor's PRs implementing AA literal support in dmd/druntime has been merged, we might even stand a chance of making this library type interoperable with AA literals, which would greatly reduce the need to add any more complications to the built-in AA's.

(In reply to bearophile_hugs from comment #26) > > it's either slow or memory-consuming. as for me it's unacceptable deal. > Why? Have you created benchmarks, have you tested it already? there is no need to test the obvious. to gain speed we need two more pointers for each element. if we add one pointer, our AA will turn to single-linked list for insertion and deletion; complete disaster. no pointers — and we have no place to store housekeeping info. two more pointers for the feature i don't need and will not use? no, i'll not buy this. ;-)

I've opened issue 13679 for the issue of using foreach_reverse directly on the AA. That leaves this with just the unlikely enhancement, of making byKey/byValue into bidirectional ranges.

> That leaves this with just the unlikely enhancement, of making byKey/byValue into bidirectional ranges. Renamed the title to match this.

THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/dmd/issues/17585 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB