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

[Yury Norov <ynorov@nvidia.com>]

On Sat, Jul 11, 2026 at 02:51:28PM +0100, Gary Guo wrote:

...

> > +static unsigned long __init benchmark_bitmap(unsigned long capacity)
> > +{
> > +	unsigned long count, index;
> > +	ktime_t alloc_time, free_time;
> > +	size_t memory;
> > +
> > +	bitmap_zero(alloc_bitmap, MAP_SIZE);
> > +	alloc_time = ktime_get();
> 
> To eliminate possible effects of optimization messing up benchmark, please add a
> barrier() after start timing and a barrier() before end timing. Probably you'd
> want one between each loop iteration too.

It was never a problem in find_bit_benchmark test, but OK.
 
> > +	for (count = 0; count < ARRAY_SIZE(region_sizes); count++) {
> > +		index = bitmap_find_next_zero_area(alloc_bitmap, capacity, 0,
> > +						   region_sizes[count], 0);
> > +		if (index >= capacity)
> > +			break;
> > +
> > +		region_indexes[count] = index;
> > +		bitmap_set(alloc_bitmap, index, region_sizes[count]);
> > +	}
> > +	alloc_time = ktime_get() - alloc_time;
> > +
> > +	index = count;
> > +	free_time = ktime_get();
> > +	while (index--)
> > +		bitmap_clear(alloc_bitmap, region_indexes[index],
> > +			     region_sizes[index]);
> > +	free_time = ktime_get() - free_time;
> > +	memory = BITS_TO_LONGS(capacity) * sizeof(unsigned long);
> > +	pr_err("%-6s   %12llu   %12llu   %8lu   %10zu\n", "bitmap", alloc_time,
> > +		free_time, capacity, memory);
> 
> I wonder if the numbers could be more useful if it is somehow normalized (e.g.
> by how many iterations are performed?)? This number can be computed by adding
> up the prefix of region_sizes until it cover all capacity.
> 
> Also, the capacity should probably be made part of the report header for all 3
> ID allocators. Given this is randomized benchmark the single line, when taken
> out of context, is not very meaningful anyway.
> 
> Something like this might be better (fake numbers below, you might also need
> some fix point printing):
> 
> capacity = 1000000, regions = 100000
> type       alloc (ns/region) free (ns/region) memory (B/capacity)
> bitmap              1795.730           3.421                0.125
> IDA                  465.556         339.314                0.134
> maple                186.296         197.413                1.548
> 
> capacity = 100000, regions = 10000
> bitmap               163.091           3.093                0.125
> IDA                  614.478         335.459                0.142
> maple                174.502         182.503                1.554
> 
> capacity = 10000, regions = 1000
> bitmap                28.448           3.374                0.125
> IDA                  418.978         333.641                0.187
> maple                185.398         211.138                1.563
> 
> capacity = 1000, regions = 100
> bitmap                22.530           6.100                0.128
> IDA                  427.550         364.320                0.144
> maple                197.280         234.740                1.552

I can add the 'regions' column, mostly for completeness. My experience
with find_bit_benchmark is that people mostly ignore it.

Your version may look more 'human friendly', but the reality is that
people understand the original version quite well. This "nice"
formatting is a substantial complication for the log parsers.

Printing anything else, except for the raw test output numbers, is
simply wrong. I don't want to force people to *my* analysis. If you
believe that ns per region is more informative, you can do that
trivial math yourself.

For more serious statistical analysis, one must take into
consideration measurement errors, distribution skewness, random
variables correlations and all that fancy statistical things.

In your example, you divide one random variable, ns, to another,
number of regions. Each of them has its own distribution, and not
necessarily normal. Simple divide operation becomes not so simple,
if you do it right.

I'm not saying that this simple test requires an analysis of such
complexity. I'm saying that raw output numbers are always preferred
at data collection phase.

Thanks,
Yury