Re: [RFC PATCH v3 00/13] lib, sched: Introduce sparsebitmap (sbm)

[K Prateek Nayak]

Hello Chenyu,

On 10/3/2026 2:40 PM, Chen Yu wrote:
> Hello Prateek!
> 
> Thanks for bringing this interesting topic,
> 
> On Thu, Oct 01, 2026 at 07:28:36PM +0000, K Prateek Nayak wrote:
>>
>> Problem
>> =======
>>
>>                                             %cycles vs global mask operation
>>
>> global mask                                     : 100.0000%  (var: 3.28%)
>> per-NUMA mask                                   :  32.9209%  (var: 7.77%)
>> per-LLC mask                                    :   1.2977%  (var: 4.85%)
>> per-LLC mask (u8 operation; no LOCK prefix)     :   0.4930%  (var: 0.83%)
>>
> 
> This shows a significant latency improvement, especially in the per-LLC (u64, u8) case.
> May I know if schbench / sched-messaging were used?

No, this was a custom benchmark with two threads per
CPU - one setting the CPU on bitmask, and other clearing it,
continuously yielding to each other.

It gives an idea of what the worst case looks like when there
may be short idling followed by a short runtime going in
cycles.

> 
>>
>> Future work
>> ===========
>>
>> o Interoperability with cpumaks since sbm lose the crucial optimizations
>>   that come naturally from for_each_cpu_and() iterations.
>>
>> o Different data representation - using the u8 variant for updates and
>>   then perform a "gather" operation to build a dense mask.
>>
>> o Extending sbm work to help in wakeup (and possibly resurrect Mel's
>>   optimization from [4] in some form). The current sbm is still far away
>>   from being used for wakeups since  updates  to sbm leaf, even on a
>>   16CPUs per LLC system is visible in benchmark performance (~8-10%).
>>
> 
> If we leverage sbm for the wakeup path, it is a per-LLC mask, there seems to be
> no much difference from Mel Gorman's proposal of allocating per sd_share
> unsigned long idle_cpus_span[]?

Ack! But the current form is still pretty expensive. I see about a
10% overhead of just maintaining that mask which is what I'm trying
to reduce.

> The frequent update to this mask might still cause
> c2c latency within 1 LLC. A wild guess is that maybe the u8 version is more suitable,
> because it has only max-to-8 CPUs touching the mask at the same time?

With a 64B cacheline, single cacheline can contain data for up to
64 CPUs - unlike current sbm that uses first 8-bytes, this used
the whole 64 bytes.

P.S. All versions were tested with 16 CPUs per LLC on my systems.

Going from atomic u64 to plain u8 writes probably avoids an
expensive atomic path in the H/W making them faster.

> My understanding is that the major case that sbm could fit is turning the global bitmask
> into a per-LLC bitmask, because it mainly avoids CPUs on different LLC/node writing the
> same cache line frequently (nohz.idle_cpus_mask set via nohz_balance_enter_idle() on
> many CPUs, etc), which might cause a costly cache RFO event storm. Meanwhile, with sbm,
> at the reader side, _nohz_idle_balance() could start scanning from the current CPU to find
> an idle CPU, so as to avoid the costly HITM event - the reader is on LLC1, while the writer
> is on LLC0 - so maybe:
> 
> for_each_cpu_wrap(balance_cpu, nohz.idle_cpus_mask, this_cpu+1)
> 
> could start from this_cpu's LLC sibling first, rather than this_cpu + 1, because this_cpu+1
> might not always be the LLC sibling of this_cpu.

Ah! Good point. Let me see if wrapping within the bitmask leaf
first and then going out makes any difference. 

> 
> I found that in the current code, there are also other global mask:
> rd->rto_mask(mentioned by Pan Deng when running ffmpeg[1])
> rd->dlo_mask
> tick_broadcast_**mask
> maybe they can also be converted into sbm.

Ack! I was juts getting started somewhere to see if there is an
appetite for sbm :-)

> 
> [1] https://lore.kernel.org/lkml/a3207ebf537bbe5605ff5454f63b5604d83a04a0.1753076363.git.pan.deng@xxxxxxxxx/
> 
> thanks,
> Chenyu 

-- 
Thanks and Regards,
Prateek