The Computer Language
Benchmarks Game

fannkuch-redux C# Mono LLVM #4 program

source code

/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/

   contributed by Isaac Gouy, transliterated from Oleg Mazurov's Java program
   concurrency fix and minor improvements by Peperud
*/

using System;
using System.Threading;
using System.Threading.Tasks;

class FannkuchRedux
{
    static int NCHUNKS = 150;
    static int CHUNKSZ;
    static int NTASKS;
    static int n;
    static int[] Fact;
    static int[] maxFlips;
    static int[] chkSums;
    static int taskId;

    int[] p, pp, count;

    const int INT_SIZE = 4;

    void FirstPermutation(int idx)
    {
        for (int i = 0; i < p.Length; ++i)
        {
            p[i] = i;
        }

        for (int i = count.Length - 1; i > 0; --i)
        {
            int d = idx / Fact[i];
            count[i] = d;
            idx = idx % Fact[i];

            Buffer.BlockCopy(p, 0, pp, 0, (i + 1) * INT_SIZE);

            for (int j = 0; j <= i; ++j)
            {
                p[j] = j + d <= i ? pp[j + d] : pp[j + d - i - 1];
            }
        }
    }

    bool NextPermutation()
    {
        int first = p[1];
        p[1] = p[0];
        p[0] = first;

        int i = 1;
        while (++count[i] > i)
        {
            count[i++] = 0;
            int next = p[0] = p[1];
            for (int j = 1; j < i; ++j)
            {
                p[j] = p[j + 1];
            }
            p[i] = first;
            first = next;
        }
        return true;
    }

    int CountFlips()
    {
        int flips = 1;
        int first = p[0];
        if (p[first] != 0)
        {
            Buffer.BlockCopy(p, 0, pp, 0, pp.Length * INT_SIZE);
            do
            {
                ++flips;
                for (int lo = 1, hi = first - 1; lo < hi; ++lo, --hi)
                {
                    int t = pp[lo];
                    pp[lo] = pp[hi];
                    pp[hi] = t;
                }
                int tp = pp[first];
                pp[first] = first;
                first = tp;
            } while (pp[first] != 0);
        }
        return flips;
    }

    void RunTask(int task)
    {
        int idxMin = task * CHUNKSZ;
        int idxMax = Math.Min(Fact[n], idxMin + CHUNKSZ);

        FirstPermutation(idxMin);

        int maxflips = 1;
        int chksum = 0;
        for (int i = idxMin; ;)
        {
            if (p[0] != 0)
            {
                int flips = CountFlips();

                if (maxflips < flips) maxflips = flips;

                chksum += i % 2 == 0 ? flips : -flips;
            }

            if (++i == idxMax)
            {
                break;
            }

            NextPermutation();
        }
        maxFlips[task] = maxflips;
        chkSums[task] = chksum;
    }

    public void Run()
    {
        p = new int[n];
        pp = new int[n];
        count = new int[n];

        int task;
        while ((task = Interlocked.Increment(ref taskId)) < NTASKS)
        {
            RunTask(task);
        }
    }


    static void Main(string[] args)
    {
        n = 7;
        if (args.Length > 0) n = int.Parse(args[0]);

        var nLen = n + 1;

        Fact = new int[nLen];
        Fact[0] = 1;
        for (int i = 1; i < nLen; ++i)
        {
            Fact[i] = Fact[i - 1] * i;
        }

        CHUNKSZ = (Fact[n] + NCHUNKS - 1) / NCHUNKS;
        NTASKS = (Fact[n] + CHUNKSZ - 1) / CHUNKSZ;
        maxFlips = new int[NTASKS];
        chkSums = new int[NTASKS];
        taskId = -1;

        int nthreads = Environment.ProcessorCount + 1;

        Task[] tasks = new Task[nthreads];
        for (int i = 0; i < nthreads; ++i)
        {
            tasks[i] = Task.Run(() =>
           {
               new FannkuchRedux().Run();
           });
        }
        Task.WaitAll(tasks);

        int res = 0, chk = 0;

        //
        // Would parallelizing this loop make any difference?
        //
        //for (int v = 0; v < NTASKS; v++)
        //{
        //    if (res < maxFlips[v]) res = maxFlips[v];
        //    chk += chkSums[v];
        //}

        Task[] t2 =
        {
            Task.Run(() =>
            {
                for (int v=0; v < NTASKS; v++)
                {
                    chk += chkSums[v];
                }
            }),

            Task.Run(() =>
            {
                for (int v=0; v < NTASKS; v++)
                {
                    if (res < maxFlips[v]) res = maxFlips[v];
                }
            })
        };

        Task.WaitAll(t2);

        Console.WriteLine("{0}\nPfannkuchen({1}) = {2}", chk, n, res);
    }
}
    

notes, command-line, and program output

NOTES:
32-bit Ubuntu one core
Mono JIT compiler version 4.5.1 (master/3e844dd Fri May  6 19:24:07 PDT 2016)
	LLVM:          yes(3.6.0svn-mono-master/9f79399)
	GC:            sgen



Thu, 22 Sep 2016 17:30:25 GMT

MAKE:
mv fannkuchredux.csharpllvm-4.csharpllvm fannkuchredux.csharpllvm-4.cs
/usr/local/bin/mcs -unsafe+ -optimize+ -platform:x86 -out:fannkuchredux.csharpllvm-4.csharpllvm_run fannkuchredux.csharpllvm-4.cs
rm fannkuchredux.csharpllvm-4.cs
3.62s to complete and log all make actions

COMMAND LINE:
/usr/local/bin/mono --llvm --gc=sgen fannkuchredux.csharpllvm-4.csharpllvm_run 12

PROGRAM OUTPUT:
3968050
Pfannkuchen(12) = 65