Guy Steele's 'Four solutions to a Trivial Problem' talk about sequential vs. parallel code


#1

I recently came across the ‘Four solutions to a Trivial Problem’ talk by Guy L. Steele.

It talks about different styles of programming to solve a problem, with the important conclusion mostly being that when you write a high-level ‘divide and conquer’ approach to solve a problem, the compiler can decide to optimize it for sequential or parallel computing (or a blend thereof).

A simple example would be to say ‘I want to sum this list of numbers’, without specifying how, meaning that the compiler can decide whether to perform a sequential accumulation (linear time, constant space) or a parallel tree-combining approach (logarithmic time, linear space).

In the talk, Fortress is mostly used as the language to present the concepts in. However, I do think that many of the concepts can easily be transferred to Rust.

So I am wondering: Are there already approaches/libraries existing in Rust where concepts such as the Monoid Cached Tree and the parallel prefix/parallel suffix operations that work in this way?


#2

Before asking that you have to write good benchmarks that show that his solutions actually improve the run-time of Rust code compared to reasonable Rayon-based solutions of the same problems.


#3

Not at all, because my question is more general. I am also not trying to prove that one solution is better than another. I’m just wondering if these concepts have been used by any Rust libraries already.

I have the feeling that Rayon’s parallel iterators like map() and sum() might very much be what Mr. Steele was going for in his talk. (See for instance the part where he talks about the ‘concise solution’)


#4

The talk seems more higher level than Rayon. In terms of having the compiler make the choice of parallelism. To do similar in Rust you would possibly try meta-programming and creating functions/macros that use some link in build.rs. Or even a compiler extension.

It’s a nice talk (acknowledging that there are trade-offs.) It fails to cover going even higher though. AI(Problem) -> Solver