Data-structure labs

5.10 Lab and reading

Lab

The code is in the companion repository under ch05-structures/, a single crate with five binaries, ring, pad, lookup, alloc and bitmap. As in the earlier labs, write the prediction down before each run, report p50, p99 and max and never an average, pin with taskset, subtract the cost of reading rdtsc twice back to back, and hand-write the hot code, with no queue or map crates in the measured path; the standard library’s mpsc and HashMap are what is being measured, and FxHash is an add, a multiply by a large odd constant and a rotate. For the two-thread runs use cores 2 and 3, and check in lscpu -e that they share an L3.

ch05-structures/
  Cargo.toml
  src/
    lib.rs          Update, Ring, Interner, Positions, the bitmap helpers,
                    and Pool: slots, a stack of free indices, a live flag each
    bin/
      ring.rs       exercise 1
      pad.rs        exercise 2
      lookup.rs     exercise 3
      alloc.rs      exercise 4
      bitmap.rs     exercise 5

1. Build the ring. Take the 16-slot ring of Chapter 3’s stretch lab, which read the other side’s counter on every item, with no cached copies, at 30–100 ns an item, and make it the real one: u64 slots, capacity 4,096, Acquire/Release on two atomics, head and tail padded to lines of their own, and a cached copy of the other side’s counter in each half. Benchmark throughput and per-item latency over 100 million items against std::sync::mpsc and a Mutex<VecDeque<u64>>. Predict the ratios first from the ladder: the ring at 5–20 ns an item, mpsc at 100–300 ns with the consumer spinning on try_recv, the mutex at 150–400 ns, so each should be 15–25 times the ring and within a factor of two of the other. Run the producer flat out for throughput but pace it to one item a microsecond for latency, its rdtsc stamped into the u64 and subtracted on pop; against a full ring, latency is only queueing.
2. Pad it. Move head and tail onto one cache line and measure again, then explain the result with Chapter 1’s false-sharing lab. The producer’s store to head takes the line from the consumer’s core and the consumer’s store to tail takes it back, and the cached copies do not help, because they save reads of the other side’s counter and not writes to your own line. Expect the unpadded ring to fall to 30–100 ns an item, and perf c2c to rank that line first by HITM events.
3. Map versus array. Make 10 million lookups of instrument id to Position over random ids below 64: HashMap<u32, Position> with the default hasher, then with your FxHash, then Vec<Position> indexed by id, passing each result through black_box (which hides a value from the optimiser). Run ./lookup map 10000000, ./lookup fx 10000000 and ./lookup array 10000000 under perf stat -e cache-misses,L1-dcache-load-misses,instructions. Predict 20–50 ns, 5–15 ns and 1 ns a lookup, so 200–500 ms, 50–150 ms and about 10 ms a run, and predict the misses: near zero for all three, because 2 KB of positions and 5,264 bytes of table sit in L1, so the difference is in instructions. Then repeat with 100,000 ids, where the table sits in L3 and the map should cost 50–100 ns a lookup against the array’s 10–40, two lines touched to one.
4. Zero allocation. Run the ring benchmark under Chapter 2’s counting global allocator, read the count after warm-up and again at the end, and assert that they are equal. Start the count once both threads are running, since spawning allocates, and preallocate the histogram, because the counter sees every thread. Then do the same for std::sync::mpsc::channel() and watch it fail: its unbounded channel allocates a block for every 31 items, about 3.2 million allocations over 100 million items. Predict first whether sync_channel(4096), whose buffer is allocated once, passes.
5. Stretch: the bitmap. Keep a 64-bit bitmap over 64 buckets and find the next set bit above index i by masking off bits 0 to i and calling trailing_zeros; compare it with a linear scan over [bool; 64], varying the distance to the next set bit from 1 to 63, fixed and random. Predict where the two cross. The bit-scan costs about 1 ns at any distance; the scan costs about 1 ns per 8 bytes plus a mispredict of 15–20 cycles at the exit, so at a fixed distance, where the predictor learns the exit, the two should cross near 8 buckets, and at random distances the scan pays 4–13 ns and never catches up. Confirm tzcnt and no loop in cargo asm, and the difference in perf stat -e branch-misses.

Check: everyone can draw the ring buffer with its two indices and explain which thread owns which cache line. A good answer says that the producer owns head and the slots it is writing, and the consumer owns tail and the slots it is reading; that each counter sits on a line of its own; that each slot line crosses once, from producer to consumer, at 50–100 ns, which is the price of the data; and that the cached copies mean a push reads no line the consumer writes.