Skip to contentSkip to conversation

sched/fair: Improve nohz fields for large systems

PATCH Superseded Shrikanth Hegde 4 participants 13 messages Jan 12 – Jan 13 Scheduler

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

v4 cover sched/fair: Improve nohz fields for large systems

Running on large systems nohz.nr_cpus cacheline was seen as contended. There is atomic inc/dec and read happening on many
CPUs at a time and it is possible for this line to bounce often.

1st and 2nd patch are minor ones. Looks like correct things to do. Not very important ones.

3rd patch: Main patch which is to get rid of nr_cpus.Instead, use the cpumask which is always updated alongside with it. Functionally it should serve the same purpose. Rest of the fields aren't updated that often. So this line shouldn't bounce that often.

Contention issue with nohz.idle_cpus_mask still remains. Mostly it is in separate cacheline than nohz. There are ongoing efforts to mitigate it. It is not addressed by this series.

v3 -> v4:
- Added to changelog on one less cacheline being dirtied on idle entry/exit (Valentin Schneider)

v2 -> v3:
- Converted out to return when there are no CPU is in tickless mode since find_ilb_cpu returns anyway (K Prateek Nayak)

v1 -> v2:
- Dropped patch to check has_blocked based on time.
- Detailed changelog for removing nr_cpus (Thanks to Ingo Molnar)

v1: https://lore.kernel.org/all/[email protected]/
v2: https://lore.kernel.org/all/[email protected]/
v3: https://lore.kernel.org/all/[email protected]/

Shrikanth Hegde (3):
sched/fair: Move checking for nohz cpus after time check sched/fair: Change likelyhood of nohz.nr_cpus sched/fair: Remove nohz.nr_cpus and use weight of cpumask instead

 kernel/sched/fair.c | 21 +++++++++++----------
 1 file changed, 11 insertions(+), 10 deletions(-)
Signature · 1 line
2.47.3
#1 lore raw

PATCH v4 1/3 sched/fair: Move checking for nohz cpus after time check

NOHZ idle load balancer is kicked off only after time check. So move the atomic read after the time check to access it only when needed.

When there are no idle CPUs(100% busy), even if the flag gets set to NOHZ_STATS_KICK | NOHZ_NEXT_KICK, find_new_ilb will fail and there will be no NOHZ idle balance. The current behaviour is retained.

Note: This patch doesn't solve any cacheline overheads. No improvement in performance apart from saving a few cycles of atomic_read.

---
 kernel/sched/fair.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -7
index 9743fc0b225c..17e4e8ac5fca 100644
@@ -12451,20 +12451,24 @@ static void nohz_balancer_kick(struct rq *rq)
 	 */
 	nohz_balance_exit_idle(rq);
 
-	/*
-	 * None are in tickless mode and hence no need for NOHZ idle load
-	 * balancing:
-	 */
-	if (likely(!atomic_read(&nohz.nr_cpus)))
-		return;
-
 	if (READ_ONCE(nohz.has_blocked_load) &&
 	    time_after(now, READ_ONCE(nohz.next_blocked)))
 		flags = NOHZ_STATS_KICK;
 
+	/*
+	 * If none are in tickless mode, though flag maybe set,
+	 * idle load balancing is not done as find_new_ilb fails
+	 */
 	if (time_before(now, nohz.next_balance))
 		goto out;
 
