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. --