Multithread fannkuchredux

[KristofferC]

Could take inspiration from https://benchmarksgame-team.pages.debian.net/benchmarksgame/program/fannkuchredux-java-1.html

[SimonDanisch]

started it, but I still messed up somewhere porting 0 to 1 based indexing -.-

# Calculate factorials
struct Fannkuch
   n::Int
   p::Vector{Int}
   pp::Vector{Int}
   count::Vector{Int}
   function Fannkuch(n::Int)
       p = Vector{Int}(undef, n)
       new(n, p, similar(p), similar(p))
    end
end
macro fields(f)
    fesc = esc(f)
    esc(quote
        n, p, pp, count = $f.n, $f.p, $f.pp, $f.count
    end)
end
# copies n elements from x to y
assign!(x, y, n) = copyto!(x, 1, y, 1, n)

function firstPermutation!(f, idx, fact)
    @fields f
    p .= 1:n
    indx = idx - 1
    for i in n:-1:2
        d = indx ÷ fact[i]
        count[i] = d
        indx = indx % fact[i]
        assign!(pp, p, i)
        for j in 1:i
            p[j] = (j + d) <= (i) ? pp[j + d] : pp[j + d - i]
        end
    end
end

function nextPermutation!(f)
    @fields f
    first = p[2]
    p[2] = p[1]
    p[1] = first
    i = 2
    count[i] += 1
    while count[i] > (i - 1)
        count[i] = 0
        i += 1
        p[1] = p[2]
        next = p[1]
        for j in 2:(i-2)
            p[j] = p[j + 1]
        end
        p[i] = first
        first = next
        count[i] += 1
    end
    return
end

function countFlips!(f)
    @fields f
    flips = 1
    first = p[1]
    if p[first] != 1
        assign!(pp, p, n)
        while true
            flips += 1
            lo = 2
            hi = first - 1
            while lo < hi
                t = pp[lo]
                pp[lo] = pp[hi]
                pp[hi] = t
                lo += 1; hi -= 1
            end
            t = pp[first]
            pp[first] = first
            first = t
            println(pp[first])
            (pp[first] != 1) || break
        end
    end
    return flips
end

function runTask(f, task, fact, maxFlips, chkSums, chunksz)
    @fields f
    idxMin = ((task - 1) * chunksz) + 1
    idxMax = (fact[n] < idxMin + chunksz) ? fact[n] + 1 : (idxMin + chunksz)
    # Determine first permutation
    firstPermutation!(f, idxMin, fact)
    maxflips = 1
    chksum = 0
    i = idxMin
    while true
        if p[1] != 1
            flips = countFlips!(f)
            if flips > maxflips
                maxflips = flips
            end
            chksum += i % 2 == 0 ? flips : -flips
        end
        i += 1
        i == idxMax && break
        nextPermutation!(f)
    end
    maxFlips[task] = maxflips
    chkSums[task] = chksum
end

function pfannkuchen(n)
    fact = Vector{Int}(undef, n + 1)
    fact[1] = 1
    for i in 2:(n + 1)
        @inbounds fact[i] = fact[i-1] * (i - 1)
    end
    # Determine number of tasks
    nchunks = 150
    chunksz = (fact[n + 1] + nchunks - 1) ÷ nchunks
    ntasks = (fact[n + 1] + chunksz - 1) ÷ chunksz

    # Allocate result vectors
    maxFlips = fill(0, ntasks)
    chkSums = fill(0, ntasks)

    for i in 1:ntasks
        f = Fannkuch(n)
        runTask(f, i, fact, maxFlips, chkSums, chunksz)
    end

    # Collect results
    res = maximum(maxFlips)
    chksum = sum(chkSums)
    res
end

pfannkuchen(7)