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



--- Comment #20 from Steven Schveighoffer <schveiguy@yahoo.com> 2012-05-22 18:06:17 PDT ---
(In reply to comment #19)
> 
> I will wait for other people to time the D and C++ versions. If they confirm such small timing difference (like 380 ms Vs of 250 ms), we can close this bug report.

Be aware that my comparisons are between dcollections and the C++ code, not std.container.  The two differences that made an impact I think are:

1. Using a custom allocator that recycles RBNode instances without going
through the GC
2. Caching the "first element" that was to be removed (i.e. the begin element)
instead of asking the container to look it up each time.

Neither of those are supported via the current std.container.RedBlackTree. With that implementation, my timing is about 580ms.

BTW, I noticed changing the C++ implementation to cache the begin node did *not* change performance.  So it may be they are caching the begin element internally since it is likely one of the most requested elements.  Without that, because the begin element is very likely to be at the bottom of the tree, saving those lookups might be how they have improved performance.  We can certainly add such an improvement to 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 #21 from bearophile_hugs@eml.cc 2012-05-24 15:54:51 PDT ---
I have asked to people on IRC #D to time the D and C++ versions.

Two persons have seen a 4.8 X and 4.6 X speed differences (optimized builds, with G++ using -Ofast -s -flto, MSVC 2010, using standard release build options /OPT:REF /OPT:ICF, and D code compiled with DMD -O -release -inline).

-- 
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 #22 from Steven Schveighoffer <schveiguy@yahoo.com> 2012-05-25 11:29:52 PDT ---
(In reply to comment #20)
> BTW, I noticed changing the C++ implementation to cache the begin node did *not* change performance.  So it may be they are caching the begin element internally since it is likely one of the most requested elements.  Without that, because the begin element is very likely to be at the bottom of the tree, saving those lookups might be how they have improved performance.  We can certainly add such an improvement to RedBlackTree.

See if this helps: https://github.com/D-Programming-Language/phobos/pull/605

-- 
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 #23 from github-bugzilla@puremagic.com 2012-05-25 12:19:50 PDT ---
Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/a83d5f13881ce79935ee73747948ab3b15ea633d
issue 5650 - A RedBlackTree performance problem
Caching first node (as _begin) to improve lookup performance of first node.

https://github.com/D-Programming-Language/phobos/commit/965df0300ae635342082b6537f719da5c926e5ff Merge pull request #605 from schveiguy/rbtree_begin

issue 5650 - A RedBlackTree performance problem

-- 
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 #24 from bearophile_hugs@eml.cc 2012-05-25 12:59:19 PDT ---
(In reply to comment #22)

> See if this helps: https://github.com/D-Programming-Language/phobos/pull/605

I have tried this latest change. Unfortunately both this benchmark, and another larger program of mine that uses RedBlackTree a lot are now a bit (2-3%) slower than before; both with GC enabled and with GC disabled.

-- 
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 #25 from Steven Schveighoffer <schveiguy@yahoo.com> 2012-05-25 13:05:10 PDT ---
That doesn't make any sense.  It resulted in a 100ms speedup on my end (about
20%).

-- 
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


safety0ff.bugz@gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |safety0ff.bugz@gmail.com


--- Comment #26 from safety0ff.bugz@gmail.com 2013-10-03 06:29:10 PDT ---
(In reply to comment #16)
> 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

The current situation on my PC is the following:

[1]   Java version: 0.26
[2]   D version: 0.28
[2]   D version + GC.disable() at the top: 0.28
[3]   D version: 0.45
[3]   D version + GC.disable() at the top: 0.21
[4]   C++ version: 0.11
[5]   C++ version: 0.12

There are other reports for more specific RedBlack tree performance issues. The performance seems to be in the ballpark you were looking for (on my PC.) Can this bug be closed?

[1]    Java version 1.7.0_40
[2]    DMD64 D Compiler v2.063.2
          Options: -O -release -noboundscheck
[3]    the LLVM D compiler (0.11.0): based on DMD v2.062 and LLVM 3.3
          Options: -O -release -noboundscheck
[4]    g++ 4.7.3
          Options: -O -DNDEBUG
[5]    clang version 3.3
          Options: -O -DNDEBUG

-- 
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 #27 from bearophile_hugs@eml.cc 2013-10-08 12:11:30 PDT ---
(In reply to comment #26)

> The current situation on my PC is the following:
> 
> [1]   Java version: 0.26
> [2]   D version: 0.28
> [2]   D version + GC.disable() at the top: 0.28
> [3]   D version: 0.45
> [3]   D version + GC.disable() at the top: 0.21
> [4]   C++ version: 0.11
> [5]   C++ version: 0.12


My current timings are improved over the #Comment16 (32 bit OS), this is good:


D:    1.13 (dmd, -O -release -inline -noboundscheck)
D:    1.11 (ldmd2, same switches)
D:    0.56 (No GC)
D:    0.51 (No GC, ldc2)
Java: 0.46
C++:  0.29 (GCC 4.9, g++ -Ofast -s -flto)


> There are other reports for more specific RedBlack tree performance issues.

What ones?


> The performance seems to be in the ballpark you were looking for (on my PC.)
> Can this bug be closed?

Here Java is about as fast as D without GC, and about twice faster than D with GC. C++ is about four times faster than D with GC. (a missing timing is the D code compiled with ldc2 that allocates from the C heap (using or not using an arena allocator)).

Is four times slower than C++ fast enough to close this bug report? Is such lower performance going to be gained back using an arena allocator from the Andrei allocators?

The situation is better than before, but perhaps it's not yet the time to close the bug report.

-- 
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 #28 from safety0ff.bugz <safety0ff.bugz@gmail.com> 2013-10-08 19:20:03 PDT ---
(In reply to comment #27)
> > There are other reports for more specific RedBlack tree performance issues.
> 
> What ones?

Issue #9513

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