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: -------

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: -------

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: -------

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: -------

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: -------

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: -------

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: -------

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: -------

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: -------

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: -------