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 extern crate arena;
  42
  43 use std::iter::range_step;
  44 use std::thread::{Thread, JoinGuard};
  45 use arena::TypedArena;
  46
  47 struct Tree<'a> {
  48     l: Option<&'a Tree<'a>>,
  49     r: Option<&'a Tree<'a>>,
  50     i: i32
  51 }
  52
  53 fn item_check(t: &Option<&Tree>) -> i32 {
  54     match *t {
  55         None => 0,
  56         Some(&Tree { ref l, ref r, i }) => i + item_check(l) - item_check(r)
  57     }
  58 }
  59
  60 fn bottom_up_tree<'r>(arena: &'r TypedArena<Tree<'r>>, item: i32, depth: i32)
  61                   -> Option<&'r Tree<'r>> {
  62     if depth > 0 {
  63         let t: &Tree<'r> = arena.alloc(Tree {
  64             l: bottom_up_tree(arena, 2 * item - 1, depth - 1),
  65             r: bottom_up_tree(arena, 2 * item, depth - 1),
  66             i: item
  67         });
  68         Some(t)
  69     } else {
  70         None
  71     }
  72 }
  73
  74 fn inner(depth: i32, iterations: i32) -> String {
  75     let mut chk = 0;
  76     for i in 1 .. iterations + 1 {
  77         let arena = TypedArena::new();
  78         let a = bottom_up_tree(&arena, i, depth);
  79         let b = bottom_up_tree(&arena, -i, depth);
  80         chk += item_check(&a) + item_check(&b);
  81     }
  82     format!("{}\t trees of depth {}\t check: {}",
  83             iterations * 2, depth, chk)
  84 }
  85
  86 fn main() {
  87     let args = std::os::args();
  88     let args = args;
  89     let n = if std::os::getenv("RUST_BENCH").is_some() {
  90         17
  91     } else if args.len() <= 1u {
  92         8
  93     } else {
  94         args[1].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 = range_step(min_depth, max_depth + 1, 2).map(|depth| {
 112         use std::num::Int;
 113         let iterations = 2.pow((max_depth - depth + min_depth) as usize);
 114         Thread::scoped(move || inner(depth, iterations))
 115     }).collect::<Vec<_>>();
 116
 117     for message in messages {
 118         println!("{}", message.join().ok().unwrap());
 119     }
 120
 121     println!("long lived tree of depth {}\t check: {}",
 122              max_depth, item_check(&long_lived_tree));
 123 }