[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