src/test/bench/shootout-binarytrees.rs

   1 // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 extern crate arena;
  12
  13 use std::iter::range_step;
  14 use std::sync::Future;
  15 use arena::TypedArena;
  16
  17 enum Tree<'a> {
  18     Nil,
  19     Node(&'a Tree<'a>, &'a Tree<'a>, int)
  20 }
  21
  22 fn item_check(t: &Tree) -> int {
  23     match *t {
  24         Nil => 0,
  25         Node(l, r, i) => i + item_check(l) - item_check(r)
  26     }
  27 }
  28
  29 fn bottom_up_tree<'r>(arena: &'r TypedArena<Tree<'r>>, item: int, depth: int)
  30                   -> &'r Tree<'r> {
  31     if depth > 0 {
  32         arena.alloc(Node(bottom_up_tree(arena, 2 * item - 1, depth - 1),
  33                          bottom_up_tree(arena, 2 * item, depth - 1),
  34                          item))
  35     } else {
  36         arena.alloc(Nil)
  37     }
  38 }
  39
  40 fn main() {
  41     let args = std::os::args();
  42     let args = args.as_slice();
  43     let n = if std::os::getenv("RUST_BENCH").is_some() {
  44         17
  45     } else if args.len() <= 1u {
  46         8
  47     } else {
  48         from_str(args[1].as_slice()).unwrap()
  49     };
  50     let min_depth = 4;
  51     let max_depth = if min_depth + 2 > n {min_depth + 2} else {n};
  52
  53     {
  54         let arena = TypedArena::new();
  55         let depth = max_depth + 1;
  56         let tree = bottom_up_tree(&arena, 0, depth);
  57
  58         println!("stretch tree of depth {}\t check: {}",
  59                  depth, item_check(tree));
  60     }
  61
  62     let long_lived_arena = TypedArena::new();
  63     let long_lived_tree = bottom_up_tree(&long_lived_arena, 0, max_depth);
  64
  65     let mut messages = range_step(min_depth, max_depth + 1, 2).map(|depth| {
  66             use std::num::pow;
  67             let iterations = pow(2, (max_depth - depth + min_depth) as uint);
  68             Future::spawn(proc() {
  69                 let mut chk = 0;
  70                 for i in range(1, iterations + 1) {
  71                     let arena = TypedArena::new();
  72                     let a = bottom_up_tree(&arena, i, depth);
  73                     let b = bottom_up_tree(&arena, -i, depth);
  74                     chk += item_check(a) + item_check(b);
  75                 }
  76                 format!("{}\t trees of depth {}\t check: {}",
  77                         iterations * 2, depth, chk)
  78             })
  79         }).collect::<Vec<Future<String>>>();
  80
  81     for message in messages.mut_iter() {
  82         println!("{}", *message.get_ref());
  83     }
  84
  85     println!("long lived tree of depth {}\t check: {}",
  86              max_depth, item_check(long_lived_tree));
  87 }