[Issue 13410] New: Performance problem with associative array byKey/byValue
via Digitalmars-d-bugs
digitalmars-d-bugs at puremagic.com
Mon Sep 1 02:14:18 PDT 2014
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 at puremagic.com
Reporter: bearophile_hugs at 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;
}
- - - - - - - - - - -
--
More information about the Digitalmars-d-bugs
mailing list