This presentation introduces Adaptive Hashing, a novel framework arguing that a hash table's performance is optimally achieved by dynamically adjusting its hash function based on the current key set. This approach addresses the limitations of fixed hash functions: universally robust functions (e.g., Murmur) suffer quantifiable performance "regret" and waste computation, while fast, handcrafted functions (e.g., SBCL Prefuzz) risk catastrophic performance degradation (denial-of-service) when key distributions deviate from expectation. The core conceptual contribution is the demonstration of fast, online adaptation within the existing hash table API.
The method is instantiated on Common Lisp's EQ (pointer/integer identity) and EQUAL (value-based) hash tables. For EQ hashing, the adaptation utilizes fast, optimistic, specialized functions (like Pointer-Shift) that exploit common memory allocation patterns (keys as arithmetic progressions) to achieve near-perfect hashing and speed. Adaptation relies on cheap runtime checks, such as maximum collision chain length and collision count during rehash, serving as proxies for performance. Empirical results confirm that adaptive hashing delivers the common-case speed of aggressive, handcrafted functions while retaining the guaranteed worst-case robustness of universal hashes, yielding significant throughput gains (up to 50% in lookup speed for specific workloads) that persist in complex macrobenchmarks.
Adaptive Hashing: Performance Optimization via Online Function Adaptation
The following is a summary of the analysis and findings presented regarding Adaptive Hashing methodology:
0:49 Ubiquity and Cost of Hash Tables: Hash tables represent a substantial, non-asymptotic drag on computational performance, consuming over 2% of total CPU cycles at hyperscale data centers (citing Google C++ codebase metrics).
2:40 Performance Metrics: Traditional cost models rely on the expected number of key comparisons required for lookup. The concept of Regret is defined as the difference between the actual cost and the minimum theoretical cost achievable by a perfect hash function.
4:09 Suboptimality of Uniform Hashing: Hash functions designed to be indistinguishable from a uniform random hash (e.g., Murmur) still exhibit a non-zero expected regret of approximately 0.5 comparisons plus $1/m$ (where $m$ is the number of buckets), demonstrating inherent suboptimality compared to a key-aware perfect hash.
8:34 Fragility of Handcrafted Hashes: While handcrafted functions (e.g., SBCL's Prefuzz) can offer a 10% performance advantage in ideal conditions due to lower computation complexity and better cache locality, they fail catastrophically (e.g., quadratic performance loss) when keys follow unexpected distributions (e.g., single floats having constant low bits).
9:55 Core Adaptive Strategy: The proposed strategy involves changing the hash function online, during the hash table's lifetime, without altering the API. Adaptation costs must be fast enough to avoid negating performance gains, typically amortized during necessary operations like rehash/resize.
12:04 EQ Hash Table Adaptation Path: The system starts with a Constant Hash (linear search on a small vector) for small sizes (under 32 keys) for maximal speed and memory efficiency. Upon reaching a threshold, it transitions to key-aware hashes.
12:41 Pointer-Shift Hash Function: The aggressive, key-aware function used for EQ keys exploits the common behavior of page-based memory allocators (e.g., SBCL's pointer bump mechanism), which generate addresses resembling arithmetic progressions. The function is highly optimized, requiring only a few bitwise instructions per key, by detecting and shifting out constant low bits common to all keys.
16:29 Multi-Level Fallback: The optimistic Pointer-Shift function is safeguarded by collision detection. If collision count or chain length is excessive, the system sequentially falls back: first to the robust Prefuzz hash, and ultimately to the universally robust Murmur3 hash, guaranteeing worst-case performance bounds.
18:31 EQ Microbenchmark Results (Arithmetic Progression): For integer keys forming arithmetic progressions, Adaptive Hashing achieves zero regret (perfect hash). This translates to a notable 50% improvement in lookup speed over Prefuzz (in random lookup tests), demonstrating the benefit of optimal bucketing when cache locality is diminished.
19:35 EQ Microbenchmark Results (Failure Case): In scenarios where Prefuzz fails catastrophically (e.g., single float keys), Adaptive Hashing successfully initiates its fallback sequence: it initially performs better than uniform hashing, detects the degradation, switches to Prefuzz, immediately finds Prefuzz's high collision count, and switches instantly to Murmur3, ensuring robustness.
21:04 EQUAL Hash Table Optimization (String Truncation): For EQUAL hashing, the focus shifts to reducing hash computation time. An aggressive strategy is used, initially hashing only the first and last two characters of a string or prefix of a list. The truncation limit is dynamically doubled if collision chains exceed expected lengths, thereby adapting to avoid performance loss.
21:33 EQUAL Performance Gains: This truncation strategy yields speedups of up to 50% for insertion and lookup in certain ranges, demonstrating that adapting to compute fewer bits is often beneficial when supported by a robust fallback mechanism.
22:14 Macrobenchmark Validation: Performance gains achieved in controlled microbenchmarks translate successfully to real-world, complex workloads, demonstrating that the adaptation overhead is sufficiently low. Overall system throughput improvements of 0.7% (EQ adaptation) and 1.5% (EQUAL adaptation) were observed.
23:02 Limitations: The adaptation logic relies on easily measurable, cheap proxies (collision count, max chain length) for actual performance, which are loose approximations of real-world costs influenced by cache architecture. Implementation of the adaptive scheme is challenging due to the strict low-overhead requirement.