On Thu, 14 Feb 2013 15:33:19 -0500, Ivan Kazmenko <ga...@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
