[Issue 10009] foreach_reverse and AA.byKey/byValue

[via Digitalmars-d-bugs]

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

--- Comment #27 from Steven Schveighoffer <schveiguy at 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.

--