Not building with newest LDC D compiler

[cyrusmsk]

Just found this issue in my fork and want to warn you @hanabi1224. So before merging the next PR maybe we could specify the version of compiler in build-d.yaml
The issue in the library's GitHub is already created. I will update this thread when new information will come.
Sorry for inconvenience.

[cyrusmsk]

So it seems the issue is fixed. And will be available in 1.32.1 version of LDC.

[renatoathaydes]

I couldn't compile the binary tree 1.d solution until I fixed the imports... not sure if that was written for very old D versions?

Here's what works for me with D v2:

@safe:
import std.stdio;
import std.conv;
import std.algorithm.comparison;
import std.format;

extern(C) __gshared string[] rt_options = [ "gcopt=minPoolSize:300" ];

const MIN_DEPTH = 4;

class Node {
    private Node left;
    private Node right;

    this(Node left, Node right)
    {
        this.left = left;
        this.right = right;
    }

    int check() {
        auto r = 1;
        auto ln = this.left;
        auto rn = this.right;
        if (ln) {
            r += ln.check();
        }
        if (rn) {
            r += rn.check();
        }
        return r;
    }

    static Node create(int depth) {
        if (depth > 0) {
            auto d = depth - 1;
            return new Node(Node.create(d), Node.create(d));
        }
        return new Node(null, null);
    }
}

void main(string[] args)
{
    auto n = args.length > 1 ? args[1].to!int() : 6;
    auto maxDepth = max(MIN_DEPTH + 2, n);
    auto stretchDepth = maxDepth + 1;
    auto stretchTree = Node.create(stretchDepth);
    writeln(format("stretch tree of depth %d\t check: %d", stretchDepth, stretchTree.check()));
    auto longLivedTree = Node.create(maxDepth);

    for (int depth = MIN_DEPTH; depth <= maxDepth; depth += 2) {
        auto iterations = 1 << (maxDepth - depth + MIN_DEPTH);
        auto sum = 0;
        for (auto i = 0; i < iterations; i++) {
            sum += Node.create(depth).check();
        }
        writeln(format("%d\t trees of depth %d\t check: %d", iterations, depth, sum));
    }

    writeln(format("long lived tree of depth %d\t check: %d", maxDepth, longLivedTree.check()));
}

This is much slower than Java and Dart, for example, which seem very strange to me. Anyone has any idea why that would be? I suppose this problem is testing mostly the GC and speed of allocation, but still D shouldn't be 5x slower as it currently is, but I couldn't speed this up myself as I don't know D very well.

[cyrusmsk]

Hi @renatoathaydes
Current version is working for me on LDC 1.35 (macOS).

Which compiler version are you using?
Because
import std;
Should just works in many scenarios. It is not an optimal way - but it is fine way to use it.

Regarding the speed - you can see that on top of the list in this problem languages with VM - Dart and JVM like..
But of course D solution could be improved.
Also keep in mind that arena allocations are forbidden by the rules of the benchmark, otherwise languages like C++/Zig/Rust/D - will have much better performance than Java.

[cyrusmsk]

Ok. I've made some changes: more close to other solutions.. moved from class to struct. And it is working a bit faster on my machine.
Code:

@safe:
import std;

extern(C) __gshared string[] rt_options = [ "gcopt=minPoolSize:300 initReserve:300" ];

const MIN_DEPTH = 4;
static empty = Node(null, null);

struct Node {
    Node* left;
    Node* right;
}


int check(Node* n) {
    if (n.left is null)
        return 1;
    return 1 + check(n.left) + check(n.right);
}

Node* bottomUpTree(int d) {
    if (d <= 0) {
        return &empty;
    }
    return new Node(bottomUpTree(d - 1), bottomUpTree(d - 1));
}

void main(string[] args)
{
    auto n = args.length > 1 ? args[1].to!int() : 6;
    auto maxDepth = max(MIN_DEPTH + 2, n);
    auto stretchDepth = maxDepth + 1;
    auto checkTree = check(bottomUpTree(stretchDepth));
    writeln(format("stretch tree of depth %d\t check: %d", stretchDepth, checkTree));
    auto longLivedTree = bottomUpTree(maxDepth);

    for (int depth = MIN_DEPTH; depth <= maxDepth; depth += 2) {
        auto iterations = 1 << (maxDepth - depth + MIN_DEPTH);
        auto sum = 0;
        for (auto i = 0; i < iterations; i++) {
            sum += check(bottomUpTree(depth));
        }
        writeln(format("%d\t trees of depth %d\t check: %d", iterations, depth, sum));
    }

    writeln(format("long lived tree of depth %d\t check: %d", maxDepth, check(longLivedTree)));
}

For comparison of performance:
Go version:

long lived tree of depth 18 check: 524287
1,50 real 4,89 user 0,34 sys

Current D version:

long lived tree of depth 18 check: 524287
1,09 real 1,05 user 0,03 sys

Updated D version:

