Skip to content
Hallway
0:00 / 0:00

#guysteele#parallelism#associativity

Four Solutions to a Trivial Problem - Guy Steele Jr.

Google TechTalks

349K subscribers • 62 videos on Hallway

YouTube
  • Recommended by 6 people: 4 on Hacker News and 2 on Lobsters.
  • A classic. People kept recommending it from 2016 to 2023.
  • Presented by Guy L. Steele Jr., Software Architect

Intermediate. Assumes working knowledge.

36K views10 years ago6 recommendations

Computer scienceSystems programmingAlgorithmsConcurrency and parallelismPerformance and optimization

Guy Steele presents a geometric problem and compares sequential and parallel computational approaches to highlight the importance of associativity.

Google Tech Talk, 12/1/2015, Presented by Guy L. Steele Jr. ABSTRACT: We present a small but interesting geometrical problem and then examine four different computational approaches to solving it: a "classic sequential solution" and three different approaches that are amenable to parallel implementation, comparing them to highlight various advantages and disadvantages, including total work required and minimum time to solution. All four solutions are illustrated both pictorially and with working code. We argue that certain approaches work better than others if exploitation of parallelism is to be automated. There will also be at least one joke. About the Speaker en.wikipedia.org/wiki/Guy_L._Steele,_Jr.

Why it's here

6 people recommend this

What people say. Highly recommended for its clear explanation of how mathematical properties like associativity enable automatic parallelism in programming languages.

tkfon Hacker News • Recommends

On “A quick introduction to data parallelism in Julia”

…y languages. My libraries are heavily inspired by these talks. Of course, if you haven't used Julia yet, it'd be great if (data) parallelism gives you an excuse to try it out! It has a fantastic foundation for composable multi-threaded parallelism 4. 1 How to Think about Parallel Programming: Not! link 2 Four Solutions to a Trivial Problem link to this video 3 Organizing Functional Code for Parallel Execution; or, foldl and foldr Considered Slightly Harmful link 4 Announcing composable multi-threaded parallelism in Julia link…
View on Hacker News

platzon Hacker News • Recommends

On “Organizing Functional Code for Parallel Execution (2009) [video]”

I enjoyed this talk along the same lines by Guy Steele, regarding not necessarily forcing a sequential solution to a non-sequential problem: Four Solutions to a Trivial Problem - Guy Steele Jr.: link to this video Look for steps that are commutative and/or associative in the problem to exploit parallelism.
View on Hacker News

heleninboodleron Hacker News • Recommends

On “Someone is pretending to be me”

This type of interviewing style is bullshit. It means the interviewer knows a better solution that is "clever" and expects you to either have the same cleverness epiphany on the spot or to have studied this question. Neither is actually very useful as a hiring criterion. Guy Steele gave an incredibly interesting guest talk1 at google about four different ways to solve this exact problem, and the fact that it's an interesting enough topic for an hour long google talk should probably be a clue that you shouldn't be expected to invent the best solution on the whiteboard in 40 minutes. 1 link to this video
View on Hacker News

MathMonkeyManon Hacker News • Recommends

On “Coroutines for Go”

Guy Steele Jr. worked on a language called "Fortress." There are a few good talks that he gives: - (toy problem) link to this video - (parallelism) link - (languages) link
View on Hacker News

dbremneron Lobsters • Recommends

Four Solutions to a Trivial Problem (2015)
3View on Lobsters

pushcxon Lobsters • Recommends

Four Solutions to a Trivial Problem
1View on Lobsters

u/qqwyin r/compsci • Mentions

What has happened to Fortress? I recently came across the talk Four Solutions to a Trivial Problem - Guy Steele Jr., which goes into some detail about the programming language Fortress. This language, as presented in the talk, seems like a very good idea. However, on Wikipedia it is mentioned that it was discontinued, and the original home page is only visible using the Way Back machine. - What happened to Fortress? Why was it cancelled? - Is it still possible to find a Fortress compiler and tutorial(s) somewhere, to tinker around with it?
56View on Reddit

u/Platzin r/haskell • Mentions

On “Programming as if the Correct Data Structure Mattered”

Guy Steele also gave an excellent talk on this problem. He gives overview of the imperative and parallel solutions to this problem. The parallel solution is in his Fortress language, but uses the same algebraic properties a Haskeller is comfortable with (e.g. Monoids) Plus, anything Guy Steele does is worth a watch. link to this video someone made a haskell version of the final solution https://gist.github.com/Teggy/1f525cf3027c92d9008d
7View on Reddit

u/reddit_lmaoin r/haskell • Mentions

On “Practical usages for (common) type classes”

Watch this video : link to this video
3View on Reddit

EdwardCoffinon Hacker News • Mentions

On “Abstract Algebra (2016) [pdf]”

…The language Fortress 4, which he was one of the language designers of, allowed one to explicitly provide the compiler with such information - you could say that a certain operation was distributive or associative for instance, and the compiler could then do some refactorings and optimizations taking this knowledge into account. 1 link . 2 link to this video 3 link to this video 4 link…
View on Hacker News

platzon Hacker News • Mentions

On “Why are monoidal categories interesting?”

associativity is the key to parallelism Four Solutions to a Trivial Problem - Guy Steele Jr. link to this video (using a monoid-cached tree)
View on Hacker News

raphlinuson Hacker News • Mentions

On “Mastering Dyalog APL (2009) [pdf]”

…bit of power which is considerably diluted in later spins such as numpy. I'm especially fond of the power (⍣) operator3, which represents parallel iteration and I think can often be translated to a per-thread while or for loop in a compute shader. I don't believe numpy has anything quite like that (but feel free to correct me!). 1: link 2: link to this video 3: link…
View on Hacker News