<div dir="ltr">So, I tried to use the Par monad instead of the Eval monad (only splitting the work into two parts, see below).<div><span style="line-height:1.5;font-size:13.1999998092651px">I now get (with 1 and 4 cores):</span><div><div><br></div><div><div>  TASKS: 4 (1 bound, 3 peak workers (3 total), using -N1)</div><div><br></div><div>  SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)</div><div><br></div><div>  INIT    time    0.000s  (  0.001s elapsed)</div><div>  MUT     time    0.994s  (  0.998s elapsed)</div><div>  GC      time    0.048s  (  0.051s elapsed)</div><div>  EXIT    time    0.000s  (  0.000s elapsed)</div><div>  Total   time    1.042s  (  1.050s elapsed)</div></div><div><div><br></div><div>------------</div><div><br></div><div>  TASKS: 10 (1 bound, 9 peak workers (9 total), using -N4)</div><div><br></div><div>  SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)</div><div><br></div><div>  INIT    time    0.000s  (  0.001s elapsed)</div><div>  MUT     time    1.083s  (  0.922s elapsed)</div><div>  GC      time    0.116s  (  0.038s elapsed)</div><div>  EXIT    time    0.001s  (  0.000s elapsed)</div><div>  Total   time    1.200s  (  0.961s elapsed)</div></div><div><br></div><div><br></div><div>So, some slight gain, but not a lot. Admittedly, the call to fromRational seems to take a good chunk of time.</div></div></div><div><br></div><div>Any comments?</div><div><br></div><div>Jens</div><div>---------------</div><div><div>import Control.Monad.Par hiding (parMap)</div><div>import Data.Ratio</div><div><br></div><div>pqCombine :: (Integer, Integer) -> (Integer, Integer) -> (Integer, Integer)</div><div>pqCombine (pl, ql) (pr, qr) = (pl*qr+pr, ql*qr)</div><div><br></div><div>pq :: (Integer, Integer) -> (Integer, Integer)</div><div>pq (a, b)</div><div>    | d >   5 = let m = (a+b+1) `div` 2</div><div>                    pql = pq (a, m)</div><div>                    pqr = pq (m, b)</div><div>                in pqCombine pql pqr</div><div>    | otherwise = (sum $ scanl1 (*) [b,b-1..a+1], product [a+1..b])</div><div>  where d = b - a</div><div><br></div><div>main = print . flip seq () . (\(p,q) -> fromRational (p%q)) . runPar $ do</div><div>  i <- new</div><div>  j <- new</div><div>  fork (put i (pq (0,160000)))</div><div>  fork (put j (pq (160000,320000)))</div><div>  a <- get i</div><div>  b <- get j</div><div>  return (pqCombine a b)</div></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr">On Fri, 14 Aug 2015 at 10:31 Jens Blanck <<a href="mailto:jens.blanck@gmail.com">jens.blanck@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>The following code simply computes the Euler constant by binary</div><div>splitting. I'm struggling to get any speed-up on multi-core.</div><div><br></div><div>Why do I get a fair number of fizzled?</div><div>Why don't I get any real speed-up even if it claims to run tasks in </div><div>parallel?</div><div><br></div><div>Could I have exhausted the integer arithmetic unit(s) on my chip</div><div>(i7-4790)?</div><div>How would I verify that?</div><div><br></div><div>The following is the code and typical runs on 1 and 4 cores respectively.</div><div><br></div><div>---------</div><div><br></div><div>import Control.Parallel.Strategies</div><div>import Control.DeepSeq</div><div><br></div><div>import Data.Ratio</div><div><br></div><div>divConq :: (NFData b) => (a -> b)</div><div>        -> a</div><div>        -> (a -> Bool)</div><div>        -> (b -> b -> b)</div><div>        -> (a -> Maybe (a,a))</div><div>        -> b</div><div>divConq f arg threshold conquer divide = go arg</div><div>    where</div><div>      go arg = </div><div>          case divide arg of</div><div>            Nothing -> f arg</div><div>            Just (l0,r0) -> conquer l1 r1 `using` strat</div><div>                where</div><div>                  l1 = go l0</div><div>                  r1 = go r0</div><div>                  strat x = do r l1; r r1; return x</div><div>                      where r | threshold arg = rdeepseq</div><div>                              | otherwise     = rpar</div><div><br></div><div>pqCombine :: (Integer, Integer) -> (Integer, Integer) -> (Integer, Integer)</div><div>pqCombine (pl, ql) (pr, qr) = (pl*qr+pr, ql*qr)</div><div><br></div><div>pq :: (Integer, Integer) -> (Integer, Integer)</div><div>pq (a, b)  = (\t -> (sum t, last t)) $ scanl1 (*) [b,b-1..a+1]</div><div><br></div><div>euler :: Integer -> Rational</div><div>euler n =</div><div>    let (p,q) = divConq pq</div><div>                        (0,n)</div><div>                        (\(a,b) -> b-a < 10000)</div><div>                        pqCombine</div><div>                        (\(a,b) -> if b-a > 5</div><div>                                   then let m = (a+b+1) `div` 2 in Just ((a,m), (m, b))</div><div>                                   else Nothing)</div><div>    in p%q</div><div><br></div><div>main = print $ euler 320000 `seq` ()</div><div><br></div><div>----------</div><div><br></div><div>> ./BinSplit +RTS -s -N1</div><div>()</div><div>     178,375,880 bytes allocated in the heap</div><div>       2,452,040 bytes copied during GC</div><div>       3,222,696 bytes maximum residency (7 sample(s))</div><div>         883,040 bytes maximum slop</div><div>              11 MB total memory in use (2 MB lost due to fragmentation)</div><div><br></div><div>                                     Tot time (elapsed)  Avg pause  Max pause</div><div>  Gen  0       333 colls,     0 par    0.004s   0.002s     0.0000s    0.0000s</div><div>  Gen  1         7 colls,     0 par    0.001s   0.001s     0.0001s    0.0003s</div><div><br></div><div>  TASKS: 4 (1 bound, 3 peak workers (3 total), using -N1)</div><div><br></div><div>  SPARKS: 126 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 126 fizzled)</div><div><br></div><div>  INIT    time    0.001s  (  0.000s elapsed)</div><div>  MUT     time    0.928s  (  0.936s elapsed)</div><div>  GC      time    0.005s  (  0.003s elapsed)</div><div>  EXIT    time    0.001s  (  0.000s elapsed)</div><div>  Total   time    0.935s  (  0.939s elapsed)</div><div><br></div><div>  Alloc rate    192,215,387 bytes per MUT second</div><div><br></div><div>  Productivity  99.4% of total user, 98.9% of total elapsed</div><div><br></div><div>gc_alloc_block_sync: 0</div><div>whitehole_spin: 0</div><div>gen[0].sync: 0</div><div>gen[1].sync: 0</div><div><br></div><div><br></div><div><br></div><div>> ./BinSplit +RTS -s -N4</div><div>()</div><div>     178,727,480 bytes allocated in the heap</div><div>       3,506,488 bytes copied during GC</div><div>       3,650,032 bytes maximum residency (7 sample(s))</div><div>         934,976 bytes maximum slop</div><div>              12 MB total memory in use (1 MB lost due to fragmentation)</div><div><br></div><div>                                     Tot time (elapsed)  Avg pause  Max pause</div><div>  Gen  0       141 colls,   141 par    0.009s   0.002s     0.0000s    0.0001s</div><div>  Gen  1         7 colls,     6 par    0.003s   0.001s     0.0001s    0.0001s</div><div><br></div><div>  Parallel GC work balance: 38.80% (serial 0%, perfect 100%)</div><div><br></div><div>  TASKS: 10 (1 bound, 9 peak workers (9 total), using -N4)</div><div><br></div><div>  SPARKS: 126 (12 converted, 0 overflowed, 0 dud, 0 GC'd, 114 fizzled)</div><div><br></div><div>  INIT    time    0.002s  (  0.002s elapsed)</div><div>  MUT     time    2.104s  (  0.946s elapsed)</div><div>  GC      time    0.012s  (  0.003s elapsed)</div><div>  EXIT    time    0.001s  (  0.000s elapsed)</div><div>  Total   time    2.119s  (  0.951s elapsed)</div><div><br></div><div>  Alloc rate    84,946,520 bytes per MUT second</div><div><br></div><div>  Productivity  99.3% of total user, 221.3% of total elapsed</div><div><br></div><div>gc_alloc_block_sync: 600</div><div>whitehole_spin: 0</div><div>gen[0].sync: 9</div><div>gen[1].sync: 1073</div><div><br></div></div></blockquote></div>