Add fannkuchredux shootout benchmark

1 files changed, 99 insertions, 0 deletions

diff --git a/src/test/bench/shootout/fannkuchredux.rs b/src/test/bench/shootout/fannkuchredux.rs
new file mode 100644
index 00000000..2d44067b
--- /dev/null
+++ b/src/test/bench/shootout/fannkuchredux.rs
@@ -0,0 +1,99 @@
+// Based on Isaac Gouy's fannkuchredux.csharp
+
+use std;
+
+import std._int;
+import std._vec;
+
+impure fn fannkuch(int n) -> int {
+
+  fn perm1init(uint i) -> mutable int {
+    ret i as int;
+  }
+  auto perm1init_ = perm1init; // Rustboot workaround
+
+  auto perm = _vec.init_elt[mutable int](0, n as uint);
+  auto perm1 = _vec.init_fn[mutable int](perm1init_, n as uint);
+  auto count = _vec.init_elt[mutable int](0, n as uint);
+
+  auto f = 0;
+  auto i = 0;
+  auto k = 0;
+  auto r = 0;
+  auto flips = 0;
+  auto nperm = 0;
+  auto checksum = 0;
+
+  r = n;
+  while (r > 0) {
+    i = 0;
+
+    while (r != 1) {
+      count.(r - 1) = r;
+      r -=1;
+    }
+
+    while (i < n) {
+      perm.(i) = perm1.(i);
+      i += 1;
+    }
+
+    // Count flips and update max and checksum
+    f = 0;
+    k = perm.(0);
+    while (k != 0) {
+      i = 0;
+      while (2 * i < k) {
+        auto t = perm.(i);
+        perm.(i) = perm.(k - i);
+        perm.(k - i) = t;
+        i += 1;
+      }
+      k = perm.(0);
+      f += 1;
+    }
+
+    if (f > flips) {
+      flips = f;
+    }
+
+    if ((nperm & 0x1) == 0) {
+      checksum += f;
+    } else {
+      checksum -= f;
+    }
+
+    // Use incremental change to generate another permutation
+    auto go = true;
+    while (go) {
+      if (r == n) {
+        log checksum;
+        ret flips;
+      }
+      auto p0 = perm1.(0);
+      i = 0;
+      while (i < r) {
+        auto j = i + 1;
+        perm1.(i) = perm1.(j);
+        i = j;
+      }
+      perm1.(r) = p0;
+
+      count.(r) -= 1;
+      if (count.(r) > 0) {
+        go = false;
+      } else {
+        r += 1;
+      }
+    }
+
+    nperm += 1;
+  }
+
+  ret flips;
+}
+
+impure fn main(vec[str] args) {
+  auto n = 7;
+  log #fmt("Pfannkuchen(%d) = %d", n, fannkuch(n));
+}
\ No newline at end of file