Guy Steele on Functional Code for Parallel Execution (2009) [video] | Hacker News Reader

Guy Steele on Functional Code for Parallel Execution (2009) [video]

vimeo.com

57 pointspmoriarty9 comments

A great paper to read if you find this talk interesting is this one about data-parallel algorithms that Steele co-authored with Daniel Hillis in 1986: http://uenics.evansville.edu/~mr56/ece757/DataParallelAlgori...

This was a really interesting talk. Pretty high information density.

It makes sense to use divide-and-conquer rather than a first-rest pattern when doing parallel computations on sequences. But I'm curious if that pattern can be applied to other data structures as well and not just tree structures like the conc list?

Well nested data parallelism generally applies to hierarchical structures like trees, whereas flat data parallelism applies to things like arrays and whatnot. You might want to watch this (similar in some ways) talk by SPJ on Data Parallel Haskell http://youtu.be/NWSZ4c9yqW8

This pattern can be applied to a large set of collection representations, as long as a former collection can be divided into smaller parts which can be processed independently giving partial results to be combined into a final outcome using an associative combiner.

For instance, to compute a count of words, the former word collection can be either a conc tree in memory or a file divided in chunks or a bunch of files. In each case, the sub counts can be computed independently and reconciled into a total count.

The deep insight Guy Steele provides in his talk, is how to deal with the non trivial cases like the count of words in a file divided in chunks where words can cross chunk boundaries.

Hence, I highly recommend watching this talk. As further reading, I recommend too a post [1] that I written after having watched Guy Steele talk. [2] is a work in progress to implement the idea in OCaml.

[1] http://acidalie.free.fr/unfoldvalue/blog/map-reduce-spirit.h...

[2] https://github.com/didier-wenzek/odist

Indeed the cross-chunk recombination is quite something. We're used to clean cut boundaries and here he is going away from this rule to bring new opportunities. But I wonder how hard it is to think about, design and test such assoc. combiners ..

Yes, it may be quit hard to design such a combiner due to constraints both on the input (as the need for cross-chunk recombination), and on the output (as too early finalization preventing further combinations); with the consequence that we often have to imagine a genuine intermediate data representation of the problem.

But this complexity is mitigated by the fact that these associative combiners can be built incrementally using a reduced set of patterns, combiner compositions and transformations.

Have a look to this remarkably well written post [1] on incremental regular expressions (it appears that incremental computation is deeply related with parallel computation). It shows well, on a non-trivial example, how to build such an intermediate data representation with its associative combiner.

[1] http://jkff.info/articles/ire/

What Guy says is his big message for the talk is on the slide seen at 2:34, transcribed below:

> This Talk Is about Performance > > The bag of programming tricks that has served us so well for the last 50 years is the wrong way to think going forward and must be thrown out.

I haven't watched this talk for several years now, so my memory may be faulty.

That said, I highly recommend watching this talk. I think the most insights regarding cons v. conc lists are worth thinking about.

If you liked this talk, or perhaps liked the topic but found the pacing a bit fast, here is a friendlier-paced revision of it presented at Strange Loop 2010: http://www.infoq.com/presentations/Thinking-Parallel-Program...

Reply on news.ycombinator.com