8258c71c2bab91e98b9e9e06fc9a80082ebe662a
[nofib.git] / shootout / binary-trees / Main.hs
1 --
2 -- The Computer Language Benchmarks Game
3 -- http://benchmarksgame.alioth.debian.org/
4 --
5 -- Contributed by Don Stewart
6 -- Parallelized by Louis Wasserman
7
8 import System.Environment
9 import Control.Monad
10 import System.Mem
11 import Data.Bits
12 import Text.Printf
13 import GHC.Conc
14
15 --
16 -- an artificially strict tree.
17 --
18 -- normally you would ensure the branches are lazy, but this benchmark
19 -- requires strict allocation.
20 --
21 data Tree = Nil | Node !Int !Tree !Tree
22
23 minN = 4
24
25 io s n t = printf "%s of depth %d\t check: %d\n" s n t
26
27 main = do
28 n <- getArgs >>= readIO . head
29 let maxN = max (minN + 2) n
30 stretchN = maxN + 1
31 -- stretch memory tree
32 let c = {-# SCC "stretch" #-} check (make 0 stretchN)
33 io "stretch tree" stretchN c
34
35 -- allocate a long lived tree
36 let !long = make 0 maxN
37
38 -- allocate, walk, and deallocate many bottom-up binary trees
39 let vs = depth minN maxN
40 mapM_ (\((m,d,i)) -> io (show m ++ "\t trees") d i) vs
41
42 -- confirm the the long-lived binary tree still exists
43 io "long lived tree" maxN (check long)
44
45 -- generate many trees
46 depth :: Int -> Int -> [(Int,Int,Int)]
47 depth d m
48 | d <= m = let
49 s = sumT d n 0
50 rest = depth (d+2) m
51 in s `par` ((2*n,d,s) : rest)
52 | otherwise = []
53 where n = bit (m - d + minN)
54
55 -- allocate and check lots of trees
56 sumT :: Int -> Int -> Int -> Int
57 sumT d 0 t = t
58 sumT d i t = a `par` b `par` sumT d (i-1) ans
59 where a = check (make i d)
60 b = check (make (-i) d)
61 ans = a + b + t
62
63 check = check' True 0
64
65 -- traverse the tree, counting up the nodes
66 check' :: Bool -> Int -> Tree -> Int
67 check' !b !z Nil = z
68 check' b z (Node i l r) = check' (not b) (check' b (if b then z+i else z-i) l) r
69
70 -- build a tree
71 make :: Int -> Int -> Tree
72 make i 0 = Node i Nil Nil
73 make i d = Node i (make (i2-1) d2) (make i2 d2)
74 where i2 = 2*i; d2 = d-1