lib/actors/examples/fannkuchredux/fannkuchredux.nit

   1 # This file is part of NIT (http://www.nitlanguage.org).
   2 #
   3 # Licensed under the Apache License, Version 2.0 (the "License");
   4 # you may not use this file except in compliance with the License.
   5 # You may obtain a copy of the License at
   6 #
   7 #     http://www.apache.org/licenses/LICENSE-2.0
   8 #
   9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14
  15 # Example implemented from "The computer Language Benchmarks Game" - Fannkuch-Redux
  16 # http://benchmarksgame.alioth.debian.org/
  17 #
  18 # Complete description of the fannkuch-redux :
  19 # https://benchmarksgame.alioth.debian.org/u64q/fannkuchredux-description.html#fannkuchredux
  20 module fannkuchredux is example, no_warning("missing-doc")
  21
  22 import actors
  23
  24 class FannkuchRedux
  25         actor
  26
  27         var p: Array[Int] is noautoinit
  28         var pp: Array[Int] is noautoinit
  29         var count: Array[Int] is noautoinit
  30
  31         fun print_p do
  32                 for i in [0..p.length[ do printn p[i] + 1
  33                 print ""
  34         end
  35
  36         fun first_permutation(idx: Int) do
  37                 for i in [0..p.length[ do p[i] = i
  38
  39                 for i in [0..count.length[.reverse_iterator do
  40                         var d = idx / fact[i]
  41                         count[i] = d
  42                         idx = idx % fact[i]
  43
  44                         p.copy_to(0, i+1, pp, 0)
  45
  46                         for j in [0..i] do p[j] = if j + d <= i then pp[j+d] else pp[j+d-i-1]
  47                 end
  48         end
  49
  50         fun next_permutation do
  51                 var first = p[1]
  52                 p[1] = p[0]
  53                 p[0] = first
  54
  55                 var i = 1
  56                 count[i] += 1
  57                 while count[i] > i do
  58                         count[i] = 0
  59                         i += 1
  60
  61                         p[0] = p[1]
  62                         var next = p[0]
  63
  64                         for j in [1..i[ do p[j] = p[j+1]
  65                         p[i] = first
  66                         first = next
  67
  68                         count[i] += 1
  69                 end
  70         end
  71
  72         fun count_flips: Int do
  73                 var flips = 1
  74                 var first = p[0]
  75                 if p[first] != 0 then
  76                         p.copy_to(0, pp.length, pp, 0)
  77                         while pp[first] != 0 do
  78                                 flips += 1
  79                                 var lo = 1
  80                                 var hi = first - 1
  81                                 while lo < hi do
  82                                         var t = pp[lo]
  83                                         pp[lo] = pp[hi]
  84                                         pp[hi] = t
  85                                         lo += 1
  86                                         hi -= 1
  87                                 end
  88                                 var t = pp[first]
  89                                 pp[first] = first
  90                                 first = t
  91                         end
  92                 end
  93                 return flips
  94         end
  95
  96         fun run_task(task: Int) do
  97                 var idx_min = task * chunk_sz
  98                 var idx_max = fact[n].min(idx_min + chunk_sz)
  99
 100                 first_permutation(idx_min)
 101
 102                 var maxflips = 1
 103                 var chk_sum = 0
 104
 105                 for i in [idx_min..idx_max[ do
 106                         if p[0] != 0 then
 107                                 var flips = count_flips
 108                                 maxflips = maxflips.max(flips)
 109                                 chk_sum += if i % 2 == 0 then flips else -flips
 110                         end
 111                         if i + 1 != idx_max then next_permutation
 112                 end
 113
 114                 max_flips[task] = maxflips
 115                 chk_sums[task] = chk_sum
 116         end
 117
 118         fun run do
 119                 p = new Array[Int].with_capacity(n)
 120                 for i in [0..n[ do p.add(0)
 121                 pp = new Array[Int].with_capacity(n)
 122                 for i in [0..n[ do pp.add(0)
 123                 count = new Array[Int].with_capacity(n)
 124                 for i in [0..n[ do count.add(0)
 125
 126                 var task = 0
 127                 loop
 128                         task = task_id.get_and_increment
 129                         if task < n_tasks then run_task(task) else break
 130                 end
 131         end
 132 end
 133
 134 redef class Sys
 135         var n_chunks = 150
 136         var chunk_sz: Int is noautoinit
 137         var n_tasks: Int is noautoinit
 138         var n: Int is noautoinit
 139         var fact: Array[Int] is noautoinit
 140         var max_flips: Array[Int] is noautoinit
 141         var chk_sums: Array[Int] is noautoinit
 142         var task_id = new AtomicInt(0)
 143         var nb_actors = 8
 144 end
 145
 146 fun print_result(n, res, chk: Int) do
 147         print chk.to_s + "\nPfannfuchen(" + n.to_s + ") = " + res.to_s
 148
 149 end
 150
 151 n = if args.is_empty then 7 else args[0].to_i
 152
 153 fact = new Array[Int].with_capacity(n+1)
 154 fact[0] = 1
 155 for i in [1..n] do fact.add(fact[i-1] * i)
 156
 157 chunk_sz = (fact[n] + n_chunks - 1) / n_chunks
 158 n_tasks = (fact[n] + chunk_sz - 1) / chunk_sz
 159 max_flips = new Array[Int].with_capacity(n_tasks)
 160 for i in [0..n_tasks[ do max_flips.add(0)
 161 chk_sums = new Array[Int].with_capacity(n_tasks)
 162 for i in [0..n_tasks[ do chk_sums.add(0)
 163
 164 var actors = new Array[FannkuchRedux].with_capacity(nb_actors)
 165 for i in [0..nb_actors[ do
 166         var a = new FannkuchRedux
 167         actors.add(a)
 168         a.async.run
 169 end
 170
 171 for i in [0..nb_actors[ do
 172         actors[i].async.terminate
 173         actors[i].async.wait_termination
 174 end
 175
 176 var res = 0
 177 for i in max_flips do res = res.max(i)
 178
 179 var chk = 0
 180 for i in chk_sums do
 181         chk += i
 182 end
 183
 184 print_result(n, res, chk)