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

[Yury Norov <ynorov@nvidia.com>]

On Wed, Jul 15, 2026 at 01:00:12AM -0400, Yury Norov wrote:
> 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.

So, I ran some experiments: 5 times with barriers, and 5 times without,
and repeated it for reverse order of capacities. 

The results are:

Experiment               1,000,000             100,000
Bitmap allocate    −0.28% (p=.631)    −5.63% (p=.0039)
Bitmap release     +0.89% (p=.247)     −1.30% (p=.089)
IDA    allocate    −0.03% (p=.971)    −19.98% (p=.035)
IDA    release     −0.27% (p=.315)     +1.38% (p=.165)
Maple  allocate    +0.09% (p=.579)     −1.06% (p=.529)
Maple  release     −0.54% (p=.315)     +0.03% (p=.971)
                            10,000              1,000
Bitmap allocate    +5.19% (p=.853)    −3.17% (p=.739)
Bitmap release     −2.16% (p=.853)    −0.45% (p=.912)
IDA    allocate    −3.42% (p=.247)    −6.80% (p=.190)
IDA    release     −1.21% (p=.315)    −5.39% (p=.063)
Maple  allocate    −1.81% (p=.529)    −0.32% (p=.529)
Maple  release     +1.39% (p=.739)    +0.11% (p=.631)

The barriers were only present in allocation loops, so release
measurements serve as a negative control. Most effects are small
and statistically insignificant.

Two allocation comparisons have unadjusted p < .05, but both show
barriers making execution faster. Across all 24 comparisons, neither
survives Holm/Bonferroni correction; the smallest adjusted p-value
is approximately .093.

Codegeneration-wise, both objects have:

 - Identical text size: 2,413 bytes.
 - Identical instruction count.
 - No additional loads, spills, or fences.

The barriers only changed scheduling of a few independent instructions:

 - Bitmap: loop-counter increment moved across __bitmap_set().
 - IDA: counter increment and ID accumulation swapped.
 - Maple Tree: region_indexes[] store moved relative to the
   loop-bound comparison.

There is no code-generation change capable to produce visible performance
impact.

With all that, I'll drop the barriers. Instead, I've added the
WARN_ON(!xxx_empty()) after the release completion for the data
structures: to ensure the release is not optimized, and to
additionally enforce integrity. 

Thanks,
Yury