Benchmarking and Testing the Three Approaches

This page sets out how you should verify and measure your three implementations. You are expected to write the test and benchmark code yourselves.

1. Questions to investigate

Write down what you expect before you measure, then compare. A result that contradicts your expectation is a finding; explain it.

• How do the three approaches compare in run time as the board size increases?
• How does each approach scale as workers are added? Where does it stop improving, and why?
• How much memory does each approach allocate, and how much time is the garbage collector responsible for?
• Does the pattern being simulated (how many cells change per turn) change which approach is best?
• What is the cost, in each approach, of producing the flipped-cell information the visualiser needs?

2. Design and analysis by approach

The implementation pages tell you what to build. This section is where you reason about why it behaves as it does; your report should answer these questions using evidence from the rest of this page.

Comparing the approaches

As you work, fill in your own version of this table with evidence (benchmark output, profiles, reasoning).

Dimension	1 · Heap	2 · Double buffer	3 · Map-reduce
Memory allocated per iteration
Which goroutine writes to which memory
Synchronisation needed, and when
Is a snapshot of the board safe to hand to another goroutine?
Cost of reporting flipped cells
Behaviour as the number of workers grows
Behaviour as the board size grows
Behaviour when few cells change per turn
Main risks / failure modes

2.1 Approach 1: Heap allocation

Design questions

1. Are your worker goroutines long-lived or created per iteration? What are the trade-offs, and which did you choose?
2. How do the workers and the distributor communicate, and how do you know no goroutine reads memory another is writing?
3. How does the distributor build the next board from the strips? Does it copy cell data, or can it avoid doing so?
4. What happens to the previous iteration's memory? Which part of the Go runtime is now involved?
5. How would you confirm whether a given allocation lives on the heap or the stack?
6. Does it matter for your design whether the previous board can still be used after the next iteration has been computed?

Things to investigate

• How much memory is allocated per iteration, and how does that scale with board size and with the number of workers?
• How many individual allocations does one iteration perform? Can that number change without changing the number of bytes?
• How much of the run time is spent on allocation and garbage collection rather than computing cells? Which tools tell you?
• What happens to the results if you change how often the garbage collector runs?

Optional extensions

• Create worker goroutines per iteration instead of reusing them, and measure the difference.
• Reduce the number of allocations each worker makes per iteration without changing the number of bytes.

2.2 Approach 2: Double buffer

Design questions

1. How does each worker obtain access to the source and destination boards? What does it hold, and what does it get told each iteration?
2. At what point is it safe to switch the pointers? What guarantees that no worker is still using the old ones?
3. Workers need the rows just above and below their strip. Where do they read them from, and why is that safe?
4. What would go wrong if a worker read neighbouring rows from the destination board instead? Would your tests detect it for every number of workers?
5. The s key, the q key and pausing all need the current board. What can you safely hand to another goroutine, and when?
6. How do you produce CellFlipped / CellsFlipped events in this design, and what does that cost?
7. How do you make sure the race detector can verify your synchronisation argument?

Things to investigate

• Memory allocated per iteration compared with Approach 1.
• How performance changes as the board grows, and as the number of workers grows. Does the board eventually become too big for your machine's caches?
• Whether the way you synchronise the end of an iteration affects performance.

Optional extensions

• Compare channel-based signalling with other synchronisation primitives from the standard library for the end-of-iteration step.
• Store each board in a single contiguous block of memory and compare against a slice per row.
• Remove the modulo operations used for wrap-around, and measure what that is worth on small boards.

2.3 Approach 3: Map-reduce

Design questions

You are free to process the channel at the end of each iteration, or concurrently with the workers if you believe that can work. Whichever you choose, your report must justify it.

1. When can the board be updated from the collected coordinates? What would go wrong if cells were flipped while other workers were still counting neighbours? Be precise about what could happen, including whether it would be deterministic.
2. Which parts of the reduce step (receiving coordinates, storing them, applying them to the board) could safely overlap with the workers, and which could not?
3. What size does the channel's buffer need to be? What happens if nothing receives from the channel until all workers have finished and the buffer is smaller than the number of flips?
4. How does the reducer know that every worker has finished and that the channel has been fully drained?
5. Is the reduce step serial in your design? What does that imply for how the approach scales as workers are added?
6. How does the amount of work done after the map phase depend on the pattern being simulated?
7. What does this design give you for the visualiser that the other two do not?

Things to investigate

• Run time as a function of the number of workers, compared with Approaches 1 and 2.
• The effect of the channel's buffer size.
• How the approach behaves on boards where many cells change per turn compared with boards that have settled down.
• Where the time goes: use a CPU profile and an execution trace to look for the serial section.

Optional extensions

• Reduce channel traffic by having workers send cells in batches rather than one at a time, and measure the effect.
• Remove the serial part of the reduce by letting workers retain their own flip lists and apply them in parallel.
• Skip work in regions of the board that cannot change.

2.4 What to say in your report

Approach	Your report should
1 · Heap	Describe the design, state which costs you expect, and support or refute that with measurements.
2 · Double buffer	Explain the synchronisation between workers and distributor, argue why the design is free of data races, and compare with Approach 1 using your evidence.
3 · Map-reduce	State whether you process the channel concurrently or at the end of each iteration, and justify it with a correctness argument and measurements.

