Map Performance Comparison and Judy Data Structure Alternatives
Article Summary
Marko Kevac from Bumble's Platform team benchmarked 6 associative array implementations to replace their aging Judy data structure. The winner? Not what you'd expect when memory matters.
Bumble's C/C++ services handle hundreds of thousands of requests per second with hundreds of gigabytes in memory. Their team tested hash tables and trees from Google, C++ STL, and others against their longtime Judy implementation, measuring both speed and memory overhead with 10 million random lookups.
Key Takeaways
- Google's dense_hash_map was fastest but used excessive memory
- spp::sparse_hash_map delivered best speed-to-memory ratio with 1-bit overhead
- Standard std::hash outperformed xxhash and t1ha for integer keys
- jemalloc allocator boosted speed but increased memory consumption
- Judy trees enable sorted iteration; hash tables sacrifice this for speed
Critical Insight
spp emerged as the top Judy replacement, balancing performance with reasonable memory overhead for high-throughput services.
