On Tue, Apr 26, 2022 at 01:08:57PM -0700, Andrew Morton wrote: > On Tue, 26 Apr 2022 15:06:19 +0000 Liam Howlett <liam.howlett@xxxxxxxxxx> wrote: > > The maple tree is an RCU-safe range based B-tree designed to use modern > > processor cache efficiently. There are a number of places in the kernel > > I think it would be helpful to expand on "a number of places". > Specifically which places? The page cache would be a good place to use it once it has a few more features to bring it up to par with the radix tree. I can go into more detail if you want. In general, anywhere that's using the IDR/Radix Tree/XArray would benefit. The radix tree has some pretty poor space consumption properties, particularly for anyone using the cyclic variants. Many users of the rbtree would have better performance if converted to the maple tree. Ultimately, it's going to be incumbent on people who know their own chunk of the kernel to say "Oh, yes, I can use that data structure", rather than on Liam to go around converting everybody's code for them.
