binary-trees Haskell GHC #6 program
source code
--
-- The Computer Language Benchmarks Game
-- http://benchmarksgame.alioth.debian.org/
--
-- Contributed by Don Stewart
-- Basic parallelization by Roman Kashitsyn
-- Tail call optimizations by Izaak Weiss
--
import System.Environment
import Data.Bits
import Text.Printf
import Control.Parallel.Strategies
--
-- 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 = check (make stretchN)
io "stretch tree" stretchN c
-- allocate a long lived tree
let !long = make 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 long)
-- generate many trees
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 lots of trees
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
-- build a tree
make :: Int -> Tree
make d = make' d d
-- This function has an extra argument to suppress the
-- Common Sub-expression Elimination optimization
make' :: Int -> Int -> Tree
make' _ 0 = Node Nil Nil
make' !n d = Node (make' (n - 1) (d - 1)) (make' (n + 1) (d - 1))
notes, command-line, and program output
NOTES:
64-bit Ubuntu quad core
The Glorious Glasgow Haskell Compilation System, version 8.4.1
Fri, 23 Mar 2018 19:58:05 GMT
MAKE:
mv binarytrees.ghc-6.ghc binarytrees.ghc-6.hs
/opt/src/ghc-8.4.1/bin/ghc --make -fllvm -O2 -XBangPatterns -threaded -rtsopts -funbox-strict-fields binarytrees.ghc-6.hs -o binarytrees.ghc-6.ghc_run
[1 of 1] Compiling Main ( binarytrees.ghc-6.hs, binarytrees.ghc-6.o )
binarytrees.ghc-6.hs:40:51: error:
Variable not in scope:
evalTuple3
:: Strategy a0 -> Strategy a1 -> t0 -> Strategy (Int, Int, Int)
|
40 | let vs = (depth minN maxN) `using` (parList $ evalTuple3 r0 r0 rseq)
| ^^^^^^^^^^
binarytrees.ghc-6.hs:40:68: error:
• Variable not in scope: rseq
• Perhaps you meant ‘seq’ (imported from Prelude)
|
40 | let vs = (depth minN maxN) `using` (parList $ evalTuple3 r0 r0 rseq)
| ^^^^
/home/dunham/benchmarksgame/nanobench/makefiles/u64q.programs.Makefile:340: recipe for target 'binarytrees.ghc-6.ghc_run' failed
make: [binarytrees.ghc-6.ghc_run] Error 1 (ignored)
rm binarytrees.ghc-6.hs
0.35s to complete and log all make actions
COMMAND LINE:
./binarytrees.ghc-6.ghc_run +RTS -N4 -K128M -H -RTS 7
MAKE ERROR