The Computer Language
23.03 Benchmarks Game

fannkuch-redux C# pgo #7 program

source code

/* The Computer Language Benchmarks Game
   https://salsa.debian.org/benchmarksgame-team/benchmarksgame/

   contributed by Isaac Gouy, transliterated from Oleg Mazurov's Java program
   concurrency fix and minor improvements by Peperud
   parallel and small optimisations by Anthony Lloyd
   15% improvement by optimizing inner loop and compiler options by Thom Kiesewetter
*/

using System.Numerics;
using System.Runtime.CompilerServices;

public static class FannkuchRedux
{
    private static int taskCount;
    private static int[] fact, chkSums, maxFlips;

    private static void FirstPermutation(int[] p, int[] pp, int[] count, int idx, int n)
    {
        for (var i = 0; i < n; ++i) p[i] = i;
        for (var i = count.Length - 1; i > 0; --i)
        {
            var d = idx / fact[i];
            count[i] = d;
            if (d > 0)
            {
                idx %= fact[i];
                new Vector<int>(p).CopyTo(pp);
                new Vector<int>(p, 4).CopyTo(pp, 4);
                for (var j = 0; j <= i; ++j) p[j] = pp[(j + d) % (i + 1)];
            }
        }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int NextPermutation(int[] p, int[] count)
    {
        var first = p[1];
        p[1] = p[0];
        p[0] = first;
        var i = 1;
        while (++count[i] > i)
        {
            count[i++] = 0;
            var next = p[1];
            p[0] = next;
            for (var j = 1; j < i;) p[j] = p[++j];
            p[i] = first;
            first = next;
        }

        return first;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int CountFlips(int first, int[] p, int[] pp)
    {
        if (first == 0) return 0;
        if (p[first] == 0) return 1;
        new Vector<int>(p).CopyTo(pp);
        new Vector<int>(p, 4).CopyTo(pp, 4);
        var flips = 1;
        var tp = pp[first];
        while (tp != 0)
        {
            var hi = first - 1;
            pp[first] = first;
            first = tp;
            for (var lo = 1; lo < hi; lo++, hi--)
            {
                var t = pp[lo];
                pp[lo] = pp[hi];
                pp[hi] = t;
            }

            tp = pp[first];
            flips++;
        }

        return flips;
    }

    private static void Run(int n, int taskSize)
    {
        int[] p = new int[16], pp = new int[16];
        var count = new int[n];
        int taskId, chkSum = 0, maxFlip = 0;
        while ((taskId = Interlocked.Decrement(ref taskCount)) >= 0)
        {
            FirstPermutation(p, pp, count, taskId * taskSize, n);
            var flips = CountFlips(p[0], p, pp);
            chkSum += flips;
            if (flips > maxFlip) maxFlip = flips;
            for (var i = 1; i < taskSize; i++)
            {
                flips = CountFlips(NextPermutation(p, count), p, pp);
                chkSum += (1 - i % 2 * 2) * flips;
                if (flips > maxFlip) maxFlip = flips;
            }
        }

        chkSums[-taskId - 1] = chkSum;
        maxFlips[-taskId - 1] = maxFlip;
    }

    public static void Main(string[] args)
    {
        var n = args.Length > 0 ? int.Parse(args[0]) : 7;
        fact = new int[n + 1];
        fact[0] = 1;
        var factN = 1;
        for (var i = 1; i < fact.Length; i++) fact[i] = factN *= i;

        taskCount = n > 9
            ? factN / (7 * 6 * 5 * 4 * 3 * 2)
            : Environment.ProcessorCount;
        var taskSize = factN / taskCount;
        var nThreads = Environment.ProcessorCount;
        chkSums = new int[nThreads];
        maxFlips = new int[nThreads];
        var threads = new Thread[nThreads];
        for (var i = 1; i < nThreads; i++)
            (threads[i] = new Thread(() => Run(n, taskSize))).Start();
        Run(n, taskSize);
        int chkSum = chkSums[0], maxFlip = maxFlips[0];
        for (var i = 1; i < threads.Length; i++)
        {
            threads[i].Join();
            chkSum += chkSums[i];
            if (maxFlips[i] > maxFlip) maxFlip = maxFlips[i];
        }

        Console.Out.WriteLineAsync(chkSum + "\nPfannkuchen(" + n + ") = " + maxFlip);
    }
}
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
.NET SDK 7.0.200
Host Version: 7.0.3
Commit: 0a2bda10e8
<ServerGarbageCollection>true
<TieredPGO>true



Sun, 19 Feb 2023 20:28:18 GMT

MAKE:
cp fannkuchredux.csharppgo-7.csharppgo Program.cs
cp Include/csharppgo/tmp.csproj .
mkdir obj
cp Include/csharppgo/project.assets.json ./obj
~/dotnet/dotnet build -c Release --no-restore --no-self-contained -r ubuntu-x64 
MSBuild version 17.5.0-preview-23061-01+040e2a90e for .NET
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/Program.cs(16,26): warning CS8618: Non-nullable field 'fact' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/tmp.csproj]
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/Program.cs(16,32): warning CS8618: Non-nullable field 'chkSums' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/tmp.csproj]
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/Program.cs(16,41): warning CS8618: Non-nullable field 'maxFlips' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/tmp.csproj]
  tmp -> /home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/bin/Release/net7.0/ubuntu-x64/tmp.dll

Build succeeded.

/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/Program.cs(16,26): warning CS8618: Non-nullable field 'fact' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/tmp.csproj]
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/Program.cs(16,32): warning CS8618: Non-nullable field 'chkSums' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/tmp.csproj]
/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/Program.cs(16,41): warning CS8618: Non-nullable field 'maxFlips' must contain a non-null value when exiting constructor. Consider declaring the field as nullable. [/home/dunham/all-benchmarksgame/benchmarksgame_i53330/fannkuchredux/tmp/tmp.csproj]
    3 Warning(s)
    0 Error(s)

Time Elapsed 00:00:04.17

5.95s to complete and log all make actions

COMMAND LINE:
./bin/Release/net7.0/ubuntu-x64/tmp 10

UNEXPECTED OUTPUT 

1,2c1,2
< 64380
< Pfannkuchen(10) = 22
---
> 73196
> Pfannkuchen(10) = 38

PROGRAM OUTPUT:
64380
Pfannkuchen(10) = 22