When more threads stop helping

Key points

• Amdahl: if a fraction s of the work is serial, the best possible speed-up is 1 / s, however many cores you add.
• At 90% parallel, eight cores buy about 4.7x, and a thousand cores still buy under 10x.
• Every task pays for handoff, scheduling and possibly a context switch. Below a few microseconds of work, that overhead wins.
• Contention is the other ceiling: a lock everyone wants turns a parallel program back into a serial one, plus queueing.
• Measure. Time the serial version first, then prove the concurrent one is faster on the machine that actually matters.

Example

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Main {
    public static void main(String[] args) {
        System.out.println("cores            : " + Runtime.getRuntime().availableProcessors());

        // Amdahl: speed-up = 1 / (serial + parallel / cores)
        for (double parallel : new double[] { 0.99, 0.90, 0.50 }) {
            System.out.printf("%.0f%% parallel     : %.1fx on 8 cores, %.1fx on 1000, ceiling %.1fx%n",
                    parallel * 100,
                    speedUp(parallel, 8), speedUp(parallel, 1000), 1 / (1 - parallel));
        }

        // Overhead is real: tiny tasks cost more to hand out than to run.
        System.out.println("tiny job serial  : " + micros(() -> burn(0, 10_000)) + " us");
        System.out.println("tiny job x4      : " + micros(Main::tinyInParallel) + " us  <- slower");
        System.out.println("big job serial   : " + micros(() -> burn(0, 40_000_000)) + " us");
        System.out.println("big job x4       : " + micros(Main::bigInParallel) + " us  <- worth it");
    }

    static double speedUp(double parallel, int cores) { return 1 / ((1 - parallel) + parallel / cores); }

    static long burn(long from, long to) { long s = 0; for (long i = from; i < to; i++) s += i % 7; return s; }

    static void tinyInParallel() { split(10_000); }

    static void bigInParallel() { split(40_000_000); }

    static void split(long total) {
        ExecutorService pool = Executors.newFixedThreadPool(4);
        try {
            Future<?>[] parts = new Future<?>[4];
            for (int i = 0; i < 4; i++) {
                long from = i * total / 4, to = (i + 1) * total / 4;
                parts[i] = pool.submit(() -> burn(from, to));
            }
            for (Future<?> part : parts) part.get();
        } catch (Exception e) {
            Thread.currentThread().interrupt();
        } finally {
            pool.shutdown();
        }
    }

    static long micros(Runnable r) {
        r.run();                                     // warm up, then measure
        long start = System.nanoTime();
        r.run();
        return (System.nanoTime() - start) / 1000;
    }
}

Threads speed up the parallel fraction only. Measure it before you pay for it.