How to properly calculate sums in parallel?

Question

Fairly new Haskell user here, I'm trying to find the sum of integers 1 to n using threads. I'm aware there are formulas to do this, but I want to play around with threads so I'm more comfortable with optimizing. I'm using GHC version 8.6.5 to compile with -O2 and, for the parallel one, -threaded.

Single-core code:

main = do
  putStrLn "Running: "
  let n = 10^9
  let a = sum [1..n `rem` 4]
  let b = sum [1 + n `rem` 4..n `rem` 2]
  let c = sum [1 + n `rem` 2..3 * n `rem` 4]
  let d = sum [1 + 3 * n `rem` 4..n]
  let total = (d + c + b + a)
  putStrLn $ "The sum is " ++ (show total)

Parallel code:

import Control.Parallel

main = do
  putStrLn "Running: "
  let n = 10^9
  let a = sum [1..n `rem` 4]
  let b = sum [1 + n `rem` 4..n `rem` 2]
  let c = sum [1 + n `rem` 2..3 * n `rem` 4]
  let d = sum [1 + 3 * n `rem` 4..n]
  let total = a `par` b `par` c `pseq` (d + c + b + a)
  putStrLn $ "The sum is " ++ (show total)

(Only changes are the import and let total = ...)

The single-core one takes 40.730s. Parallel one is run with -N4 and takes 38.549s. It doesn't seem that all 4 sums are running in parallel as intended, though the summary says 2 sparks were converted. What is really going on with the sums and how can I fix it?

user_7203016 · Answer

As was noted by others, you aren't actually splitting up your list evenly with rem. Your lists a, b, and c are all empty, and d is the entire list.

A fixed version:

import Control.Parallel

main = do
  putStrLn "Running: "
  let n = 10^9
      n1 = n `quot` 4
      n2 = 2*n1
      n3 = 3*n1

  let a = sum [1..n1]
      b = sum [n1+1..n2]
      c = sum [n2+1..n3]
      d = sum [n3..n]

  let total = a `par` b `par` c `pseq` (d + c + b + a)
  putStrLn $ "The sum is " ++ (show total)

performs better. I see a speed up of about two times, from 15sec for the single-threaded version to 8sec for the threaded version and +RTS -N.

However, there's a bug in your total. This sparks computations for a and b, then fully evaluates c before starting to evaluate d. The effect is that a, b, and c are run in parallel, and then d is run serially, so you only get a 2x speed-up.

If I replace total with the corrected:

let total = a `par` b `par` c `par` d `pseq` a + b + c + d

which sparks all four computations in parallel, then I see a speed-up of about 4 times to 4sec, so almost perfect parallelism on my four-core desktop.

How to properly calculate sums in parallel?

1 Answers