[Issue 9513] RedBlackTree excessively copies structs by value

[d-bugmail at puremagic.com]

http://d.puremagic.com/issues/show_bug.cgi?id=9513



--- Comment #2 from Ivan Kazmenko <gassa at mail.ru> 2013-02-14 15:26:07 PST ---
Original forum discussion thread:
http://forum.dlang.org/thread/qhlsrpqajuwstvlspimf@forum.dlang.org

First, being fixable from user side, this is not that big of an issue. 
However, it is counter-intuitive that we should use a custom but still rather
idiomatic comparison function (lessfun in the modified example) to have
asymptotically fewer copy operations: O(1) versus O(log(n)) per insertion.

As for the proposed solution, I don't have an obviously right one at hand. 
Still, below are a few attempts to guess what could possibly be done.

As I see it, the problem is in counter-intuitive behavior of the default "a <
b" predicate.  One approach is changing that behavior to accept arguments by
reference and not by value.  Such a change will perhaps break too much working
code, and worse, it will actually reduce performance in case of integers and
class references and the like.

A better idea would be to change "a < b" only for structs, but then again,
there are small structs with no postblit constructor, and all they get from
such change is an extra indirection.

A more conservative approach would be to fix stuff only for the RedBlackTree
container by specifying a custom version of the default instead of "a < b".

And if everything fails, at least there should be a visible note in the
documentation on how to properly use RedBlackTree with large structs.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------