Re: [PATCH v2] lib: test bitmap vs IDA vs Maple Tree performance for region allocations

[Yury Norov <ynorov@nvidia.com>]

On Wed, Jul 15, 2026 at 10:41:01PM +0100, Pedro Falcato wrote:
> On Sat, Jul 11, 2026 at 02:36:01AM -0400, Yury Norov wrote:
> > Compare the cost of allocating and freeing variable-sized regions using
> > a bitmap, IDA and a Maple Tree. All implementations process the same
> > randomly generated sequence of region sizes, ranging from 1 to 32 entries,
> > until the configured capacity is exhausted.
> > 
> > Run the benchmark at several capacities to show how the approaches
> > scale. Report allocation and free times separately because bitmap,
> > IDA and Maple Tree removal have substantially different costs.
> > 
> > On x86/kvm, the output example is:
> > 
> > type       alloc (ns)      free (ns)   capacity   memory (B)
> > bitmap      179573071         342105    1000000       125000
> > IDA          46555636       33931498    1000000       134864
> > maple        18629665       19741396    1000000      1548304
> > bitmap        1630912          30933     100000        12504
> > IDA           6144785        3354590     100000        14288
> > maple         1745026        1825032     100000       155408
> > bitmap          28448           3374      10000         1256
> > IDA            418978         333641      10000         1872
> > maple          185398         211138      10000        15632
> > bitmap           2253            610       1000          128
> > IDA             42755          36432       1000          144
> > maple           19728          23474       1000         1552
> > 
> 
> I don't understand the comparison. bitmap, IDA and maple are
> completely different data structures for completely different purposes.

Sure. Please check this link from the patch description:

https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/

The test is very well motivated by that discussion. I'm not saying
it compares apples to apples. I'm trying to quantify the answer to a
very specific question: what is better for NOVA ID allocator. Or more
broadly: what's the best data structure for range ID allocators of a
given capacity.
 
> 1) IDA is 16 bytes when empty, maple is 16 bytes when empty, bitmap
> is $size bytes
> 2) bitmap is statically sized, IDA and maple have to deal with actual
> allocation and freeing of memory
> 3) xarray and maple (especially maple) are optimized for RCU usage and
> have different tradeoffs
> 4) IDA does not support ranges
> 5) xarray (the underlying data structure for IDA) does not support ranges
> in any optimal way
> 6) maple is not optimized for 1-sized ranges, nor ID allocation; it
> actually stores data, so instead of 1 bit per index you get 8 whole
> bytes.
> 7) maple and IDA both handle locking implicitly

Yes, this to some extent follows John's arguments why bitmaps are
preferred for NOVA Id allocator. I'd also add serializeability, if
it's needed.
 
> There are also other pressing questions about the benchmark itself:
> it's pretty much the ideal scenario for bitmap.

It's pretty much the worst scenario for bitmaps, because the test
starts searching for a region from the beginning of the bitmap on
every iteration, making it "Shlemiel the Painter" algorithm with
O(N^2) complexity.

If I wanted to cheat, I'd carry the last allocated ID over the loop.
It would make the complexity O(N). I could choose to start searching
from a random ID, saying it's 'more realistic'. It makes the complexity
converging to O(N*logN). This is how cpumask_*_distribute() works, btw.

So no, this is far from being the ideal scenario.

> doing the find in
> bitmap is essentially testing how far the CPU can speculate, and how
> large the cache is. It's pretty darn large on modern hardware.

Yes, it's a very effective data structure. That's why it's the 2nd
most popular in the kernel, after spinlocks.

> Since you
> never actually free the ranges in any way, every bitmap branch should predict
> extremely well. Fragmentation in the bitmap can very quickly turn into a
> nightmare, while maple will eat it up just fine.

Assuming "fragmentation" is the uniform distribution of free areas, it
wouldn't "turn to nightmare", it would asymptotically turn to O(N*logN).

> These are very different data structures and picking between them requires
> understanding all the tradeoffs. I don't think this benchmark helps with
> that.

OK, I see. You seemingly think that I want to throw all and every data
structure away from the kernel in favor of the bitmaps.

No, I don't.

Thanks,
Yury