Opened 5 years ago

Closed 5 years ago

Last modified 4 years ago

#2868 closed bug (fixed)

`par` `pseq` does not work as expected

Reported by: hoangta Owned by: simonmar
Priority: normal Milestone: 6.12 branch
Component: Runtime System Version: 6.10.1
Keywords: par, pseq, parallel Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Difficulty: Easy (less than 1 hour)
Test Case: Blocked By:
Blocking: Related Tickets:

Description (last modified by simonmar)

The following Wombat program is from "A Tutorial on Parallel and Concurrent Programming in Haskell". It does not work as expected on my computer (Core(TM)2 Quad CPU). Only one core is used when I watch by "mpstat -P ALL 1 200". I compile and run by:

ghc --make -threaded wombat.hs
./wombat +RTS -N4

and the result is:

par sum: 119201850
par time: 20.932636 seconds.
seq sum: 119201850
seq time: 20.926783 seconds.

Please check if is is a bug.

---- wombat.hs ----
import System.Time
import Control.Parallel

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

secDiff :: ClockTime -> ClockTime -> Float
secDiff (TOD secs1 psecs1) (TOD secs2 psecs2) = 
	fromInteger (psecs2 - psecs1) / 1e12 + fromInteger (secs2 - secs1)

mkList :: Int -> [Int]
mkList n = [1..n-1]

relprime :: Int -> Int -> Bool
relprime x y = gcd x y == 1

euler :: Int -> Int
euler n = length (filter (relprime n) (mkList n))

sumEuler :: Int -> Int
sumEuler = sum . (map euler) . mkList

seqSumFibEuler:: Int -> Int -> Int
seqSumFibEuler a b = fib a + sumEuler b

parSumFibEuler a b = f `par` (e `pseq` (e+ f)) 
	where  
		f = fib a 
		e = sumEuler b

r1 = seqSumFibEuler 40 7450
r2 = parSumFibEuler 40 7450

main :: IO ()
main = 
	do 
		t0 <- getClockTime
		pseq r1 (return())
		t1 <- getClockTime
		putStrLn ("seq sum: " ++ show r1)
		putStrLn ("seq time: " ++ show (secDiff t0 t1) ++ " seconds.")
		t0 <- getClockTime
		pseq r2 (return())
		t1 <- getClockTime
		putStrLn ("par sum: " ++ show r2)
		putStrLn ("par time: " ++ show (secDiff t0 t1) ++ " seconds.")

Change History (5)

comment:1 Changed 5 years ago by simonmar

  • Difficulty set to Easy (1 hr)
  • Milestone set to 6.10.2
  • Operating System changed from Linux to Unknown/Multiple
  • Owner set to simonmar

Ok, this is a known bug but we don't have a ticket for it. Thanks for the report.

It affects programs that create just one spark - the scheduler's load-balancing algorithm isn't doing its job properly in that case.

comment:2 Changed 5 years ago by simonmar

  • Description modified (diff)

comment:3 Changed 5 years ago by simonmar

  • Milestone changed from 6.10.2 to 6.12 branch

Copy of more detailed reply I sent to ghc-users:

Your program is suffering from microbenchmarkitis, I'm afraid. There's only one spark, which tickles a bug in the scheduler in 6.10.1 and earlier (but sometimes doesn't happen due to random scheduling behaviour). Even with that fixed, the program uses fib which tickles another bug: when optimised, fib doesn't do any allocation, and GHC's scheduler relies on allocation happening at regular enough intervals.

In 6.10.1 we never get to do load-balancing in this example, because fib doesn't ever yield control to the scheduler. In HEAD, where we have work-stealing and don't rely on the scheduler for load-balancing, the load-balancing problem goes away but reveals another problem: the second thread wants to GC, but in order to GC it has to synchronise with the other running threads, but the other thread is running fib and never yields. We can fix this by allowing CPUs to GC independently (which we plan to do), but even then you could still run into the same problem because eventually a global GC will be required. If you really want to see the program running in parallel, turn off -O.


I've now fixed the scheduling bug in stable.

Wed Dec 10 14:42:35 GMT 2008  Simon Marlow <marlowsd@gmail.com>
  * Fix (part of) #2868: do load-balancing when there's only one spark

There's a similar bug in HEAD (but it happens less often), so I'm leaving the ticket open.

comment:4 Changed 5 years ago by simonmar

  • Resolution set to fixed
  • Status changed from new to closed

Fixed in HEAD too

Wed Dec 10 08:46:44 PST 2008  Simon Marlow <marlowsd@gmail.com>
  * wake up other Capabilities even when there is only one spark (see #2868)

comment:5 Changed 4 years ago by simonmar

  • Difficulty changed from Easy (1 hr) to Easy (less than 1 hour)
Note: See TracTickets for help on using tickets.