+	/*
+	 * None are in tickless mode and hence no need for NOHZ idle load
+	 * balancing:
+	 */
+	if (likely(!atomic_read(&nohz.nr_cpus)))
+		return;
+
 	if (rq->nr_running >= 2) {
 		flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK;
 		goto out;
Signature · 1 line
2.47.3
maintainer
#2 lore raw

Re: [PATCH v4 1/3] sched/fair: Move checking for nohz cpus after time check

Quoted 10 lines · Shrikanth Hegde

NOHZ idle load balancer is kicked off only after time check. So move the atomic read after the time check to access it only when needed.

When there are no idle CPUs(100% busy), even if the flag gets set to NOHZ_STATS_KICK | NOHZ_NEXT_KICK, find_new_ilb will fail and there will be no NOHZ idle balance. The current behaviour is retained.

Note: This patch doesn't solve any cacheline overheads. No improvement in performance apart from saving a few cycles of atomic_read.

But won't these cycles be then wasted by calling needlessly kick_ilb

Quoted 45 lines
---
 kernel/sched/fair.c | 18 +++++++++++-------
 1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -8
index 9743fc0b225c..17e4e8ac5fca 100644
@@ -12451,20 +12451,24 @@ static void nohz_balancer_kick(struct rq *rq)
         */
        nohz_balance_exit_idle(rq);
 
-       /*
-        * None are in tickless mode and hence no need for NOHZ idle load
-        * balancing:
-        */
-       if (likely(!atomic_read(&nohz.nr_cpus)))
-               return;
-
        if (READ_ONCE(nohz.has_blocked_load) &&
            time_after(now, READ_ONCE(nohz.next_blocked)))
                flags = NOHZ_STATS_KICK;
 
+       /*
+        * If none are in tickless mode, though flag maybe set,
+        * idle load balancing is not done as find_new_ilb fails
+        */
        if (time_before(now, nohz.next_balance))
                goto out;
 
+       /*
+        * None are in tickless mode and hence no need for NOHZ idle load
+        * balancing:
+        */
+       if (likely(!atomic_read(&nohz.nr_cpus)))
+               return;
+
        if (rq->nr_running >= 2) {
                flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK;
                goto out;
--

2.47.3

#3 lore raw

Re: [PATCH v4 1/3] sched/fair: Move checking for nohz cpus after time check

Quoted 5 lines · Vincent Guittot
Quoted 4 lines · Shrikanth Hegde

NOHZ idle load balancer is kicked off only after time check. So move the atomic read after the time check to access it only when needed.

Quoted 9 lines
Quoted 6 lines

When there are no idle CPUs(100% busy), even if the flag gets set to NOHZ_STATS_KICK | NOHZ_NEXT_KICK, find_new_ilb will fail and there will be no NOHZ idle balance. The current behaviour is retained.

Note: This patch doesn't solve any cacheline overheads. No improvement in performance apart from saving a few cycles of atomic_read.

But won't these cycles be then wasted by calling needlessly kick_ilb

when there are nohz cpus, i.e nohz.nr_cpus > 0, there is no change in codeflow.

Only when system is 100%(which is expected to be rare), nohz.nr_cpus == 0, then it is expected that has_blocked_load = 0. So flags shouldn't be set. Note we are still doing a return if nohz.nr_cpus == 0. So kick_ilb shouldn't be called.

Do you see any path still calling kick_ilb un-necessarily?

Quoted 45 lines
Quoted 45 lines
---
  kernel/sched/fair.c | 18 +++++++++++-------
  1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -8
index 9743fc0b225c..17e4e8ac5fca 100644
@@ -12451,20 +12451,24 @@ static void nohz_balancer_kick(struct rq *rq)
          */
         nohz_balance_exit_idle(rq);
 
-       /*
-        * None are in tickless mode and hence no need for NOHZ idle load
-        * balancing:
-        */
-       if (likely(!atomic_read(&nohz.nr_cpus)))
-               return;
-
         if (READ_ONCE(nohz.has_blocked_load) &&
             time_after(now, READ_ONCE(nohz.next_blocked)))
                 flags = NOHZ_STATS_KICK;
 
+       /*
+        * If none are in tickless mode, though flag maybe set,
+        * idle load balancing is not done as find_new_ilb fails
+        */
         if (time_before(now, nohz.next_balance))
                 goto out;
 
+       /*
+        * None are in tickless mode and hence no need for NOHZ idle load
+        * balancing:
+        */
+       if (likely(!atomic_read(&nohz.nr_cpus)))
+               return;
+
         if (rq->nr_running >= 2) {
                 flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK;
                 goto out;
--

2.47.3

maintainer
#4 lore raw

Re: [PATCH v4 1/3] sched/fair: Move checking for nohz cpus after time check

Quoted 16 lines · Shrikanth Hegde
Quoted 12 lines · Vincent Guittot
Quoted 10 lines · Shrikanth Hegde

NOHZ idle load balancer is kicked off only after time check. So move the atomic read after the time check to access it only when needed.

When there are no idle CPUs(100% busy), even if the flag gets set to NOHZ_STATS_KICK | NOHZ_NEXT_KICK, find_new_ilb will fail and there will be no NOHZ idle balance. The current behaviour is retained.

Note: This patch doesn't solve any cacheline overheads. No improvement in performance apart from saving a few cycles of atomic_read.

Quoted 7 lines
Quoted 2 lines

But won't these cycles be then wasted by calling needlessly kick_ilb

when there are nohz cpus, i.e nohz.nr_cpus > 0, there is no change in codeflow.

Only when system is 100%(which is expected to be rare), nohz.nr_cpus == 0, then it is expected that has_blocked_load = 0. So flags shouldn't be set.

The way we are setting/clearing has_blocked_load vs nr_cpus/idle_cpus_mask implies that it's possible to get has_blocked_load == 1 but nr_cpus == 0 although it's a corner case and not a default behavior

No CPUs are idle: nr_cpus == 0

CPU 0 enters idle
- inc nr_cpus and set idle_cpus_mask
- set nohz.has_blocked

CPU0 wakes up

Tick fires on CPU0
- dec nr_cpus and clear idle_cpus_mask
- nohz.has_blocked == 1, most probably now > nohz.next_blocked, if
now < nohz.next_balance, we skip the test of nr_cpus and we call kick_ilb() but nr_cpus == 0 and idle_cpus_mask is empty

Quoted 2 lines

Note we are still doing a return if nohz.nr_cpus == 0. So kick_ilb shouldn't be called.

The return can be skipped by if (time_before(now, nohz.next_balance)) goto out

Quoted 2 lines

Do you see any path still calling kick_ilb un-necessarily?

Yes but at the same time it's clearly not the main case

Quoted 48 lines
Quoted 47 lines
Quoted 47 lines
---
  kernel/sched/fair.c | 18 +++++++++++-------
  1 file changed, 11 insertions(+), 7 deletions(-)
kernel/sched/fair.c +11 -8
index 9743fc0b225c..17e4e8ac5fca 100644
@@ -12451,20 +12451,24 @@ static void nohz_balancer_kick(struct rq *rq)
          */
         nohz_balance_exit_idle(rq);
 
-       /*
-        * None are in tickless mode and hence no need for NOHZ idle load
-        * balancing:
-        */
-       if (likely(!atomic_read(&nohz.nr_cpus)))
-               return;
-
         if (READ_ONCE(nohz.has_blocked_load) &&
             time_after(now, READ_ONCE(nohz.next_blocked)))
                 flags = NOHZ_STATS_KICK;
 
+       /*
+        * If none are in tickless mode, though flag maybe set,
+        * idle load balancing is not done as find_new_ilb fails
+        */
         if (time_before(now, nohz.next_balance))
                 goto out;
 
+       /*
+        * None are in tickless mode and hence no need for NOHZ idle load
+        * balancing:
+        */
+       if (likely(!atomic_read(&nohz.nr_cpus)))
+               return;
+
         if (rq->nr_running >= 2) {
                 flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK;
                 goto out;
--

2.47.3

#5 lore raw

Re: [PATCH v4 1/3] sched/fair: Move checking for nohz cpus after time check

Quoted 44 lines · Vincent Guittot
Quoted 16 lines · Shrikanth Hegde
Quoted 12 lines · Vincent Guittot
Quoted 10 lines · Shrikanth Hegde

NOHZ idle load balancer is kicked off only after time check. So move the atomic read after the time check to access it only when needed.

When there are no idle CPUs(100% busy), even if the flag gets set to NOHZ_STATS_KICK | NOHZ_NEXT_KICK, find_new_ilb will fail and there will be no NOHZ idle balance. The current behaviour is retained.

Note: This patch doesn't solve any cacheline overheads. No improvement in performance apart from saving a few cycles of atomic_read.

Quoted 7 lines
Quoted 2 lines

But won't these cycles be then wasted by calling needlessly kick_ilb

when there are nohz cpus, i.e nohz.nr_cpus > 0, there is no change in codeflow.

Only when system is 100%(which is expected to be rare), nohz.nr_cpus == 0, then it is expected that has_blocked_load = 0. So flags shouldn't be set.

The way we are setting/clearing has_blocked_load vs nr_cpus/idle_cpus_mask implies that it's possible to get has_blocked_load == 1 but nr_cpus == 0 although it's a corner case and not a default behavior

No CPUs are idle: nr_cpus == 0

CPU 0 enters idle
- inc nr_cpus and set idle_cpus_mask
- set nohz.has_blocked

CPU0 wakes up

Tick fires on CPU0
- dec nr_cpus and clear idle_cpus_mask
- nohz.has_blocked == 1, most probably now > nohz.next_blocked, if
now < nohz.next_balance, we skip the test of nr_cpus and we call kick_ilb() but nr_cpus == 0 and idle_cpus_mask is empty

Quoted 5 lines
Quoted 2 lines

Note we are still doing a return if nohz.nr_cpus == 0. So kick_ilb shouldn't be called.

The return can be skipped by if (time_before(now, nohz.next_balance)) goto out

Assuming HZ=1000,

I see LOAD_AVG_PERIOD = 32, whereas next_balance is usually 60. so it is a really narrow window of 28 ticks and system being close to 100% busy.

Quoted 6 lines
Quoted 2 lines

Do you see any path still calling kick_ilb un-necessarily?

Yes but at the same time it's clearly not the main case

So i assume we can do this patch considering the common case? If not, let me know, I can drop it.

maintainer
#6 lore raw

Re: [PATCH v4 1/3] sched/fair: Move checking for nohz cpus after time check

Quoted 61 lines · Shrikanth Hegde
Quoted 44 lines · Vincent Guittot
Quoted 16 lines · Shrikanth Hegde
Quoted 12 lines · Vincent Guittot
Quoted 10 lines · Shrikanth Hegde

NOHZ idle load balancer is kicked off only after time check. So move the atomic read after the time check to access it only when needed.

When there are no idle CPUs(100% busy), even if the flag gets set to NOHZ_STATS_KICK | NOHZ_NEXT_KICK, find_new_ilb will fail and there will be no NOHZ idle balance. The current behaviour is retained.

Note: This patch doesn't solve any cacheline overheads. No improvement in performance apart from saving a few cycles of atomic_read.

Quoted 7 lines
Quoted 2 lines

But won't these cycles be then wasted by calling needlessly kick_ilb

when there are nohz cpus, i.e nohz.nr_cpus > 0, there is no change in codeflow.

Only when system is 100%(which is expected to be rare), nohz.nr_cpus == 0, then it is expected that has_blocked_load = 0. So flags shouldn't be set.

The way we are setting/clearing has_blocked_load vs nr_cpus/idle_cpus_mask implies that it's possible to get has_blocked_load == 1 but nr_cpus == 0 although it's a corner case and not a default behavior

No CPUs are idle: nr_cpus == 0

CPU 0 enters idle
- inc nr_cpus and set idle_cpus_mask
- set nohz.has_blocked

CPU0 wakes up

Tick fires on CPU0
- dec nr_cpus and clear idle_cpus_mask
- nohz.has_blocked == 1, most probably now > nohz.next_blocked, if
now < nohz.next_balance, we skip the test of nr_cpus and we call kick_ilb() but nr_cpus == 0 and idle_cpus_mask is empty

Quoted 5 lines
Quoted 2 lines

Note we are still doing a return if nohz.nr_cpus == 0. So kick_ilb shouldn't be called.

The return can be skipped by if (time_before(now, nohz.next_balance)) goto out

Assuming HZ=1000,

I see LOAD_AVG_PERIOD = 32, whereas next_balance is usually 60. so it is a really narrow window of 28 ticks and system being close to 100% busy.

Quoted 1 line
Quoted 1 line
Quoted 8 lines
Quoted 5 lines
Quoted 1 line

Do you see any path still calling kick_ilb un-necessarily?

Yes but at the same time it's clearly not the main case

So i assume we can do this patch considering the common case? If not, let me know, I can drop it.

Yes, I suppose it's ok.
Could you add a comment in commit so we remember

#7 lore raw

PATCH v4 2/3 sched/fair: Change likelyhood of nohz.nr_cpus

In reply to Shrikanth Hegde

These days most of the system have multi cores. The likelyhood of at least one or more CPUs in nohz (idle state) is higher.

Give accurate hint to the branch predictor.

---
 kernel/sched/fair.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
kernel/sched/fair.c +2 -2
index 17e4e8ac5fca..c03f963f6216 100644
@@ -12464,9 +12464,9 @@ static void nohz_balancer_kick(struct rq *rq)
 
 	/*
 	 * None are in tickless mode and hence no need for NOHZ idle load
-	 * balancing:
+	 * balancing
 	 */
-	if (likely(!atomic_read(&nohz.nr_cpus)))
+	if (unlikely(!atomic_read(&nohz.nr_cpus)))
 		return;
 
 	if (rq->nr_running >= 2) {
Signature · 1 line
2.47.3
#8 lore raw

PATCH v4 3/3 sched/fair: Remove nohz.nr_cpus and use weight of cpumask instead

In reply to Shrikanth Hegde

nohz.nr_cpus was observed as contended cacheline when running enterprise workload on large systems.

Fundamental scalability challenge with nohz.idle_cpus_mask and nohz.nr_cpus is the following:

(1) nohz_balancer_kick() observes (reads) nohz.nr_cpus
(or nohz.idle_cpu_mask) and nohz.has_blocked to see whether there's any nohz balancing work to do, in every scheduler tick.

(2) nohz_balance_enter_idle() and nohz_balance_exit_idle() (through nohz_balancer_kick() via sched_tick()) modify (write) nohz.nr_cpus (and/or nohz.idle_cpu_mask) and nohz.has_blocked.

The characteristic frequencies are the following:

(1) nohz_balancer_kick() happens at scheduler (busy)tick frequency on CPU(which has not gone idle). This is a relatively constant frequency in the ~1 kHz range or lower.

(2) happens at idle enter/exit frequency on every CPU that goes to idle. This is workload dependent, but can easily be hundreds of kHz for IO-bound loads and high CPU counts. Ie. can be orders of magnitude higher than (1), in which case a cachemiss at every invocation of (1) is almost inevitable. idle exit will trigger (1) on the CPU which is coming out of idle.

There's two types of costs from these functions:

(A) scheduler tick cost via (1): this happens on busy CPUs too, and is thus a primary scalability cost. But the rate here is constant and typically much lower than (B), hence the absolute benefit to workload scalability will be lower as well.

(B) idle cost via (2): going-to-idle and coming-from-idle costs are secondary concerns, because they impact power efficiency more than they impact scalability. But in terms of absolute cost this scales up with nr_cpus as well, and a much faster rate, and thus may also approach and negatively impact system limits like memory bus/fabric bandwidth.

Note that nohz.idle_cpus_mask and nohz.nr_cpus may appear to reside in the same cacheline, however under CONFIG_CPUMASK_OFFSTACK=y the backing storage for nohz.idle_cpus_mask will be elsewhere. With CPUMASK_OFFSTACK=n, the nohz.idle_cpus_mask and rest of nohz fields are in different cachelines under typical NR_CPUS=512/2048. This implies two separate cachelines being dirtied upon idle entry / exit.

nohz.nr_cpus can be derived from the mask itself. Its usage doesn't warrant a functionally correct value. This means one less cacheline being dirtied in idle entry/exit path which helps to save some bus bandwidth w.r.t to those nohz functions(approx 50%). This in turn helps to improve enterprise workload throughput.

On system with 480 CPUs, running "hackbench 40 process 10000 loops" (Avg of 3 runs)
baseline:

     0.81%  hackbench          [k] nohz_balance_exit_idle
     0.21%  hackbench          [k] nohz_balancer_kick
     0.09%  swapper            [k] nohz_run_idle_balance

With patch:

     0.35%  hackbench          [k] nohz_balance_exit_idle
     0.09%  hackbench          [k] nohz_balancer_kick
     0.07%  swapper            [k] nohz_run_idle_balance
[Ingo Molnar: scalability analysis changlog]
---
 kernel/sched/fair.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
kernel/sched/fair.c +1 -4
index c03f963f6216..3408a5beb95b 100644
@@ -7144,7 +7144,6 @@ static DEFINE_PER_CPU(cpumask_var_t, should_we_balance_tmpmask);
 
 static struct {
 	cpumask_var_t idle_cpus_mask;
-	atomic_t nr_cpus;
 	int has_blocked_load;		/* Idle CPUS has blocked load */
 	int needs_update;		/* Newly idle CPUs need their next_balance collated */
 	unsigned long next_balance;     /* in jiffy units */
@@ -12466,7 +12465,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	 * None are in tickless mode and hence no need for NOHZ idle load
 	 * balancing
 	 */
-	if (unlikely(!atomic_read(&nohz.nr_cpus)))
+	if (unlikely(cpumask_empty(nohz.idle_cpus_mask)))
 		return;
 
 	if (rq->nr_running >= 2) {
@@ -12579,7 +12578,6 @@ void nohz_balance_exit_idle(struct rq *rq)
 
 	rq->nohz_tick_stopped = 0;
 	cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask);
-	atomic_dec(&nohz.nr_cpus);
 
 	set_cpu_sd_state_busy(rq->cpu);
 }
@@ -12637,7 +12635,6 @@ void nohz_balance_enter_idle(int cpu)
 	rq->nohz_tick_stopped = 1;
 
 	cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
-	atomic_inc(&nohz.nr_cpus);
 
 	/*
 	 * Ensures that if nohz_idle_balance() fails to observe our
Signature · 1 line
2.47.3
reviewer Reviewed-by on v4 3/3
#9 lore raw

Re: [PATCH v4 3/3] sched/fair: Remove nohz.nr_cpus and use weight of cpumask instead

Quoted 61 lines · Shrikanth Hegde

nohz.nr_cpus was observed as contended cacheline when running enterprise workload on large systems.

Fundamental scalability challenge with nohz.idle_cpus_mask and nohz.nr_cpus is the following:

(1) nohz_balancer_kick() observes (reads) nohz.nr_cpus
(or nohz.idle_cpu_mask) and nohz.has_blocked to see whether there's any nohz balancing work to do, in every scheduler tick.

(2) nohz_balance_enter_idle() and nohz_balance_exit_idle() (through nohz_balancer_kick() via sched_tick()) modify (write) nohz.nr_cpus (and/or nohz.idle_cpu_mask) and nohz.has_blocked.

The characteristic frequencies are the following:

(1) nohz_balancer_kick() happens at scheduler (busy)tick frequency on CPU(which has not gone idle). This is a relatively constant frequency in the ~1 kHz range or lower.

(2) happens at idle enter/exit frequency on every CPU that goes to idle. This is workload dependent, but can easily be hundreds of kHz for IO-bound loads and high CPU counts. Ie. can be orders of magnitude higher than (1), in which case a cachemiss at every invocation of (1) is almost inevitable. idle exit will trigger (1) on the CPU which is coming out of idle.

There's two types of costs from these functions:

(A) scheduler tick cost via (1): this happens on busy CPUs too, and is thus a primary scalability cost. But the rate here is constant and typically much lower than (B), hence the absolute benefit to workload scalability will be lower as well.

(B) idle cost via (2): going-to-idle and coming-from-idle costs are secondary concerns, because they impact power efficiency more than they impact scalability. But in terms of absolute cost this scales up with nr_cpus as well, and a much faster rate, and thus may also approach and negatively impact system limits like memory bus/fabric bandwidth.

Note that nohz.idle_cpus_mask and nohz.nr_cpus may appear to reside in the same cacheline, however under CONFIG_CPUMASK_OFFSTACK=y the backing storage for nohz.idle_cpus_mask will be elsewhere. With CPUMASK_OFFSTACK=n, the nohz.idle_cpus_mask and rest of nohz fields are in different cachelines under typical NR_CPUS=512/2048. This implies two separate cachelines being dirtied upon idle entry / exit.

nohz.nr_cpus can be derived from the mask itself. Its usage doesn't warrant a functionally correct value. This means one less cacheline being dirtied in idle entry/exit path which helps to save some bus bandwidth w.r.t to those nohz functions(approx 50%). This in turn helps to improve enterprise workload throughput.

On system with 480 CPUs, running "hackbench 40 process 10000 loops" (Avg of 3 runs)
baseline:

     0.81%  hackbench          [k] nohz_balance_exit_idle
     0.21%  hackbench          [k] nohz_balancer_kick
     0.09%  swapper            [k] nohz_run_idle_balance
Quoted 7 lines

With patch:

     0.35%  hackbench          [k] nohz_balance_exit_idle
     0.09%  hackbench          [k] nohz_balancer_kick
     0.07%  swapper            [k] nohz_run_idle_balance
[Ingo Molnar: scalability analysis changlog]
maintainer
#10 lore raw

Re: [PATCH v4 3/3] sched/fair: Remove nohz.nr_cpus and use weight of cpumask instead

In reply to Shrikanth Hegde
Quoted 62 lines · Shrikanth Hegde

nohz.nr_cpus was observed as contended cacheline when running enterprise workload on large systems.

Fundamental scalability challenge with nohz.idle_cpus_mask and nohz.nr_cpus is the following:

(1) nohz_balancer_kick() observes (reads) nohz.nr_cpus
(or nohz.idle_cpu_mask) and nohz.has_blocked to see whether there's any nohz balancing work to do, in every scheduler tick.

(2) nohz_balance_enter_idle() and nohz_balance_exit_idle() (through nohz_balancer_kick() via sched_tick()) modify (write) nohz.nr_cpus (and/or nohz.idle_cpu_mask) and nohz.has_blocked.

The characteristic frequencies are the following:

(1) nohz_balancer_kick() happens at scheduler (busy)tick frequency on CPU(which has not gone idle). This is a relatively constant frequency in the ~1 kHz range or lower.

(2) happens at idle enter/exit frequency on every CPU that goes to idle. This is workload dependent, but can easily be hundreds of kHz for IO-bound loads and high CPU counts. Ie. can be orders of magnitude higher than (1), in which case a cachemiss at every invocation of (1) is almost inevitable. idle exit will trigger (1) on the CPU which is coming out of idle.

There's two types of costs from these functions:

(A) scheduler tick cost via (1): this happens on busy CPUs too, and is thus a primary scalability cost. But the rate here is constant and typically much lower than (B), hence the absolute benefit to workload scalability will be lower as well.

(B) idle cost via (2): going-to-idle and coming-from-idle costs are secondary concerns, because they impact power efficiency more than they impact scalability. But in terms of absolute cost this scales up with nr_cpus as well, and a much faster rate, and thus may also approach and negatively impact system limits like memory bus/fabric bandwidth.

Note that nohz.idle_cpus_mask and nohz.nr_cpus may appear to reside in the same cacheline, however under CONFIG_CPUMASK_OFFSTACK=y the backing storage for nohz.idle_cpus_mask will be elsewhere. With CPUMASK_OFFSTACK=n, the nohz.idle_cpus_mask and rest of nohz fields are in different cachelines under typical NR_CPUS=512/2048. This implies two separate cachelines being dirtied upon idle entry / exit.

nohz.nr_cpus can be derived from the mask itself. Its usage doesn't warrant a functionally correct value. This means one less cacheline being dirtied in idle entry/exit path which helps to save some bus bandwidth w.r.t to those nohz functions(approx 50%). This in turn helps to improve enterprise workload throughput.

On system with 480 CPUs, running "hackbench 40 process 10000 loops" (Avg of 3 runs)
baseline:

     0.81%  hackbench          [k] nohz_balance_exit_idle
     0.21%  hackbench          [k] nohz_balancer_kick
     0.09%  swapper            [k] nohz_run_idle_balance
Quoted 7 lines

With patch:

     0.35%  hackbench          [k] nohz_balance_exit_idle
     0.09%  hackbench          [k] nohz_balancer_kick
     0.07%  swapper            [k] nohz_run_idle_balance
[Ingo Molnar: scalability analysis changlog]

This change makes sense to me but I'm not convinced by patch1. You wrote in patch 1 that It doesn't provide any real benefit, what are the figures with only patch 3 ?

Quoted 44 lines
---
 kernel/sched/fair.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)
kernel/sched/fair.c +1 -5
index c03f963f6216..3408a5beb95b 100644
@@ -7144,7 +7144,6 @@ static DEFINE_PER_CPU(cpumask_var_t, should_we_balance_tmpmask);
 
 static struct {
        cpumask_var_t idle_cpus_mask;
-       atomic_t nr_cpus;
        int has_blocked_load;           /* Idle CPUS has blocked load */
        int needs_update;               /* Newly idle CPUs need their next_balance collated */
        unsigned long next_balance;     /* in jiffy units */
@@ -12466,7 +12465,7 @@ static void nohz_balancer_kick(struct rq *rq)
         * None are in tickless mode and hence no need for NOHZ idle load
         * balancing
         */
-       if (unlikely(!atomic_read(&nohz.nr_cpus)))
+       if (unlikely(cpumask_empty(nohz.idle_cpus_mask)))
                return;
 
        if (rq->nr_running >= 2) {
@@ -12579,7 +12578,6 @@ void nohz_balance_exit_idle(struct rq *rq)
 
        rq->nohz_tick_stopped = 0;
        cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask);
-       atomic_dec(&nohz.nr_cpus);
 
        set_cpu_sd_state_busy(rq->cpu);
 }
@@ -12637,7 +12635,6 @@ void nohz_balance_enter_idle(int cpu)
        rq->nohz_tick_stopped = 1;
 
        cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
-       atomic_inc(&nohz.nr_cpus);
 
        /*
         * Ensures that if nohz_idle_balance() fails to observe our
--

2.47.3

#11 lore raw

Re: [PATCH v4 3/3] sched/fair: Remove nohz.nr_cpus and use weight of cpumask instead

Hi Vincent.

Quoted 12 lines
Quoted 12 lines

On system with 480 CPUs, running "hackbench 40 process 10000 loops" (Avg of 3 runs)
baseline:

      0.81%  hackbench          [k] nohz_balance_exit_idle
      0.21%  hackbench          [k] nohz_balancer_kick
      0.09%  swapper            [k] nohz_run_idle_balance

With patch:

      0.35%  hackbench          [k] nohz_balance_exit_idle
      0.09%  hackbench          [k] nohz_balancer_kick
      0.07%  swapper            [k] nohz_run_idle_balance
Quoted 7 lines
Quoted 2 lines
[Ingo Molnar: scalability analysis changlog]

This change makes sense to me but I'm not convinced by patch1. You wrote in patch 1 that It doesn't provide any real benefit, what are the figures with only patch 3 ?

Whole point of patch 1 is, (assuming normal case i.e system wont be 100% busy)

- we read the value and then do time check.
- we bail out if time is not due.

Why bother reading, if time is not due.

I won't expect patch1 to make any major difference. But seemed like right thing to do, considering that most of the time system won't be 100% busy.

So numbers will be same without patch1.

Quoted 44 lines
Quoted 44 lines
---
  kernel/sched/fair.c | 5 +----
  1 file changed, 1 insertion(+), 4 deletions(-)
kernel/sched/fair.c +1 -5
index c03f963f6216..3408a5beb95b 100644
@@ -7144,7 +7144,6 @@ static DEFINE_PER_CPU(cpumask_var_t, should_we_balance_tmpmask);
 
  static struct {
         cpumask_var_t idle_cpus_mask;
-       atomic_t nr_cpus;
         int has_blocked_load;           /* Idle CPUS has blocked load */
         int needs_update;               /* Newly idle CPUs need their next_balance collated */
         unsigned long next_balance;     /* in jiffy units */
@@ -12466,7 +12465,7 @@ static void nohz_balancer_kick(struct rq *rq)
          * None are in tickless mode and hence no need for NOHZ idle load
          * balancing
          */
-       if (unlikely(!atomic_read(&nohz.nr_cpus)))
+       if (unlikely(cpumask_empty(nohz.idle_cpus_mask)))
                 return;
 
         if (rq->nr_running >= 2) {
@@ -12579,7 +12578,6 @@ void nohz_balance_exit_idle(struct rq *rq)
 
         rq->nohz_tick_stopped = 0;
         cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask);
-       atomic_dec(&nohz.nr_cpus);
 
         set_cpu_sd_state_busy(rq->cpu);
  }
@@ -12637,7 +12635,6 @@ void nohz_balance_enter_idle(int cpu)
         rq->nohz_tick_stopped = 1;
 
         cpumask_set_cpu(cpu, nohz.idle_cpus_mask);
-       atomic_inc(&nohz.nr_cpus);
 
         /*
          * Ensures that if nohz_idle_balance() fails to observe our
--

2.47.3

#12 lore raw
In reply to Shrikanth Hegde

Hello Shrikanth,

Quoted 12 lines · Shrikanth Hegde

Running on large systems nohz.nr_cpus cacheline was seen as contended. There is atomic inc/dec and read happening on many
CPUs at a time and it is possible for this line to bounce often.

1st and 2nd patch are minor ones. Looks like correct things to do. Not very important ones.

3rd patch: Main patch which is to get rid of nr_cpus.Instead, use the cpumask which is always updated alongside with it. Functionally it should serve the same purpose. Rest of the fields aren't updated that often. So this line shouldn't bounce that often.

Quoted 7 lines

Contention issue with nohz.idle_cpus_mask still remains. Mostly it is in separate cacheline than nohz. There are ongoing efforts to mitigate it. It is not addressed by this series.

v3 -> v4:
- Added to changelog on one less cacheline being dirtied on idle entry/exit (Valentin Schneider)

I tested the v3 over the weekend and didn't spot any regressions (at least none that I can reproduce consistently) so feel free to include:

If anyone is curious, following are results from my setup (3rd Generation EPYC, 2 socket x 64/128T, boost on, C2 disabled):

Note: tbench hit some insane luck on higher utilization runs. I haven't been able to reproduce those regressions reliably. Most data points that show regression also have high run to run variance on both tip and tip + patch making them unreliable.

==================================================================
Test : hackbench
Units : Normalized time in seconds
Interpretation: Lower is better
Statistic : AMean
==================================================================
Case: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

   1-groups     1.00 [ -0.00]( 6.43)     1.04 [ -3.60](15.15)
   2-groups     1.00 [ -0.00]( 5.42)     1.02 [ -2.17]( 3.57)
   4-groups     1.00 [ -0.00]( 2.72)     0.99 [  0.84]( 3.11)
   8-groups     1.00 [ -0.00]( 3.65)     1.00 [  0.31]( 2.50)
  16-groups     1.00 [ -0.00]( 2.26)     1.02 [ -1.67]( 2.92)

==================================================================
Test : tbench
Units : Normalized throughput
Interpretation: Higher is better
Statistic : AMean
==================================================================
Clients: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

      1     1.00 [  0.00]( 0.40)     1.00 [ -0.25]( 1.22)
      2     1.00 [  0.00]( 1.33)     0.99 [ -0.57]( 0.37)
      4     1.00 [  0.00]( 0.27)     1.00 [  0.07]( 0.89)
      8     1.00 [  0.00]( 0.53)     0.99 [ -0.83]( 0.32)
     16     1.00 [  0.00]( 1.39)     1.00 [  0.11]( 1.92)
     32     1.00 [  0.00]( 1.85)     0.99 [ -1.44]( 3.08)
     64     1.00 [  0.00]( 1.55)     0.98 [ -2.17]( 2.51)
    128     1.00 [  0.00]( 1.05)     0.94 [ -6.11]( 0.28)
    256     1.00 [  0.00]( 0.68)     0.94 [ -5.58]( 3.77)
    512     1.00 [  0.00]( 0.30)     0.95 [ -4.91]( 0.22)
   1024     1.00 [  0.00]( 0.19)     0.95 [ -4.86]( 0.21)

==================================================================
Test : stream-10
Units : Normalized Bandwidth, MB/s
Interpretation: Higher is better
Statistic : HMean
==================================================================
Test: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

   Copy     1.00 [  0.00]( 8.08)     1.03 [  2.91]( 4.84)
  Scale     1.00 [  0.00]( 5.43)     1.04 [  3.56]( 3.32)
    Add     1.00 [  0.00]( 5.96)     1.04 [  4.10]( 2.96)
  Triad     1.00 [  0.00]( 6.36)     0.99 [ -1.23]( 5.83)

==================================================================
Test : stream-100
Units : Normalized Bandwidth, MB/s
Interpretation: Higher is better
Statistic : HMean
==================================================================
Test: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

   Copy     1.00 [  0.00]( 3.78)     1.03 [  3.17]( 1.90)
  Scale     1.00 [  0.00]( 4.17)     1.02 [  1.79]( 0.91)
    Add     1.00 [  0.00]( 1.97)     1.01 [  0.52]( 1.66)
  Triad     1.00 [  0.00]( 2.28)     0.99 [ -1.49]( 4.44)

==================================================================
Test : schbench
Units : Normalized 99th percentile latency in us
Interpretation: Lower is better
Statistic : Median
==================================================================
#workers: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

    1     1.00 [ -0.00](33.02)     1.21 [-20.59]( 8.06)
    2     1.00 [ -0.00](14.30)     1.14 [-14.29]( 6.45)
    4     1.00 [ -0.00]( 2.22)     0.98 [  2.22]( 4.55)
    8     1.00 [ -0.00]( 4.63)     0.94 [  5.56]( 1.96)
   16     1.00 [ -0.00]( 1.67)     1.07 [ -6.67]( 1.82)
   32     1.00 [ -0.00]( 5.58)     0.99 [  1.04]( 2.11)
   64     1.00 [ -0.00]( 6.03)     0.99 [  0.52]( 5.25)
  128     1.00 [ -0.00]( 7.09)     1.00 [ -0.49]( 5.11)
  256     1.00 [ -0.00]( 3.14)     0.94 [  6.06](13.53)
  512     1.00 [ -0.00]( 0.86)     0.98 [  2.23]( 1.53)

==================================================================
Test : new-schbench-requests-per-second
Units : Normalized Requests per second
Interpretation: Higher is better
Statistic : Median
==================================================================
#workers: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

    1     1.00 [  0.00]( 0.14)     1.00 [  0.00]( 0.52)
    2     1.00 [  0.00]( 0.14)     1.00 [  0.28]( 0.00)
    4     1.00 [  0.00]( 0.14)     1.00 [  0.00]( 0.00)
    8     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.14)
   16     1.00 [  0.00]( 0.00)     1.00 [  0.00]( 0.00)
   32     1.00 [  0.00]( 5.05)     0.97 [ -3.11]( 1.91)
   64     1.00 [  0.00](10.41)     1.06 [  5.60]( 3.79)
  128     1.00 [  0.00]( 0.30)     0.98 [ -2.38]( 0.31)
  256     1.00 [  0.00]( 1.43)     0.98 [ -1.73]( 1.38)
  512     1.00 [  0.00]( 1.45)     0.97 [ -3.33]( 1.48)

==================================================================
Test : new-schbench-wakeup-latency
Units : Normalized 99th percentile latency in us
Interpretation: Lower is better
Statistic : Median
==================================================================
#workers: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

    1     1.00 [ -0.00](24.99)     1.08 [ -8.33](16.90)
    2     1.00 [ -0.00]( 0.00)     1.40 [-40.00](18.20)
    4     1.00 [ -0.00](12.06)     1.27 [-27.27]( 7.75)
    8     1.00 [ -0.00](14.13)     0.90 [ 10.00](23.66)
   16     1.00 [ -0.00](15.96)     1.09 [ -9.09]( 7.45)
   32     1.00 [ -0.00](12.06)     0.91 [  9.09](18.23)
   64     1.00 [ -0.00](15.78)     1.06 [ -6.25](13.18)
  128     1.00 [ -0.00](10.57)     1.03 [ -3.41]( 5.15)
  256     1.00 [ -0.00]( 0.32)     1.00 [ -0.00]( 0.21)
  512     1.00 [ -0.00]( 0.00)     1.00 [  0.38]( 0.20)

==================================================================
Test : new-schbench-request-latency
Units : Normalized 99th percentile latency in us
Interpretation: Lower is better
Statistic : Median
==================================================================
#workers: tip[pct imp](CV) nohz_no_nr_cpus[pct imp](CV)

    1     1.00 [ -0.00]( 0.00)     1.00 [ -0.27]( 1.79)
    2     1.00 [ -0.00]( 0.74)     0.96 [  4.07]( 1.90)
    4     1.00 [ -0.00]( 0.37)     0.96 [  3.83]( 1.91)
    8     1.00 [ -0.00]( 1.02)     1.00 [ -0.28]( 1.52)
   16     1.00 [ -0.00]( 1.61)     1.00 [  0.28]( 1.86)
   32     1.00 [ -0.00]( 9.22)     1.04 [ -3.52]( 6.84)
   64     1.00 [ -0.00]( 6.39)     1.06 [ -5.96](22.58)
  128     1.00 [ -0.00]( 1.08)     1.12 [-12.43]( 4.61)
  256     1.00 [ -0.00]( 6.10)     1.01 [ -0.77]( 4.87)
  512     1.00 [ -0.00]( 1.41)     1.01 [ -1.03]( 1.27) 
Signature · 2 lines
Thanks and Regards,
Prateek