src/test/bench/shootout-spectralnorm.rs

   1 // The Computer Language Benchmarks Game
   2 // http://benchmarksgame.alioth.debian.org/
   3 //
   4 // contributed by the Rust Project Developers
   5
   6 // Copyright (c) 2012-2014 The Rust Project Developers
   7 //
   8 // All rights reserved.
   9 //
  10 // Redistribution and use in source and binary forms, with or without
  11 // modification, are permitted provided that the following conditions
  12 // are met:
  13 //
  14 // - Redistributions of source code must retain the above copyright
  15 //   notice, this list of conditions and the following disclaimer.
  16 //
  17 // - Redistributions in binary form must reproduce the above copyright
  18 //   notice, this list of conditions and the following disclaimer in
  19 //   the documentation and/or other materials provided with the
  20 //   distribution.
  21 //
  22 // - Neither the name of "The Computer Language Benchmarks Game" nor
  23 //   the name of "The Computer Language Shootout Benchmarks" nor the
  24 //   names of its contributors may be used to endorse or promote
  25 //   products derived from this software without specific prior
  26 //   written permission.
  27 //
  28 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  31 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  32 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  33 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  34 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  35 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  37 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  38 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  39 // OF THE POSSIBILITY OF SUCH DAMAGE.
  40
  41 // no-pretty-expanded FIXME #15189
  42
  43 #![allow(non_snake_case)]
  44 #![feature(unboxed_closures, iter_arith, core_simd, scoped)]
  45
  46 use std::iter::repeat;
  47 use std::thread;
  48 use std::env;
  49 use std::simd::f64x2;
  50
  51 fn main() {
  52     let mut args = env::args();
  53     let answer = spectralnorm(if env::var_os("RUST_BENCH").is_some() {
  54         5500
  55     } else if args.len() < 2 {
  56         2000
  57     } else {
  58         args.nth(1).unwrap().parse().unwrap()
  59     });
  60     println!("{:.9}", answer);
  61 }
  62
  63 fn spectralnorm(n: usize) -> f64 {
  64     assert!(n % 2 == 0, "only even lengths are accepted");
  65     let mut u = repeat(1.0).take(n).collect::<Vec<_>>();
  66     let mut v = u.clone();
  67     let mut tmp = v.clone();
  68     for _ in 0..10 {
  69         mult_AtAv(&u, &mut v, &mut tmp);
  70         mult_AtAv(&v, &mut u, &mut tmp);
  71     }
  72     (dot(&u, &v) / dot(&v, &v)).sqrt()
  73 }
  74
  75 fn mult_AtAv(v: &[f64], out: &mut [f64], tmp: &mut [f64]) {
  76     mult_Av(v, tmp);
  77     mult_Atv(tmp, out);
  78 }
  79
  80 fn mult_Av(v: &[f64], out: &mut [f64]) {
  81     parallel(out, |start, out| mult(v, out, start, |i, j| A(i, j)));
  82 }
  83
  84 fn mult_Atv(v: &[f64], out: &mut [f64]) {
  85     parallel(out, |start, out| mult(v, out, start, |i, j| A(j, i)));
  86 }
  87
  88 fn mult<F>(v: &[f64], out: &mut [f64], start: usize, a: F)
  89            where F: Fn(usize, usize) -> f64 {
  90     for (i, slot) in out.iter_mut().enumerate().map(|(i, s)| (i + start, s)) {
  91         let mut sum = f64x2(0.0, 0.0);
  92         for (j, chunk) in v.chunks(2).enumerate().map(|(j, s)| (2 * j, s)) {
  93             let top = f64x2(chunk[0], chunk[1]);
  94             let bot = f64x2(a(i, j), a(i, j + 1));
  95             sum += top / bot;
  96         }
  97         let f64x2(a, b) = sum;
  98         *slot = a + b;
  99     }
 100 }
 101
 102 fn A(i: usize, j: usize) -> f64 {
 103     ((i + j) * (i + j + 1) / 2 + i + 1) as f64
 104 }
 105
 106 fn dot(v: &[f64], u: &[f64]) -> f64 {
 107     v.iter().zip(u).map(|(a, b)| *a * *b).sum()
 108 }
 109
 110
 111 // Executes a closure in parallel over the given mutable slice. The closure `f`
 112 // is run in parallel and yielded the starting index within `v` as well as a
 113 // sub-slice of `v`.
 114 fn parallel<'a,T, F>(v: &mut [T], ref f: F)
 115                   where T: Send + Sync + 'a,
 116                         F: Fn(usize, &mut [T]) + Sync + 'a {
 117     // FIXME: pick a more appropriate parallel factor
 118     let parallelism = 4;
 119     let size = v.len() / parallelism + 1;
 120     v.chunks_mut(size).enumerate().map(|(i, chunk)| {
 121         thread::scoped(move|| {
 122             f(i * size, chunk)
 123         })
 124     }).collect::<Vec<_>>();
 125 }