Two CTFE benchmarks

[bearophile]

It's a lot of time I don't show benchmarks here :-)
I have taken the timings of run time or compile time of a integer-based function (nqueens) and a function that works with small arrays of integers (adapted from the Shootout).

I have used dmd 2.042 with -O -release -inline
The timings for the CFTE version don't include the printing on screen, I have just timed the compile time.
The CPU is a Celeron at about 2.3 GHz. Code is shown below.


Timings nqueens, seconds:
  N=         10    11     12    13    14    15
  ctfe:    0.43  1.83  23.40     -     -     -
  runtime: 0.04  0.04   0.05  0.13  0.55  3.21


Timings fannkuch, seconds:
  N=          6     7      8     9    10    11
  ctfe:    0.22  0.51  17.50     -     -     -
  runtime: 0.03  0.03   0.04  0.07  0.43  4.63


I have not timed ldc, but usually it's about 20-30% faster than dmd at CFTE (and often 100-300% faster than dmd at runtime).

The CFTE is quite slower, but the main problem is that it uses a too much large amount of RAM. Reducing the RAM used can probably speed up too a little.

----------------------------

// nqueens

import std.c.stdio: printf;

// the original code is not mine
uint nqueens(uint c, uint ll=0, uint r=0, uint n=0) {
    uint b;
    if (~c)
        for (uint
             S = ll | c | r; ~0U != S;
             b = ~S & (S + 1), S |= b, n = nqueens(c | b, (ll | b) << 1, (r | b) >> 1, n)
            ) {}
    else
        n++;
    return n;
}

enum int n = 10;
version(ctfe) enum uint result = nqueens(~0U >> n); // ctfe
void main() {
    version(ctfe) {} else uint result = nqueens(~0U >> n); // runtime
    printf("nqueens(%d) = %u\n", n, result);
}

----------------------------

// fannkuch

import std.c.stdio: printf;

int fannkuch(int n) {
    int i, j, k, t, flips, maxFlipsCount, check;
    int r = n;
    auto perm = new int[n];
    auto perm1 = new int[n];
    auto count = new int[n];

    foreach (ist; 0 .. n)
        perm1[ist] = ist;
    for ( ; ; ) {
        if (check < 30) {
            //pragma(msg, permToString(perm1)); // not possible
            check++;
        }

        while (r != 1) {
            count[r - 1] = r;
            r--;
        }

        if (!(perm1[0] == 0 || perm1[n-1] == n-1)) {
            foreach (ist; 0 .. n)
                perm[ist] = perm1[ist];

            flips = 0;
            i = perm[0];
            do {
                for (j = 1, k = i - 1; j < k; j++, k--) {
                    t = perm[j];
                    perm[j] = perm[k];
                    perm[k] = t;
                }
                flips++;
                t = perm[i];
                perm[i] = i;
                i = t;
            } while(i);

            if (flips > maxFlipsCount)
                maxFlipsCount = flips;
        }

        for ( ; ; ) {
            if (r == n)
                return maxFlipsCount;
            t = perm1[0];
            for (i = 0; i < r; ) {
                j = i + 1;
                perm1[i] = perm1[j];
                i = j;
            }
            perm1[r] = t;

            count[r]--;
            if (count[r] > 0)
                break;
            r++;
        }
    }
}


/*
This is faster as run-time function:

int fannkuch(int n)() {
    int i, j, k, t, flips, maxFlipsCount, check;
    int r = n;
    int[n] perm, perm1, count;

    foreach (ist; Range!(0, n))
        perm1[ist] = ist;
    for ( ; ; ) {
        if (check < 30) {
            //pragma(msg, permToString(perm1)); // not possible because of many D bugs
            check++;
        }

        while (r != 1) {
            count[r - 1] = r;
            r--;
        }

        if (!(perm1[0] == 0 || perm1[n-1] == n-1)) {
            foreach (ist; Range!(0, n))
                perm[ist] = perm1[ist];
...
*/


enum int n = 11;
version(ctfe) enum int result = fannkuch(n); // ctfe
void main() {
    version(ctfe) {} else int result = fannkuch(n); // runtime
    printf("Pfannkuchen(%d) = %d\n", n, result);
}

----------------------------

Bye,
bearophile