[Issue 13410] Performance problem with associative array byKey/byValue (page 4)

https://issues.dlang.org/show_bug.cgi?id=13410 --- Comment #31 from Martin Nowak <code@dawg.eu> --- (In reply to bearophile_hugs from comment #29) > Nope. If you take a look at the link, that code doesn't need an ordered container. The "pop" operation just needs to give one arbitrary item. Take an array or a stack for that. --

https://issues.dlang.org/show_bug.cgi?id=13410 --- Comment #32 from bearophile_hugs@eml.cc --- (In reply to Martin Nowak from comment #31) > (In reply to bearophile_hugs from comment #29) > > Nope. If you take a look at the link, that code doesn't need an ordered container. The "pop" operation just needs to give one arbitrary item. > > Take an array or a stack for that. Nope, the associative array nature is needed for other reasons by the code. And keeping the same keys in two collections in parallel is a waste. --

October 02, 2014

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

Posted by Steven Schveighoffer

Permalink

Steven Schveighoffer

Permalink

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

--- Comment #34 from Steven Schveighoffer <schveiguy@yahoo.com> ---
(In reply to Ketmar Dark from comment #33)
> (In reply to Steven Schveighoffer from comment #30)
> > bearophile or ketmar, can you test the new PR?
> for what reason? see #2 and #3, i was tried the variant without caching in
> remove().

This PR should have identical performance as your latest for the code in question, but not cause any slowdown for remove otherwise. But my box for some reason doesn't even exhibit the original problem with no patch. The speedup on my system is not measurable. So I need someone to test to make sure it's actually fixing the issue properly who does experience the problem.

>i'm telling again that remove() is NOT slowed down by any
> noticable time, and if you doing alot of removes which all happen to hit the first used bucket, and each such hit empties that bucket, and you used .byKey/.byValue before… this is very unusual scenario, and if you *know* that it goes like this, you can force rehashing.

As has been discussed, this isn't an acceptable tradeoff. Forcing a rehash for this seems unintuitive, users will not get it. Besides, there is no reason to recalculate cache unless you need it.

> yet i'm not interested in defending the code: i integrated it in my local builds since i published the patch and it's ok for me. i don't really care if it will make to mainline in one form on another.

Hm... people here have made a lot of effort to work with your patch given your objections to github. Normally I would suggest that unless you submit a PR, you will not get this code included. Your response confirms that should have been the correct action, and I'll remember that from now on.

--

https://issues.dlang.org/show_bug.cgi?id=13410 Ketmar Dark <ketmar@ketmar.no-ip.org> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |ketmar@ketmar.no-ip.org --- Comment #35 from Ketmar Dark <ketmar@ketmar.no-ip.org> --- (In reply to Steven Schveighoffer from comment #34) > This PR should have identical performance as your latest for the code in question, but not cause any slowdown for remove otherwise. sorry, i misread your patch (yes, i've looked at it before posting my answer). yet you doing a slightly different thing and i don't want to argue. that's why i'm saying that i don't care: both variants are good, and my own has some good points for my use cases. that's why i'm not interesting in defending my code — not that i don't care about changes or so. > Hm... people here have made a lot of effort to work with your patch given your objections to github. i can't remember when i forced anybody to do anything with this patch. yet if somebody feels bad about it, he can ask for refund: i'll gladly return his money. > Normally I would suggest that unless you submit a > PR, you will not get this code included. i don't really care. i'm putting my patches here for those who interested and they are free to do anything they want with my code. i know that bugzilla patches have very little chance to be included in mainline. i just want to share my vision in the form of the code for others to decide. --

https://issues.dlang.org/show_bug.cgi?id=13410 --- Comment #36 from Steven Schveighoffer <schveiguy@yahoo.com> --- I can reproduce the issue, I was accidentally using bearophile's second D implementation, which does not call byKey/byValue every time through the loop, but instead uses aa.keys. oops! --

https://issues.dlang.org/show_bug.cgi?id=13410 --- Comment #37 from github-bugzilla@puremagic.com --- Commit pushed to master at https://github.com/D-Programming-Language/druntime https://github.com/D-Programming-Language/druntime/commit/7cb7307cb5ab8df5f285fd6c5d0d8b0918517d6d Merge pull request #979 from schveiguy/issue13410 issue 13410 -- Performance problem with associative array byKey/byValue --

https://issues.dlang.org/show_bug.cgi?id=13410 --- Comment #38 from bearophile_hugs@eml.cc --- The original D program ( http://forum.dlang.org/thread/efmjlfpehqqfszcrxmwq@forum.dlang.org ) was about 30 times slower than the equivalent C++ code. Now the D code is only 5 times slower than the C++ code. So the situation is much better now. But the two programs are not exactly equivalent: the C++ code uses a tree-based map while the D code uses the built-in hash-based associative array. --

https://issues.dlang.org/show_bug.cgi?id=13410 --- Comment #39 from Steven Schveighoffer <schveiguy@yahoo.com> --- Bearophile, 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. --

Forums