CSE Roadmap

Core tier · about 6 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Lag of the counter (20 minutes)

A sloppy counter has 8 threads and a threshold of 500. By how much can the global value lag?

Done when: at most 4,000 (8 × 500).

Hint

The lag is the number of threads times the threshold.

Easy 2: Per-increment cost (20 minutes)

A run of 4,000,000 increments takes 0.291 s. Give the cost per increment in nanoseconds.

Done when: about 73 ns.

Hint

Time divided by the number of increments.

Easy 3: Choose the lock (20 minutes)

A hash table of 1,000,000 keys is updated by 16 threads. Choose coarse or fine locking, and say why.

Done when: fine-grained (lock striping), because one lock would be a bottleneck.

Hint

Think about how many threads would wait on one lock.

Medium

Medium 1: Reproduce the counters (45 minutes)

Write the mutex, atomic and sloppy counters. Run each with 1, 2 and 4 threads, 2,000,000 increments each, five times, and report medians.

Done when: a table like section 2 in which the sloppy counter scales best and the mutex worst.

Hint

Pad each local counter to a cache line.

Medium 2: Tune the threshold (45 minutes)

Run the sloppy counter with thresholds 1, 4, 16, 64, 256 and 1,024 on 4 threads. Plot the time against the threshold and the maximum lag.

Done when: a table that shows falling time and rising lag, and the threshold you would choose.

Hint

The lag is the threads times the threshold; the time falls with it.

Medium 3: Check the hash table (45 minutes)

Write the one-lock table. After a run with 4 threads, check that it holds all keys and every lookup succeeds. Then remove the lock and repeat.

Done when: a correct run with the lock, and a failure (lost keys or a crash) without it.

Hint

Without the lock, two inserts into one bucket can lose a node.

Hard

Hard 1: The two tables (90 minutes)

Build both tables and measure 1, 2 and 4 threads with 200,000 operations. Report the medians and the speed-up of the fine-grained table over the coarse one.

Done when: a table like section 4, with a paragraph on the causes of the result.

Hint

Use the same keys and the same total work for both tables.

Hard 2: A table that grows (90 minutes)

Add a resize operation that doubles the number of buckets when the average chain exceeds 8. Make it correct by taking all bucket locks in order. Test it with 4 threads inserting while one thread resizes.

Done when: no lost keys in 20 runs, and a run under ThreadSanitizer with no warnings.

Hint

Lock bucket 0 first, then 1, and so on, before moving any node.

Hard 3: Your own case study (120 minutes)

Choose a shared structure (a queue, a stack or a cache). Write the coarse version, measure it, find the contention, and apply one improvement. Report before and after with medians.

Done when: a one-page report with the data, the change and the result, with no lost or duplicated items.

Hint

Start from the simplest correct version.