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

[monarch_dodra]

On Thursday, 14 February 2013 at 20:33:21 UTC, Ivan Kazmenko 
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.
>
> -----
> Ivan Kazmenko.

Also keep in mind that "a < b" is implemented as two calls to 
"a.opCmp(b)", and "a.opCmp(b)" is itself usually implemented as 
two calls to "something < something else" (!)

as convenient as opCmp is for the implementation implementation, 
it is not always the best in terms of raw power.

If you have can write a straight up less(S1, S2) function, such 
as "a.i < b.i", then using that can buy you a hefty amount of 
time.