Problem 4 MinMaxSum

Each worker thread reduces one contiguous slice of the array to three scalars (a partial min, max, and sum) and writes each scalar into its own pre-indexed slot of a shared results array — slot threadId is touched by exactly one thread, so no two threads ever write the same memory cell and no lock is needed; the main thread then does the final combine alone, after join(), which is precisely where it becomes safe to read every slot.

The two-phase structure

Every problem in this family (linear search, π, min/max/sum) is the same shape: a parallel map over disjoint partitions, then a sequential reduce over the partial results. What makes min/max/sum clean is that all three reductions are associative — min(min(a,b),c) = min(a,min(b,c)), same for max and + — so splitting the array and recombining the pieces in any order gives the identical answer a single thread would compute. That algebraic property, not anything about threads, is what licenses the parallelism.

Why disjoint output slots remove the lock

A data race needs two threads to access the same location with at least one write and no ordering between them. Here the writes are threadResultsSum[threadId] = sum, and threadId is unique per thread. Thread 0 writes only slot 0, thread 1 only slot 1, and so on — the write sets are pairwise disjoint, so the precondition for a race never holds. This is the output partitioning trick: you don't protect a shared accumulator with a mutex; you give each worker its own private mailbox and merge the mailboxes once, single-threaded.

This is strictly cheaper than the naive alternative (one shared totalSum guarded by a lock) because there is zero lock contention on the hot path — each thread runs its whole loop with no cross-thread coordination at all.

Why the reduce step is correct

Two things must hold for the final combine to be right. First, visibility: when main reads threadResultsSum[2], does it see the value thread 2 wrote, or a stale value? The Java Memory Model answers this with Thread.join(). The JMM specifies that all actions in a thread happen-before any other thread successfully returns from join() on it. So after the for (Thread t : threads) t.join(); loop, every slot write is guaranteed visible to main — no volatile, no lock required. Skip the join and you'd be reading slots that may still hold their default 0.

