Opened 6 years ago

Last modified 20 months ago

#5672 new feature request

parBufferWHNF could be less subtle

Reported by: duncan Owned by: duncan
Priority: normal Milestone:
Component: Core Libraries Version: 7.2.1
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

I would suggest modifying parBufferWHNF as follows, with the {- x seq -} actually included.

parBufferWHNF :: Int -> Strategy [a]
parBufferWHNF n0 xs0 = return (ret xs0 (start n0 xs0))
  where -- ret :: [a] -> [a] -> [a]
    ret (x:xs) (y:ys) = y `par` (x : ({-x `seq`-} ret xs ys))
    ret xs     _      = xs

    -- start :: Int -> [a] -> [a]
    start 0   ys     = ys
    start !_n []     = []
    start !n  (y:ys) = y `par` start (n-1) ys

The point of the extra x seq is so that consumers that do not evaluate the list element before evaluating the next cons cell don't get such surprising loss of parallelism. For example non-strict left folds like sum will rush to the end of the list spine without evaluating the list elements, and then evaluate the elements later. That does not work well with the parBufferWHNF strategy. Adding the extra seq fixes it. Note that in this case I think seq or pseq would work.

Change History (10)

comment:1 Changed 6 years ago by igloo

difficulty: Unknown
Milestone: 7.6.1
Status: newpatch

Does that make more sense than

y `par` (x `seq` (x : ret xs ys))

?

comment:2 Changed 6 years ago by simonmar

The fix is slightly odd, because it makes parBufferWHNF strict in the list elements. We'd have to update the generic parBuffer to be strict in the list elements too, for consistency.

Arguably further sparks should be created by demand for the elements, not the spine. Wouldn't this work?

    ret (x:xs) (y:ys) = (y `par` x) : ret xs ys

comment:3 Changed 6 years ago by igloo

Status: patchnew

comment:4 Changed 6 years ago by igloo

Owner: set to duncan

Duncan, do you think you would be able to lead the way to working out what the best fix for this ticket is, please?

comment:5 Changed 5 years ago by igloo

Milestone: 7.6.17.6.2

comment:6 Changed 3 years ago by thoughtpolice

Milestone: 7.6.27.10.1

Moving to 7.10.1.

comment:7 Changed 3 years ago by thoughtpolice

Component: libraries (other)Core Libraries

Moving over to new owning component 'Core Libraries'.

comment:8 Changed 3 years ago by thoughtpolice

Milestone: 7.10.17.12.1

Moving to 7.12.1 milestone; if you feel this is an error and should be addressed sooner, please move it back to the 7.10.1 milestone.

comment:9 Changed 2 years ago by thoughtpolice

Milestone: 7.12.18.0.1

Milestone renamed

comment:10 Changed 20 months ago by thomie

Milestone: 8.0.1
Note: See TracTickets for help on using tickets.