<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Time to start replacing the use of rhashtable in the code? :-)<br class=""><div><br class=""><blockquote type="cite" class=""><div class="">Begin forwarded message:</div><br class="Apple-interchange-newline"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">From: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">"Matthew Wilcox (Oracle)" <<a href="mailto:willy@infradead.org" class="">willy@infradead.org</a>><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">Subject: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class=""><b class="">[PATCH 0/1] Rosebush, a new hash table</b><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">Date: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">February 22, 2024 at 1:37:23 PM MST<br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">To: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class=""><a href="mailto:linux-kernel@vger.kernel.org" class="">linux-kernel@vger.kernel.org</a><br class=""></span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px;" class=""><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif; color:rgba(0, 0, 0, 1.0);" class=""><b class="">Cc: </b></span><span style="font-family: -webkit-system-font, Helvetica Neue, Helvetica, sans-serif;" class="">"Matthew Wilcox (Oracle)" <<a href="mailto:willy@infradead.org" class="">willy@infradead.org</a>>, Thomas Graf <<a href="mailto:tgraf@suug.ch" class="">tgraf@suug.ch</a>>, Herbert Xu <<a href="mailto:herbert@gondor.apana.org.au" class="">herbert@gondor.apana.org.au</a>>, <a href="mailto:netdev@vger.kernel.org" class="">netdev@vger.kernel.org</a>, <a href="mailto:linux-fsdevel@vger.kernel.org" class="">linux-fsdevel@vger.kernel.org</a>, <a href="mailto:maple-tree@lists.infradead.org" class="">maple-tree@lists.infradead.org</a>, <a href="mailto:rcu@vger.kernel.org" class="">rcu@vger.kernel.org</a><br class=""></span></div><br class=""><div class=""><div class="">Rosebush is a resizing, scalable, cache-aware, RCU optimised hash table.<br class="">I've written a load of documentation about how it works, mostly in<br class="">Documentation/core-api/rosebush.rst but some is dotted through the<br class="">rosebush.c file too.<br class=""><br class="">You can see this code as a further exploration of the "Linked lists are<br class="">evil" design space. For the workloads which a hashtable is suited to,<br class="">it has lower overhead than either the maple tree or the rhashtable.<br class="">It cannot support ranges (so is not a replacement for the maple tree),<br class="">but it does have per-bucket locks so is more scalable for write-heavy<br class="">workloads. I suspect one could reimplement the rhashtable API on top<br class="">of the rosebush, but I am not interested in doing that work myself.<br class=""><br class="">The per-object overhead is 12 bytes, as opposed to 16 bytes for the<br class="">rhashtable and 32 bytes for the maple tree. The constant overhead is also<br class="">small, being just 16 bytes for the struct rosebush. The exact amount<br class="">of memory consumed for a given number of objects is going to depend on<br class="">the distribution of hashes; here are some estimated consumptions for<br class="">power-of-ten entries distributed evenly over a 32-bit hash space in the<br class="">various data structures:<br class=""><br class="">number<span class="Apple-tab-span" style="white-space:pre"> </span>xarray<span class="Apple-tab-span" style="white-space:pre"> </span>maple<span class="Apple-tab-span" style="white-space:pre"> </span>rhash<span class="Apple-tab-span" style="white-space:pre"> </span>rosebush<br class="">1<span class="Apple-tab-span" style="white-space:pre"> </span>3472<span class="Apple-tab-span" style="white-space:pre"> </span>272<span class="Apple-tab-span" style="white-space:pre"> </span>280<span class="Apple-tab-span" style="white-space:pre"> </span>256<br class="">10<span class="Apple-tab-span" style="white-space:pre"> </span>32272<span class="Apple-tab-span" style="white-space:pre"> </span>784<span class="Apple-tab-span" style="white-space:pre"> </span>424<span class="Apple-tab-span" style="white-space:pre"> </span>256<br class="">100<span class="Apple-tab-span" style="white-space:pre"> </span>262kB<span class="Apple-tab-span" style="white-space:pre"> </span>3600<span class="Apple-tab-span" style="white-space:pre"> </span>1864<span class="Apple-tab-span" style="white-space:pre"> </span>2080<br class="">1000<span class="Apple-tab-span" style="white-space:pre"> </span>[1]<span class="Apple-tab-span" style="white-space:pre"> </span>34576<span class="Apple-tab-span" style="white-space:pre"> </span>17224<span class="Apple-tab-span" style="white-space:pre"> </span>16432<br class="">10k<span class="Apple-tab-span" style="white-space:pre"> </span>[1]<span class="Apple-tab-span" style="white-space:pre"> </span>343k<span class="Apple-tab-span" style="white-space:pre"> </span>168392<span class="Apple-tab-span" style="white-space:pre"> </span>131344<br class="">100k<span class="Apple-tab-span" style="white-space:pre"> </span>[1]<span class="Apple-tab-span" style="white-space:pre"> </span>3.4M<span class="Apple-tab-span" style="white-space:pre"> </span>1731272<span class="Apple-tab-span" style="white-space:pre"> </span>2101264<br class=""><br class="">As you can see, rosebush and rhashtable are close the whole way.<br class="">Rosebush moves in larger chunks because it doubles each time; there's<br class="">no actual need to double the bucket size, but that works well with<br class="">the slab allocator's existing slabs. As noted in the documentation,<br class="">we could create our own slabs and get closer to the 12 bytes per object<br class="">minimum consumption. [2]<br class=""><br class="">Where I expect rosebush to shine is on dependent cache misses.<br class="">I've assumed an average chain length of 10 for rhashtable in the above<br class="">memory calculations. That means on average a lookup would take five cache<br class="">misses that can't be speculated. Rosebush does a linear walk of 4-byte<br class="">hashes looking for matches, so the CPU can usefully speculate the entire<br class="">array of hash values (indeed, we tell it exactly how many we're going to<br class="">look at) and then take a single cache miss fetching the correct pointer.<br class="">Add that to the cache miss to fetch the bucket and that's just two cache<br class="">misses rather than five.<br class=""><br class="">I have not yet converted any code to use the rosebush. The API is<br class="">designed for use by the dcache, and I expect it will evolve as it actually<br class="">gets used. I think there's probably some more refactoring to be done.<br class="">I am not aware of any bugs, but the test suite is pitifully small.<br class="">The current algorithm grows the buckets more aggressively than the table;<br class="">that's probably exactly the wrong thing to do for good performance.<br class=""><br class="">This version is full of debugging printks. You should probably take<br class="">them out if you're going to try to benchmark it. The regex '^print'<br class="">should find them all. Contributions welcome; I really want to get back<br class="">to working on folios, but this felt like an urgent problem to be fixed.<br class=""><br class="">[1] I stopped trying to estimate the memory costs for xarray; I couldn't<br class="">be bothered to as it's not a serious competitor for this use case.<br class=""><br class="">[2] We have ideas for improving the maple tree memory consumption for<br class="">this kind of workload; a new node type for pivots that fit in 4 bytes and<br class="">sparse nodes to avoid putting a NULL entry after each occupied entry.<br class="">The maple tree really is optimised for densely packed ranges at the<br class="">moment.<br class=""><br class="">Matthew Wilcox (Oracle) (1):<br class=""> rosebush: Add new data structure<br class=""><br class=""> Documentation/core-api/index.rst | 1 +<br class=""> Documentation/core-api/rosebush.rst | 135 ++++++<br class=""> MAINTAINERS | 8 +<br class=""> include/linux/rosebush.h | 41 ++<br class=""> lib/Kconfig.debug | 3 +<br class=""> lib/Makefile | 3 +-<br class=""> lib/rosebush.c | 707 ++++++++++++++++++++++++++++<br class=""> lib/test_rosebush.c | 135 ++++++<br class=""> 8 files changed, 1032 insertions(+), 1 deletion(-)<br class=""> create mode 100644 Documentation/core-api/rosebush.rst<br class=""> create mode 100644 include/linux/rosebush.h<br class=""> create mode 100644 lib/rosebush.c<br class=""> create mode 100644 lib/test_rosebush.c<br class=""><br class="">-- <br class="">2.43.0<br class=""><br class=""><br class=""></div></div></blockquote></div><br class=""><div class="">
<span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><br class="">Cheers, Andreas<br class=""><br class=""><br class=""><br class=""><br class=""></span>
</div>
<br class=""></body></html>