On Tuesday, 6 May 2014 at 00:30:10 UTC, Brian Schott wrote:
These are my biggest concerns with the allocator API:
[Snip]
3. GC.removeRange is one of the slowest functions I've ever
used. My allocator-backed binary tree implementation took 14
seconds to load a very large data set (compared to
RedBlackTree's 35 seconds) and then spent the next five minutes
in GC.removeRange before I got bored and killed it.
I've just created a PR [1] which changes GC addRange/removeRange
to use a treap instead of an unsorted array which you might be
interested in testing.
It should change your use case of "add N ranges afterwards remove
those N ranges" from taking O(N^2) time to O(N log N) time.
It would be nice to have a real-world comparison between the
enhancement and existing implementation.
[1] https://github.com/D-Programming-Language/druntime/pull/788
