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

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:

quoted

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.

quoted

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@intel.com/ (local)

thanks,
Chenyu 

-- 
Thanks and Regards,
Prateek