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

[Pedro Falcato]

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.

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

There are also other pressing questions about the benchmark itself:
it's pretty much the ideal scenario for bitmap. 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. 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.

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

-- 
Pedro