binary-trees Haskell GHC #2 program
source code
--
-- The Computer Language Benchmarks Game
-- https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
--
-- 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 9.4.8
LLVM version 17.0.2
Thu, 07 Mar 2024 22:58:27 GMT
MAKE:
mv binarytrees.ghc-2.ghc binarytrees.ghc-2.hs
~/.ghcup/bin/ghc --make -optlo-passes='module(default<O2>)' -O2 -fno-llvm-tbaa -XBangPatterns -threaded -rtsopts -fno-cse -package ghc-compact binarytrees.ghc-2.hs -o binarytrees.ghc-2.ghc_run
Loaded package environment from /home/dunham/.ghc/x86_64-linux-9.4.8/environments/default
[1 of 2] Compiling Main ( binarytrees.ghc-2.hs, binarytrees.ghc-2.o )
[2 of 2] Linking binarytrees.ghc-2.ghc_run
rm binarytrees.ghc-2.hs
11.05s 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