September 01, 2014 [Issue 13410] New: Performance problem with associative array byKey/byValue | ||||
---|---|---|---|---|
| ||||
https://issues.dlang.org/show_bug.cgi?id=13410 Issue ID: 13410 Summary: Performance problem with associative array byKey/byValue Product: D Version: D2 Hardware: x86 OS: Windows Status: NEW Severity: normal Priority: P1 Component: druntime Assignee: nobody@puremagic.com Reporter: bearophile_hugs@eml.cc This is a reduction of a performance problem I have found (ketmar on the newsgroup D.learn has found it). This is the D version: - - - - - - - - - - - import core.stdc.stdio; int main() { long[int] aa; for (int i = 0; i < 50000; i++) aa[i] = i; long total = 0; while (aa.length) { int k = aa.byKey.front; long v = aa.byValue.front; aa.remove(k); total += k + v; } printf("%lld\n", total); return 0; } - - - - - - - - - - - The C++ version: #include <stdio.h> #include <map> int main() { std::map<int, long long> aa; for (int i = 0; i < 50000; i++) aa[i] = i; long long total = 0; while (!aa.empty()) { int k = aa.begin()->first; long long v = aa.begin()->second; aa.erase(aa.begin()); total += k + v; } printf("%lld\n", total); return 0; } - - - - - - - - - - - The run-time of the C++ version is about 0.05 seconds (the output is 2499950000), while the D code runs in about 3.8 seconds (76 times slower). To show the performance problems don't come from the associative array creation, and that they don't come from the associative array remove, or from the long sum, here is a very similar version that just avoids byKey/byValue (idea suggested by ketmar), note that this code allocates an eager array with aa.keys. This runs in about 0.06 seconds, sufficiently similar to the C++ version: - - - - - - - - - - - import core.stdc.stdio; int main() { long[int] aa; for (int i = 0; i < 50000; i++) aa[i] = i; long total = 0; foreach (int k; aa.keys) { long v = aa[k]; aa.remove(k); total += k + v; } printf("%lld\n", total); return 0; } - - - - - - - - - - - -- |
Copyright © 1999-2021 by the D Language Foundation