long lived tree of depth 18 check: 524287
0,63 real 0,59 user 0,04 sys

[renatoathaydes]

Hi @cyrusmsk

I was using gdc and that doesn't work on gdc. I am testing this on Linux.

I can compile your code using DMD and it does run, and is a bit faster.

DMD time:

➜  d dmd -of=main -O main.d
➜  d time ./main 18
stretch tree of depth 19	 check: 1048575
262144	 trees of depth 4	 check: 8126464
65536	 trees of depth 6	 check: 8323072
16384	 trees of depth 8	 check: 8372224
4096	 trees of depth 10	 check: 8384512
1024	 trees of depth 12	 check: 8387584
256	 trees of depth 14	 check: 8388352
64	 trees of depth 16	 check: 8388544
16	 trees of depth 18	 check: 8388592
long lived tree of depth 18	 check: 524287
./main 18   1.62s  user 0.12s system 99% cpu 1.740 total
avg shared (code):         0 KB
avg unshared (data/stack): 0 KB
total (sum):               0 KB
max memory:                313 MB
page faults from disk:     0
other page faults:         79522

LDC2:

➜  d source ~/dlang/ldc-1.35.0/deactivate         
source: no such file or directory: /home/renato/dlang/ldc-1.35.0/deactivate
➜  d source ~/dlang/ldc-1.35.0/activate  
(ldc-1.35.0)➜  d ldc2 -of=main -O main.d
(ldc-1.35.0)➜  d time ./main 18
stretch tree of depth 19	 check: 1048575
262144	 trees of depth 4	 check: 8126464
65536	 trees of depth 6	 check: 8323072
16384	 trees of depth 8	 check: 8372224
4096	 trees of depth 10	 check: 8384512
1024	 trees of depth 12	 check: 8387584
256	 trees of depth 14	 check: 8388352
64	 trees of depth 16	 check: 8388544
16	 trees of depth 18	 check: 8388592
long lived tree of depth 18	 check: 524287
./main 18   1.25s  user 0.16s system 99% cpu 1.416 total
avg shared (code):         0 KB
avg unshared (data/stack): 0 KB
total (sum):               0 KB
max memory:                312 MB
page faults from disk:     0
other page faults:         79508

I was surprised that DMD gets the same speed as LDC.

For reference, here's the Dart times (which I submitted in a PR), which is faster than the #1 Java solution (so this should be faster than the Kotlin one as well):

(ldc-1.35.0)➜  d dart compile exe tree.dart
Generated: /home/renato/programming/experiments/d/tree.exe
(ldc-1.35.0)➜  d time ./tree.exe 18
stretch tree of depth 19	 check: 1048575
262144	 trees of depth 4	 check: 8126464
65536	 trees of depth 6	 check: 8323072
16384	 trees of depth 8	 check: 8372224
4096	 trees of depth 10	 check: 8384512
1024	 trees of depth 12	 check: 8387584
256	 trees of depth 14	 check: 8388352
64	 trees of depth 16	 check: 8388544
16	 trees of depth 18	 check: 8388592
long lived tree of depth 18	 check: 524287
./tree.exe 18   0.65s  user 0.05s system 103% cpu 0.678 total
avg shared (code):         0 KB
avg unshared (data/stack): 0 KB
total (sum):               0 KB
max memory:                63 MB
page faults from disk:     0
other page faults:         15755

So D is still much slower, disappointingly.

[cyrusmsk]

Usually Dart will be much slower than D. Just this algorithm that proposed to be used for this problem not doing well..

[cyrusmsk]

For example you can find another approach of BinaryTrees.. https://github.com/BinaryTrees
this implementation should be much more efficient in compiled C++/D/Rust than in Dart/Java/Kotlin…

[cyrusmsk]

And there are also optimized solutions https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/binarytrees.html

[renatoathaydes]

Usually Dart will be much slower than D.

I also ran a HTTP Server and Dart again was quite a bit faster. In which problems is Dart slower?

[cyrusmsk]

Usually Dart will be much slower than D.

I also ran a HTTP Server and Dart again was quite a bit faster. In which problems is Dart slower?

Many of them actually. https://programming-language-benchmarks.vercel.app/dart-vs-d
Yeah - server implementation is just broken for D in this repo)
For HTTP server you can check something like this https://web-frameworks-benchmark.netlify.app/result?l=dart,d
D has not the fastest servers.. but doing good enough

[renatoathaydes]

The HTTP Server I tried was not from this repository but from the "canonical" servers in each language (Dart has one in the stdlib and for D I used Vibe.d).

In the comparisons page you linked, D is faster in some, slower in some, much faster in some, much slower in some, but mostly it's pretty close - with D perhaps having at most a small edge ... so I think your assertion that Dart is much slower than D doesn't reflect that page at all.

[cyrusmsk]

The HTTP Server I tried was not from this repository but from the "canonical" servers in each language (Dart has one in the stdlib and for D I used Vibe.d).

