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