Writing Efficient and Fair Multi-Threaded Programs

A common instinct when optimizing compute-intensive code is to parallelize execution across multiple threads. While spinning up worker threads invariably speeds up processing compared to a single-threaded loop, simply adding concurrency does not mean the system is operating at maximum efficiency.

To write high-performance concurrent software, we must evaluate two core dimensions:

1. Correctness: Ensuring that shared state mutations are free from race conditions and data corruption via appropriate synchronization primitives.
2. Fairness: Ensuring that the computational workload is distributed evenly across all active threads, preventing stragglers from stretching the overall wall-clock runtime.

Here, we examine the problem of counting all prime numbers between $1$ and $100,000,000$, analyzing three sequential and parallel architectures to demonstrate how work allocation models impact CPU saturation and throughput.

---

The Problem: Counting Primes up to 100 Million

Given an upper bound MAX_INT = 100,000,000, the objective is to count the total quantity of prime numbers.

Primality Check Logic

A standard trial-division algorithm checks whether a number $N$ is prime by attempting division against odd integers up to $\sqrt{N}$:

func checkPrime(n int) bool {
    if n <= 1 {
        return false
    }
    for i := 3; i*i <= n; i += 2 {
        if n%i == 0 {
            return false
        }
    }
    return true
}

Computational Characteristics

• Computational cost grows with $\sqrt{N}$: Testing whether $101$ is prime takes far fewer iterations than testing whether $99,999,989$ is prime.
• Prime density drops: Primes are dense in lower ranges and sparse in higher ranges. Non-prime composite numbers exit early as soon as a small factor divides them, while large prime numbers force the loop to run all the way to $\sqrt{N}$.

Consequently, the compute workload is non-uniform across the input domain.

---

Approach 1: The Sequential Baseline

A naive single-threaded implementation tests numbers sequentially from $3$ to $100,000,000$:

var totalPrimeNumbers int64 = 1 // accounting for 2

func countPrimesSequential() {
    start := time.Now()
    for i := 3; i <= maxInt; i += 2 {
        if checkPrime(i) {
            totalPrimeNumbers++
        }
    }
    fmt.Printf("Found %d primes in %v\n", totalPrimeNumbers, time.Since(start))
}

Performance Profile

• Execution Time: ~3 minutes 55 seconds (up to 4+ minutes depending on background OS CPU contention).
• Resource Utilization: Exactly 1 CPU core is saturated at 100%, leaving all other cores completely idle.

---

Approach 2: Naive Multi-Threading via Static Range Partitioning

To parallelize the search across $C = 10$ threads, the natural initial solution is static range chunking. The range $[1, 100\text{M}]$ is divided into 10 equal batches of $10\text{M}$ numbers each:

• Thread 0: $[1, 10,000,000]$
• Thread 1: $[10,000,001, 20,000,000]$
• …
• Thread 9: $[90,000,001, 100,000,000]$

Implementation

Shared state (totalPrimeNumbers) is protected using atomic increments (atomic.AddInt64) to guarantee correctness:

func worker(start, end int, wg *sync.WaitGroup, threadID int) {
    defer wg.Done()
    t0 := time.Now()
    
    for i := start; i <= end; i += 2 {
        if checkPrime(i) {
            atomic.AddInt64(&totalPrimeNumbers, 1)
        }
    }
    
    fmt.Printf("Thread %d [%d - %d] finished in %v\n", threadID, start, end, time.Since(t0))
}

The Straggler Problem and Unfairness

Running this version reduces execution time from ~4 minutes down to approximately 1 minute (or ~42-60 seconds depending on machine load)—roughly a 4x to 5x speedup. However, reviewing per-thread runtimes reveals significant imbalance:

Thread ID	Sub-range	Approximate Time Taken
Thread 0	1 – 10M	~18 seconds
Thread 1	10M – 20M	~30 seconds
Thread 2	20M – 30M	~37 seconds
…	…	…
Thread 9	90M – 100M	~60 seconds

Thread 0 [========>                                         ]  18s (Idles for 42s!)
Thread 1 [=============>                                    ]  30s (Idles for 30s!)
Thread 2 [=================>                                ]  37s (Idles for 23s!)
...
Thread 9 [==================================================]  60s (Bottleneck)

Why Static Chunking Fails Optimality

Because higher numbers require scanning factors up to a significantly larger $\sqrt{N}$, Thread 9 performs vastly more CPU cycles than Thread 0.

