https://issues.dlang.org/show_bug.cgi?id=13410
safety0ff.bugz <safety0ff.b...@gmail.com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |safety0ff.b...@gmail.com
--- Comment #10 from safety0ff.bugz <safety0ff.b...@gmail.com> ---
(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.)
>
C++ unordered_map uses templates and can do all kinds of things the D AA's
currently can't.
It can inline/devirtualize the comparison functions, it can store the key and
value together, etc.
D's AAs essentially go through a C interface, and so this limits what it can
do.
I don't think there's a great data structure for this task out of the box in D:
- Using std.container's red-black tree isn't ideal because there's no
equivalent to std::map's bracket operator (without doing multiple lookups.)
- You can't roll a bag (linked list) into the hash table because since key and
value are stored separately you cannot map a reference to a value to a
reference to the key (without storing a copy of the key inside the value and
then doing a lookup.)
As for ketmar's patch, I don't think we should introduce a slowdown in _aaDelX.
The first entry can be simply treated as a hint, meaning that the first bucket
is greater or equal to the hint.
I think _aaDelX should leave the cache value alone since _aaGetFirstEntry
checks that the bucket is non-null anyway.
Furthermore, I don't think the plus one indexing is necessary.
--
