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: [email protected]
Reporter: [email protected]
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;
}
- - - - - - - - - - -
--
