test: Add fannkuch-redux and fasta-redux shootout benchmarks

4 files changed, 322 insertions, 82 deletions

diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index 3e0ba38a6e8..8934b6cab67 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -12,8 +12,9 @@
 
 #[warn(non_camel_case_types)];
 
-use container::{Container, Mutable};
+use cast::transmute;
 use cast;
+use container::{Container, Mutable};
 use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
 use clone::Clone;
 use iter::BaseIter;
@@ -2137,6 +2138,7 @@ pub trait ImmutableCopyableVector<T> {
     fn filtered(&self, f: &fn(&T) -> bool) -> ~[T];
     fn rfind(&self, f: &fn(t: &T) -> bool) -> Option<T>;
     fn partitioned(&self, f: &fn(&T) -> bool) -> (~[T], ~[T]);
+    unsafe fn unsafe_get(&self, elem: uint) -> T;
 }
 
 /// Extension methods for vectors
@@ -2173,6 +2175,13 @@ impl<'self,T:Copy> ImmutableCopyableVector<T> for &'self [T] {
     fn partitioned(&self, f: &fn(&T) -> bool) -> (~[T], ~[T]) {
         partitioned(*self, f)
     }
+
+    /// Returns the element at the given index, without doing bounds checking.
+    #[inline(always)]
+    unsafe fn unsafe_get(&self, elem: uint) -> T {
+        let (ptr, _): (*T, uint) = transmute(*self);
+        *ptr.offset(elem)
+    }
 }
 
 pub trait OwnedVector<T> {
@@ -2313,6 +2322,19 @@ impl<T:Eq> OwnedEqVector<T> for ~[T] {
     }
 }
 
