The Computer Language
Benchmarks Game

binary-trees Haskell GHC #2 program

source code

--
-- The Computer Language Benchmarks Game
-- http://benchmarksgame.alioth.debian.org/
--
-- Contributed by Daniel Smith
--

import Data.Foldable (for_)
import Data.Monoid ((<>))
import System.Environment (getArgs)

main :: IO ()
main = do
    n <- read . head <$> getArgs

    let stretchN = n + 1
        stretchT = make stretchN
    putStrLn . makeOutput "stretch tree" stretchN $ check stretchT
    stretchT `seq` pure ()

    let longT = make n
        longC = check longT
    longC `seq` pure ()

    for_ [4, 6 .. n] $ \d -> do
        let c = 16 * 2 ^ (n - d)
        putStrLn . makeOutput (show c <> "\t trees") d $ sumT c d

    longT `seq` pure ()
    putStrLn $ makeOutput "long lived tree" n longC

makeOutput :: String -> Int -> Int -> String
makeOutput p n c = p <> " of depth " <> show n <> "\t check: " <> show c

data Tree = Nil | Node Tree Tree

sumT :: Int -> Int -> Int
sumT = go 0
  where
    go s 0 _ = s
    go s c d = s' `seq` t `seq` go s' (c - 1) d
      where
        t = make d
        s' = s + check t

check :: Tree -> Int
check Nil = 0
check (Node l r) = 1 + check l + check r

make :: Int -> Tree
make 0 = Node Nil Nil
make n = Node (make $ n - 1) (make $ n - 1)
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
The Glorious Glasgow Haskell Compilation System, version 8.2.1


Mon, 24 Jul 2017 18:03:43 GMT

MAKE:
mv binarytrees.ghc-2.ghc binarytrees.ghc-2.hs
/usr/local/src/ghc-8.2.1/bin/ghc --make -fllvm -O2 -XBangPatterns -threaded -rtsopts -funbox-strict-fields binarytrees.ghc-2.hs -o binarytrees.ghc-2.ghc_run
[1 of 1] Compiling Main             ( binarytrees.ghc-2.hs, binarytrees.ghc-2.o )
You are using an unsupported version of LLVM!
Currently only 3.9 is supported.
We will try though...
Linking binarytrees.ghc-2.ghc_run ...
rm binarytrees.ghc-2.hs

1.60s to complete and log all make actions

COMMAND LINE:
./binarytrees.ghc-2.ghc_run +RTS -N4 -K128M -H -RTS 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303