[Haskell-cafe] cap 3: stopping thread 3 (stackoverflow)

[Brandon Moore]

----- Original Message -----

> From: Johannes Waldmann <waldmann at imn.htwk-leipzig.de>
> Sent: Tuesday, June 7, 2011 8:22 AM
> 
> Here's source and logs:
> 
> http://www.imn.htwk-leipzig.de/~waldmann/draft/skpp11/subseqsum/Subseqsum.hs
> 
> The program is meant to show an application of the "third homomorphism 
> theorem"
> approach (hom-based structural parallel programming).
> 
> My observation (for this program) is that there is little speedup,
> indeed the threadscope picture shows a peak only at the very end,
> but the eventlog contains surprising (for me) stack and heap overflows.
> 
> Would this work better with Data.Sequence instead of List?
> (Is there a really cheap way (O(1)) to split some Data.Sequence roughly in 
> half?)

You can split a Sequence in O(log n) time, or a bit cheaper near the ends.

I'd be surprised if you see any speedup with this code.
The serial algorithm is already O(n), maintaining two counters,
and with a lazily generated list it probably runs in constant memory.
length and splitAt are already O(n), make two separate traversals,
and require allocating memory for the entire list.

Even if you have an efficiently splittable data structure, the
parallel version of the code needs to keep four counts for each chunk,
and do more on each update.

Have you tried a version that splits the list into larger chunks, and
uses the serial algorithm for computing the left, right, overall, 
and maximum sums of each chunk, before summing them together?

> PS: I keep telling my students that "structural parallel programming"
> is the right thing to do, but I find it surprisingly difficult
> to exhibit clear-cut examples that support the claim
> (and work with standard ghc, so students can reproduce it).
> 
> I appreciate any comments.  - J.W.