[Issue 9513] New: RedBlackTree excessively copies structs by value

[d-bugmail]

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: nob...@puremagic.com
        ReportedBy: ga...@mail.ru


--- Comment #0 from Ivan Kazmenko <ga...@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: -------