src/test/bench/shootout-mandelbrot.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 #![feature(macro_rules)]
  42 #![feature(simd)]
  43 #![allow(experimental)]
  44
  45 // ignore-pretty very bad with line comments
  46
  47 use std::io;
  48 use std::os;
  49 use std::simd::f64x2;
  50 use std::sync::Arc;
  51 use std::thread::Thread;
  52
  53 const ITER: int = 50;
  54 const LIMIT: f64 = 2.0;
  55 const WORKERS: uint = 16;
  56
  57 #[inline(always)]
  58 fn mandelbrot<W: io::Writer>(w: uint, mut out: W) -> io::IoResult<()> {
  59     assert!(WORKERS % 2 == 0);
  60
  61     // Ensure w and h are multiples of 8.
  62     let w = (w + 7) / 8 * 8;
  63     let h = w;
  64
  65     let chunk_size = h / WORKERS;
  66
  67     // Account for remainders in workload division, e.g. 1000 / 16 = 62.5
  68     let last_chunk_size = if h % WORKERS != 0 {
  69         chunk_size + h % WORKERS
  70     } else {
  71         chunk_size
  72     };
  73
  74     // precalc values
  75     let inverse_w_doubled = 2.0 / w as f64;
  76     let inverse_h_doubled = 2.0 / h as f64;
  77     let v_inverses = f64x2(inverse_w_doubled, inverse_h_doubled);
  78     let v_consts = f64x2(1.5, 1.0);
  79
  80     // A lot of this code assumes this (so do other lang benchmarks)
  81     assert!(w == h);
  82     let mut precalc_r = Vec::with_capacity(w);
  83     let mut precalc_i = Vec::with_capacity(h);
  84
  85     let precalc_futures = range(0, WORKERS).map(|i| {
  86         Thread::spawn(move|| {
  87             let mut rs = Vec::with_capacity(w / WORKERS);
  88             let mut is = Vec::with_capacity(w / WORKERS);
  89
  90             let start = i * chunk_size;
  91             let end = if i == (WORKERS - 1) {
  92                 start + last_chunk_size
  93             } else {
  94                 (i + 1) * chunk_size
  95             };
  96
  97             // This assumes w == h
  98             for x in range(start, end) {
  99                 let xf = x as f64;
 100                 let xy = f64x2(xf, xf);
 101
 102                 let f64x2(r, i) = xy * v_inverses - v_consts;
 103                 rs.push(r);
 104                 is.push(i);
 105             }
 106
 107             (rs, is)
 108         })
 109     }).collect::<Vec<_>>();
 110
 111     for res in precalc_futures.into_iter() {
 112         let (rs, is) = res.join().ok().unwrap();
 113         precalc_r.extend(rs.into_iter());
 114         precalc_i.extend(is.into_iter());
 115     }
 116
 117     assert_eq!(precalc_r.len(), w);
 118     assert_eq!(precalc_i.len(), h);
 119
 120     let arc_init_r = Arc::new(precalc_r);
 121     let arc_init_i = Arc::new(precalc_i);
 122
 123     let data = range(0, WORKERS).map(|i| {
 124         let vec_init_r = arc_init_r.clone();
 125         let vec_init_i = arc_init_i.clone();
 126
 127         Thread::spawn(move|| {
 128             let mut res: Vec<u8> = Vec::with_capacity((chunk_size * w) / 8);
 129             let init_r_slice = vec_init_r.as_slice();
 130
 131             let start = i * chunk_size;
 132             let end = if i == (WORKERS - 1) {
 133                 start + last_chunk_size
 134             } else {
 135                 (i + 1) * chunk_size
 136             };
 137
 138             for &init_i in vec_init_i.slice(start, end).iter() {
 139                 write_line(init_i, init_r_slice, &mut res);
 140             }
 141
 142             res
 143         })
 144     }).collect::<Vec<_>>();
 145
 146     try!(writeln!(&mut out as &mut Writer, "P4\n{} {}", w, h));
 147     for res in data.into_iter() {
 148         try!(out.write(res.join().ok().unwrap().as_slice()));
 149     }
 150     out.flush()
 151 }
 152
 153 fn write_line(init_i: f64, vec_init_r: &[f64], res: &mut Vec<u8>) {
 154     let v_init_i : f64x2 = f64x2(init_i, init_i);
 155     let v_2 : f64x2 = f64x2(2.0, 2.0);
 156     const LIMIT_SQUARED: f64 = LIMIT * LIMIT;
 157
 158     for chunk_init_r in vec_init_r.chunks(8) {
 159         let mut cur_byte = 0xff;
 160         let mut i = 0;
 161
 162         while i < 8 {
 163             let v_init_r = f64x2(chunk_init_r[i], chunk_init_r[i + 1]);
 164             let mut cur_r = v_init_r;
 165             let mut cur_i = v_init_i;
 166             let mut r_sq = v_init_r * v_init_r;
 167             let mut i_sq = v_init_i * v_init_i;
 168
 169             let mut b = 0;
 170             for _ in range(0, ITER) {
 171                 let r = cur_r;
 172                 let i = cur_i;
 173
 174                 cur_i = v_2 * r * i + v_init_i;
 175                 cur_r = r_sq - i_sq + v_init_r;
 176
 177                 let f64x2(bit1, bit2) = r_sq + i_sq;
 178
 179                 if bit1 > LIMIT_SQUARED {
 180                     b |= 2;
 181                     if b == 3 { break; }
 182                 }
 183
 184                 if bit2 > LIMIT_SQUARED {
 185                     b |= 1;
 186                     if b == 3 { break; }
 187                 }
 188
 189                 r_sq = cur_r * cur_r;
 190                 i_sq = cur_i * cur_i;
 191             }
 192
 193             cur_byte = (cur_byte << 2) + b;
 194             i += 2;
 195         }
 196
 197         res.push(cur_byte^-1);
 198     }
 199 }
 200
 201 fn main() {
 202     let args = os::args();
 203     let args = args.as_slice();
 204     let res = if args.len() < 2 {
 205         println!("Test mode: do not dump the image because it's not utf8, \
 206                   which interferes with the test runner.");
 207         mandelbrot(1000, io::util::NullWriter)
 208     } else {
 209         mandelbrot(args[1].parse().unwrap(), io::stdout())
 210     };
 211     res.unwrap();
 212 }