• tschoo wh10.tu-dresden.de Jun 04 2011
• bearophile <bearophileHUGS lycos.com> Jun 04 2011
• Joseph Schuchart <tschoo wh10.tu-dresden.de> Jun 05 2011

tschoo wh10.tu-dresden.de writes:

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

bearophile <bearophileHUGS lycos.com> writes:

tschoo:

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


Have you seen this page?
http://shootout.alioth.debian.org/debian/benchmark.php?test=all&lang=gdc&lang2=gcc&box=1#ratio


 I am now stuck with my second try: a simple binary tree.


This benchmark stresses just the GC. The D GC is simple and slow.

Bye,
bearophile

Joseph Schuchart <tschoo wh10.tu-dresden.de> writes:

 Have you seen this page?
 http://shootout.alioth.debian.org/debian/benchmark.php?test=all&lang=gdc&lang2=gcc&box=1#ratio


outdated though. I was wondering why there are no results for the D
language in the current version of this benchmarking game. It seems
someone has submitted code that is not used in the new version?
 I am now stuck with my second try: a simple binary tree.


From the posts I have read on digitalmars.D I expected the GC to be a


 Bye,
 bearophile