RedBlackTree excessively copies structs by value

[dlangBugzillaToGithub]

gassa (@GassaFM) reported this on 2013-02-14T15:06:12Z

Transfered from https://issues.dlang.org/show_bug.cgi?id=9513

CC List

• bearophile_hugs
• schveiguy (@schveiguy)

Description

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.

!!!There are attachements in the bugzilla issue that have not been copied over!!!

[dlangBugzillaToGithub]

bearophile_hugs commented on 2013-02-14T15:17:57Z

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

[dlangBugzillaToGithub]

gassa commented on 2013-02-14T15:26:07Z

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.

[dlangBugzillaToGithub]

gassa commented on 2013-02-14T16:21:09Z

(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?

[dlangBugzillaToGithub]

gassa commented on 2013-02-14T17:04:46Z

Created attachment 1186
Example with excessive copying

[dlangBugzillaToGithub]

gassa commented on 2013-02-14T17:05:27Z

Created attachment 1187
Solution 1: two redundant functions

[dlangBugzillaToGithub]

gassa commented on 2013-02-14T17:06:11Z

Created attachment 1188
Solution 2: template with auto ref

[dlangBugzillaToGithub]

schveiguy (@schveiguy) commented on 2013-02-15T06:58:45Z

(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.