<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>