The Q6600
Benchmarks Game

fannkuch-redux Matz's Ruby #2 program

source code

# The Computer Language Benchmarks Game
# https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
# Contributed by Wesley Moxam
# Modified by Sokolov Yura aka funny_falcon
# Parallelised by Scott Leggett

require 'thread'

module MiniParallel
    class Worker
        def initialize(read, write)
            @read, @write = read, write
        end

        def close_pipes
            @read.close
            @write.close
        end

        def work(index)
            Marshal.dump(index, @write)
            Marshal.load(@read)
        end
    end

    def self.map(array, &block)
        work_in_processes(
            array,
            [array.size, core_count].min,
            &block
        )
    end

    def self.core_count
        @@core_count ||= IO.read("/proc/cpuinfo").scan(/^processor/).size
    end

    private

    def self.work_in_processes(array, count, &block)
        index = -1
        results, threads = [], []

        workers = create_workers(array, count, &block)

        workers.each do |worker|
            threads << Thread.new do
                loop do
                    Thread.exclusive{ index += 1 }
                    break if index >= array.size
                    results[index] = worker.work(index)
                end
                worker.close_pipes
            end
        end

        threads.each(&:join)
        Process.waitall

        results
    end

    def self.create_workers(array, count, &block)
        workers = []
        count.times do
            workers << create_worker(array, workers, &block)
        end
        workers
    end

    def self.create_worker(array, started_workers, &block)
        child_read, parent_write = IO.pipe
        parent_read, child_write = IO.pipe

        Process.fork do
            started_workers.each(&:close_pipes)

            parent_write.close
            parent_read.close

            process_incoming_jobs(child_read, child_write, array, &block)

            child_read.close
            child_write.close
        end

        child_read.close
        child_write.close

        Worker.new(parent_read, parent_write)
    end

    def self.process_incoming_jobs(read, write, array, &block)
        until read.eof?
            index = Marshal.load(read)
            Marshal.dump(block.call(array[index]), write)
        end
    end
end

class Fannkuch

    def initialize(n, start, max_perms)
        @n = n
        @p = (0..n).to_a
        @s = @p.dup
        @q = @p.dup
        @sign = 1
        @sum = @maxflips = 0
        @max_perms = max_perms
        @perm_count = -start
        start.times{permute}
    end

    def flip
        loop do
            if @perm_count == @max_perms
                return [@sum, @maxflips]
            end
            if (q1 = @p[1]) != 1
                @q[0..-1] = @p
                flips = 1
                until (qq = @q[q1]) == 1
                    @q[q1] = q1
                    if q1 >= 4
                        i, j = 2, q1 - 1
                        while i < j
                            @q[i], @q[j] = @q[j], @q[i]
                            i += 1
                            j -= 1
                        end
                    end
                    q1 = qq
                    flips += 1
                end
                @sum += @sign * flips
                @maxflips = flips if flips > @maxflips # New maximum?
            end
            permute
        end
    end

    def permute
        @perm_count += 1

        if @sign == 1
            # Rotate 1<-2.

            @p[1], @p[2] = @p[2], @p[1]
            @sign = -1
        else
            # Rotate 1<-2 and 1<-2<-3.

            @p[2], @p[3] = @p[3], @p[2]
            @sign = 1
            i = 3
            while i <= @n && @s[i] == 1
                @s[i] = i
                # Rotate 1<-...<-i+1.

                t = @p.delete_at(1)
                i += 1
                @p.insert(i, t)
            end
            @s[i] -= 1  if i <= @n
        end
    end
end

abort "Usage: #{__FILE__} n\n(n > 6)" if (n = ARGV[0].to_i) < 6

core_count = MiniParallel.core_count
chunk_size = (1..n).reduce(:*) / core_count

sum, flips =
    if core_count > 1
        # adjust job sizes to even out workload
        weights = if core_count > 1
                      weights = []
                      (core_count/2).times do |i|
                          weights << i * 0.1 + 0.05
                      end
                      weights = weights.reverse + weights.map{|i|-i}
                  else
                      [0]
                  end

        # Generate start position for each chunk
        chunks = core_count.times.zip(weights).map do |count, weight|
            [count * chunk_size +
             (count > 0 ? (weights[0,count].reduce(:+) * chunk_size).round : 0),
             chunk_size + (weight * chunk_size).round]
        end

        chunk_results =
            if (RUBY_PLATFORM == 'java')
                chunk_collector = []
                threads = []
                chunks.each.with_index do |(start,weighted_size),i|
                    threads << Thread.new do
                        chunk_collector[i] = Fannkuch.new(n,start,weighted_size).flip
                    end
                end
                threads.all?(&:join)
                chunk_collector
            else
                MiniParallel.map(chunks) do |start, weighted_size|
                    Fannkuch.new(n,start,weighted_size).flip
                end
            end

        chunk_results.reduce do |memo, (cksum, fmax)|
            [memo[0] + cksum, [memo[1], fmax].max]
        end
    else
        Fannkuch.new(n,0,chunk_size).flip
    end

printf "%d\nPfannkuchen(%d) = %d\n", sum, n, flips
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
ruby 1.8.7 (2008-08-11 patchlevel 72) [x86_64-linux]
 
So old that I haven't been able to get rubygems to work
no backport, no gmp


Sun, 05 Jan 2020 02:08:52 GMT

COMMAND LINE:
/usr/bin/ruby fannkuchredux.mri-2.mri 12

PROGRAM OUTPUT:
3968050
Pfannkuchen(12) = 65