www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 9513] New: RedBlackTree excessively copies structs by value

reply d-bugmail puremagic.com writes:
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


--- Comment #0 from Ivan Kazmenko <gassa mail.ru> 2013-02-14 15:06:12 PST ---
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
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc


--- Comment #1 from bearophile_hugs eml.cc 2013-02-14 15:17:57 PST ---
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513



--- Comment #2 from Ivan Kazmenko <gassa 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: -------
Feb 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513



--- Comment #3 from Ivan Kazmenko <gassa mail.ru> 2013-02-14 16:21:09 PST ---
(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? -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513



--- Comment #4 from Ivan Kazmenko <gassa mail.ru> 2013-02-14 17:04:46 PST ---
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513



--- Comment #5 from Ivan Kazmenko <gassa mail.ru> 2013-02-14 17:05:27 PST ---
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513



--- Comment #6 from Ivan Kazmenko <gassa mail.ru> 2013-02-14 17:06:11 PST ---
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
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513


Ivan Kazmenko <gassa mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #1186|application/octet-stream    |text/plain
          mime type|                            |


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513


Ivan Kazmenko <gassa mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #1187|application/octet-stream    |text/plain
          mime type|                            |


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513


Ivan Kazmenko <gassa mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #1188|application/octet-stream    |text/plain
          mime type|                            |


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 14 2013
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=9513


Steven Schveighoffer <schveiguy yahoo.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |schveiguy yahoo.com


--- Comment #7 from Steven Schveighoffer <schveiguy yahoo.com> 2013-02-15
06:58:45 PST ---
(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. -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------
Feb 15 2013
prev sibling parent d-bugmail puremagic.com writes:
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