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

via Digitalmars-d-bugs digitalmars-d-bugs at puremagic.com
Mon Sep 1 23:27:48 PDT 2014


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

--- Comment #12 from Ketmar Dark <ketmar at 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. ;-)

--


More information about the Digitalmars-d-bugs mailing list