Concurrent Hash Table … Summary

We finish the tour with the structure you reach for most — the hash table — and the lessons the whole chapter was really about.

29.4 Concurrent Hash Table

The trick is to not invent anything new. Build the hash table out of the concurrent lists you already have, one per bucket — and give each bucket its own lock rather than sharing one global lock:

#define BUCKETS (101)

typedef struct __hash_t {
    list_t lists[BUCKETS];        // each bucket is a concurrent list
} hash_t;

void Hash_Init(hash_t *H) {
    for (int i = 0; i < BUCKETS; i++)
        List_Init(&H->lists[i]);  // ... each with its OWN lock
}

int Hash_Insert(hash_t *H, int key) {
    return List_Insert(&H->lists[key % BUCKETS], key);
}

int Hash_Lookup(hash_t *H, int key) {
    return List_Lookup(&H->lists[key % BUCKETS], key);
}

(This one doesn’t resize — handling growth is left as an exercise.) Because a lock protects only one bucket, operations on different buckets never contend. Step through two concurrent inserts:

A hash table = an array of BUCKETS independent locked lists. A lock per bucket means many buckets can be active at once.

1The structure: one lock PER bucket

The whole table is 101 buckets, each a concurrent list from §29.2 with its own lock. Hash_Insert(key) simply calls List_Insert on bucket key % 101 — no global lock anywhere.

step 1 / 5

The payoff is dramatic. Compared with a single-lock list under the same four-thread insert load, the per-bucket hash table barely moves off the x-axis:

Figure 29.11: Scaling hash tables. Four threads, 10k–50k concurrent inserts each. The single-lock list climbs steeply; the per-bucket hash table stays flat — it scales magnificently. (Empirical — measured on the authors’ 4-CPU iMac.)

29.5 Summary

Four structures — counter, list, queue, hash table — and a handful of lessons that matter more than any one of them:

What the four structures taught — the lessons that outlive the code. Click one.
	why it matters
Guard lock/unlock around control flow	error paths that return mid-function must undo every lock and allocation first
More concurrency ≠ more performance	a scheme drowning in lock traffic can be slower than one big lock
Fix performance only once it exists	avoid premature optimization — no value in speeding up what was never the bottleneck

Dotted-underlined cells have explanations — click one.

Tip: Avoid Premature Optimization (Knuth’s Law)

When building a concurrent structure, start with the most basic approach — one big lock for synchronized access. You’ll likely get a correct lock; only if it then shows performance problems should you refine it. As Knuth famously put it, “premature optimization is the root of all evil.”

History bears this out. Early multiprocessor kernels used a single lock — in Linux it even had a name, the big kernel lock (BKL). For years that simple approach was fine; only when multi-CPU systems became the norm did one-thread-in-the-kernel turn into a bottleneck. Linux took the straightforward path — replace one lock with many; Sun took the radical one — build a whole new OS, Solaris, with concurrency baked in from day one.

And this is only the surface. Beyond locks entirely lie non-blocking data structures, which coordinate with atomic instructions (like the compare-and-swap of chapter 28) instead of locks — a taste comes with common concurrency bugs, a couple of chapters on. An entire field waits there for the curious.

Check yourself: hash tables and lessons

1.Why does the concurrent hash table scale magnificently while the single-lock list does not?

2.With BUCKETS = 101, a thread calls Hash_Insert(104). What happens?

3.Following Knuth's law, how should you start when building a concurrent data structure?

4.What was the 'big kernel lock' (BKL), and why did Linux move away from it?

5.How do non-blocking data structures coordinate threads without traditional locks?

5 questions