[Issue 13410] Performance problem with associative array byKey/byValue

[via Digitalmars-d-bugs]

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

--- Comment #41 from bearophile_hugs at eml.cc ---
(In reply to Steven Schveighoffer from comment #39)

> With the tree-based solution, when the front element is removed, the "next"
> element is 1 hop away.
> 
> But with hash, it can be far away in the table. So you likely are better off
> using a tree-based map, something like RedBlackTree if you want to come
> close to C++ performance.
> 
> There is also the issue that C++ uses a template-based map, so it can
> optimize the code, inline comparisons, etc. The AA-based solution cannot do
> this.

I understand all this (the C++ program with a hash_map is 2.5 times faster than
the current D situation).


> So you likely are better off
> using a tree-based map, something like RedBlackTree if you want to come
> close to C++ performance.

I have not tried to use the Phobos RedBlackTree in this program, it's an
interesting test.

--