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

[Onur Özkan]

On Sat, 11 Jul 2026 02:36:01 -0400
Yury Norov <ynorov@xxxxxxxxxx> 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?

Regards,
Onur

> 
> IDA has no region-allocation API, so each region is implemented as
> a sequence of single-ID allocations. The IDs remain contiguous
> because this benchmark fills an initially empty IDA monotonically.
> 
> The benchmark is motivated by the discussion at the link below about
> choosing the best data structure for the channel ID pool with the
> capacity of 2048 IDs for the nova GPU driver.
> 
> Specifically for 2048 IDs the result is:
> 
> bitmap           3907            831       2048          256
> IDA             83545          71007       2048          848
> maple           34632          39710       2048         3600
> 
> Link: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@xxxxxxxxxx/
> Signed-off-by: Yury Norov <ynorov@xxxxxxxxxx>
> ---
> v2: add IDA benchmark (Matthew)
> v1: https://lore.kernel.org/all/20260711013910.349586-1-ynorov@xxxxxxxxxx/
> 
>  MAINTAINERS                  |   3 +
>  lib/Kconfig.debug            |   9 ++
>  lib/Makefile                 |   1 +
>  lib/region_alloc_benchmark.c | 174 +++++++++++++++++++++++++++++++++++
>  4 files changed, 187 insertions(+)
>  create mode 100644 lib/region_alloc_benchmark.c
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 7cc4bca5a2c5..9e487a94aba4 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4615,6 +4615,7 @@ F:	lib/bitmap.c
>  F:	lib/cpumask.c
>  F:	lib/find_bit.c
>  F:	lib/find_bit_benchmark.c
> +F:	lib/region_alloc_benchmark.c
>  F:	lib/test_bitmap.c
>  F:	lib/tests/cpumask_kunit.c
> +		bitmap_count = benchmark_bitmap(capacities[i]);

[...]

> +		ida_count = benchmark_ida(capacities[i]);
> +		maple_count = benchmark_maple_tree(capacities[i]);
> +		WARN_ON(bitmap_count != ida_count);
> +		WARN_ON(bitmap_count != maple_count);
> +	}
> +
> +	/* Let the benchmark be loaded and run repeatedly without rmmod. */
> +	return -EINVAL;
> +}
> +module_init(region_alloc_benchmark);
> +
> +MODULE_AUTHOR("Yury Norov <ynorov@xxxxxxxxxx>");
> +MODULE_DESCRIPTION("Benchmark bitmap, IDA and Maple Tree region allocation");
> +MODULE_LICENSE("GPL");
> -- 
> 2.53.0
>