http://d.puremagic.com/issues/show_bug.cgi?id=5650
--- Comment #17 from Steven Schveighoffer <schvei...@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: -------