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.
