[Issue 5650] A RedBlackTree performance problem

[d-bugmail at puremagic.com]

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



--- Comment #17 from Steven Schveighoffer <schveiguy at yahoo.com> 2012-05-22 16:40:50 PDT ---
If the issue is that my redblacktree implementation isn't fast enough, you are
welcome to try and improve it.

I implemented it based on the algorithm I found inside my CLR Algorithms book. 
I have never pretended really to be an expert in RBT implementation.  I have no
idea how optimized it is, or how much more optimized it could be.  I made some
refactoring adjustments from the standard algorithm, and the red black
algorithm in my code is well documented.

I also have not looked at any of the g++ STL code, so I have no idea how it
compares to that.  Obviously I haven't looked at any Java implementations.

On my system, the D version with dcollections, which uses the same RBT
implementation as std.algorithm, takes about 380 milliseconds (-release -O
-inline), while the equivalent C++ version takes 250 ms.  I don't think I have
the JDK installed, so I cannot test the java version.

I don't think the GC is really hindering performance any more, it's just pure
algorithmic + compiler optimization comparison.

BTW, MAKE SURE you compile with -release for testing, because without this, the
runtime calls Object.invariant for every method call.

Here is the optimized-for-dcollections code (which keeps track of the begin
element), you can't do this in std.container, since the concept of cursors does
not exist:

import std.stdio;
import dcollections.TreeSet;

void main() {
    enum int range = 100;
    enum int n = 1_000_000;

    auto t = new TreeSet!int(0);
    auto nextToRemove = t.begin;

    for (int i = 0; i < n; i++) {
        if (i > range)
            nextToRemove = t.remove(nextToRemove);
        t.add(i);
    }

    //writeln(walkLength(t[]));
    //writeln(t[]);
}

Same code in C++:

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

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

    set<int> t;
    t.insert(0);
    set<int>::iterator nextToRemove = t.begin();

    for (int i = 0; i < n; i++) {
        if (i > range)
        {
            set<int>::iterator tmp = nextToRemove;
            tmp++;
            t.erase(nextToRemove);
            nextToRemove = tmp;
        }
        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: -------