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

[Steven Schveighoffer]

On Thu, 14 Feb 2013 15:33:19 -0500, Ivan Kazmenko <gassa at mail.ru> wrote:

> Rob T wrote:
>> When I look at the std.container source code, it seems that the payload  
>> element is passed by value multiple times unnecessarily, so to minimize  
>> copy construction you'll have to implement element as a class and  
>> implement a dup function for it.
>
> Thank you all for assistance, I've finally pinned it down!  It's the  
> default magic "a < b" that devours the most copies of my precious  
> structs!  Once I change the declaration:
>
> -----
> alias RedBlackTree !(element) container;
> -----
>
> to
>
> -----
> bool lessfun (ref element a, ref element b)
> {
> 	return a < b;
> }
>
> alias RedBlackTree !(element, lessfun) container;
> -----
>
> ... I get only exactly 3 * LIMIT postblit constructor calls, which is  
> 300,000 instead of 11,389,556.  While I still want to find where the  
> excess 200,000 calls originate from, this is definitely asymptotically  
> better than before: O (n) versus O (n log n) calls.  And it is now less  
> of a bottleneck in my original program.
>
> This raises the question to the default behavior of  
> std.functional.binaryFun.  Sure, for integers, class references and  
> small types, the current way is the best.  On the other hand, for large  
> structs and maybe some other complex objects that obey value semantics,  
> it seems it would be beneficial to, given a string like "a < b", produce  
> a function taking arguments by reference and not by value.  Maybe there  
> is some simple criterion (size of type greater than size_t - seems bad?  
> type is a struct - better?) which can be used with static if to generate  
> "(ref a, ref b)" instead of "(a, b)" version by default.  Of course, all  
> that could only work if there is a more detailed hierarchy of binary  
> functions, at least a binaryFunConst taking const arguments.

It is great that you found this!

Again, the issue here is D has restrictions on ref parameters.  There are  
no such restrictions on pass-by-value parameters.  So by default, the  
predicate tries by-value.

In this case, RedBlackTree is always assured of having lvalues for the  
predicate, so I can probably make the default use pass-by-ref.  If you  
could file a bug, that would be most helpful.

http://d.puremagic.com/issues/enter_bug.cgi?product=D

-Steve