src/test/bench/shootout-binarytrees.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(rustc_private, core, step_by)]
  42
  43 extern crate arena;
  44
  45 use std::thread;
  46 use arena::TypedArena;
  47
  48 struct Tree<'a> {
  49     l: Option<&'a Tree<'a>>,
  50     r: Option<&'a Tree<'a>>,
  51     i: i32
  52 }
  53
  54 fn item_check(t: &Option<&Tree>) -> i32 {
  55     match *t {
  56         None => 0,
  57         Some(&Tree { ref l, ref r, i }) => i + item_check(l) - item_check(r)
  58     }
  59 }
  60
  61 fn bottom_up_tree<'r>(arena: &'r TypedArena<Tree<'r>>, item: i32, depth: i32)
  62                   -> Option<&'r Tree<'r>> {
  63     if depth > 0 {
  64         let t: &Tree<'r> = arena.alloc(Tree {
  65             l: bottom_up_tree(arena, 2 * item - 1, depth - 1),
  66             r: bottom_up_tree(arena, 2 * item, depth - 1),
  67             i: item
  68         });
  69         Some(t)
  70     } else {
  71         None
  72     }
  73 }
  74
  75 fn inner(depth: i32, iterations: i32) -> String {
  76     let mut chk = 0;
  77     for i in 1 .. iterations + 1 {
  78         let arena = TypedArena::new();
  79         let a = bottom_up_tree(&arena, i, depth);
  80         let b = bottom_up_tree(&arena, -i, depth);
  81         chk += item_check(&a) + item_check(&b);
  82     }
  83     format!("{}\t trees of depth {}\t check: {}",
  84             iterations * 2, depth, chk)
  85 }
  86
  87 fn main() {
  88     let mut args = std::env::args();
  89     let n = if std::env::var_os("RUST_BENCH").is_some() {
  90         17
  91     } else if args.len() <= 1 {
  92         8
  93     } else {
  94         args.nth(1).unwrap().parse().unwrap()
  95     };
  96     let min_depth = 4;
  97     let max_depth = if min_depth + 2 > n {min_depth + 2} else {n};
  98
  99     {
 100         let arena = TypedArena::new();
 101         let depth = max_depth + 1;
 102         let tree = bottom_up_tree(&arena, 0, depth);
 103
 104         println!("stretch tree of depth {}\t check: {}",
 105                  depth, item_check(&tree));
 106     }
 107
 108     let long_lived_arena = TypedArena::new();
 109     let long_lived_tree = bottom_up_tree(&long_lived_arena, 0, max_depth);
 110
 111     let messages = (min_depth..max_depth + 1).step_by(2).map(|depth| {
 112         let iterations = 2i32.pow((max_depth - depth + min_depth) as u32);
 113         thread::spawn(move || inner(depth, iterations))
 114     }).collect::<Vec<_>>();
 115
 116     for message in messages {
 117         println!("{}", message.join().unwrap());
 118     }
 119
 120     println!("long lived tree of depth {}\t check: {}",
 121              max_depth, item_check(&long_lived_tree));
 122 }