Map-reduce¶

Category: Parallelism · Status: stub · Lessons: chapter 07, Parallelism

One line: Apply a function to every item independently, then combine the results with an associative operation, so that both halves can be split across workers.

Also called: MapReduce.

How it connects¶

flowchart LR
  n_data_parallelism["Data parallelism"]
  n_map_reduce["Map-reduce"]
  n_map_reduce -->|is a| n_data_parallelism
  classDef center stroke-width:3px
  class n_map_reduce center
  classDef outside stroke-dasharray: 4 3
  class n_data_parallelism outside

Is a kind of: Data parallelism
See also: Fork-join

In each language¶


Rust	Rayon's `reduce` ↗ takes an identity value as well as the combining operation
C++	`std::transform_reduce` ↗; with a non-associative or non-commutative operation the result is non-deterministic
Java	`Stream.reduce` ↗ requires an associative accumulator, so that a parallel stream can split the work
Elsewhere	Hadoop MapReduce ↗ runs the same split across a cluster

Where to read more¶

In this library: Splitting a sum across workers
In the books: Concurrency in .NET, Riccardo Terrell — ch. 5, 'PLINQ and MapReduce: data parallelism, part 2'
In the books: The Art of Concurrency, Clay Breshears — ch. 7, 'MapReduce'
In the books: Python Concurrency with asyncio, Matthew Fowler — ch. 6, 'Handling CPU-bound work' → 'Solving a problem with MapReduce using asyncio'
In the books: Python Parallel Programming Cookbook, Giancarlo Zaccone — ch. 5, 'Distributed Python' → 'Using MapReduce with Disco'
In the books: Seven Concurrency Models in Seven Weeks, Paul Butcher — ch. 8, 'The Lambda Architecture' → 'Day 1: MapReduce'
In the books: The Go Programming Language Phrasebook, David Chisnall — ch. 10, 'Concurrency Design Patterns' → 'Map Reduce, Go Style'
In the books: An Introduction to Parallel Programming, Peter S. Pacheco, Matthew Malensek — ch. 1, 'Why parallel computing'
Reference: Wikipedia: MapReduce ↗