Ticket #3061: A.hs

File A.hs, 2.3 KB (added by dons, 5 years ago)

A parallel binary trees program

Line 
1{-# OPTIONS -funbox-strict-fields #-}
2{-# LANGUAGE BangPatterns #-}
3--
4-- The Computer Language Benchmarks Game
5-- http://shootout.alioth.debian.org/
6--
7-- Contributed by Don Stewart
8-- Modified by Stephen Blackheath to parallelize (a very tiny tweak)
9--
10-- Compile with:
11--
12-- >    ghc -O2 -fasm -threaded --make
13--
14-- Run with:
15--
16-- >    ./A +RTS -N4 -H300M -RTS 20
17--
18-- Where '4' is the number of cores. and "set your -H value high (3 or
19-- more times the maximum residency)", as per GHC User's Guide:
20--
21--  <http://haskell.org/ghc/docs/6.10.1/html/users_guide/runtime-control.html#rts-options-gc>
22--
23-- -H "provides a “suggested heap size” for the garbage collector. The
24-- garbage collector will use about this much memory until the program
25-- residency grows and the heap size needs to be expanded to retain
26-- reasonable performance."
27--
28
29import System
30import Data.Bits
31import Text.Printf
32import Control.Parallel.Strategies
33
34--
35-- an artificially strict tree.
36--
37-- normally you would ensure the branches are lazy, but this benchmark
38-- requires strict allocation.
39--
40data Tree = Nil | Node !Int !Tree !Tree
41
42minN = 4
43
44io s n t = printf "%s of depth %d\t check: %d\n" s n t
45
46main = do
47    n <- getArgs >>= readIO . head
48    let maxN     = max (minN + 2) n
49        stretchN = maxN + 1
50
51    -- stretch memory tree
52    let c = check (make 0 stretchN)
53    io "stretch tree" stretchN c
54
55    -- allocate a long lived tree
56    let !long    = make 0 maxN
57
58    -- allocate, walk, and deallocate many bottom-up binary trees
59    let vs = parMap rnf id $ depth minN maxN
60    mapM_ (\((m,d,i)) -> io (show m ++ "\t trees") d i) vs
61
62    -- confirm the the long-lived binary tree still exists
63    io "long lived tree" maxN (check long)
64
65-- generate many trees
66depth :: Int -> Int -> [(Int,Int,Int)]
67depth d m
68    | d <= m    = (2*n,d,sumT d n 0) : depth (d+2) m
69    | otherwise = []
70  where n = 1 `shiftL` (m - d + minN)
71
72-- allocate and check lots of trees
73sumT :: Int -> Int -> Int -> Int
74sumT d 0 t = t
75sumT  d i t = sumT d (i-1) (t + a + b)
76  where a = check (make i    d)
77        b = check (make (-i) d)
78
79-- traverse the tree, counting up the nodes
80check :: Tree -> Int
81check Nil          = 0
82check (Node i l r) = i + check l - check r
83
84-- build a tree
85make :: Int -> Int -> Tree
86make i 0 = Node i Nil Nil
87make i d = Node i (make (i2-1) d2) (make i2 d2)
88  where i2 = 2*i; d2 = d-1
89