3. Keep the experiment controlled

Only the thing you are studying should change between measurements.

• Same cell-update logic, strip splitting and starting board for all three approaches.
• Same number of iterations in every measured run. (Activity in Game of Life changes over time, so letting the benchmark framework choose the number of iterations would make different configurations simulate different workloads.)
• Same machine, same power settings, same Go version, no other heavy programs running, no SDL window during benchmarks.
• Record your hardware (CPU model, physical and logical cores), operating system and go version.

4. Testing for correctness

A fast wrong answer is not a result. Before benchmarking, show that all three implementations are correct.

1. Run the course tests against each approach, with the race detector:

   go test ./tests -v -race

2. Write your own tests that compare each approach against an independent, deliberately simple reference implementation of the rules. Think about what the reference should not share with your parallel code.
3. Choose test inputs that stress the edges of your design. Consider at least:
   • square and non-square boards, and very small ones;
   • board heights that are not divisible by the number of workers;
   • more workers than rows;
   • one worker;
   • patterns with known behaviour (still lifes, oscillators, a glider crossing the edge of the board);
   • random boards at several densities and many iterations.
4. Check more than the final board: compare after every iteration, and check the flipped-cell information as well as the board.
5. Check that the caller's starting board is not modified, and that no goroutines are left running after the game finishes.
6. For Approach 3, test small channel buffer sizes so that a design flaw cannot hide behind a large buffer. Run with a timeout so that a deadlock fails the test instead of hanging it:

   go test ./... -race -timeout 120s

7. Show your tests can fail. Deliberately introduce a bug into each approach (for instance reading from the wrong board, or updating the board too early) and confirm that your tests catch it.

5. Benchmarking

Use Go's testing package benchmarks, as described in the report guidance, but adapt the structure for this comparison.

• Benchmark each approach at several board sizes and worker counts (include counts beyond your number of physical cores).
• Report allocation behaviour as well as time (look at the options of go test -bench).
• Decide and justify what one benchmark operation measures: a fixed number of iterations from the same starting board is recommended, and a metric of time per iteration makes configurations with different iteration counts comparable.
• Consider whether set-up costs (starting goroutines, allocating boards) belong inside or outside the timed region, and say what you chose.
• Benchmark at two levels if you can: the computation engine alone, and the full program via gol.Run including events. Compare, and explain the difference.
• Measure the cost of producing flipped-cell information separately from the cost of computing the next generation.

Running benchmarks

• Repeat every configuration several times (for example -count=10) and use the median. One run says nothing about noise.
• Run all approaches in the same session so that thermal throttling or background activity affects them equally.
• Use benchstat to decide whether a difference is larger than the noise.
• Make your own conversion from benchmark output to a simple CSV with the columns engine,size,threads,ns_per_turn (one row per run) so that you can paste it into the explorer below or into any plotting tool you prefer.

6. Results explorer

Paste CSV in the form engine,size,threads,ns_per_turn (a header line is optional; # starts a comment). The explorer plots time per turn and speedup, and tabulates efficiency and the Karp–Flatt metric, an experimentally determined serial fraction: e = (1/S − 1/n) / (1 − 1/n) for speedup S on n workers. Think about what the metric tells you if it stays roughly constant as workers are added, and what it tells you if it grows. The "placeholder" button loads formula-generated numbers purely to demonstrate the charts; they are not measurements.

Board size

Paste your results.csv above to draw the charts.

7. Explaining your results

A benchmark tells you which is faster; a profile tells you why. Use at least some of the following tools and say what each told you:

• CPU and memory profiles with go tool pprof (-cpuprofile, -memprofile with go test).
• The garbage collector's trace output (GODEBUG=gctrace=1).
• The execution tracer (-trace and go tool trace) to see scheduling, waiting at barriers and any serial sections.
• Changing one factor at a time (an ablation): the garbage-collection setting (GOGC), the number of available cores (GOMAXPROCS), the channel buffer size, the density of the starting board.

Be careful with GOGC=off

Approach 1 allocates roughly the size of the board every iteration. Turning off the collector on a large board for many iterations can exhaust your machine's memory.

8. Threats to validity

Say a sentence about each of these in your methodology.

• Workload dependence: a few hundred iterations from a random board is not representative of a long run or of the provided images. Which inputs did you use, and why?
• Hardware: core counts, hyper-threading, cache sizes and memory bandwidth shape every curve.
• Noise: thermal throttling, background load, garbage-collection timing. How did you control it?
• Implementation quality: a weaker implementation of one approach makes it look worse. How did you make sure each was a fair attempt?
• Small boards: synchronisation can dominate; more workers may make things slower. That is a valid result.

9. Mapping to In Your Report

Report bullet	Evidence you should bring
Discuss the goroutines you used and how they work together	A diagram per approach; include the IO, ticker and key-handling goroutines, not just the workers
Explain and analyse the benchmark results	Charts of time and speedup per approach, backed by profiles that explain the differences
Analyse how your implementation scales as more workers are added	Speedup, efficiency and a serial-fraction estimate for each approach, and your explanation of the shapes
Briefly discuss your methodology	Sections 3, 5 and 8 of this page