[Issue 5650] A RedBlackTree performance problem

d-bugmail at puremagic.com d-bugmail at puremagic.com
Tue May 22 14:54:33 PDT 2012


http://d.puremagic.com/issues/show_bug.cgi?id=5650



--- Comment #16 from bearophile_hugs at eml.cc 2012-05-22 14:56:09 PDT ---
Now on my PC the D version (using redBlackTree) is just 3.7 times slower than
the Java version that uses boxed Integers. This is not good enough still, but
now redBlackTree is usable (DMD 2.060alpha, 32 bit, Windows):

Timings, seconds:
  D version: 1.65
  D versions + GC.disable() at the top: 0.78
  Java version: 0.45

I think a good D version has to run this benchmark in 0.2 - 0.3 seconds.

And indeed, this C++ program (that uses a STL ordered set, that is usually
implemented with a Red-Black Tree) runs in 0.27 seconds on my PC (GCC 4.7.0,
-Ofast -flto -s), it's about 6.1 times faster than the current D code (that
uses a different and less efficient back-end):


#include <set>
#include <stdio.h>
using namespace std;

int main() {
    const int range = 100;
    const int n = 1000000;

    set<int> t;
    t.insert(0);

    for (int i = 0; i < n; i++) {
        if (i > range)
            t.erase(t.begin());
        t.insert(i);
    }

    /*
    printf("%u\n", t.size()); // prints 101
    for (set<int>::iterator it = t.begin(); it != t.end(); it++)
        printf("%d ", *it);
    printf("\n");
    */
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------


More information about the Digitalmars-d-bugs mailing list