https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #42 from github-bugzi...@puremagic.com ---
Commit pushed to 2.067 at https://github.com/D-Programming-Language/druntime
https://github.com/D-Programming-Language/druntime/commit/7cb7307cb5ab8df5f285fd6c5d0d8b0918517d6d
Merge pull request
request #979 from schveiguy/issue13410
issue 13410 -- Performance problem with associative array byKey/byValue
--
https://issues.dlang.org/show_bug.cgi?id=13410
Steven Schveighoffer schvei...@yahoo.com changed:
What|Removed |Added
Status|NEW |RESOLVED
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #38 from bearophile_h...@eml.cc ---
The original D program (
http://forum.dlang.org/thread/efmjlfpehqqfszcrx...@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++
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #39 from Steven Schveighoffer schvei...@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
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #40 from Ketmar Dark ket...@ketmar.no-ip.org ---
2Steven Schveighoffer: thanks for your work.
--
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #41 from bearophile_h...@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.
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #36 from Steven Schveighoffer schvei...@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 #34 from Steven Schveighoffer schvei...@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
https://issues.dlang.org/show_bug.cgi?id=13410
Ketmar Dark ket...@ketmar.no-ip.org changed:
What|Removed |Added
CC||ket...@ketmar.no-ip.org
https://issues.dlang.org/show_bug.cgi?id=13410
Martin Nowak c...@dawg.eu changed:
What|Removed |Added
CC||c...@dawg.eu
--- Comment #23
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #24 from Martin Nowak c...@dawg.eu ---
In other words, this optimizes the following code
foreach (_; 0 .. 1_000_000)
aa.byKey();
but pessimizes the following
aa.remove(key);
It does NOT improve iterating byKey.
So
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #25 from Ketmar Dark ket...@ketmar.no-ip.org ---
and we can make it alot less expensive without losing speed. and all this with
only 4/8 bytes of overhead for single AA (not for single AA entry, but for the
whole AA).
the only
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #26 from bearophile_h...@eml.cc ---
(In reply to Martin Nowak from comment #24)
So unless there is a valid use case to call aa.byKey.front in a loop this
would only improve a pointless microbenchmark.
See here, it's not just a
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #27 from hst...@quickfur.ath.cx ---
@bearophile: perhaps that's an indication that what you want is actually an
*ordered* map, not a hash map?
--
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #28 from Steven Schveighoffer schvei...@yahoo.com ---
New simpler pull which shouldn't affect performance of aa.remove
https://github.com/D-Programming-Language/druntime/pull/979
--
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #29 from bearophile_h...@eml.cc ---
(In reply to hsteoh from comment #27)
@bearophile: perhaps that's an indication that what you want is actually an
*ordered* map, not a hash map?
Nope. If you take a look at the link, that code
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #30 from Steven Schveighoffer schvei...@yahoo.com ---
bearophile or ketmar, can you test the new PR? The timings I get on my system
are not very different from the original.
--
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #31 from Martin Nowak c...@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
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #32 from bearophile_h...@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
https://issues.dlang.org/show_bug.cgi?id=13410
Ketmar Dark ket...@ketmar.no-ip.org changed:
What|Removed |Added
CC|ket...@ketmar.no-ip.org |
--- Comment #33 from
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #22 from hst...@quickfur.ath.cx ---
PR updated.
--
https://issues.dlang.org/show_bug.cgi?id=13410
Ketmar Dark ket...@ketmar.no-ip.org changed:
What|Removed |Added
Attachment #1409|0 |1
is obsolete|
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #20 from bearophile_h...@eml.cc ---
(In reply to Ketmar Dark from comment #18)
i like this trick and will not remove it.
I have not taken a look at the code, but in general leaving tricks in the code
that some people find not intuitive
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #21 from Ketmar Dark ket...@ketmar.no-ip.org ---
it's widely known trick. at least among us, old farts.
--
https://issues.dlang.org/show_bug.cgi?id=13410
Steven Schveighoffer schvei...@yahoo.com changed:
What|Removed |Added
CC|
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #18 from Ketmar Dark ket...@ketmar.no-ip.org ---
(In reply to Steven Schveighoffer from comment #17)
Hm... I think you can just use 0. When caching is off, you need to start
looking at bucket 0 anyway.
please read _aaDelX() code too.
https://issues.dlang.org/show_bug.cgi?id=13410
hst...@quickfur.ath.cx changed:
What|Removed |Added
Keywords||pull
CC|
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #15 from Ketmar Dark ket...@ketmar.no-ip.org ---
tnx for turning this into PR.
--
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #16 from hst...@quickfur.ath.cx ---
And this time, I remembered to set you as author, unlike the previous patches I
turned into PRs. I know you said it doesn't matter, but still. :-)
--
https://issues.dlang.org/show_bug.cgi?id=13410
safety0ff.bugz safety0ff.b...@gmail.com changed:
What|Removed |Added
CC|
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #11 from Ketmar Dark ket...@ketmar.no-ip.org ---
(In reply to bearophile_hugs from comment #9)
Right. (But using an unordered_map in the C++ code from the newsgroup the
C++ code only gets a little more than twice slower, that seems
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #12 from Ketmar Dark ket...@ketmar.no-ip.org ---
(In reply to safety0ff.bugz from comment #10)
As for ketmar's patch, I don't think we should introduce a slowdown in
_aaDelX.
cache bookkeeping turns on only when the code used
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #13 from safety0ff.bugz safety0ff.b...@gmail.com ---
(In reply to Ketmar Dark from comment #12)
cache bookkeeping turns on only when the code used byKey/byValue at least
once (i.e. directly or in foreach loop). this is not that frequent
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #1 from bearophile_h...@eml.cc ---
The exact problem was found by Daniel Kozak.
--
https://issues.dlang.org/show_bug.cgi?id=13410
Ketmar Dark ket...@ketmar.no-ip.org changed:
What|Removed |Added
CC||ket...@ketmar.no-ip.org
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #3 from Ketmar Dark ket...@ketmar.no-ip.org ---
Created attachment 1408
-- https://issues.dlang.org/attachment.cgi?id=1408action=edit
simple 'first used bucket' caching for AAs with '_aaDelX' recaching
here is another patch which tries
https://issues.dlang.org/show_bug.cgi?id=13410
Ketmar Dark ket...@ketmar.no-ip.org changed:
What|Removed |Added
Attachment #1407|0 |1
is obsolete|
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #5 from bearophile_h...@eml.cc ---
(In reply to Ketmar Dark from comment #4)
and code from the forum (~3.5 seconds -- 1.1 seconds).
For me the C++ version of the code runs in about 0.20 seconds, so there's still
a significant
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #6 from Ketmar Dark ket...@ketmar.no-ip.org ---
(In reply to bearophile_hugs from comment #5)
For me the C++ version of the code runs in about 0.20 seconds, so there's
still a significant performance difference.
yes, AA still needs to
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #7 from Orvid King blah38...@gmail.com ---
It would be nice if this were done as a PR on github, as it would be much
easier to review.
--
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #8 from Ketmar Dark ket...@ketmar.no-ip.org ---
(In reply to Orvid King from comment #7)
It would be nice if this were done as a PR on github, as it would be much
easier to review.
sorry, each time i'm thinking about registering at
https://issues.dlang.org/show_bug.cgi?id=13410
--- Comment #9 from bearophile_h...@eml.cc ---
(In reply to Ketmar Dark from comment #8)
but to find first available item we must loop thru all buckets
until we find the used one.
Right. (But using an unordered_map in the C++ code from the
43 matches
Mail list logo
