Session 09¶

Topic 2: The Go language¶

• tour of Go
• tour of Go (continued)
• Go’s programming syntax
• many workers with Goroutines 👈
• shared memory between workers
• message passing with Go channels
• case studies with concurrency
• performance and scalability
• case studies with parallel algorithms

Today¶

Many workers with Goroutines¶

1. parallel thinking
2. fork-join pattern
3. workgroup management
4. goroutines vs. threads
5. example: Mandelbrot

Parallel thinking in Go (and beyond)¶

The cognitive shift¶

Comfortable sequential world 🧵¶

In school, most of your programs were sequential.
Order is clear. Life is good.

your data pipeline:

1. load the entire raw data
2. clean data
3. preprocess the data
4. fit a model
5. evaluate
6. deploy

Reality hits 🧨¶

But this dataset is now 2 TB.
Training takes 14 hours.

your manager says:

“We have 256 cores in this machine.
Why are we using one?”

now you think:

“Fine. Let’s parallelize.”

First attempt at parallelism¶

you decide to:

• split the dataset into chunks
• preprocess chunks in parallel
• train multiple models
• aggregate results

but suddenly strange things happen:

• sometimes the model accuracy differs slightly
• sometimes the logs look out of order
• sometimes a run crashes
• sometimes everything works just fine

“Parallelism is randomness
you cannot avoid.”

Cognitive shift to parallelism¶

imagine 2 workers computing at the same time:

• worker A preprocesses data chunk
• worker B writes results to shared storage

—

• the logic of A and B can be correct
• what has changed is the timing

Sequential vs concurrent¶

Sequential programs¶

• execute one action at a time
• easy to reason about their order
• deterministic:
  same inputs → same outputs
  always the same order of actions 📏

mental image: a straight timeline of actions

Concurrent programs¶

• multiple actions/tasks active at once
• harder to reason about their order
• intuition from sequential programming may lead us astray
• nondeterministic:
  same inputs → different interleavings 🎲

gopl.io, p217:

Reasoning about concurrent programs is inherently harder than about sequential ones, and intuitions acquired from sequential programming may at times lead us astray.

A sequential program may call one function and then call the other, but in a concurrent program with two or more goroutines, calls to both functions can be active at the same time.

mental image: multiple timelines with interleaving

Core challenges¶

• in sequential: “A then B”
• in concurrent: “A then B” or “B then A” or “A/B overlap”
• both A and B may be active simultaneously
• rethink correctness:
  “What if tasks interleave differently?”

Structuring Parallel Programs¶

• task/data decomposition
  → How to divide work into concurrent tasks?
• distribution
  → How to assign tasks to workers/goroutines?
• task/data dependencies
  → What must happen before what?
• synchronization
  → How tasks coordinate safely?
• scalability
  → performance vs resources

Task parallelism & data parallelism¶

Task parallelism¶

• running many different tasks at the same time
• tasks operate on the same data

Data parallelism¶

• running one task
• task operates on many different chunks of the data

Dependence & independence¶

• identify independent work units
• avoid unnecessary dependencies
• design algorithms around independent work units

—

• more independent tasks → easier parallelization
• where dependencies exist → explicit synchronization

Synchronization¶

• in task parallelism:
  when tasks must be called in a specific order

  task A1 → task B1 → task C1 ↘ task B2 → task C2

• in data parallelism:
  when data must be generated in a specific order

  data X1 → data Y1 → data Z1 data X1 → data Y2 ↗

Example: dependent or independent?¶

func columnMean(data [][]float64, col int) float64 {
  M := len(data)  // number of rows
  var sum float64
  for i := 0; i < M; i++ {
    sum += data[i][col]
  }
  return sum / float64(M)
}

func cumulativeMovingAverage(data [][]float64, col int) []float64 {
  M := len(data)  // number of rows
  var sum float64
  cma := make([]float64, M)
  for i := 0; i < M; i++ {
    sum += data[i][col]
    cma[i] = sum / float64(i+1)
  }
  return cma
}

Goroutines¶

What are goroutines?¶

• goroutines run functions concurrently with other functions
• very cheap → thousands to millions possible

f()     // calls f() (by the main goroutine)
// now, wait for f() to return

go f()  // create a new goroutine that calls f()
// don't wait for `go f()` to return

Note: Now we called 3 things “main”: a package, a function, and a goroutine.

gopl.io, pp217:

When a program starts, its only goroutine is the one that calls the main function, so we call it the main goroutine. New goroutines are created by the go statement.

When the main function returns, all goroutines are abruptly terminated and the program exits. Other than by returning from main or exiting the program, there is no programmatic way for one goroutine to stop another, but as we will see later, there are ways to communicate with a goroutine to request that it stop itself.

Fork-join pattern¶

a general concept used for threads, applies also to goroutines:

1. fork: spawn multiple goroutines/threads for tasks
2. join: wait for all to finish before proceeding

→ natural in parallel problems (e.g., loops)

mental image: main goroutine → forks goroutines → joins them later (so only the main goroutine remains)

Wikipedia - Fork-join model:

Fork-join is the main model of parallel execution in the “OpenMP” framework, although OpenMP implementations may or may not support nesting of parallel sections. It is also supported by the “Java concurrency” framework, the “Task Parallel Library” for .NET, and Intel’s “Threading Building Blocks.”

sequential execution:

parallel execution (fork-join):

Forking in Go¶

// only the main goroutine exists at the start 🪿

for i := 0; i < N; i++ {
  go func(i int) {    // ← fork happens here 🐤
    work(i)           // (placeholder for computations)
  }(i)
}

Joining in Go¶