+pub trait MutableVector<T> {
+    unsafe fn unsafe_set(&self, elem: uint, val: T);
+}
+
+impl<'self,T> MutableVector<T> for &'self mut [T] {
+    #[inline(always)]
+    unsafe fn unsafe_set(&self, elem: uint, val: T) {
+        let pair_ptr: &(*mut T, uint) = transmute(self);
+        let (ptr, _) = *pair_ptr;
+        *ptr.offset(elem) = val;
+    }
+}
+
 /**
 * Constructs a vector from an unsafe pointer to a buffer
 *
diff --git a/src/test/bench/shootout-fannkuch-redux.rs b/src/test/bench/shootout-fannkuch-redux.rs
new file mode 100644
index 00000000000..21f38245ca3
--- /dev/null
+++ b/src/test/bench/shootout-fannkuch-redux.rs
@@ -0,0 +1,95 @@
+use core::from_str::FromStr;
+use core::i32::range;
+use core::vec::MutableVector;
+
+fn max(a: i32, b: i32) -> i32 {
+    if a > b {
+        a
+    } else {
+        b
+    }
+}
+
+#[inline(never)]
+fn fannkuch_redux(n: i32) -> i32 {
+    let mut perm = vec::from_elem(n as uint, 0i32);
+    let mut perm1 = vec::from_fn(n as uint, |i| i as i32);
+    let mut count = vec::from_elem(n as uint, 0i32);
+    let mut max_flips_count = 0i32, perm_count = 0i32, checksum = 0i32;
+
+    let mut r = n;
+    loop {
+        unsafe {
+            while r != 1 {
+                count.unsafe_set((r-1) as uint, r);
+                r -= 1;
+            }
+
+            // XXX: Need each2_mut.
+            for vec::eachi_mut(perm) |i, perm_i| {
+                *perm_i = perm1.unsafe_get(i);
+            }
+
+            let mut flips_count: i32 = 0;
+            let mut k: i32;
+            loop {
+                k = perm.unsafe_get(0);
+                if k == 0 {
+                    break;
+                }
+
+                let k2 = (k+1) >> 1;
+                for range(0, k2) |i| {
+                    let (perm_i, perm_k_i) = {
+                        (perm.unsafe_get(i as uint),
+                            perm.unsafe_get((k-i) as uint))
+                    };
+                    perm.unsafe_set(i as uint, perm_k_i);
+                    perm.unsafe_set((k-i) as uint, perm_i);
+                }
+                flips_count += 1;
+            }
+
+            max_flips_count = max(max_flips_count, flips_count);
+            checksum += if perm_count % 2 == 0 {
+                flips_count
+            } else {
+                -flips_count
+            };
+
+            // Use incremental change to generate another permutation.
+            loop {
+                if r == n {
+                    println(checksum.to_str());
+                    return max_flips_count;
+                }
+
+                let perm0 = perm1[0];
+                let mut i: i32 = 0;
+                while i < r {
+                    let j = i + 1;
+                    let perm1_j = { perm1.unsafe_get(j as uint) };
+                    perm1.unsafe_set(i as uint, perm1_j);
+                    i = j;
+                }
+                perm1.unsafe_set(r as uint, perm0);
+
+                let count_r = { count.unsafe_get(r as uint) };
+                count.unsafe_set(r as uint, count_r - 1);
+                if count.unsafe_get(r as uint) > 0 {
+                    break;
+                }
+                r += 1;
+            }
+
+            perm_count += 1;
+        }
+    }
+}
+
+#[fixed_stack_segment]
+fn main() {
+    let n: i32 = FromStr::from_str(os::args()[1]).get();
+    println(fmt!("Pfannkuchen(%d) = %d", n as int, fannkuch_redux(n) as int));
+}
+
diff --git a/src/test/bench/shootout-fannkuchredux.rs b/src/test/bench/shootout-fannkuchredux.rs
deleted file mode 100644
index 675151cf6c9..00000000000
--- a/src/test/bench/shootout-fannkuchredux.rs
+++ /dev/null
@@ -1,81 +0,0 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-// Based on Isaac Gouy's fannkuchredux.csharp
-extern mod std;
-
-fn fannkuch(n: int) -> int {
-    fn perm1init(i: uint) -> int { return i as int; }
-
-    let mut perm = vec::from_elem(n as uint, 0);
-    let mut perm1 = vec::from_fn(n as uint, |i| perm1init(i));
-    let mut count = vec::from_elem(n as uint, 0);
-    let mut f = 0;
-    let mut i = 0;
-    let mut k = 0;
-    let mut r = 0;
-    let mut flips = 0;
-    let mut nperm = 0;
-    let mut 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 {
-                let 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
-
-        let mut go = true;
-        while go {
-            if r == n {
-                io::println(fmt!("%d", checksum));
-                return flips;
-            }
-            let p0 = perm1[0];
-            i = 0;
-            while i < r { let 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;
-    }
-    return flips;
-}
-
-fn main() {
-    let args = os::args();
-    let args = if os::getenv(~"RUST_BENCH").is_some() {
-        ~[~"", ~"10"]
-    } else if args.len() <= 1u {
-        ~[~"", ~"8"]
-    } else {
-        args
-    };
-
-    let n = int::from_str(args[1]).get();
-    io::println(fmt!("Pfannkuchen(%d) = %d", n, fannkuch(n)));
-}
diff --git a/src/test/bench/shootout-fasta-redux.rs b/src/test/bench/shootout-fasta-redux.rs
new file mode 100644
index 00000000000..5cb04fcd27a
--- /dev/null
+++ b/src/test/bench/shootout-fasta-redux.rs
@@ -0,0 +1,204 @@
+use core::cast::transmute;
+use core::from_str::FromStr;
+use core::libc::{FILE, STDOUT_FILENO, c_int, fdopen, fputc, fputs, fwrite};
+use core::uint::{min, range};
+use core::vec::bytes::copy_memory;
+
+static LINE_LEN: uint = 60;
+static LOOKUP_SIZE: uint = 4 * 1024;
+static LOOKUP_SCALE: f32 = (LOOKUP_SIZE - 1) as f32;
+
+// Random number generator constants
+static IM: u32 = 139968;
+static IA: u32 = 3877;
+static IC: u32 = 29573;
+
+static ALU: &'static str = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTG\
+                            GGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGA\
+                            GACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAA\
+                            AATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAAT\
+                            CCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAAC\
+                            CCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTG\
+                            CACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA";
+
+static NULL_AMINO_ACID: AminoAcid = AminoAcid { c: ' ' as u8, p: 0.0 };
+
+static MESSAGE_1: &'static str = ">ONE Homo sapiens alu\n";
+static MESSAGE_2: &'static str = ">TWO IUB ambiguity codes\n";
+static MESSAGE_3: &'static str = ">THREE Homo sapiens frequency\n";
+
+static IUB: [AminoAcid, ..15] = [
+    AminoAcid { c: 'a' as u8, p: 0.27 },
+    AminoAcid { c: 'c' as u8, p: 0.12 },
+    AminoAcid { c: 'g' as u8, p: 0.12 },
+    AminoAcid { c: 't' as u8, p: 0.27 },
+    AminoAcid { c: 'B' as u8, p: 0.02 },
+    AminoAcid { c: 'D' as u8, p: 0.02 },
+    AminoAcid { c: 'H' as u8, p: 0.02 },
+    AminoAcid { c: 'K' as u8, p: 0.02 },
+    AminoAcid { c: 'M' as u8, p: 0.02 },
+    AminoAcid { c: 'N' as u8, p: 0.02 },
+    AminoAcid { c: 'R' as u8, p: 0.02 },
+    AminoAcid { c: 'S' as u8, p: 0.02 },
+    AminoAcid { c: 'V' as u8, p: 0.02 },
+    AminoAcid { c: 'W' as u8, p: 0.02 },
+    AminoAcid { c: 'Y' as u8, p: 0.02 },
+];
+
+static HOMO_SAPIENS: [AminoAcid, ..4] = [
+    AminoAcid { c: 'a' as u8, p: 0.3029549426680 },
+    AminoAcid { c: 'c' as u8, p: 0.1979883004921 },
+    AminoAcid { c: 'g' as u8, p: 0.1975473066391 },
+    AminoAcid { c: 't' as u8, p: 0.3015094502008 },
+];
+
+// XXX: Use map().
+fn sum_and_scale(a: &'static [AminoAcid]) -> ~[AminoAcid] {
+    let mut result = ~[];
+    let mut p = 0f32;
+    for a.each |a_i| {
+        let mut a_i = *a_i;
+        p += a_i.p;
+        a_i.p = p * LOOKUP_SCALE;
+        result.push(a_i);
+    }
+    result[result.len() - 1].p = LOOKUP_SCALE;
+    result
+}
+
+struct AminoAcid {
+    c: u8,
+    p: f32,
+}
+
+struct RepeatFasta {
+    alu: &'static str,
+    stdout: *FILE,
+}
+
+impl RepeatFasta {
+    fn new(stdout: *FILE, alu: &'static str) -> RepeatFasta {
+        RepeatFasta {
+            alu: alu,
+            stdout: stdout,
+        }
+    }
+
+    fn make(&mut self, n: uint) {
+        unsafe {
+            let stdout = self.stdout;
+            let alu_len = self.alu.len();
+            let mut buf = vec::from_elem(alu_len + LINE_LEN, 0u8);
+            let alu: &[u8] = str::byte_slice_no_callback(self.alu);
+
+            copy_memory(buf, alu, alu_len);
+            copy_memory(vec::mut_slice(buf, alu_len, buf.len()),
+                        alu,
+                        LINE_LEN);
+
+            let mut pos = 0, bytes, n = n;
+            while n > 0 {
+                bytes = min(LINE_LEN, n);
+                fwrite(transmute(&buf[pos]), bytes as u64, 1, stdout);
+                fputc('\n' as c_int, stdout);
+                pos += bytes;
+                if pos > alu_len {
+                    pos -= alu_len;
+                }
+                n -= bytes;
+            }
+        }
+    }
+}
+
+struct RandomFasta {
+    seed: u32,
+    stdout: *FILE,
+    lookup: [AminoAcid, ..LOOKUP_SIZE],
+}
+
+impl RandomFasta {
+    fn new(stdout: *FILE, a: &[AminoAcid]) -> RandomFasta {
+        RandomFasta {
+            seed: 42,
+            stdout: stdout,
+            lookup: RandomFasta::make_lookup(a),
+        }
+    }
+
+    fn make_lookup(a: &[AminoAcid]) -> [AminoAcid, ..LOOKUP_SIZE] {
+        let mut lookup = [ NULL_AMINO_ACID, ..LOOKUP_SIZE ];
+        let mut j = 0;
+        for vec::eachi_mut(lookup) |i, slot| {
+            while a[j].p < (i as f32) {
+                j += 1;
+            }
+            *slot = a[j];
+        }
+        lookup
+    }
+
+    fn rng(&mut self, max: f32) -> f32 {
+        self.seed = (self.seed * IA + IC) % IM;
+        max * (self.seed as f32) / (IM as f32)
+    }
+
+    fn nextc(&mut self) -> u8 {
+        let r = self.rng(1.0);
+        for self.lookup.each |a| {
+            if a.p >= r {
+                return a.c;
+            }
+        }
+        0
+    }
+
+    fn make(&mut self, n: uint) {
+        unsafe {
+            let lines = n / LINE_LEN, chars_left = n % LINE_LEN;
+            let mut buf = [0, ..LINE_LEN + 1];
+
+            for lines.times {
+                for range(0, LINE_LEN) |i| {
+                    buf[i] = self.nextc();
+                }
+                buf[LINE_LEN] = '\n' as u8;
+                fwrite(transmute(&buf[0]),
+                       LINE_LEN as u64 + 1,
+                       1,
+                       self.stdout);
+            }
+            for range(0, chars_left) |i| {
+                buf[i] = self.nextc();
+            }
+            fwrite(transmute(&buf[0]), chars_left as u64, 1, self.stdout);
+        }
+    }
+}
+
+#[fixed_stack_segment]
+fn main() {
+    let n: uint = FromStr::from_str(os::args()[1]).get();
+
+    unsafe {
+        let mode = "w";
+        let stdout = fdopen(STDOUT_FILENO as c_int, transmute(&mode[0]));
+
+        fputs(transmute(&MESSAGE_1[0]), stdout);
+        let mut repeat = RepeatFasta::new(stdout, ALU);
+        repeat.make(n * 2);
+
+        fputs(transmute(&MESSAGE_2[0]), stdout);
+        let iub = sum_and_scale(IUB);
+        let mut random = RandomFasta::new(stdout, iub);
+        random.make(n * 3);
+
+        fputs(transmute(&MESSAGE_3[0]), stdout);
+        let homo_sapiens = sum_and_scale(HOMO_SAPIENS);
+        random.lookup = RandomFasta::make_lookup(homo_sapiens);
+        random.make(n * 5);
+
+        fputc('\n' as c_int, stdout);
+    }
+}
+