If we choose to store a struct in a RedBlackTree in the most intuitive way, it gets passed by value quite a few more times than one would expect. This can severely reduce performance when the struct is large and/or has a non-trivial postblit constructor. An example follows: ----- import std.container; import std.stdio; immutable int LIMIT = 100000; struct element { static int postblit_counter; int x; int opCmp (ref element other) { return x - other.x; } this (this) { postblit_counter++; } } alias RedBlackTree !(element) container; void main () { auto f = new container (); element.postblit_counter = 0; foreach (i; 0..LIMIT) { f.insert (element (i)); } writefln ("%s", element.postblit_counter); } ----- Here, upon inserting 100,000 elements in the tree, we make 11,389,556 calls to this(this). However, if we choose to override the default predicate for RedBlackTree (that is, "a < b") with one which accepts arguments by reference, the program makes just 300,000 calls to this(this). The modification: ----- import std.container; import std.stdio; immutable int LIMIT = 100000; struct element { static int postblit_counter; int x; int opCmp (ref element other) { return x - other.x; } this (this) { postblit_counter++; } } bool lessfun (ref element a, ref element b) { return a < b; } alias RedBlackTree !(element, lessfun) container; void main () { auto f = new container (); element.postblit_counter = 0; foreach (i; 0..LIMIT) { f.insert (element (i)); } writefln ("%s", element.postblit_counter); } ----- These are both tested for D2 v2.059 for Win32. Adding compiler options "-O -release -inline" does not change the result of the test.
The second program gives me: temp.d(28): Error: template instance RedBlackTree!(element, lessfun) RedBlackTree!(element, lessfun) does not match template declaration RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if (is(typeof(binaryFun!(less)(T.init, T.init))))
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.
(In reply to comment #1) > The second program gives me: > > temp.d(28): Error: template instance RedBlackTree!(element, lessfun) > RedBlackTree!(element, lessfun) does not match template declaration > RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if > (is(typeof(binaryFun!(less)(T.init, T.init)))) Hmm, I just tried with the current release, DMD 2.061, and it gives me the same error. However, DMD 2.059 works with no complaint. The problem arises from the constraint in RedBlackTree declaration: ----- final class RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if(is(typeof(binaryFun!less(T.init, T.init)))) ----- The function taking ref arguments can not work for T.init and T.init since ref implies lvalue. Currently, I found two work-arounds, more or less clumsy. The first one is to define the second function to avoid the check: ----- // old one bool lessfun (ref element a, ref element b) { return a < b; } // new one bool lessfun (element a, element b) { return a < b; } ----- Obviously, this way, we need four identical functions to cover all possible cases. The second one is to use template and auto ref: ----- bool lessfun (T) (auto ref T a, auto ref T b) { return a < b; } ----- This works fine. And this could be a suitable solution for the original problem. That is, implementing "a < b" in a similar way as the default predicate for the RedBlackTree!(AnyStructType) container may be not that bad. But that makes me wonder: under the hood, does it still create the four identical functions?
Created attachment 1186 [details] Example with excessive copying
Created attachment 1187 [details] Solution 1: two redundant functions
Created attachment 1188 [details] Solution 2: template with auto ref
(In reply to comment #3) > (In reply to comment #1) > > The second program gives me: > > > > temp.d(28): Error: template instance RedBlackTree!(element, lessfun) > > RedBlackTree!(element, lessfun) does not match template declaration > > RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false) if > > (is(typeof(binaryFun!(less)(T.init, T.init)))) > > The function taking ref arguments can not work for T.init and T.init since ref > implies lvalue. Yes, this was recently more strictly enforced. However, the function will only ever be called on lvalues inside the class We should change the if statement to something like this: if(is(typeof({T t; bool x = binaryFun!less(t, t);}))) That should fix the issue.
THIS ISSUE HAS BEEN MOVED TO GITHUB https://github.com/dlang/phobos/issues/9598 DO NOT COMMENT HERE ANYMORE, NOBODY WILL SEE IT, THIS ISSUE HAS BEEN MOVED TO GITHUB