var wg sync.WaitGroup // new: create wg

for i := 0; i < N; i++ {
  wg.Add(1)           //   +1 worker (before goroutine)
  go func(i int) {    // ← fork happens here 🐤
    defer wg.Done()   //   -1 worker (inside goroutine)
    work(i)
  }(i)
}
wg.Wait()             // ← join 🪹 (wait for all goroutines)

// only the main goroutine continues 🪿

At the start of the program, only one goroutine exists. It is the main goroutine and it executes the main() function.

New goroutines are created using the go keyword, called forking:

• the keyword go is followed by an ordinary function/method call
• the function being called is executed concurrently by a goroutine
• the goroutine forking the new goroutine returns immediately after the go statement

Using a WaitGroup defined in the sync package allows us to implement the joining part of the fork-join pattern:

type WaitGroup
func (wg *WaitGroup) Add(delta int) // use before go statement
func (wg *WaitGroup) Done()         // use inside go function
func (wg *WaitGroup) Wait()         // join, use after all go statements

From Go’s documentation:

A WaitGroup waits for a collection of goroutines to finish. The main goroutine calls Add to set the number of goroutines to wait for. Then each of the goroutines runs and calls Done when finished. At the same time, Wait can be used to block until all goroutines have finished.

Workgroup management¶

what we observed in the previous code snippet:

• use sync.WaitGroup to manage goroutines
• pattern:
  fan-out (fork many workers)
  fan-in (complete/collect results)

mental image: task pool → workers → results

Goroutines vs. threads¶

Switching Between Units of Execution

Goroutines: cooperative Switching (Go runtime)

• Goroutines are scheduled by the Go runtime, not the OS.
• A goroutine switch (context switch) only happens at safe points, which are places where the runtime knows it’s safe to pause and resume. Example: when a goroutine does I/O, hits a channel send/receive, waits on a lock, calls runtime.Gosched(), or finishes.
• This is called cooperative scheduling: the goroutine “gives up control” voluntarily.
• pro: Switching is cheap (no full OS context switch).
• con: A CPU-hungry goroutine that never yields can block others (runtime can’t interrupt it mid-calculation, except in rare preemption cases introduced in newer Go versions).
• Puts the burden on programmers and runtime to ensure goroutines don’t hog CPU.

OS Threads: preemptive Switching (OS Kernel)

• OS threads are scheduled by the operating system kernel.
• The OS can interrupt a running thread at any time (based on a timer, priority, or signals).
• This is called preemptive scheduling: the thread doesn’t get to choose when to pause.
• pro: Provides fairness automatically, because no thread can hog the CPU forever.
• con: It’s expensive: the OS must save/restore registers, stacks, caches, etc., leading to higher context-switch overhead.

Analogy:

• Cooperative (goroutines): Imagine a group of people in a meeting where each speaker politely says “I’m done, your turn.” If one person keeps talking forever, others can’t speak.
• Preemptive (threads): Imagine a moderator with a timer who cuts off a speaker after their time is up, whether they’re finished or not.

Example: Mandelbrot set¶

• the Mandelbrot set is a fractal curve
• computationally heavy
• embarrassingly parallel tasks (i.e., simple parallelism)

Goal:

• split image into horizontal bands (1 pixel in height)
• each band computed by one goroutine

Sequential code code/go/mandelbrot/sequential¶

for py := 0; py < height; py++ {
  y := float64(py) / height * (ymax - ymin) + ymin
  for px := 0; px < width; px++ {
    x := float64(px) / width * (xmax - xmin) + xmin
    z := complex(x, y)
    // Image point (px, py) represents complex value z.
    img.Set(px, py, mandelbrot(z))
  }
}

rows are independent → perfect for goroutines

gopl.io, p62:

The two nested loops iterate over each point in a grayscale raster image representing the −2 to +2 portion of the complex plane. The program tests whether repeatedly squaring and adding the number that point represents eventually “escapes” the circle of radius 2. If so, the point is shaded by the number of iterations it took to escape. If not, the value belongs to the Mandelbrot set, and the point remains black.

Hands-on¶

• divide the image into horizontal rows
• assign each row to a goroutine
• use a sync.WaitGroup for fork-join synchronization
• implement a timer to see a speedup

mental image: Mandelbrot image divided into slices

Example demonstrates:

• task decomposition: each row is an independent task.
• fork-join pattern: rows are forked into goroutines, then joined via WaitGroup.
• independence of actions: Each pixel can be computed without dependencies.
• scalability: More CPU cores → faster image generation.

var wg sync.WaitGroup

for py := 0; py < height; py++ {
  wg.Add(1)
  go func(py int) {
    defer wg.Done()
    y := float64(py) / height * (ymax - ymin) + ymin
    for px := 0; px < width; px++ {
      x := float64(px) / width * (xmax - xmin) + xmin
      z := complex(x, y)
      // Image point (px, py) represents complex value z.
      img.Set(px, py, mandelbrot(z))
    }
  }(py)
}

wg.Wait()

use the Mandelbrot fractal to illustrate the effects of granularity:

• fine granularity: more tasks with less work each
• coarse granularity: fewer tasks with more work each

Exercise¶

• implement and compare one goroutine per row vs. one per pixel
• what can you say about efficiency and overhead?

Key takeaways¶

• goroutines are cheap and scalable
• simpler than OS threads
• fork-join is the backbone of concurrency in Go
• sync.WaitGroup → simple, powerful coordination

Looking ahead¶

• practice your skills by reviewing the previous sessions
• practice implementing math formulas/problems in Go

Prepare for the next session 🌱¶

sessions/10-todo