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

by pmoriarty • 12 years ago

57 9 12 years ago

pohl• 12 years ago

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.

EdwardCoffin• 12 years ago

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.

htor• 12 years ago

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?

anaphor• 12 years ago

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

dwenzek2• 12 years ago

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

agumonkey• 12 years ago

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 ..

jonathanhefner• 12 years ago

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...

sedachv• 12 years ago

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...

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

Related Stories