[Issue 5650] A RedBlackTree performance problem

[d-bugmail]

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



--- Comment #16 from bearophile_h...@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: -------