On Sat, 11 Jul 2026 02:36:01 -0400 Yury Norov <[email protected]> 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/[email protected]/ > Signed-off-by: Yury Norov <[email protected]> > --- > v2: add IDA benchmark (Matthew) > v1: https://lore.kernel.org/all/[email protected]/ > > 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 <[email protected]>"); > +MODULE_DESCRIPTION("Benchmark bitmap, IDA and Maple Tree region allocation"); > +MODULE_LICENSE("GPL"); > -- > 2.53.0 >