When Thread 0 finishes in 18 seconds, its assigned CPU core goes idle for the remaining 42 seconds while Thread 9 continues grinding. The entire program can only finish as fast as its slowest thread.

---

Approach 3: Dynamic Work Distribution (Fair Allocation)

To achieve true fairness, threads must not be constrained by pre-allocated ranges. Instead, workers dynamically fetch the next available piece of work on demand.

Architecture: Atomic Task Pulling

Rather than static ranges, a globally shared atomic counter currentNumber tracks progress. Each thread loops continuously, atomically claiming the next number, verifying it, and repeating until the range is exhausted.

sequenceDiagram
    autonumber
    participant W1 as Worker Thread 1
    participant W2 as Worker Thread 2
    participant AC as Atomic Counter (currentNumber)
    participant Res as Atomic Total Counter

    W1->>AC: FetchAndAdd(1)
    AC-->>W1: Returns 1,000,001
    W2->>AC: FetchAndAdd(1)
    AC-->>W2: Returns 1,000,002
    W1->>W1: Run checkPrime(1,000,001)
    W2->>W2: Run checkPrime(1,000,002)
    W1->>Res: atomic.AddInt64 (if prime)
    W1->>AC: FetchAndAdd(1) (Next Job)

Go Implementation

var (
    currentNumber     int64 = 2
    totalPrimeNumbers int64 = 0
    maxInt            int64 = 100_000_000
)

func doWork(wg *sync.WaitGroup, id int) {
    defer wg.Done()
    t0 := time.Now()

    for {
        // Atomically claim the next number
        n := atomic.AddInt64(&currentNumber, 1)
        if n > maxInt {
            break
        }

        if checkPrime(int(n)) {
            atomic.AddInt64(&totalPrimeNumbers, 1)
        }
    }

    fmt.Printf("Thread %d completed in %v\n", id, time.Since(t0))
}

func main() {
    concurrency := 10
    var wg sync.WaitGroup
    wg.Add(concurrency)

    start := time.Now()
    for i := 0; i < concurrency; i++ {
        go doWork(&wg, i)
    }

    wg.Wait()
    fmt.Printf("Checked up to %d, total primes: %d in %v\n", 
        maxInt, atomic.LoadInt64(&totalPrimeNumbers), time.Since(start))
}

Fairness and Performance Results

• Per-Thread Duration: Every thread executes for virtually the same duration (~50.0 to 51.0 seconds).
• Total Program Wall-Clock Time: Drops from ~60 seconds to ~51 seconds (an immediate ~15–20% performance improvement over static partitioning).
• Zero Idle Cycles: No thread idles while other threads are working. Fast iterations (composite numbers or smaller integers) finish quickly, enabling workers to take on more items automatically.

---

Comparison Summary

Metric	Approach 1: Sequential	Approach 2: Static Batches	Approach 3: Dynamic Atomic Pulling
Concurrency	1 thread	10 threads	10 threads
Work Allocation	Linear sequence	Static split ($10\text{M}$ numbers/thread)	Dynamic self-scheduling (atomic.Add)
Thread Workloads	Monolithic	Unfair (Thread 0: 18s, Thread 9: 60s)	Fair (All threads finish in ~51s)
CPU Utilization	Poor (1 Core)	Uneven (Cores drop out progressively)	Maximum (All cores 100% busy throughout)
Total Runtime	~235 seconds	~60 seconds	~51 seconds
Correctness Guard	None needed	atomic.AddInt64 for results	atomic.AddInt64 for counter + results

---

Key Architectural Takeaways

1. Parallelism $\neq$ Automatic Optimality: Adding threads prevents sequential bottlenecks, but naive batching often introduces tail latency due to the “slowest worker” constraint.
2. Identify Asymmetric Workloads: If task duration depends on dynamic input characteristics (e.g., query complexity, document sizes, mathematical properties like $\sqrt{N}$), static domain decomposition leads to worker starvation.
3. Work Stealing and Dynamic Pulling: Adopting a pull-based or work-stealing pattern using low-overhead synchronization (such as atomic operations or concurrent queues) balances resource usage across all available CPU cores.
4. Balance Contention with Granularity: While pulling individual numbers via atomic.AddInt64 worked well here, workloads with microsecond-level tasks should pull small batches (e.g., batches of 1,000 numbers) to amortize atomic bus-locking overhead while preserving fairness.