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 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                 var i = count.length - 1
  40                 while i > 0 do
  41                         var d = idx / fact[i]
  42                         count[i] = d
  43                         idx = idx % fact[i]
  44
  45                         p.copy_to(0, i+1, pp, 0)
  46
  47                         for j in [0..i] do
  48                                 if j + d <= i then
  49                                         p[j] = pp[j+d]
  50                                 else
  51                                         p[j] = pp[j+d-i-1]
  52                                 end
  53                         end
  54                         i -= 1
  55                 end
  56         end
  57
  58         fun next_permutation do
  59                 var first = p[1]
  60                 p[1] = p[0]
  61                 p[0] = first
  62
  63                 var i = 1
  64                 count[i] += 1
  65                 while count[i] > i do
  66                         count[i] = 0
  67                         i += 1
  68
  69                         p[0] = p[1]
  70                         var next = p[0]
  71
  72                         for j in [1..i[ do p[j] = p[j+1]
  73                         p[i] = first
  74                         first = next
  75
  76                         count[i] += 1
  77                 end
  78         end
  79
  80         fun count_flips: Int do
  81                 var flips = 1
  82                 var first = p[0]
  83                 if p[first] != 0 then
  84                         p.copy_to(0, pp.length, pp, 0)
  85                         loop
  86
  87                                 flips += 1
  88                                 var lo = 1
  89                                 var hi = first - 1
  90                                 while lo < hi do
  91                                         var t = pp[lo]
  92                                         pp[lo] = pp[hi]
  93                                         pp[hi] = t
  94                                         lo += 1
  95                                         hi -= 1
  96                                 end
  97                                 var t = pp[first]
  98                                 pp[first] = first
  99                                 first = t
 100
 101                                 if pp[first] == 0 then break
 102                         end
 103                 end
 104                 return flips
 105         end
 106
 107         fun run_task(task: Int) do
 108                 var idx_min = task * chunk_sz
 109                 var idx_max = fact[n].min(idx_min + chunk_sz)
 110
 111                 first_permutation(idx_min)
 112
 113                 var maxflips = 1
 114                 var chk_sum = 0
 115
 116                 var i = idx_min
 117                 loop
 118                         if p[0] != 0 then
 119                                 var flips = count_flips
 120                                 maxflips = maxflips.max(flips)
 121                                 if i % 2 == 0 then
 122                                         chk_sum += flips
 123                                 else
 124                                         chk_sum += -flips
 125                                 end
 126                         end
 127
 128                         i += 1
 129                         if i == idx_max then break
 130                         next_permutation
 131                 end
 132
 133                 max_flips[task] = maxflips
 134                 chk_sums[task] = chk_sum
 135         end
 136
 137         fun run do
 138                 p = new Array[Int].with_capacity(n)
 139                 for i in [0..n[ do p.add(0)
 140                 pp = new Array[Int].with_capacity(n)
 141                 for i in [0..n[ do pp.add(0)
 142                 count = new Array[Int].with_capacity(n)
 143                 for i in [0..n[ do count.add(0)
 144
 145                 var task = 0
 146                 loop
 147                         task = task_id.get_and_increment
 148                         if task < n_tasks then
 149                                 run_task(task)
 150                         else
 151                                 break
 152                         end
 153                 end
 154         end
 155 end
 156
 157 redef class Sys
 158         var n_chunks = 150
 159         var chunk_sz: Int is noautoinit
 160         var n_tasks: Int is noautoinit
 161         var n: Int is noautoinit
 162         var fact: Array[Int] is noautoinit
 163         var max_flips: Array[Int] is noautoinit
 164         var chk_sums: Array[Int] is noautoinit
 165         var task_id = new AtomicInt(0)
 166         var nb_actors = 8
 167 end
 168
 169 fun print_result(n, res, chk: Int) do
 170         print chk.to_s + "\nPfannfuchen(" + n.to_s + ") = " + res.to_s
 171
 172 end
 173
 174 if args.is_empty then
 175         n = 7
 176 else
 177         n = args[0].to_i
 178 end
 179
 180 fact = new Array[Int].with_capacity(n+1)
 181 fact[0] = 1
 182 for i in [1..n] do fact.add(fact[i-1] * i)
 183
 184 chunk_sz = (fact[n] + n_chunks - 1) / n_chunks
 185 n_tasks = (fact[n] + chunk_sz - 1) / chunk_sz
 186 max_flips = new Array[Int].with_capacity(n_tasks)
 187 for i in [0..n_tasks[ do max_flips.add(0)
 188 chk_sums = new Array[Int].with_capacity(n_tasks)
 189 for i in [0..n_tasks[ do chk_sums.add(0)
 190
 191 var actors = new Array[FannkuchRedux].with_capacity(8)
 192 for i in [0..nb_actors[ do
 193         var a = new FannkuchRedux
 194         actors.add(a)
 195         a.async.run
 196 end
 197
 198 for i in [0..nb_actors[ do
 199         actors[i].async.terminate
 200         actors[i].async.wait_termination
 201 end
 202
 203 var res = 0
 204 for i in max_flips do res = res.max(i)
 205
 206 var chk = 0
 207 for i in chk_sums do
 208         chk += i
 209 end
 210
 211 print_result(n, res, chk)