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

--- Comment #11 from Ketmar Dark <ketmar@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 about twice faster than the patched D code. I don't know the source of such performance difference.)
we can make D code alot faster if we'll add one pointer to each AA Entry, for example. but i think that this is just a wasted memory.

i have some other ideas, but they requires either additional memory or more support code in add/remove functions (thus making adding and removing elements slower in general).

but i'm still thinking. maybe i'll do some more patches soon. or someone who already knows the solution but don't bother to write it 'cause he never sees use cases for that. ;-)

i'm still thinking about adding `aa.frontKey` and `aa.frontValue`, 'cause i don't like the fact that using AA in foreach() turns on caching. but i believe that adding new methods will zero merging chances. "we already have too many methods and runtime hooks, there is no sense in adding two more, blah-blah-blah".

--

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

--- Comment #12 from Ketmar Dark <ketmar@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 byKey/byValue at least once
(i.e. directly or in foreach loop). this is not that frequent operations for
AAs. and user cannot modify AA in `foreach(k; aa.byKeys)` or `foreach(v;
aa.byValues)` anyway.

the second thing is that cache bookkeeping is in effect only when "first used" bucket becomes empty.

and any rehash operation will turn off caching too.

without that code in _aaDelX syntetic test from this report is ALOT slower (~1
second vs ~0.3 seconds) and code from the forum is somewhat slower (~1.5
seconds vs ~1.1 seconds).

yet i'm sure that overhead for `aa.remove()` is so small that it can be
ignored.

ok, we need some performance tests here. somebody?

> The first entry can be simply treated as a hint, meaning that the first bucket is greater or equal to the hint.
i've tried this 'hinting' strategy too, and it gives ~1.1 and ~1.9 seconds on samples. don't like that.

> I think _aaDelX should leave the cache value alone since _aaGetFirstEntry checks that the bucket is non-null anyway.
see above.

> Furthermore, I don't think the plus one indexing is necessary.
it's a matter of taste, i think. i need "cache turned off" flag, and zero is fine. sure we can use "size_t.max", for example, but then we can't use this trick:

  if (i+1 < aa.impl.firstUsedBucket) aa.impl.firstUsedBucket = i+1;

and have to write

  if (aa.impl.firstUsedBucket != size_t.max && i < aa.impl.firstUsedBucket)
aa.impl.firstUsedBucket = i;

don't like it. ;-)

--

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

--- Comment #13 from safety0ff.bugz <safety0ff.bugz@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 operations for AAs.

Ah, okay, I missed that it wasn't always on.

--

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

hsteoh@quickfur.ath.cx changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |pull
                 CC|                            |hsteoh@quickfur.ath.cx

--- Comment #14 from hsteoh@quickfur.ath.cx ---
Created a PR using Ketmar's patch:

https://github.com/D-Programming-Language/druntime/pull/967

Thanks for contributing!

--

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

--- Comment #15 from Ketmar Dark <ketmar@ketmar.no-ip.org> ---
tnx for turning this into PR.

--

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

--- Comment #16 from hsteoh@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

Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy@yahoo.com

--- Comment #17 from Steven Schveighoffer <schveiguy@yahoo.com> ---
(In reply to Ketmar Dark from comment #12)
> (In reply to safety0ff.bugz from comment #10)
> > Furthermore, I don't think the plus one indexing is necessary.
> it's a matter of taste, i think. i need "cache turned off" flag, and zero is fine. sure we can use "size_t.max", for example, but then we can't use this trick:
> 
>   if (i+1 < aa.impl.firstUsedBucket) aa.impl.firstUsedBucket = i+1;
> 
> and have to write
> 
>   if (aa.impl.firstUsedBucket != size_t.max && i < aa.impl.firstUsedBucket)
> aa.impl.firstUsedBucket = i;
> 
> don't like it. ;-)

Hm... I think you can just use 0. When caching is off, you need to start looking at bucket 0 anyway.

--

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

--- Comment #18 from Ketmar Dark <ketmar@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. trick is harmless, neat looking and yeah,
confuses some readers who aren't read the whole code (and so they will not
'fix' the thing they not fully understand ;-).

to keep the long story short: i like this trick and will not remove it. but it doesn't mean that anyone else can't took my code and rewrite it in any other way. ;-)

--

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

Ketmar Dark <ketmar@ketmar.no-ip.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #1409|0                           |1
        is obsolete|                            |

--- Comment #19 from Ketmar Dark <ketmar@ketmar.no-ip.org> ---
Created attachment 1441
  --> https://issues.dlang.org/attachment.cgi?id=1441&action=edit
simple 'first used bucket' caching for AAs

found a bug in remove(), updated patch.

2hsteoh: time to update PR. ;-)

--

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

--- Comment #20 from bearophile_hugs@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 introduces technical debt in the code. It's not a practice for a wise programmer.

--