lib: test bitmap vs IDA vs Maple Tree performance for region allocations

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 regions containing up to 32 entries, until
the configured capacity is exhausted.

The benchmark exercises monotonic allocation into an initially empty pool,
followed by reverse-order freeing. It does not model fragmentation or
interleaved allocation and freeing, nor does it isolate locking or RCU
overhead. Allocation time includes the terminal failed request that detects
exhaustion.

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:

Start testing bitmap vs IDA vs Maple Tree region allocation
memory: bitmap is exact; IDA and Maple Tree are lower bounds
Type      alloc (ns)     free (ns)   regions  capacity  memory (B)
Bitmap      93457345        176151     60644   1000000      125000
Maple       11758660      12870146     60644   1000000     1552656
IDA         31066416      20870824     60644   1000000      134864
Bitmap        919119         17679      6032    100000       12504
Maple        1158193       1187140      6032    100000      154640
IDA          2759670       2116004      6032    100000       14288
Bitmap         17120          2043       613     10000        1256
Maple         116350        117537       613     10000       15888
IDA           243396        202654       613     10000        1872
Bitmap          1220           262        55      1000         128
Maple          12076         10106        55      1000        1552
IDA            25730         20875        55      1000         144
Bitmap           593           124        18       100          16
Maple           3599          4782        18       100         528
IDA             3266          1960        18       100         144
Bitmap           414           129        10        10           8
Maple           2143          1385        10        10         272
IDA              892           648        10        10          16
Region allocation benchmark complete

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.

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 linked 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          5112           615       121      2048         256
Maple          78526         59592       121      2048        3344
IDA           165274        117761       121      2048         848

The benchmark accepts a list of up to 64 nonzero capacities to test.
For example:

  insmod region_alloc_benchmark.ko capacities=1024,2048,4096,65536

The list may contain duplicate capacities. Each occurrence generates a new
region-size sequence, which is useful for collecting statistical
characteristics of the benchmark results.

Link: https://lore.kernel.org/all/20260710-chid-maple-v1-1-4ee869055268@nvidia.com/
Tested-by: Eliot Courtney <ecourtney@nvidia.com>
Reviewed-by: Eliot Courtney <ecourtney@nvidia.com>
Signed-off-by: Yury Norov <ynorov@nvidia.com>

0 files changed, 0 insertions, 0 deletions