"Rewrite, Optimize, Repeat: Our Journey Porting a Triemap from C to Rust"
summary
Porting a C TrieMap to Rust starts with a baseline: safe Rust reimplementation (roughly 2x slower and ~2x memory than C) and moves to an optimized unsafe design that matches or outperforms C. Work uses microbenchmarks (Criterion), end-to-end suites, property tests, and Miri checks; implements a custom DST/NodeData with manual alloc/realloc and pointer ops, ends up with 128 unsafe blocks and about 95.6% coverage, and ships in Redis 8.2.
AI-written summary · about
chapters (14)
- 0:00Introduction to C to Rust migration
- 1:08Redis Query Engine overview
- 3:49Incremental rewrite strategy
- 6:29Challenges in real-world ports
- 6:50TrieMap data structure explained
- 11:07C TrieMap memory layout
- 13:50Baseline Rust implementation
- 17:14Benchmarking the baseline
- 18:44Optimized Rust memory layout
- 20:24Custom DST in Rust
- 22:37Heap allocation in unsafe Rust
- 24:58Managing unsafe code safely
- 31:07Porting results and takeaways
- 33:13Q&A session
related talks
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
48mC++ Data Structures That Make Video Games Go Round
01h 05mImplementing Understandable World Class Hash Tables in C++
17mBring Your Own Data Structures to Datalog
59mA Hash Map for Graph Processing Workloads & a Methodology for Transactional Data Structures
57mExtending Redis with Rust
32mBuilding Reliable Infrastructure in Rust
06mUsing STL containers efficiently