Second, completeness: the union of the slices must be the whole array with no gaps and no overlap. With start = id * (N/T) and end = (id+1) * (N/T), slice boundaries chain end-to-end. (Note the trap below when N isn't divisible by T.)

Worked example: the sum reduce, real values

Take data = [4, 5, 2, 6, 1, 7, 8, 3, 9, 10] with 2 threads. Slices: part0 = [4,5,2,6,1], part1 = [7,8,3,9,10].

Reduce (main, after join): min(1,3)=1, max(6,10)=10, sum = 18 + 37 = 55. Cross-check serially: 4+5+2+6+1+7+8+3+9+10 = 55. Match — the partition didn't change the answer because addition is associative.

The code, Java and Go side by side

The shipped Java spawns 3 × NUMBER_OF_THREADS threads — a separate thread for each of min, max, sum per slice. That's lock-free and correct (every thread still owns a unique slot in its own result array), but it's wasteful: one pass over a slice can compute all three. The version below fuses them so each slice is read once.

public class MinMaxSum {
  static final int N = 100, T = 4;
  static int[] data = new int[N];
  static int[] pMin = new int[T], pMax = new int[T], pSum = new int[T];

  public static void main(String[] a) throws InterruptedException {
    java.util.Random r = new java.util.Random();
    for (int i = 0; i < N; i++) data[i] = r.nextInt(500);

    Thread[] th = new Thread[T];
    for (int id = 0; id < T; id++) {
      final int tid = id;
      final int start = tid * (N / T);
      // last thread takes the remainder so no element is dropped
      final int end = (tid == T - 1) ? N : (tid + 1) * (N / T);
      th[id] = new Thread(() -> {
        int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE, s = 0;
        for (int i = start; i < end; i++) {
          int v = data[i];
          if (v < mn) mn = v;
          if (v > mx) mx = v;
          s += v;
        }
        pMin[tid] = mn; pMax[tid] = mx; pSum[tid] = s; // disjoint slot: no lock
      });
      th[id].start();
    }
    for (Thread t : th) t.join(); // happens-before: all writes now visible

    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, sum = 0;
    for (int i = 0; i < T; i++) {
      min = Math.min(min, pMin[i]);
      max = Math.max(max, pMax[i]);
      sum += pSum[i];
    }
    System.out.printf("min=%d max=%d sum=%d%n", min, max, sum);
  }
}

In Go the same shape is idiomatic with goroutines and a sync.WaitGroup as the join barrier. A struct result per slice keeps the three partials together; the slice of results is the disjoint-slot array.

package main

import (
	"fmt"
	"math"
	"math/rand"
	"sync"
)

type partial struct{ min, max, sum int }

func main() {
	const N, T = 100, 4
	data := make([]int, N)
	for i := range data {
		data[i] = rand.Intn(500)
	}

	res := make([]partial, T) // one disjoint slot per goroutine
	var wg sync.WaitGroup
	for id := 0; id < T; id++ {
		wg.Add(1)
		start := id * (N / T)
		end := (id + 1) * (N / T)
		if id == T-1 {
			end = N // remainder to the last goroutine
		}
		go func(id, start, end int) {
			defer wg.Done()
			mn, mx, s := math.MaxInt, math.MinInt, 0
			for i := start; i < end; i++ {
				v := data[i]
				if v < mn {
					mn = v
				}
				if v > mx {
					mx = v
				}
				s += v
			}
			res[id] = partial{mn, mx, s} // slot id: no mutex
		}(id, start, end)
	}
	wg.Wait() // happens-before: goroutine writes visible to main

	min, max, sum := math.MaxInt, math.MinInt, 0
	for _, p := range res {
		if p.min < min {
			min = p.min
		}
		if p.max > max {
			max = p.max
		}
		sum += p.sum
	}
	fmt.Printf("min=%d max=%d sum=%d\n", min, max, sum)
}

Where the two runtimes differ

• Threads vs goroutines. Each Java Thread is a real OS thread (~1 MB stack, kernel-scheduled). The shipped 3×T-thread version costs 12 OS threads for 100 elements — fine here, catastrophic if you scaled the fan-out. Go's goroutines start at a ~2 KB growable stack and are multiplexed onto a small pool of OS threads by the runtime, so the same fan-out is cheap; you'd still partition for cache locality, not to save threads.
• Join barrier. Java's Thread.join() is per-thread and provides the JMM happens-before edge directly. Go has no join; sync.WaitGroup.Wait() is the barrier, and the Go memory model guarantees the wg.Done() in each goroutine happens-before the Wait() returns. Channels would also work (send a partial per goroutine, receive T of them) but a WaitGroup is leaner when you already have indexed slots.
• Same lock-free principle, both languages. Neither version uses a mutex on the hot path. The correctness argument is identical: disjoint writes during map, a memory barrier at the join, then a single-threaded reduce.

Pitfalls

• Dropping the remainder. With N=100, T=3, N/T = 33 and the original end = (id+1)*33 formula gives slices ending at 33, 66, 99 — element data[99] is never read, so sum and max silently undercount. Always give the last worker end = N (as above) or distribute the remainder.
• Reading partials before join()/Wait(). Without the barrier you have a data race; main may read a slot still holding its default 0, which poisons min (since 0 < any positive partial min) and undercounts sum. The bug is non-deterministic and often hides on a fast laptop, then surfaces under load.
• Default-zero initialization corrupting min/max. If a slice is empty (more threads than elements), its slot keeps the default 0, and the reduce folds a bogus 0 into the global min/max. Either skip empty slices or seed unused slots with MAX_VALUE/MIN_VALUE.
• Integer overflow in the sum. Partial sums fit in int here, but on a large array of large values either a partial or the final total can overflow. Use long (Java) / int64 (Go) for the accumulators.
• False sharing. Packing all partials into one tightly-packed int[] can put adjacent slots on the same cache line; threads writing neighboring slots ping-pong that line between cores. It's correct but can erase the speedup. Padding slots (or per-thread structs/locals merged at the end) avoids it.

Takeaways

• Min/max/sum parallelize because all three reductions are associative — partition freely, recombine in any order, get the same answer.
• The lock disappears not by luck but by design: disjoint output slots (one per worker) mean no two threads write the same cell, so there's no race to guard.
• The reduce is correct because join() / WaitGroup.Wait() establishes a happens-before edge that makes every partial write visible to the single thread doing the final combine.
• Fuse the three reductions into one pass per slice; spawning 3×T threads is correct but wasteful — and in Go, prefer goroutines + a WaitGroup over OS-thread-per-task.

Sources: Brian Goetz et al., Java Concurrency in Practice (happens-before, Thread.join semantics, false sharing); the Java Language Specification §17.4 Memory Model; The Go Memory Model (go.dev/ref/mem) and the sync package docs for WaitGroup ordering; Herlihy & Shavit, The Art of Multiprocessor Programming (map/reduce over disjoint partitions). Re-authored and deepened for this guide: added the disjoint-output-slot correctness argument, the happens-before reasoning for the reduce step, the fused single-pass Java rewrite with the remainder fix, a side-by-side Go version, and the pitfalls a working engineer hits.