binary-trees Haskell GHC #8 program

--
-- The Computer Language Benchmarks Game
-- https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
--
-- Contributed by Don Stewart
-- Basic parallelization by Roman Kashitsyn and Artem Pelenitsyn
-- Tail call optimizations by Izaak Weiss
-- Compact region optimization by Jaro Reinders
--

import System.Environment
import Data.Bits
import Text.Printf
import Control.Parallel.Strategies
import GHC.Compact

--
-- an artificially strict tree. 
--
-- normally you would ensure the branches are lazy, but this benchmark
-- requires strict allocation.
--
data Tree = Nil | Node !Tree !Tree

minN = 4

io s n t = printf "%s of depth %d\t check: %d\n" s n t

main = do
    n <- getArgs >>= readIO . head
    let maxN     = max (minN + 2) n
        stretchN = maxN + 1

    -- stretch memory tree
    let c = checkPar4 (makePar4 stretchN)
    io "stretch tree" stretchN c

    -- allocate a long lived tree (in a compact region)
    long <- compact (makePar2 maxN)

    -- allocate, walk, and deallocate many bottom-up binary trees
    let vs = (depth minN maxN) `using`
             (parList $ evalTuple3 r0 r0 rseq)
    mapM_ (\((m,d,i)) -> io (show m ++ "\t trees") d i) vs

    -- confirm the the long-lived binary tree still exists
    io "long lived tree" maxN (check (getCompact long))

-- generate trees of depth @d@, @d+1@... until @m@
depth :: Int -> Int -> [(Int, Int, Int)]
depth d m
    | d <= m    = (n, d, sumT d n 0) : depth (d+2) m
    | otherwise = []
  where n = 1 `shiftL` (m - d + minN)

-- allocate and check @i@ trees of depth @d@
sumT :: Int -> Int -> Int -> Int
sumT d 0 t = t
sumT d i t = sumT d (i-1) (t + a)
  where a = check (make d)

-- traverse the tree, counting up the nodes
check :: Tree -> Int
check t = tailCheck t 0

tailCheck :: Tree -> Int -> Int
tailCheck Nil        !a = a
tailCheck (Node l r) !a = tailCheck l $ tailCheck r $ a + 1

-- traverse and count nodes in parallel (4-threaded version)
checkPar4 :: Tree -> Int
checkPar4 (Node (Node ll lr) (Node rl rr)) = all + alr + arl + arr + 3 `using` strat where
  all = tailCheck ll 0
  alr = tailCheck lr 0
  arl = tailCheck rl 0
  arr = tailCheck rr 0
  strat v = do
    rpar all
    rpar alr
    rpar arl
    rseq arr
    return v

-- build a tree
make :: Int -> Tree
make d =
  if d < 10 then make' d else makePar2 d

make' :: Int -> Tree
make' 0 = Node Nil Nil
make' d = Node (make' (d - 1)) (make' (d - 1))

-- build a tree in parallel (4-threaded version)
makePar4 :: Int -> Tree
makePar4 d = Node (Node ll lr) (Node rl rr) `using` strat where
  !d' = d - 2
  ll = make' d'
  lr = make' d'
  rl = make' d'
  rr = make' d'
  strat v = do
    rpar ll
    rpar lr
    rpar rl
    rseq rr
    return v

-- build a tree in parallel (2-threaded version)
makePar2 :: Int -> Tree
makePar2 d = Node l r  `using` strat where
  !d' = d - 1
  l = make' d'
  r = make' d'
  strat v = do
    rpar l
    rseq r
    return v
    
    

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:57:25 GMT

MAKE:
mv binarytrees.ghc-8.ghc binarytrees.ghc-8.hs
~/.ghcup/bin/ghc --make -optlo-passes='module(default<O2>)' -O2 -fno-llvm-tbaa -XBangPatterns -threaded -rtsopts -fno-cse -package ghc-compact binarytrees.ghc-8.hs -o binarytrees.ghc-8.ghc_run
Loaded package environment from /home/dunham/.ghc/x86_64-linux-9.4.8/environments/default
[1 of 2] Compiling Main             ( binarytrees.ghc-8.hs, binarytrees.ghc-8.o )
[2 of 2] Linking binarytrees.ghc-8.ghc_run
rm binarytrees.ghc-8.hs

2.72s to complete and log all make actions

COMMAND LINE:
 ./binarytrees.ghc-8.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