Performance of new operator

[tschoo at wh10.tu-dresden.de]

Hi all,

I am currently trying to port some of the benchmarks from the Computer
Language Benchmark Project in order to get a comparison of D with Java and
C++. While the results of the first benchmark (n-body) look very
promising, I am now stuck with my second try: a simple binary tree. The
C++ and Java implementation can be seen at
http://shootout.alioth.debian.org/u32/benchmark.php?test=binarytree

My first D attempt can be found at the end of this mail. My problem: While
the C++ and Java code takes about 15 seconds with a maxdepth of 20 on my
laptop, my D version takes >6 minutes. I suspect the recursive new in the
create method to be a problem. The C++ code uses a boost::object_pool,
however I have not found something equivalent in the D library.

Can anyone provide me with a hint on how to improve the code? The code was
compiled with optimizations enabled (both dmd and gdc).

final class Node{
public:
    this(int i)
    {
        this.i = i;
    }

    this(int i, Node l, Node r)
    {
        this.i = i;
        this.l = l;
        this.r = r;
    }

    int check() const
    {
        if (l !is null)
        {
            return l.check() + i - r.check();
        }
        return i;
    }

    static Node create(int i, int d)
    {
        if (d > 0)
            return new Node(i, create(2*i-1, d-1), create(2*i, d-1));
        else
            return new Node(i);
    }

private:
    Node l;
    Node r;
    int i;
}


int main(string[] args)
{
    const int mindepth = 4;
    const int n = (args.length > 1) ? to!int(args[1]) : 10;
    const int maxdepth = max(mindepth + 2, n);

    for (int d = mindepth; d <= maxdepth; d += 2)
    {
        int iterations = 1 << (maxdepth - d + mindepth);
        int c = 0;
        for (int i = 1; i <= iterations; ++i)
        {
            c+= Node.create(i, d).check();
            c+= Node.create(-i, d).check();
        }
        writefln("%d trees of depth %d check = %d", (2 * iterations), d, c);
    }

    return 0;
}

Thanks in advance!
Joseph