Two CTFE benchmarks

[bearophile]

Don:

>Thanks for the benchmarks, they're very helpful.<

You are welcome :-)


> 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


For comparison, I have run the same programs in Python and Python+Psyco (remember that Python integers are multi-precision, so they are slower).

Python 2.6.5 and the latest Psyco, same CPU and OS.


Timings nqueens, seconds:
  N=        10    11     12     13     14     15
  Python: 0.17  0.51   2.34  12.19  71.
  Psyco:  0.15  0.35   1.40   7.15  45.61   261.

Timings fannkuch, seconds:
  N=          6     7     8     9    10      11
  Python:  0.08  0.11  0.32  2.47  28.4  361.
  Psyco:   0.09  0.10  0.10  0.15  0.84    9.80

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

The Python code I have used (the extra operations done with 0xFFFFFFFF are necessary because Python has no uints that wrap, it has multi-precision ints that keep growing):


import sys, psyco

def search(cb, lb=0, rb=0, cnt=0):
    if cb == 0xFFFFFFFF:
        cnt += 1
    else:
        bs = lb | cb | rb
        while bs != 0xFFFFFFFF:
            b = ~bs & (bs + 1)
            bs |= b
            cnt = search(cb | b, ((lb | b) << 1) & 0xFFFFFFFF,
                         (rb | b) >> 1, cnt)
    return cnt

psyco.full()
N = int(sys.argv[1])
print search(0xFFFFFFFF >> N)

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

fannkuch:


import sys, array
import psyco
USES_PSYCO = True

def fannkuch(n):
    if USES_PSYCO:
        perm = array.array('l', [0] * n)
        perm1 = array.array('l', range(n))
        count = array.array('l', [0] * n)
    else:
        perm = [0] * n
        perm1 = range(n)
        count = [0] * n

    m = n - 1
    r = n
    maxFlipsCount = 0
    didpr = 0

    while True:
        if didpr < 30:
            #print "".join(str(i+1) for i in perm1)
            didpr += 1

        while r != 1:
            count[r-1] = r
            r -= 1

        if perm1[0] and perm1[m] != m:
            for i in xrange(n):
                perm[i] = perm1[i] # To avoid memory trashing

            i = perm[0]
            flips = 0
            while i:
                temp = perm[i]
                perm[i] = i
                i = temp

                j = 1
                k = i - 1
                while j < k:
                    temp = perm[j]
                    perm[j] = perm[k]
                    perm[k] = temp
                    j += 1
                    k -= 1
                flips += 1

            if flips > maxFlipsCount:
                maxFlipsCount = flips

        while True:
            if r == n:
                return maxFlipsCount
            temp = perm1[0]
            i = 0
            while i < r:
                j = i + 1
                perm1[i] = perm1[j]
                i = j
            perm1[r] = temp

            count[r] -= 1
            if count[r] > 0:
                break
            r += 1


if USES_PSYCO:
    psyco.bind(fannkuch)
N = int(sys.argv[1])
print "Pfannkuchen(%d) = %d" % (N, fannkuch(N))

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

Bye,
bearophile