CHT-Radix
EE 361C (Multicore Algorithms) project run like a research artifact, with a paper, a reproducibility recipe and citable metadata. Concurrent structures are almost always benchmarked on random keys, so we built five hash-table variants and two radix trees behind one interface and replayed a ShareGPT-derived trace against them. On a synthetic shared-prefix sweep, finer-grained locking made the same radix tree about 13x faster than its global-lock version, peaking at 88.36M ops/sec; on the real trace, p99 latency differed by roughly 40x between hash-table variants.
Case study
Problem
LLM serving engines look up cached prompt prefixes from many threads at once, but concurrent hash tables and tries are usually ranked on uniform or Zipfian random keys. We asked whether those rankings hold on a workload shaped like a real prefix cache, and how hash tables compare with radix trees when prefixes are shared.
Approach
A three-person course team. Seven structures sit behind one C++17 interface, each isolating a synchronization choice: chaining under one global lock or one lock per bucket, cuckoo hashing with optimistic readers or striped locks, hopscotch hashing with optimistic reads, and a 256-way radix trie under one global lock or an atomic pointer walk that locks only leaf values. One harness replays uniform, skewed, cache-resident and read-heavy mixes plus a ShareGPT-derived prefix trace.
Evidence
Two separate experiments. Hash tables on the ShareGPT trace, where about 40% of operations are writes: the ranking from uniform and Zipfian keys no longer holds, and at 16 threads p99 ranged from 1.36 µs (optimistic cuckoo) to 60.84 µs (hopscotch). Radix trees on a synthetic shared-prefix sweep at 8 threads and 95% reads: with 100 shared prefixes, fine-grained synchronization ran 13.47x faster than the global lock (81.86 vs 6.08M ops/s), and with 10 prefixes it peaked at 88.36M ops/s. Medians of three seeded runs on one machine, from experiments_canonical.csv and radix_sweep_canonical.csv, rerunnable from REPRODUCIBILITY.md.
Limits
Fixed-size tables with no resizing, one machine, and uncompressed byte-level tries that never reclaim removed nodes; the fine-grained trie still locks leaf values.
Skills
- C++
- Concurrency
- Multicore
- Data Structures
- Benchmarking
- LLM Caching