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 sync;
  12 extern crate arena;
  13
  14 use std::iter::range_step;
  15 use sync::Future;
  16 use arena::TypedArena;
  17
  18 enum Tree<'a> {
  19     Nil,
  20     Node(&'a Tree<'a>, &'a Tree<'a>, int)
  21 }
  22
  23 fn item_check(t: &Tree) -> int {
  24     match *t {
  25         Nil => 0,
  26         Node(l, r, i) => i + item_check(l) - item_check(r)
  27     }
  28 }
  29
  30 fn bottom_up_tree<'r>(arena: &'r TypedArena<Tree<'r>>, item: int, depth: int)
  31                   -> &'r Tree<'r> {
  32     if depth > 0 {
  33         arena.alloc(Node(bottom_up_tree(arena, 2 * item - 1, depth - 1),
  34                          bottom_up_tree(arena, 2 * item, depth - 1),
  35                          item))
  36     } else {
  37         arena.alloc(Nil)
  38     }
  39 }
  40
  41 fn main() {
  42     let args = std::os::args();
  43     let args = args.as_slice();
  44     let n = if std::os::getenv("RUST_BENCH").is_some() {
  45         17
  46     } else if args.len() <= 1u {
  47         8
  48     } else {
  49         from_str(args[1]).unwrap()
  50     };
  51     let min_depth = 4;
  52     let max_depth = if min_depth + 2 > n {min_depth + 2} else {n};
  53
  54     {
  55         let arena = TypedArena::new();
  56         let depth = max_depth + 1;
  57         let tree = bottom_up_tree(&arena, 0, depth);
  58
  59         println!("stretch tree of depth {}\t check: {}",
  60                  depth, item_check(tree));
  61     }
  62
  63     let long_lived_arena = TypedArena::new();
  64     let long_lived_tree = bottom_up_tree(&long_lived_arena, 0, max_depth);
  65
  66     let mut messages = range_step(min_depth, max_depth + 1, 2).map(|depth| {
  67             use std::num::pow;
  68             let iterations = pow(2, (max_depth - depth + min_depth) as uint);
  69             Future::spawn(proc() {
  70                 let mut chk = 0;
  71                 for i in range(1, iterations + 1) {
  72                     let arena = TypedArena::new();
  73                     let a = bottom_up_tree(&arena, i, depth);
  74                     let b = bottom_up_tree(&arena, -i, depth);
  75                     chk += item_check(a) + item_check(b);
  76                 }
  77                 format!("{}\t trees of depth {}\t check: {}",
  78                         iterations * 2, depth, chk)
  79             })
  80         }).collect::<Vec<Future<~str>>>();
  81
  82     for message in messages.mut_iter() {
  83         println!("{}", *message.get_ref());
  84     }
  85
  86     println!("long lived tree of depth {}\t check: {}",
  87              max_depth, item_check(long_lived_tree));
  88 }