The Computer Language
Benchmarks Game

fannkuch-redux C# .NET Core #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:
64-bit Ubuntu quad core
dotnet 1.0.1 005db40cd1
"System.GC.Server": true


Sun, 16 Apr 2017 15:24:33 GMT

MAKE:
cp fannkuchredux.csharpcore-4.csharpcore Program.cs
cp Include/csharpcore/tmp.csproj .
cp Include/csharpcore/runtimeconfig.template.json .
mkdir obj
cp Include/csharpcore/tmp.csproj.nuget.g.props ./obj
cp Include/csharpcore/tmp.csproj.nuget.g.targets ./obj
/usr/bin/dotnet build -c Release
Microsoft (R) Build Engine version 15.1.548.43366
Copyright (C) Microsoft Corporation. All rights reserved.

  tmp -> /home/dunham/benchmarksgame_quadcore/fannkuchredux/tmp/bin/Release/netcoreapp1.1/tmp.dll

Build succeeded.
    0 Warning(s)
    0 Error(s)

Time Elapsed 00:00:03.62
4.08s to complete and log all make actions

COMMAND LINE:
/usr/bin/dotnet ./bin/Release/netcoreapp1.1/tmp.dll 12

PROGRAM OUTPUT:
3968050
Pfannkuchen(12) = 65