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

[Yury Norov]

On Sat, Jul 11, 2026 at 11:27:08AM +0300, Onur Özkan wrote:
> On Sat, 11 Jul 2026 02:36:01 -0400
> Yury Norov <ynorov at nvidia.com> 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
> > 
> > Reported IDA and Maple Tree memory figures exclude slab overhead
> > and transient allocations. The Maple Tree figure is additionally
> > a lower-bound estimate that assumes fully occupied leaf nodes and
> > excludes internal nodes.
> 
> The report itself doesn't make it obvious. I think "memory (B)" can be
> misleading. Perhaps we should use a clearer column name or add a short note
> before/after the report for explaining the columns?

OK, will add.