std.container.RedBlackTree versus C++ std::set

[Jonathan M Davis]

On Thursday, February 14, 2013 00:33:26 Ivan Kazmenko wrote:
> P.S. More on C++ version:
> > Personally, I don't see why at all we should call the copy
> > constructor more than once per element. I mean, if we intend to
> > build a generic data structure, we sure need an internal node
> > object with some extra bytes (internal references and counters)
> > per each element, at least in the case of a red-black tree. So
> > why don't we just bind each element to that internal node once
> > and for all, and then, as long as the node is in the structure,
> > use the data contained in it only by reference? What do we
> > achieve if we choose to use it by value somewhere?
> 
> Well, when I just changed
> "bool operator < (const element other) const"
> to
> "bool operator < (const element & other) const"
> in the C++ version of the program, it gave me the exact 100,000
> copy constructor calls which justifies the above paragraph.
> Ouch... I had hopes GCC -O2 optimizes such obvious cases; perhaps
> it's not that obvious from the compiler point of view.

The biggest performance problem is the GC. The nodes in the RBT are allocated 
with the GC, so depending on what how many elements you're inserting, how 
often you're removing them, etc., it could have performance issues. A better 
GC is in the works but obviously hasn't made it in yet. Also, work is being 
done on designing custom allocators that std.container can use, but that also 
has a ways to go. So, the main items which would help make std.container's RBT 
perform on par with std::set are in the works but not ready yet. Also, it 
could make a big difference if you use gdc or ldc rather than dmd. dmd compiles 
code much faster than they do, but its optimizer is much worse - gdc and ldc 
consistently produce faster code, and if you're compiling the C++ code with 
gcc, then gdc is a much better comparison anyway, since then both the C++ and 
D code are using the same compiler backend.

- Jonathan M Davis