Repository navigation
SSRB Outperforms Abseil flat_hash_map: O(1) Worst-Case Lookup, Lower Memory Usage and Higher Throughput #2476
VipulxKumarxGoswam
started this conversation in
Ideas
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Overview
I have developed a specialized container engine called Symmetrically Shrinking Radix Bucket (SSRB) optimized specifically for fixed-width 64-bit numeric keys. It guarantees a hard mathematical worst-case profile of O(1) for lookups ,insertions and deletion.
To evaluate its performance against production-grade layouts, I benchmarked it directly against absl::flat_hash_map.
Empirical Benchmark Output
Below is the raw, reproducible terminal output tracking build and lookup performance across a universe of 2,000,000 keys and 1,000,000 query operations (averaged over 10 repetitions):
$ ./ssrb_abesil.exe
SSRB vs GOOGLE ABSL FLAT_HASH_MAP
Universe: 2000000
Queries: 1000000
Repetitions: 10
Stored keys: 1000181
BUILD THROUGHPUT
SSRB 5.462 ms | 183.103 M keys/s
Abseil flat_hash_map 83.149 ms | 12.029 M keys/s
CORRECTNESS TEST
CORRECTNESS: PASS
SUCCESSFUL LOOKUPS
SSRB 6.272 ms | 159.446 M queries/s
Abseil flat_hash_map 36.037 ms | 27.749 M queries/s
UNSUCCESSFUL LOOKUPS
SSRB 6.043 ms | 165.474 M queries/s
Abseil flat_hash_map 28.915 ms | 34.585 M queries/s
50/50 MIXED LOOKUPS
SSRB 6.746 ms | 148.232 M queries/s
Abseil flat_hash_map 38.816 ms | 25.762 M queries/s
============================================
BENCHMARK COMPLETED
Global sink: 0
Performance Vectors
Build Velocity (15x Speedup): SSRB populates at 183.1 M keys/s compared to Abseil’s 12.0 M keys/s. This is achieved by bypassing standard hash calculation pipelines and table resize/rehash allocation pauses.
Lookup Dominance (~5.7x Speedup): In a 50/50 mixed query setting, SSRB handles 148.2 M queries/s against Abseil's 25.7 M queries/s due to strict O(1) hardware cache-aligned coordinate mapping.
Sparse Layout Optimization: Unlike traditional radix layouts, the SSRB structural logic manages sparse integer fields (large gaps between numeric keys) without encountering a catastrophic memory amplification factor.
Reproduction & API Availability
The repository contains the explicit C++ API header
Repository Link: https://github.com/VipulxKumarxGoswam/SSRB
Note on Source Code: To adhere to specific deployment and validation frameworks, the underlying source code implementation is currently kept confidential. However, I am entirely open to coordinating a live demonstration, technical architectural deep dive, or discussing integration paths with a Core Infrastructure Engineer under standard developer parameters.
I would love to get the Abseil maintainers' feedback on these throughput deltas and understand what edge-case workloads or hardware-level limitations you typically look for when evaluating an O(1) numeric tracking system.
All reactions