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@puremagic.com
        ReportedBy: bearophile_hugs@eml.cc


--- Comment #0 from bearophile_hugs@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: -------

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


Steven Schveighoffer <schveiguy@yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|nobody@puremagic.com        |schveiguy@yahoo.com


--- Comment #1 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-02-24 14:08:18 PST ---
This is an odd thing.

dcollections way outperforms std.container.RedBlackTree, but I'm positive this is because of the custom allocator.  On my PC, the phobos version takes anywhere from 26 to 38 seconds.  The dcollections version takes .6 seconds.

However, every few runs, the dcollections version goes to > 25 seconds.  I have no idea why.  The result seems to be the same, so I'm not sure what is causing that big pause.  I'll have to investigate it more.

But in the short run, I'd recommend using dcollections until std.container figures out how it will do custom allocation.

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

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



--- Comment #2 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-02-24 14:24:25 PST ---
:O

Cannot, I mean *really* cannot believe this, but this was still in my d2 code:

http://www.dsource.org/projects/dcollections/browser/branches/d2/dcollections/DefaultAllocator.d#L325

Which means the chunk allocator was not even being used (BTW, it has a bug in it, for some reason it seg faults, but that's not a dmd or phobos problem).

I'd say the problem is definitely the GC running too often.  If I print out each loop, and in a debugger hit ctrl-C when it pauses, it's invariably in GC.fullCollect.

This looks like a GC problem, I wonder if David's recent changes help...

I'm going to leave this bug open.  We'll see how the thing works on the next version with David's GC improvements.

In the meantime, I'll get dcollections fixed, and maybe that can be an interim solution.

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

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



--- Comment #3 from bearophile_hugs@eml.cc 2011-02-24 14:27:34 PST ---
The D version runs in about 20.6 seconds, the Java -server version in about 0.49 seconds, and this C++ (GCC 4.5.1 -O3) version in about 0.3 seconds (this is not a fully apples-to-apples comparison because this doesn't use a GC, but it's good as reference point):


#include <stdio.h>
#include <set>

using namespace std;

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

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

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

    return 0;
}

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

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



--- Comment #4 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-02-24 14:36:47 PST ---
Fixed the dcollections custom allocator, time is now consistently .5 seconds.

I noticed the phobos version also occasionally dips down to .5 or .6 seconds. I'm unsure why sometimes the collect cycles take so long.  Perhaps there are false pointer problems, the RBNode elements contain pointers and also the ints.

This is definitely a GC issue.  Not much RedBlackTree can do about it.

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

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



--- Comment #5 from David Simcha <dsimcha@yahoo.com> 2011-02-24 14:40:27 PST ---
(In reply to comment #2)
> This looks like a GC problem, I wonder if David's recent changes help...
> 
> I'm going to leave this bug open.  We'll see how the thing works on the next version with David's GC improvements.
> 

I'd doubt that the changes I've posted to Bugzilla so far would help this benchmark, because those changes focus entirely on large (>2KB) allocations. However, in rebuilding my mental model of the GC, I've come up with several smaller (i.e. a few percent each) ideas for optimizing the GC.  These are currently half-implemented.  I'm going to fork druntime on GitHub and commit them all there, and show the progressive performance improvements on a few different benchmarks with each one on the GitHub wiki page for my fork.

This, I guess, will be added to my list of GC benchmarks for small allocations, though I'm not sure if it will tell us anything that Bearophile's other recent tree-building GC benchmark didn't.

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

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



--- Comment #6 from Steven Schveighoffer <schveiguy@yahoo.com> 2011-02-24 14:48:54 PST ---
I have a really good suspicion that this has more to do with false pointer problems than GC performance.

The only reason I feel this way is because between you can run this program 5 times, and 1 time, it will take 38 seconds, and the other 4 it takes .5 seconds.  Everything in this little test program should be deterministic *except* what address segment the OS gives the GC...

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

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


SomeDude <lovelydear@mailmetrash.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |lovelydear@mailmetrash.com


--- Comment #7 from SomeDude <lovelydear@mailmetrash.com> 2012-04-22 16:36:01 PDT ---
This test no longer compiles in 2.059:

PS E:\DigitalMars\dmd2\samples> rdmd bug
bug.d(7): Error: no property 'opCall' for type
'std.container.RedBlackTree!(int).RedBlackTree'

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

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



--- Comment #8 from bearophile_hugs@eml.cc 2012-04-24 18:58:41 PDT ---
(In reply to comment #7)
> This test no longer compiles in 2.059:
> 
> PS E:\DigitalMars\dmd2\samples> rdmd bug
> bug.d(7): Error: no property 'opCall' for type
> 'std.container.RedBlackTree!(int).RedBlackTree'

Now RedBlackTree is a class. So replace this line:
auto t = RedBlackTree!int(0);

With:
auto t = redBlackTree!int(0);

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

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



--- Comment #9 from SomeDude <lovelydear@mailmetrash.com> 2012-04-25 00:56:28 PDT ---
Ah ok, my measurements (Core2Duo 2,14GHz, 2Gb RAM WinXP SP3):

range = 100_000_000
n = 10_000_000

Eclipse, JVM1.6 with option -Xmx512M : 9781 ms  537Mb RAM (note that I don't
have a server JVM)
dmd -O -release -inline (2.059): 25367 ms , 321 Mb RAM

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