A hash table by any other name

On June 25, Matthew Wilcox introduced a new data structure called rosebush, designed as a scalable, cache-aware hash table optimized for the Linux kernel's directory-entry cache (dcache). This structure aims to improve performance compared to the existing rhashtable by avoiding linked lists, which can lead to inefficient memory access patterns. Rosebush maintains a similar API to rhashtable but utilizes fixed-size arrays for buckets, allowing for more efficient cache usage during lookups. The design includes a two-level structure where the hash selects a bucket from an array, followed by a linear scan within that bucket. This method reduces cache misses, particularly during dependent cache accesses.

Rosebush supports concurrent access through read-copy-update (RCU), allowing for efficient reads while minimizing locking overhead during resizing operations. Unlike rhashtable, which uses intrusive linked lists, rosebush's design permits items to be stored in multiple structures without additional memory overhead. The patch set has received mixed feedback, with some reviewers questioning the performance claims without empirical data. Wilcox's assertions about rosebush's efficiency stem from the assumption that rhashtable's average bucket length is longer than expected, which may not hold true in practice. The ongoing discussion among developers highlights the complexities of hash table performance and the importance of empirical validation in evaluating new data structures.