[Haskell-cafe] Re: Parallel foldl doesn't work correctly

[Maciej Piechotka]

On Sat, 2009-12-12 at 02:57 +0000, Philip Beadling wrote:
> Hi,
> 
> Can anyone put me right here.  I am trying to use a setup similar to
> parMap to spark each valuation in a list in parallel, where the
> resulting (evaluated) list is folded to produce a final single result.
> 
> Having done the obligatory google, I modified a few common examples to
> give:
> 
> pfoldl f acc xs =  foldl' f acc (xs `using` parList rwhnf)
> 
> 
> This compiles and if I monitor my CPUs it starts to use both cores, but
> after approx 10 seconds, one core drops to low rate (I'm using a 2 core
> machine).
> 
> The end result is that -N2 is actually a bit slower than -N1!
> 
> I'm guessing I haven't grasped the concept properly - although as map is
> just 'foldl (+) 0' I'm at a loss to see why this approach wouldn't work
> given it is pretty similar to parMap - could anyone point out what I'm
> missing?
> 
> If it's any use the context of the code is below.
> 
> Many thanks!
> 
> 
> Phil.

At least IMHO foldl cannot be pararalized since it have rather strong
dependencies i.e. only calculation of acc and first value of list.

If operation is associative it can be done using divide et impera
spliting list in half and operating on it pararerlly then split in half
etc.
8 stages (the same number (O n) as normally + cost of synchronization
etc).
                     1
                  +
                     2
               +
                  3
            +
               4
         +
            5
      +
         6
   +
      7
+
   8

3 operations (to be more specific O (log n)):
            1
        +
            2
    +
            3
        +
            4
+  
            5
        +
            6
    +
            7
        +
            8


Regards
PS. I don't know nor understend the pararell library. Maybe I don't
understend something but without associativity IMHO data is too
interdependent IMHO to do something.