digitalmars.D.bugs - [Issue 9513] New: RedBlackTree excessively copies structs by value
- d-bugmail puremagic.com (91/91) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (14/14) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (25/25) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (43/49) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (7/7) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (7/7) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (7/7) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (9/9) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (9/9) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (9/9) Feb 14 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (15/25) Feb 15 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
- d-bugmail puremagic.com (9/9) Feb 15 2013 http://d.puremagic.com/issues/show_bug.cgi?id=9513
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Summary: RedBlackTree excessively copies structs by value Product: D Version: D2 Platform: All OS/Version: All Status: NEW Severity: enhancement Priority: P2 Component: Phobos AssignedTo: nobody puremagic.com ReportedBy: gassa mail.ru 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. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 bearophile_hugs eml.cc changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |bearophile_hugs eml.cc 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)))) -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 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: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513The 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? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Created an attachment (id=1186) Example with excessive copying -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Created an attachment (id=1187) Solution 1: two redundant functions -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Created an attachment (id=1188) Solution 2: template with auto ref -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Ivan Kazmenko <gassa mail.ru> changed: What |Removed |Added ---------------------------------------------------------------------------- mime type| | -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Ivan Kazmenko <gassa mail.ru> changed: What |Removed |Added ---------------------------------------------------------------------------- mime type| | -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Ivan Kazmenko <gassa mail.ru> changed: What |Removed |Added ---------------------------------------------------------------------------- mime type| | -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Steven Schveighoffer <schveiguy yahoo.com> changed: What |Removed |Added ---------------------------------------------------------------------------- CC| |schveiguy yahoo.com 06:58:45 PST ---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. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------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.
Feb 15 2013
http://d.puremagic.com/issues/show_bug.cgi?id=9513 Steven Schveighoffer <schveiguy yahoo.com> changed: What |Removed |Added ---------------------------------------------------------------------------- Status|NEW |ASSIGNED AssignedTo|nobody puremagic.com |schveiguy yahoo.com -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 15 2013