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

--- Comment #22 from yebblies <yebblies@gmail.com> ---
(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.

--

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

--- Comment #23 from hsteoh@quickfur.ath.cx ---
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.)

--

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

--- Comment #24 from bearophile_hugs@eml.cc ---
(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...

--

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

--- Comment #25 from Ketmar Dark <ketmar@ketmar.no-ip.org> ---
(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.

--

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

--- Comment #26 from bearophile_hugs@eml.cc ---
(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?

--

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

--- Comment #27 from Steven Schveighoffer <schveiguy@yahoo.com> ---
(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.

--

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

--- Comment #28 from hsteoh@quickfur.ath.cx ---
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.

--

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

--- Comment #29 from Ketmar Dark <ketmar@ketmar.no-ip.org> ---
(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. ;-)

--

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

yebblies <yebblies@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://issues.dlang.org/sh
                   |                            |ow_bug.cgi?id=13679
           Severity|normal                      |enhancement

--- Comment #30 from yebblies <yebblies@gmail.com> ---
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.

--

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

Seb <greensunny12@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |bootcamp
                 CC|                            |greensunny12@gmail.com
            Summary|foreach_reverse and         |AA.byKey/byValue should be
                   |AA.byKey/byValue            |bidirectional ranges

--- Comment #31 from Seb <greensunny12@gmail.com> ---
> That leaves this with just the unlikely enhancement, of making byKey/byValue into bidirectional ranges.

Renamed the title to match this.

--