In the comparisons page you linked, D is faster in some, slower in some, much faster in some, much slower in some, but mostly it's pretty close - with D perhaps having at most a small edge ... so I think your assertion that Dart is much slower than D doesn't reflect that page at all.

Let's check closely. For more accurate analysis.
I'm not sure which work Google made for AOT in Dart - is it based on LLVM optimization?

Where Dart is faster:

1. HTTP server - doesn't count. Because check the specific web-benchmark. ✅
2. Binarytrees, merkletrees - because of rules of the benchmark. Compiled langs forbidden to use arena/memorypool strategies, while VM-based langs most probably use it under the hood. If provide proper implementation in C++/Rust/D - it will be faster. See original benchmark games repo. ✅
3. Coro-prime-sieve - it was not my implementation (implemented by author of the repo who is not very good at D). Mostly it is based on async. Need to check D's implementation if it is could be better. It will be definitely more complex - because D doesn't have async/await. But not sure if it should be slower, if properly implemented. 🟡
4. Pidigits - used BigInt, which is quite slow for big values in the std. But it is possible to use GMP (and some langs just use GMP inside). ✅
   Please try to compare this code (make sure you added gmp-d into dependency):

@safe:
import std;
import std.outbuffer : OutBuffer;
import gmp.z;

alias Z = CopyableMpZ;


void main(string[] args)
{
    auto digits_to_print = args.length > 1 ? args[1].to!int() : 27;

    immutable one = 1.Z;
    immutable two = 2.Z;
    immutable ten = 10.Z;

    int digits_printed = 0;
    auto k = 1.Z;
    auto n1 = 4.Z;
    auto n2 = 3.Z;
    auto d = 1.Z;
    Z u,v,w;

    OutBuffer b = new OutBuffer();
    while(true) {

        u = n1 / d;
        v = n2 / d;
        if (u == v) {
            b.writef("%s",u);
            digits_printed += 1;
            int digits_printed_mod = digits_printed % 10;
            if (digits_printed_mod == 0)
                b.writef("\t%d\n", digits_printed);

            if (digits_printed >= digits_to_print) {
                if (digits_printed_mod > 0) {
                    foreach(_; 0..(10 - digits_printed_mod))
                        b.write(" ");
                    b.writef("\t%d\n", digits_printed);
                }

                write(b.toString());
                return;
            }

            auto to_minus = u * ten * d;
            n1 = n1 * ten - to_minus;
            n2 = n2 * ten - to_minus;
        }
        else {
            auto k2 = k * two;
            u = n1 * (k2 - one);
            v = n2 * two;
            w = n1 * (k - one);
            n1 = u + v;
            u = n2 * (k + two);
            n2 = w + u;
            d = d * (k2 + one);
            k = k + one;
        }
    }
}

[cyrusmsk]

The HTTP Server I tried was not from this repository but from the "canonical" servers in each language (Dart has one in the stdlib and for D I used Vibe.d).

In the comparisons page you linked, D is faster in some, slower in some, much faster in some, much slower in some, but mostly it's pretty close - with D perhaps having at most a small edge ... so I think your assertion that Dart is much slower than D doesn't reflect that page at all.

Ok. With help of 'brianush1' the code for Coro-prime-sieve was prepared. It's slower than Go, but should be close in performance to Rust/Crystal I think. And I assume faster than Dart.

import core.thread;
import std;
import std.outbuffer: OutBuffer;

class Generator(T) : Fiber {
	private T value;

	this(void delegate() dg) {
		super(dg);
	}

	static void yield(T value) {
		(cast(Generator!T) Fiber.getThis()).value = value;
		Fiber.yield();
	}

	T getNext() {
		call();
		return value;
	}

	int opApply(scope int delegate(T) dg) {
		int result = 0;

		while (state != State.TERM) {
			result = dg(getNext());
			if (result)
				break;
		}
		return result;
	}
}

auto generate() {
	return new Generator!long({
		long i = 2;
		while (true) {
			Generator!long.yield(i);
			i += 1;
		}
	});
}

auto filter(Generator!long ch, long prime) {
	return new Generator!long({
		foreach (i; ch)
			if (i % prime != 0)
				Generator!long.yield(i);
	});
}

void main(string[] args) {
    long n = args.length > 1 ? args[1].to!long: 10;

    auto buf = new OutBuffer();
    scope(exit)
        write(buf.toString());

	Generator!long ch = generate();
	foreach (i; 0 .. n) {
		long prime = ch.getNext();
		buf.writef("%d\n",prime);
		ch = filter(ch, prime);
	}
}

[renatoathaydes]

Not sure if it's valid, but D has a very fast HTTP server as well: https://github.com/tchaloupka/httparsed

Also, are you also trying to speed up the Dart solution?

[cyrusmsk]

Not sure if it's valid, but D has a very fast HTTP server as well: https://github.com/tchaloupka/httparsed

D server unfortunately not very fast( httpparser is good yes.

Also, are you also trying to speed up the Dart solution?

No, I’ve never worked with Dart