[Issue 5650] New: A RedBlackTree performance problem

[d-bugmail at puremagic.com]

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

           Summary: A RedBlackTree performance problem
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Windows
            Status: NEW
          Keywords: performance
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody at puremagic.com
        ReportedBy: bearophile_hugs at eml.cc


--- Comment #0 from bearophile_hugs at eml.cc 2011-02-24 13:42:25 PST ---
On my PC the D version is about 41 times slower than the Java (-server)
version, despite the Java version is using boxed Integers. (The Java version
also seem to use a few megabytes less memory, but this is not so significant).

(Because of this performance problem I can't use RedBlackTree in a program I am
writing, and I need to use a different solution.)

---------------------------

// D2 code
import std.stdio, std.container, std.range;

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

    auto t = RedBlackTree!int(0);

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

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

---------------------------

// Java code
import java.util.TreeSet;

class Test1 {
    public static void main(String[] args) {
        final int range = 100;
        final int n = 1000000;

        TreeSet<Integer> t = new TreeSet<Integer>();

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

        //System.out.println(t.size());
        //System.out.println(t);
    }
}

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