[Issue 5650] A RedBlackTree performance problem

[d-bugmail at puremagic.com]

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



--- Comment #20 from Steven Schveighoffer <schveiguy at 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: -------