Rosebush Proposed As A New Data Structure For The Linux Kernel

Matthew Wilcox with Oracle who previously worked on the Maple Tree data structure for the Linux kernel along with memory folios has now proposed "Rosebush" as a new hash table data structure for the Linux kernel.

Rosebush is described as a resizing, scalable, cache-aware RCU-optimized hash table for the kernel. Rosebush is suitable to replace a hash table while having lower overhead than the maple tree or rhashtable. But it's not a replacement to the maple tree as it doesn't support ranges. Another described benefit of Rosebush is having per-bucket locks so it's more scalable for write-heavy workloads.

While Rosebush sounds nice as a new hash table for the Linux kernel, Wilcox hasn't converted any existing kernel code yet to using it. So ultimately the real-world performance benefits are yet to be proven.

In any event those interested in learning more about Rosebush data structure for the Linux kernel can do so via the RFC mailing list message.