Skip to contentSkip to conversation

sched/fair: Wake short task on current CPU

PATCH Superseded Chen Yu 4 participants 9 messages Feb 22, 2023 – Mar 16, 2023 Scheduler

v6 of 8 Superseded Latest is v8 →

lore
Share & tools
lore

Chen Yu

author
#0 lore raw

v6 cover sched/fair: Wake short task on current CPU

The main purpose is to avoid too many cross CPU wake up when it is unnecessary. The frequent cross CPU wake up brings significant damage to some workloads, especially on high core count systems.

Inhibits the cross CPU wake-up by placing the wakee on waking CPU, if both the waker and wakee are short-duration tasks. The short duration task could become a trouble maker on high-load system, because it could bring frequent context switch. This strategy only takes effect when the system is busy. Because it is unreasonable to inhibit the idle CPU scan when there are still idle CPUs.

First, introduce the definition of a short-duration task. Then leverages the first patch to choose a local CPU for wakee.

Overall there is performance improvement on some overloaded case. Such as will-it-scale, netperf. And no noticeable impact on schbench, hackbench, tbench and a OLTP workload with a commercial RDBMS, tested on a Intel Xeon 2 x 56C machine.

Per the test on Zen3 from Prateek, most benchmarks result saw small wins or are comparable to sched:tip. SpecJBB Critical-jOps improved while Max-jOPS saw a small hit, but it might be in the expected range. ycsb-mongodb saw small uplift in NPS1 mode.

Throughput improvement of netperf(localhost) was observed on a Rome 2 x 64C machine, when the number of clients equals the CPUs.

Abel reported against a latency regression from Redis on an overloaded system. Inspired by his description, v5 added the check of wakee_flips to mitigate task stacking.

Changes since v5:
1. Check the wakee_flips of the waker/wakee. If the wakee_flips of waker/wakee are both 0, it indicates that the waker and the wakee are waking up each other. In this case, put them together on the same CPU. This is to avoid that too many wakees are stacked on one CPU, which might cause regression on redis.

Changes since v4:
1. Dietmar has commented on the task duration calculation. So refined the commit log to reduce confusion.
2. Change [PATCH 1/2] to only record the average duration of a task. So this change could benefit UTIL_EST_FASTER[1].
3. As v4 reported regression on Zen3 and Kunpeng Arm64, add back the system average utilization restriction that, if the system is not busy, do not enable the short wake up. Above logic has shown improvment on Zen3[2].
4. Restrict the wakeup target to be current CPU, rather than both current CPU and task's previous CPU. This could also benefit wakeup optimization from interrupt in the future, which is suggested by Yicong.

Changes since v3:
1. Honglei and Josh have concern that the threshold of short task duration could be too long. Decreased the threshold from sysctl_sched_min_granularity to (sysctl_sched_min_granularity / 8), and the '8' comes from get_update_sysctl_factor().
2. Export p->se.dur_avg to /proc/{pid}/sched per Yicong's suggestion.
3. Move the calculation of average duration from put_prev_task_fair() to dequeue_task_fair(). Because there is an issue in v3 that, put_prev_task_fair() will not be invoked by pick_next_task_fair() in fast path, thus the dur_avg could not be updated timely.
4. Fix the comment in PATCH 2/2, that "WRITE_ONCE(CPU1->ttwu_pending, 1);" on CPU0 is earlier than CPU1 getting "ttwu_list->p0", per Tianchen.
5. Move the scan for CPU with short duration task from select_idle_cpu() to select_idle_siblings(), because there is no CPU scan involved, per Yicong.

Changes since v2:

1. Peter suggested comparing the duration of waker and the cost to scan for an idle CPU: If the cost is higher than the task duration, do not waste time finding an idle CPU, choose the local or previous CPU directly. A prototype was created based on this suggestion. However, according to the test result, this prototype does not inhibit the cross CPU wakeup and did not bring improvement. Because the cost to find an idle CPU is small in the problematic scenario. The root cause of the problem is a race condition between scanning for an idle CPU and task enqueue(please refer to the commit log in PATCH 2/2). So v3 does not change the core logic of v2, with some refinement based on Peter's suggestion.

2. Simplify the logic to record the task duration per Peter and Abel's suggestion.

[1] https://lore.kernel.org/lkml/[email protected]/
[2] https://lore.kernel.org/all/[email protected]/

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

Chen Yu (2):
sched/fair: Record the average duration of a task sched/fair: Introduce SIS_SHORT to wake up short task on current CPU

 include/linux/sched.h   |  3 +++
 kernel/sched/core.c     |  2 ++
 kernel/sched/debug.c    |  1 +
 kernel/sched/fair.c     | 49 +++++++++++++++++++++++++++++++++++++++++
 kernel/sched/features.h |  1 +
 5 files changed, 56 insertions(+)
Signature · 1 line
2.25.1
author
#1 lore raw

PATCH v6 1/2 sched/fair: Record the average duration of a task

Record the average duration of a task, as there is a requirement to leverage this information for better task placement.

At first thought the (p->se.sum_exec_runtime / p->nvcsw) can be used to measure the task duration. However, the history long past was factored too heavily in such a formula. Ideally, the old activity should decay and not affect the current status too much.

Although something based on PELT can be used, se.util_avg might not be appropriate to describe the task duration:
Task p1 and task p2 are doing frequent ping-pong scheduling on one CPU, both p1 and p2 have a short duration, but the util_avg can be up to 50%, which is inconsistent with task duration.

It was found that there was once a similar feature to track the duration of a task:
commit ad4b78bbcbab ("sched: Add new wakeup preemption mode: WAKEUP_RUNNING") Unfortunately, it was reverted because it was an experiment. Pick the patch up again, by recording the average duration when a task voluntarily switches out.

For example, suppose on CPU1, task p1 and p2 run alternatively:

--------------------> time

 | p1 runs 1ms | p2 preempt p1 | p1 switch in, runs 0.5ms and blocks |
               ^               ^                                     ^
 |_____________|               |_____________________________________|
                                                                     ^
                                                                     |
                                                                  p1 dequeued

p1's duration in one section is (1 + 0.5)ms. Because if p2 does not preempt p1, p1 can run 1.5ms. This reflects the nature of a task:
how long it wishes to run at most.

---
 include/linux/sched.h |  3 +++
 kernel/sched/core.c   |  2 ++
 kernel/sched/debug.c  |  1 +
 kernel/sched/fair.c   | 13 +++++++++++++
 4 files changed, 19 insertions(+)
include/linux/sched.h +3 -0
index 4df2b3e76b30..e21709402a31 100644
@@ -557,6 +557,9 @@ struct sched_entity {
 	u64				prev_sum_exec_runtime;
 
 	u64				nr_migrations;
+	u64				prev_sleep_sum_runtime;
+	/* average duration of a task */
+	u64				dur_avg;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	int				depth;
kernel/sched/core.c +2 -0
index 4580fe3e1d0c..455ab9edfe6a 100644
@@ -4428,6 +4428,8 @@ static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
 	p->se.prev_sum_exec_runtime	= 0;
 	p->se.nr_migrations		= 0;
 	p->se.vruntime			= 0;
+	p->se.dur_avg			= 0;
+	p->se.prev_sleep_sum_runtime	= 0;
 	INIT_LIST_HEAD(&p->se.group_node);
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
kernel/sched/debug.c +1 -0
index 1637b65ba07a..8d64fba16cfe 100644
@@ -1024,6 +1024,7 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,
 	__PS("nr_involuntary_switches", p->nivcsw);
 
 	P(se.load.weight);
+	P(se.dur_avg);
 #ifdef CONFIG_SMP
 	P(se.avg.load_sum);
 	P(se.avg.runnable_sum);
kernel/sched/fair.c +13 -0
index ff4dbbae3b10..9ac63868eaaa 100644
@@ -6279,6 +6279,18 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 
 static void set_next_buddy(struct sched_entity *se);
 
+static inline void dur_avg_update(struct task_struct *p, bool task_sleep)
+{
+	u64 dur;
+
+	if (!task_sleep)
+		return;
+
+	dur = p->se.sum_exec_runtime - p->se.prev_sleep_sum_runtime;
+	p->se.prev_sleep_sum_runtime = p->se.sum_exec_runtime;
+	update_avg(&p->se.dur_avg, dur);
+}
+
 /*
  * The dequeue_task method is called before nr_running is
  * decreased. We remove the task from the rbtree and
@@ -6351,6 +6363,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 
 dequeue_throttle:
 	util_est_update(&rq->cfs, p, task_sleep);
+	dur_avg_update(p, task_sleep);
 	hrtick_update(rq);
 }
 
Signature · 1 line
2.25.1
author
#2 lore raw

PATCH v6 2/2 sched/fair: Introduce SIS_SHORT to wake up short task on current CPU

In reply to Chen Yu

[Problem Statement]
For a workload that is doing frequent context switches, the throughput scales well until the number of instances reaches a peak point. After that peak point, the throughput drops significantly if the number of instances continues to increase.

The will-it-scale context_switch1 test case exposes the issue. The test platform has 112 CPUs per LLC domain. The will-it-scale launches 1, 8, 16 ... 112 instances respectively. Each instance is composed of 2 tasks, and each pair of tasks would do ping-pong scheduling via pipe_read() and pipe_write(). No task is bound to any CPU. It is found that, once the number of instances is higher than 56, the throughput drops accordingly:

          ^
throughput|
          |                 X
          |               X   X X
          |             X         X X
          |           X               X
          |         X                   X
          |       X
          |     X
          |   X
          | X
          |
          +-----------------.------------------->
                            56
                                 number of instances

[Symptom analysis]

The performance downgrading was caused by a high system idle percentage(around 20% ~ 30%). The CPUs waste a lot of time in idle and do nothing. As a comparison, if set CPU affinity to these workloads and stops them from migrating among CPUs, the idle percentage drops to nearly 0%, and the throughput increases a lot. This indicates room for optimization.

The cause is the race condition between select_task_rq() and the task enqueue.

Suppose there are nr_cpus pairs of ping-pong scheduling tasks. For example, p0' and p0 are ping-pong scheduling, so do p1' <=> p1, and p2'<=> p2. None of these tasks are bound to any CPUs. The problem can be summarized as:
more than 1 wakers are stacked on 1 CPU, which slows down waking up their wakees:

CPU0 CPU1 CPU2

p0' p1' => idle p2'

try_to_wake_up(p0) try_to_wake_up(p2);
CPU1 = select_task_rq(p0); CPU1 = select_task_rq(p2);
ttwu_queue(p0, CPU1); ttwu_queue(p2, CPU1);

  __ttwu_queue_wakelist(p0, CPU1);
    WRITE_ONCE(CPU1->ttwu_pending, 1);
    __smp_call_single_queue(CPU1, p0);	=> ttwu_list->p0
					quiting cpuidle_idle_call()

									  __ttwu_queue_wakelist(p2, CPU1);
									    WRITE_ONCE(CPU1->ttwu_pending, 1);
					ttwu_list->p2->p0	<=	    __smp_call_single_queue(CPU1, p2);

p0' => idle

					sched_ttwu_pending()
					  enqueue_task(p2 and p0)

					idle => p2

					...
					p2 time slice expires
					...
									!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
								<===	!!! p2 delays the wake up of p0' !!!
									!!! causes long idle on CPU0     !!!
					p2 => p0			!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
					p0 wakes up p0'

idle => p0'

Since there are many waker/wakee pairs in the system, the chain reaction causes many CPUs to be victims. These idle CPUs wait for their waker to be scheduled.

Tiancheng has mentioned the above issue here[1].

[Proposal]
The root cause is that there is no strict synchronization of select_task_rq() and the set of ttwu_pending flag among several CPUs. And this might be by design because the scheduler prefers parallel wakeup.

Avoid this problem indirectly. If the following conditions are met:
1. the system does not have idle cores,
2. the waker and wakee are both short duration tasks,
3. the waker and wakee have very limited wakee_flips, then wake up the wakee on current CPU.

The reason is that, if the waker is a short-duration task, it might relinquish the CPU soon, and the wakee has the chance to be scheduled. On the other hand, if the wakee is a short duration task, putting it on non-idle CPU would bring minimal impact to the running task. No idle core in the system indicates that this mechanism should not inhibit spreading the tasks if the system is not busy. Besides, if two tasks wake up each other frequently(wakee_flips = 0), it suggests that they share resource and should be put together.

This wake up strategy can be viewed as dynamic WF_SYNC. Except that WF_SYNC does not treat non-idle CPU as candidate CPU.

[Benchmark results]
The baseline is v6.2-rc6 tip:sched/core, on top of
Commit 7c4a5b89a0b5 ("sched/rt: pick_next_rt_entity(): check list_entry"). The test platform has 2 x 56C/112T and 224 CPUs in total. C-states deeper than C1E are disabled. Turbo is disabled. CPU frequency governor is performance.

will-it-scale
=============
case load baseline compare%
context_switch1 224 groups 1.00 +946.68%

There is a huge improvement in fast context switch test case, especially when the number of groups equals the CPUs.

netperf
=======

case            	load    	baseline(std%)	compare%( std%)
TCP_RR          	56-threads	 1.00 (  1.12)	 -0.05 (  0.97)
TCP_RR          	112-threads	 1.00 (  0.50)	 +0.31 (  0.35)
TCP_RR          	168-threads	 1.00 (  3.46)	 +5.50 (  2.08)
TCP_RR          	224-threads	 1.00 (  2.52)	+665.38 (  3.38)
TCP_RR          	280-threads	 1.00 ( 38.59)	+22.12 ( 11.36)
TCP_RR          	336-threads	 1.00 ( 15.88)	 -0.00 ( 19.96)
TCP_RR          	392-threads	 1.00 ( 27.22)	 +0.26 ( 24.26)
TCP_RR          	448-threads	 1.00 ( 37.88)	 +0.04 ( 27.87)
UDP_RR          	56-threads	 1.00 (  2.39)	 -0.36 (  8.33)
UDP_RR          	112-threads	 1.00 ( 22.62)	 -0.65 ( 24.66)
UDP_RR          	168-threads	 1.00 ( 15.72)	 +3.97 (  5.02)
UDP_RR          	224-threads	 1.00 ( 15.90)	+134.98 ( 28.59)
UDP_RR          	280-threads	 1.00 ( 32.43)	 +0.26 ( 29.68)
UDP_RR          	336-threads	 1.00 ( 39.21)	 -0.05 ( 39.71)
UDP_RR          	392-threads	 1.00 ( 31.76)	 -0.22 ( 32.00)
UDP_RR          	448-threads	 1.00 ( 44.90)	 +0.06 ( 31.83)

There is significant 600+% improvement for TCP_RR and 100+% for UDP_RR when the number of threads equals the CPUs.

tbench
======

case            	load    	baseline(std%)	compare%( std%)
loopback        	56-threads	 1.00 (  0.15)	 +0.88 (  0.08)
loopback        	112-threads	 1.00 (  0.06)	 -0.41 (  0.52)
loopback        	168-threads	 1.00 (  0.17)	+45.42 ( 39.54)
loopback        	224-threads	 1.00 ( 36.93)	+24.10 (  0.06)
loopback        	280-threads	 1.00 (  0.04)	 -0.04 (  0.04)
loopback        	336-threads	 1.00 (  0.06)	 -0.16 (  0.14)
loopback        	392-threads	 1.00 (  0.05)	 +0.06 (  0.02)
loopback        	448-threads	 1.00 (  0.07)	 -0.02 (  0.07)

There is no noticeable impact on tbench. Although there is run-to-run variance in 168/224 threads case, with or without this patch applied.

hackbench
=========

case            	load    	baseline(std%)	compare%( std%)
process-pipe    	1-groups	 1.00 (  5.39)	 +5.26 (  7.26)
process-pipe    	2-groups	 1.00 (  7.56)	 +1.85 (  1.98)
process-pipe    	4-groups	 1.00 ( 11.14)	 +6.40 (  4.77)
process-pipe    	8-groups	 1.00 (  1.99)	 -1.03 (  0.29)
process-sockets 	1-groups	 1.00 (  0.32)	 +0.81 (  0.53)
process-sockets 	2-groups	 1.00 (  0.44)	 -1.57 (  0.04)
process-sockets 	4-groups	 1.00 (  0.43)	 -0.33 (  1.13)
process-sockets 	8-groups	 1.00 (  0.42)	 -0.91 (  0.92)
threads-pipe    	1-groups	 1.00 (  0.15)	 -1.28 (  1.42)
threads-pipe    	2-groups	 1.00 (  4.20)	 -4.82 (  4.20)
threads-pipe    	4-groups	 1.00 (  2.23)	 +0.57 (  3.89)
threads-pipe    	8-groups	 1.00 (  1.24)	 -0.37 (  1.08)
threads-sockets 	1-groups	 1.00 (  1.93)	 +0.89 (  1.43)
threads-sockets 	2-groups	 1.00 (  0.43)	 -2.92 (  4.96)
threads-sockets 	4-groups	 1.00 (  0.59)	 -2.63 (  1.60)
threads-sockets 	8-groups	 1.00 (  0.38)	 -0.42 (  0.33)

Overall there is no noticeable impact on hackbench.

schbench
========

case            	load    	baseline(std%)	compare%( std%)
normal          	1-mthreads	 1.00 (  2.27)	 +1.75 (  3.31)
normal          	2-mthreads	 1.00 (  4.10)	 +0.59 (  4.72)
normal          	4-mthreads	 1.00 (  2.41)	 +1.91 (  4.11)
normal          	8-mthreads	 1.00 (  1.74)	 +4.87 (  1.40)

Overall there is no noticeable impact on schbench.

Redis
=====
Launch 224 instances of redis-server on machine A, launch 224 instances of redis-benchmark on machine B, measure the SET/GET latency on B. It was tested on a 1G NIC card. The 99th latency before vs after SIS_SHORT did not change much.
baseline sis_short

SET      115 ms                   116 ms
GET      225 ms                   228 ms

Reaim was tested on a 2 x 8C Intel Xeon E-2278G, 16.48% jobs_per_min improvement was observed when the system is overloaded.

[Limitations/Miscellaneous]

[a]
Peter has suggested[2] comparing task duration with the cost of searching for an idle CPU. If the latter is higher, then give up the scan, to achieve better task affine. However, this method does not fit in the case encountered in this patch. Because there are plenty of (fast)idle CPUs in the system, it will not take too long to find an idle CPU. The bottleneck is caused by the race condition mentioned above.

[b]
The short task threshold is sysctl_sched_min_granularity / 8. According to get_update_sysctl_factor(), the sysctl_sched_min_granularity could be 0.75 msec * 4 for SCHED_TUNABLESCALING_LOG,
or 0.75 msec * ncpus for SCHED_TUNABLESCALING_LINEAR. Choosing 8 as the divisor is a trade-off. Thanks Honglei for pointing this out.

[c]
SIS_SHORT leverages SIS_UTIL to do better task placement. If the scan number suggested by SIS_UTIL is smaller than 60% of llc_weight, it indicates a util_avg% higher than 50%, which indicates a half-busy LLC domain. This co-exists with !has_idle_core to not stack too many tasks on one CPU. System busier than this could lower its bar to choose a compromised "idle" CPU.

[d]
Inspired by Abel's Redis test, the short task definination not only considers the duration, but also checks the wakee_flips of both waker and wakee. A task will only be regarded as short task if the wakee_flips is 0. That is to say, task A only wakes up task B, and task B only wakes up A, A and B can be put together on one CPU.

[1] https://lore.kernel.org/lkml/[email protected]/
[2] https://lore.kernel.org/lkml/Y2O8a%[email protected]/

---
 kernel/sched/fair.c     | 36 ++++++++++++++++++++++++++++++++++++
 kernel/sched/features.h |  1 +
 2 files changed, 37 insertions(+)
kernel/sched/fair.c +36 -0
index 9ac63868eaaa..4f8d5af2d9b9 100644
@@ -6497,6 +6497,23 @@ static int wake_wide(struct task_struct *p)
 	return 1;
 }
 
+/*
+ * If a task switches in and then voluntarily relinquishes the
+ * CPU quickly, it is regarded as a short duration task.
+ *
+ * SIS_SHORT tries to wake up the short wakee on current CPU. This
+ * aims to avoid race condition among CPUs due to frequent context
+ * switch. Besides, the candidate short task should not be the one
+ * that wakes up more than one tasks, otherwise SIS_SHORT might
+ * stack too many tasks on current CPU.
+ */
+static inline int is_short_task(struct task_struct *p)
+{
+	return sched_feat(SIS_SHORT) && !p->wakee_flips &&
+	       p->se.dur_avg &&
+	       ((p->se.dur_avg * 8) < sysctl_sched_min_granularity);
+}
+
 /*
  * The purpose of wake_affine() is to quickly determine on which CPU we can run
  * soonest. For the purpose of speed we only consider the waking and previous
@@ -6533,6 +6550,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
 	if (available_idle_cpu(prev_cpu))
 		return prev_cpu;
 
+	/* The only running task is a short duration one. */
+	if (cpu_rq(this_cpu)->nr_running == 1 &&
+	    is_short_task(rcu_dereference(cpu_curr(this_cpu))))
+		return this_cpu;
+
 	return nr_cpumask_bits;
 }
 
@@ -6907,6 +6929,20 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
 			/* overloaded LLC is unlikely to have idle cpu/core */
 			if (nr == 1)
 				return -1;
+
+			/*
+			 * If the scan number suggested by SIS_UTIL is smaller
+			 * than 60% of llc_weight, it indicates a util_avg% higher
+			 * than 50%. System busier than this could lower its bar to
+			 * choose a compromised "idle" CPU. This co-exists with
+			 * !has_idle_core to not stack too many tasks on one CPU.
+			 */
+			if (!has_idle_core && this == target &&
+			    (5 * nr < 3 * sd->span_weight) &&
+			    cpu_rq(target)->nr_running <= 1 &&
+			    is_short_task(p) &&
+			    is_short_task(rcu_dereference(cpu_curr(target))))
+				return target;
 		}
 	}
 
kernel/sched/features.h +1 -0
index ee7f23c76bd3..efdc29c42161 100644
@@ -62,6 +62,7 @@ SCHED_FEAT(TTWU_QUEUE, true)
  */
 SCHED_FEAT(SIS_PROP, false)
 SCHED_FEAT(SIS_UTIL, true)
+SCHED_FEAT(SIS_SHORT, true)
 
 /*
  * Issue a WARN when we do multiple update_rq_clock() calls
Signature · 1 line
2.25.1
reviewer Tested-by on the v6 series
#5 lore raw
In reply to Chen Yu

Hello Chenyu,

I did not observe any regression when testing v6 :) Most of the benchmark results are comparable to the tip with minor gains in some benchmarks with single sender and single receiver.

Following are the results from testing the series on a dual socket Zen3 machine (2 x 64C/128T):

NPS Modes are used to logically divide single socket into multiple NUMA region.
Following is the NUMA configuration for each NPS mode on the system:

NPS1: Each socket is a NUMA node.

    Total 2 NUMA nodes in the dual socket machine.

    Node 0: 0-63,   128-191
    Node 1: 64-127, 192-255

NPS2: Each socket is further logically divided into 2 NUMA regions.

    Total 4 NUMA nodes exist over 2 socket.
   
    Node 0: 0-31,   128-159
    Node 1: 32-63,  160-191
    Node 2: 64-95,  192-223
    Node 3: 96-127, 223-255

NPS4: Each socket is logically divided into 4 NUMA regions.

    Total 8 NUMA nodes exist over 2 socket.
   
    Node 0: 0-15,    128-143
    Node 1: 16-31,   144-159
    Node 2: 32-47,   160-175
    Node 3: 48-63,   176-191
    Node 4: 64-79,   192-207
    Node 5: 80-95,   208-223
    Node 6: 96-111,  223-231
    Node 7: 112-127, 232-255

Benchmark Results:

Kernel versions:
- tip: 6.2.0-rc6 tip sched/core
- sis_short: 6.2.0-rc6 tip sched/core + this series

When the testing started, the tip was at:
commit 7c4a5b89a0b5 "sched/rt: pick_next_rt_entity(): check list_entry"

~~~~~~~~~~~~~
~ hackbench ~
~~~~~~~~~~~~~

o NPS1

Test: tip sis-short

 1-groups:	   4.63 (0.00 pct)	   4.47 (3.45 pct)
 2-groups:	   4.42 (0.00 pct)	   4.41 (0.22 pct)
 4-groups:	   4.21 (0.00 pct)	   4.24 (-0.71 pct)
 8-groups:	   4.95 (0.00 pct)	   5.06 (-2.22 pct)
16-groups:	   5.43 (0.00 pct)	   5.36 (1.28 pct)

o NPS2

Test: tip sis-short

 1-groups:	   4.68 (0.00 pct)	   4.58 (2.13 pct)
 2-groups:	   4.45 (0.00 pct)	   4.37 (1.79 pct)
 4-groups:	   4.19 (0.00 pct)	   4.30 (-2.62 pct)
 8-groups:	   4.80 (0.00 pct)	   5.22 (-8.75 pct)	*

8-groups: 4.91 (0.00 pct) 5.01 (-2.03 pct) [Verification Run]
16-groups: 5.60 (0.00 pct) 5.66 (-1.07 pct)

o NPS4

Test: tip sis-short

 1-groups:	   4.68 (0.00 pct)	   4.66 (0.42 pct)
 2-groups:	   4.56 (0.00 pct)	   4.52 (0.87 pct)
 4-groups:	   4.50 (0.00 pct)	   4.62 (-2.66 pct)
 8-groups:	   5.76 (0.00 pct)	   5.64 (2.08 pct)
16-groups:	   5.60 (0.00 pct)	   5.79 (-3.39 pct)

~~~~~~~~~~~~
~ schbench ~
~~~~~~~~~~~~

o NPS1

#workers: tip sis-short

  1:	  36.00 (0.00 pct)	  34.00 (5.55 pct)
  2:	  37.00 (0.00 pct)	  36.00 (2.70 pct)
  4:	  38.00 (0.00 pct)	  40.00 (-5.26 pct)
  8:	  52.00 (0.00 pct)	  46.00 (11.53 pct)
 16:	  66.00 (0.00 pct)	  68.00 (-3.03 pct)

32: 111.00 (0.00 pct) 111.00 (0.00 pct)
64: 213.00 (0.00 pct) 214.00 (-0.46 pct)
128: 502.00 (0.00 pct) 497.00 (0.99 pct)
256: 45632.00 (0.00 pct) 46784.00 (-2.52 pct)
512: 78720.00 (0.00 pct) 75136.00 (4.55 pct)

o NPS2

#workers: tip sis-short

  1:	  31.00 (0.00 pct)	  31.00 (0.00 pct)
  2:	  32.00 (0.00 pct)	  32.00 (0.00 pct)
  4:	  39.00 (0.00 pct)	  39.00 (0.00 pct)
  8:	  52.00 (0.00 pct)	  47.00 (9.61 pct)
 16:	  67.00 (0.00 pct)	  69.00 (-2.98 pct)

32: 113.00 (0.00 pct) 118.00 (-4.42 pct)
64: 213.00 (0.00 pct) 231.00 (-8.45 pct) *
64: 225.00 (0.00 pct) 214.00 (4.88 pct) [Verification Run]
128: 508.00 (0.00 pct) 513.00 (-0.98 pct)
256: 46912.00 (0.00 pct) 45888.00 (2.18 pct)
512: 76672.00 (0.00 pct) 79232.00 (-3.33 pct)

o NPS4

#workers: tip sis-short

  1:	  33.00 (0.00 pct)	  29.00 (12.12 pct)
  2:	  40.00 (0.00 pct)	  35.00 (12.50 pct)
  4:	  44.00 (0.00 pct)	  40.00 (9.09 pct)
  8:	  73.00 (0.00 pct)	  60.00 (17.80 pct)
 16:	  71.00 (0.00 pct)	  69.00 (2.81 pct)

32: 111.00 (0.00 pct) 119.00 (-7.20 pct)
64: 217.00 (0.00 pct) 208.00 (4.14 pct)
128: 509.00 (0.00 pct) 889.00 (-74.65 pct) *
128: 525.90 (0.00 pct) 542.00 (-3.23 pct) [Verification Run]
256: 44352.00 (0.00 pct) 46528.00 (-4.90 pct)
512: 75392.00 (0.00 pct) 78720.00 (-4.41 pct)

~~~~~~~~~~
~ tbench ~
~~~~~~~~~~

o NPS1

Clients: tip sis-short

    1	 483.10 (0.00 pct)	 479.99 (-0.64 pct)
    2	 956.03 (0.00 pct)	 961.15 (0.53 pct)
    4	 1786.36 (0.00 pct)	 1793.16 (0.38 pct)
    8	 3304.47 (0.00 pct)	 3224.76 (-2.41 pct)

16 5440.44 (0.00 pct) 5584.12 (2.64 pct)
32 10462.02 (0.00 pct) 10667.21 (1.96 pct)
64 18995.99 (0.00 pct) 19802.51 (4.24 pct)
128 27896.44 (0.00 pct) 28509.96 (2.19 pct)
256 49742.89 (0.00 pct) 50404.44 (1.32 pct)
512 49583.01 (0.00 pct) 49362.40 (-0.44 pct)
1024 48467.75 (0.00 pct) 49393.34 (1.90 pct)

o NPS2

Clients: tip sis-short

    1	 472.57 (0.00 pct)	 491.88 (4.08 pct)
    2	 938.27 (0.00 pct)	 962.87 (2.62 pct)
    4	 1764.34 (0.00 pct)	 1782.85 (1.04 pct)
    8	 3043.57 (0.00 pct)	 3275.90 (7.63 pct)

16 5103.53 (0.00 pct) 5098.77 (-0.09 pct)
32 9767.22 (0.00 pct) 9730.51 (-0.37 pct)
64 18712.65 (0.00 pct) 19153.47 (2.35 pct)
128 27691.95 (0.00 pct) 28738.51 (3.77 pct)
256 47939.24 (0.00 pct) 48571.73 (1.31 pct)
512 47843.70 (0.00 pct) 49224.01 (2.88 pct)
1024 48412.05 (0.00 pct) 48662.85 (0.51 pct)

o NPS4

Clients: tip sis-short

    1	 486.74 (0.00 pct)	 487.21 (0.09 pct)
    2	 950.50 (0.00 pct)	 944.87 (-0.59 pct)
    4	 1778.58 (0.00 pct)	 1785.67 (0.39 pct)
    8	 3106.36 (0.00 pct)	 3269.40 (5.24 pct)

16 5139.81 (0.00 pct) 5346.01 (4.01 pct)
32 9911.04 (0.00 pct) 9961.37 (0.50 pct)
64 18201.46 (0.00 pct) 18755.21 (3.04 pct)
128 27284.67 (0.00 pct) 27372.54 (0.32 pct)
256 46793.72 (0.00 pct) 47277.47 (1.03 pct)
512 48841.96 (0.00 pct) 47736.63 (-2.26 pct)
1024 48811.99 (0.00 pct) 48066.96 (-1.52 pct)

~~~~~~~~~~
~ stream ~
~~~~~~~~~~

o NPS1

- 10 Runs:

Test: tip sis-short
Copy: 321229.54 (0.00 pct) 332046.15 (3.36 pct)
Scale: 207471.32 (0.00 pct) 209724.40 (1.08 pct)
Add: 234962.15 (0.00 pct) 238593.38 (1.54 pct)
Triad: 246256.00 (0.00 pct) 259065.38 (5.20 pct)

- 100 Runs:

Test: tip sis-short
Copy: 332714.94 (0.00 pct) 330868.23 (-0.55 pct)
Scale: 216140.84 (0.00 pct) 218881.39 (1.26 pct)
Add: 239605.00 (0.00 pct) 243423.22 (1.59 pct)
Triad: 258580.84 (0.00 pct) 257857.39 (-0.27 pct)

o NPS2

- 10 Runs:

Test: tip sis-short
Copy: 324423.92 (0.00 pct) 314693.42 (-2.99 pct)
Scale: 215993.56 (0.00 pct) 216081.04 (0.04 pct)
Add: 250590.28 (0.00 pct) 250786.87 (0.07 pct)
Triad: 261284.44 (0.00 pct) 258434.05 (-1.09 pct)

- 100 Runs:

Test: tip sis-short
Copy: 325993.72 (0.00 pct) 321152.67 (-1.48 pct)
Scale: 227201.27 (0.00 pct) 224454.35 (-1.20 pct)
Add: 256601.84 (0.00 pct) 253548.96 (-1.18 pct)
Triad: 260222.19 (0.00 pct) 259141.98 (-0.41 pct)

o NPS4

- 10 Runs:

Test: tip sis-short
Copy: 356850.80 (0.00 pct) 355198.15 (-0.46 pct)
Scale: 247219.39 (0.00 pct) 240196.59 (-2.84 pct)
Add: 268588.78 (0.00 pct) 265259.51 (-1.23 pct)
Triad: 272932.59 (0.00 pct) 275791.62 (1.04 pct)

- 100 Runs:

Test: tip sis-short
Copy: 365965.18 (0.00 pct) 364556.47 (-0.38 pct)
Scale: 246068.58 (0.00 pct) 249613.08 (1.44 pct)
Add: 263677.73 (0.00 pct) 267118.22 (1.30 pct)
Triad: 273701.36 (0.00 pct) 275324.29 (0.59 pct)

~~~~~~~~~~~~~
~ unixbench ~
~~~~~~~~~~~~~

o NPS1

Test Metric Parallelism tip sis_short

unixbench-dhry2reg      Hmean     unixbench-dhry2reg-1      49077561.21 (   0.00%)    48958154.65 (  -0.24%)
unixbench-dhry2reg      Hmean     unixbench-dhry2reg-512  6276672225.10 (   0.00%)  6282377092.30 (   0.09%)
unixbench-syscall       Amean     unixbench-syscall-1        2664815.40 (   0.00%)     2682364.37 *  -0.66%*
unixbench-syscall       Amean     unixbench-syscall-512      7848462.70 (   0.00%)     7935735.97 *  -1.11%*
unixbench-pipe          Hmean     unixbench-pipe-1           2531131.89 (   0.00%)     2510761.89 *  -0.80%*
unixbench-pipe          Hmean     unixbench-pipe-512       305244521.98 (   0.00%)   302210856.64 *  -0.99%*
unixbench-spawn         Hmean     unixbench-spawn-1             4058.05 (   0.00%)        4060.15 (   0.05%)
unixbench-spawn         Hmean     unixbench-spawn-512          80162.90 (   0.00%)       80337.40 (   0.22%)
unixbench-execl         Hmean     unixbench-execl-1             4148.64 (   0.00%)        4150.92 (   0.05%)
unixbench-execl         Hmean     unixbench-execl-512          11077.20 (   0.00%)       11124.06 (   0.42%)

o NPS2

Test Metric Parallelism tip sis_short

unixbench-dhry2reg      Hmean     unixbench-dhry2reg-1      49394822.56 (   0.00%)    49562225.47 (   0.34%)
unixbench-dhry2reg      Hmean     unixbench-dhry2reg-512  6262917314.00 (   0.00%)  6270269390.20 (   0.12%)
unixbench-syscall       Amean     unixbench-syscall-1        2663675.03 (   0.00%)     2685044.77 *  -0.80%*
unixbench-syscall       Amean     unixbench-syscall-512      7342392.90 (   0.00%)     7369717.10 *  -0.37%*
unixbench-pipe          Hmean     unixbench-pipe-1           2533194.04 (   0.00%)     2508985.37 *  -0.96%*
unixbench-pipe          Hmean     unixbench-pipe-512       303588239.03 (   0.00%)   301439936.90 *  -0.71%*
unixbench-spawn         Hmean     unixbench-spawn-1             5141.40 (   0.00%)        4840.60 (  -5.85%)	*
unixbench-spawn         Hmean     unixbench-spawn-1             4780.20 (   0.00%)        5235.90 *   9.53%*	[Verification Run]
unixbench-spawn         Hmean     unixbench-spawn-512          82993.79 (   0.00%)       77573.59 *  -6.53%*	*
unixbench-spawn         Hmean     unixbench-spawn-512          79664.40 (   0.00%)       81747.60 *   2.61%*	[Verification Run]
unixbench-execl         Hmean     unixbench-execl-1             4140.15 (   0.00%)        4134.94 (  -0.13%)
unixbench-execl         Hmean     unixbench-execl-512          12229.25 (   0.00%)       12392.40 (   1.33%)

o NPS4

Test Metric Parallelism tip sis_short

unixbench-dhry2reg      Hmean     unixbench-dhry2reg-1      48970677.27 (   0.00%)    48906123.72 (  -0.13%)
unixbench-dhry2reg      Hmean     unixbench-dhry2reg-512  6294483486.30 (   0.00%)  6284127003.20 (  -0.16%)
unixbench-syscall       Amean     unixbench-syscall-1        2664715.13 (   0.00%)     2685194.30 *  -0.77%*
unixbench-syscall       Amean     unixbench-syscall-512      7938670.70 (   0.00%)     7824901.77 *   1.43%*
unixbench-pipe          Hmean     unixbench-pipe-1           2527605.54 (   0.00%)     2503782.85 *  -0.94%*
unixbench-pipe          Hmean     unixbench-pipe-512       305068507.23 (   0.00%)   302815020.95 *  -0.74%*
unixbench-spawn         Hmean     unixbench-spawn-1             5207.34 (   0.00%)        5221.99 (   0.28%)
unixbench-spawn         Hmean     unixbench-spawn-512          81352.38 (   0.00%)       82374.89 *   1.26%*
unixbench-execl         Hmean     unixbench-execl-1             4131.37 (   0.00%)        4130.76 (  -0.01%)
unixbench-execl         Hmean     unixbench-execl-512          13025.56 (   0.00%)       12816.98 (  -1.60%)

~~~~~~~~~~~~~~~~
~ ycsb-mongodb ~
~~~~~~~~~~~~~~~~

0 NPS1

tip : 130249.00 (var: 1.16%)
sis_short : 133626.00 (var: 1.09%) (2.59%)

o NPS2

tip : 131100.00 (var: 1.07%)
sis_short : 133713.00 (var: 3.17%) (1.99%)

o NPS4

tip : 136446.00 (var: 1.97%)
sis_short : 136700.00 (var: 3.16%) (0.18%)

~~~~~~~~~~~~~~~~~
~ SpecJBB & DSB ~
~~~~~~~~~~~~~~~~~

- SpecJBB numbers see small improvements of ~2%.
- DeathStarBench numbers remain similar to tip.

~~~~~~~~~~~
~ netperf ~
~~~~~~~~~~~

o NPS1

tip sis_short

 1-clients:      107932.22 (0.00 pct)    110175.53 (2.07 pct)
 2-clients:      106887.99 (0.00 pct)    108626.93 (1.62 pct)
 4-clients:      106676.11 (0.00 pct)    107736.87 (0.99 pct)
 8-clients:      98645.45 (0.00 pct)     97700.99 (-0.95 pct)
16-clients:      88881.23 (0.00 pct)     88800.03 (-0.09 pct)
32-clients:      86654.28 (0.00 pct)     87252.74 (0.69 pct)
64-clients:      81431.90 (0.00 pct)     79703.33 (-2.12 pct)
128-clients:     55993.77 (0.00 pct)     55681.20 (-0.55 pct)
256-clients:     43865.59 (0.00 pct)     42588.18 (-2.91 pct)

o NPS4

tip sis_short

 1-clients:      106711.81 (0.00 pct)    109905.29 (2.99 pct)
 2-clients:      106987.79 (0.00 pct)    108469.16 (1.38 pct)
 4-clients:      105275.37 (0.00 pct)    106707.13 (1.36 pct)
 8-clients:      103028.31 (0.00 pct)    103106.39 (0.07 pct)
16-clients:      87382.43 (0.00 pct)     88974.74 (1.82 pct)
32-clients:      86578.14 (0.00 pct)     87616.81 (1.19 pct)
64-clients:      81470.63 (0.00 pct)     81519.56 (0.06 pct)
128-clients:     54803.35 (0.00 pct)     55102.65 (0.54 pct)
256-clients:     42910.29 (0.00 pct)     41887.09 (-2.38 pct)
Quoted 98 lines · Chen Yu

The main purpose is to avoid too many cross CPU wake up when it is unnecessary. The frequent cross CPU wake up brings significant damage to some workloads, especially on high core count systems.

Inhibits the cross CPU wake-up by placing the wakee on waking CPU, if both the waker and wakee are short-duration tasks. The short duration task could become a trouble maker on high-load system, because it could bring frequent context switch. This strategy only takes effect when the system is busy. Because it is unreasonable to inhibit the idle CPU scan when there are still idle CPUs.

First, introduce the definition of a short-duration task. Then leverages the first patch to choose a local CPU for wakee.

Overall there is performance improvement on some overloaded case. Such as will-it-scale, netperf. And no noticeable impact on schbench, hackbench, tbench and a OLTP workload with a commercial RDBMS, tested on a Intel Xeon 2 x 56C machine.

Per the test on Zen3 from Prateek, most benchmarks result saw small wins or are comparable to sched:tip. SpecJBB Critical-jOps improved while Max-jOPS saw a small hit, but it might be in the expected range. ycsb-mongodb saw small uplift in NPS1 mode.

Throughput improvement of netperf(localhost) was observed on a Rome 2 x 64C machine, when the number of clients equals the CPUs.

Abel reported against a latency regression from Redis on an overloaded system. Inspired by his description, v5 added the check of wakee_flips to mitigate task stacking.

Changes since v5:
1. Check the wakee_flips of the waker/wakee. If the wakee_flips of waker/wakee are both 0, it indicates that the waker and the wakee are waking up each other. In this case, put them together on the same CPU. This is to avoid that too many wakees are stacked on one CPU, which might cause regression on redis.

Changes since v4:
1. Dietmar has commented on the task duration calculation. So refined the commit log to reduce confusion.
2. Change [PATCH 1/2] to only record the average duration of a task. So this change could benefit UTIL_EST_FASTER[1].
3. As v4 reported regression on Zen3 and Kunpeng Arm64, add back the system average utilization restriction that, if the system is not busy, do not enable the short wake up. Above logic has shown improvment on Zen3[2].
4. Restrict the wakeup target to be current CPU, rather than both current CPU and task's previous CPU. This could also benefit wakeup optimization from interrupt in the future, which is suggested by Yicong.

Changes since v3:
1. Honglei and Josh have concern that the threshold of short task duration could be too long. Decreased the threshold from sysctl_sched_min_granularity to (sysctl_sched_min_granularity / 8), and the '8' comes from get_update_sysctl_factor().
2. Export p->se.dur_avg to /proc/{pid}/sched per Yicong's suggestion.
3. Move the calculation of average duration from put_prev_task_fair() to dequeue_task_fair(). Because there is an issue in v3 that, put_prev_task_fair() will not be invoked by pick_next_task_fair() in fast path, thus the dur_avg could not be updated timely.
4. Fix the comment in PATCH 2/2, that "WRITE_ONCE(CPU1->ttwu_pending, 1);" on CPU0 is earlier than CPU1 getting "ttwu_list->p0", per Tianchen.
5. Move the scan for CPU with short duration task from select_idle_cpu() to select_idle_siblings(), because there is no CPU scan involved, per Yicong.

Changes since v2:

1. Peter suggested comparing the duration of waker and the cost to scan for an idle CPU: If the cost is higher than the task duration, do not waste time finding an idle CPU, choose the local or previous CPU directly. A prototype was created based on this suggestion. However, according to the test result, this prototype does not inhibit the cross CPU wakeup and did not bring improvement. Because the cost to find an idle CPU is small in the problematic scenario. The root cause of the problem is a race condition between scanning for an idle CPU and task enqueue(please refer to the commit log in PATCH 2/2). So v3 does not change the core logic of v2, with some refinement based on Peter's suggestion.

2. Simplify the logic to record the task duration per Peter and Abel's suggestion.

[1] https://lore.kernel.org/lkml/[email protected]/
[2] https://lore.kernel.org/all/[email protected]/

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

Chen Yu (2):
sched/fair: Record the average duration of a task sched/fair: Introduce SIS_SHORT to wake up short task on current CPU

Quoted 7 lines
 include/linux/sched.h   |  3 +++
 kernel/sched/core.c     |  2 ++
 kernel/sched/debug.c    |  1 +
 kernel/sched/fair.c     | 49 +++++++++++++++++++++++++++++++++++++++++
 kernel/sched/features.h |  1 +
 5 files changed, 56 insertions(+)

With the introduction of wakee_flips condition in is_short_task(), most benchmarks that have multiple tasks interacting are now comparable to tip. There may be other avenues for optimization using SIS_SHORT as Abel pointed but this series is a good start in that direction.

--
Thanks and Regards,
Prateek

author
#6 lore raw
Quoted 6 lines · K Prateek Nayak

Hello Chenyu,

I did not observe any regression when testing v6 :) Most of the benchmark results are comparable to the tip with minor gains in some benchmarks with single sender and single receiver.

Quoted 7 lines

With the introduction of wakee_flips condition in is_short_task(), most benchmarks that have multiple tasks interacting are now comparable to tip. There may be other avenues for optimization using SIS_SHORT as Abel pointed but this series is a good start in that direction.

Thanks Prateek!

thanks,
Chenyu

#7 lore raw
In reply to Chen Yu

Hi Chenyu,

Quoted 31 lines · Chen Yu

The main purpose is to avoid too many cross CPU wake up when it is unnecessary. The frequent cross CPU wake up brings significant damage to some workloads, especially on high core count systems.

Inhibits the cross CPU wake-up by placing the wakee on waking CPU, if both the waker and wakee are short-duration tasks. The short duration task could become a trouble maker on high-load system, because it could bring frequent context switch. This strategy only takes effect when the system is busy. Because it is unreasonable to inhibit the idle CPU scan when there are still idle CPUs.

First, introduce the definition of a short-duration task. Then leverages the first patch to choose a local CPU for wakee.

Overall there is performance improvement on some overloaded case. Such as will-it-scale, netperf. And no noticeable impact on schbench, hackbench, tbench and a OLTP workload with a commercial RDBMS, tested on a Intel Xeon 2 x 56C machine.

Per the test on Zen3 from Prateek, most benchmarks result saw small wins or are comparable to sched:tip. SpecJBB Critical-jOps improved while Max-jOPS saw a small hit, but it might be in the expected range. ycsb-mongodb saw small uplift in NPS1 mode.

Throughput improvement of netperf(localhost) was observed on a Rome 2 x 64C machine, when the number of clients equals the CPUs.

Abel reported against a latency regression from Redis on an overloaded system. Inspired by his description, v5 added the check of wakee_flips to mitigate task stacking.

Quoted 7 lines

Changes since v5:
1. Check the wakee_flips of the waker/wakee. If the wakee_flips of waker/wakee are both 0, it indicates that the waker and the wakee are waking up each other. In this case, put them together on the same CPU. This is to avoid that too many wakees are stacked on one CPU, which might cause regression on redis.

The patch looks good to me. And for the v6 version there's no significant regression on our server. :)

Detailed results below. The setup are the same as what used on v4. There're some gain for UDP_RR. For mysql no significant regression, there're ~2% loss for 128 threads case but the proportion is within the fluctuation range so it should be ok.

Thanks,
Yicong

tbench results (node 0):
Compare
6.3-rc1-vanilla sis-short-v6

  1:        322.2940        324.6750 (    0.74%)
  4:       1293.4000       1294.2900 (    0.07%)
  8:       2568.7700       2606.9200 (    1.49%)
 16:       5158.0800       5254.5500 (    1.87%)
 32:      10074.2000      10286.9000 (    2.11%)
 64:       7910.5000       7969.1000 (    0.74%)
128:       6670.3900       6699.7600 (    0.44%)
tbench results (node 0-1):
Compare
      6.3-rc1-vanilla                sis-short-v6
  1:        324.5650        330.9840 (    1.98%)
  4:       1302.9000       1311.3300 (    0.65%)
  8:       2573.7200       2615.5500 (    1.63%)
 16:       5092.7900       5178.4200 (    1.68%)
 32:       8766.8000       9466.6700 (    7.98%)
 64:      16859.5000      16535.2000 (   -1.92%)
128:      13673.6000      11960.7000 (  -12.53%)
128:      13673.6000      13066.6000 (   -4.43%) [verification]

netperf results TCP_RR (node 0):
Compare
6.3-rc1-vanilla sis-short-v6

  1:      74952.4633      74964.7067 (    0.02%)
  4:      76020.1192      75984.1158 (   -0.05%)
  8:      76698.5804      76846.1312 (    0.19%)
 16:      77713.0350      77858.9752 (    0.19%)
 32:      65947.7090      66124.5758 (    0.27%)
 64:      25195.1539      25374.4948 (    0.71%)
128:      10602.2112      10703.6223 (    0.96%)
netperf results TCP_RR (node 0-1):
Compare
      6.3-rc1-vanilla                sis-short-v6
  1:      76229.5167      76178.0700 (   -0.07%)
  4:      77196.7558      76546.3333 (   -0.84%)
  8:      76340.5733      76612.0829 (    0.36%)
 16:      75808.3848      75132.6454 (   -0.89%)
 32:      75178.5653      71464.7628 (   -4.94%)
 64:      75222.3510      76028.7949 (    1.07%)
128:      28552.5946      28830.6498 (    0.97%)
netperf results UDP_RR (node 0):
Compare
      6.3-rc1-vanilla                sis-short-v6
  1:      90744.2900      94082.3967 (    3.68%)
  4:      92323.3100      95160.6525 (    3.07%)
  8:      92951.3996      96303.9783 (    3.61%)
 16:      93418.8117      97358.5925 (    4.22%)
 32:      78725.5393      84363.7384 (    7.16%)
 64:      30069.7350      30929.4379 (    2.86%)
128:      12501.6386      12695.0588 (    1.55%)
netperf results UDP_RR (node 0-1):
Compare
      6.3-rc1-vanilla                sis-short-v6
  1:      92030.0200      95568.9767 (    3.85%)
  4:      90041.0042      94265.9775 (    4.69%)
  8:      90273.7354      94055.1283 (    4.19%)
 16:      90404.9869      95233.8633 (    5.34%)
 32:      74813.0918      83538.5368 (   11.66%) [*]
 64:      57494.5351      74612.3866 (   29.77%) [*]
128:      24803.3562      16420.1439 (  -33.80%) [*]

[*] untrustworthy due to large fluactuation

               6.3.0-rc1-vanilla     6.3.0-rc1-sis-short-v6
                       Avg                 Avg (%)
     TPS-8       4496.25         4520.99 (0.55%)
     QPS-8      71940.01        72335.93 (0.55%)
 avg_lat-8          1.78            1.77 (0.38%)
95th_lat-8          2.10            2.11 (-0.48%)
     TPS-16      8905.41         8844.63 (-0.68%)
     QPS-16     142486.59       141514.08 (-0.68%)
 avg_lat-16         1.80            1.81 (-0.56%)
95th_lat-16         2.18            2.23 (-2.45%)
     TPS-32     14214.88        14378.30 (1.15%)
     QPS-32     227438.14       230052.76 (1.15%)
 avg_lat-32         2.25            2.22 (1.19%)
95th_lat-32         3.06            2.95 (3.70%)
     TPS-64     14697.57        14801.04 (0.70%)
     QPS-64     235161.20       236816.57 (0.70%)
 avg_lat-64         4.35            4.32 (0.69%)
95th_lat-64         6.51            6.39 (1.79%)
     TPS-128    18417.83        18010.42 (-2.21%)
     QPS-128    294685.24       288166.68 (-2.21%)
 avg_lat-128        6.97            7.13 (-2.30%)
95th_lat-128       10.22           10.46 (-2.35%)
     TPS-256    29940.82        30491.62 (1.84%)
     QPS-256    479053.21       487865.89 (1.84%)

avg_lat-256 8.54 8.41 (1.60%)
95th_lat-256 13.22 13.55 (-2.50%)

Quoted 67 lines

Changes since v4:
1. Dietmar has commented on the task duration calculation. So refined the commit log to reduce confusion.
2. Change [PATCH 1/2] to only record the average duration of a task. So this change could benefit UTIL_EST_FASTER[1].
3. As v4 reported regression on Zen3 and Kunpeng Arm64, add back the system average utilization restriction that, if the system is not busy, do not enable the short wake up. Above logic has shown improvment on Zen3[2].
4. Restrict the wakeup target to be current CPU, rather than both current CPU and task's previous CPU. This could also benefit wakeup optimization from interrupt in the future, which is suggested by Yicong.

Changes since v3:
1. Honglei and Josh have concern that the threshold of short task duration could be too long. Decreased the threshold from sysctl_sched_min_granularity to (sysctl_sched_min_granularity / 8), and the '8' comes from get_update_sysctl_factor().
2. Export p->se.dur_avg to /proc/{pid}/sched per Yicong's suggestion.
3. Move the calculation of average duration from put_prev_task_fair() to dequeue_task_fair(). Because there is an issue in v3 that, put_prev_task_fair() will not be invoked by pick_next_task_fair() in fast path, thus the dur_avg could not be updated timely.
4. Fix the comment in PATCH 2/2, that "WRITE_ONCE(CPU1->ttwu_pending, 1);" on CPU0 is earlier than CPU1 getting "ttwu_list->p0", per Tianchen.
5. Move the scan for CPU with short duration task from select_idle_cpu() to select_idle_siblings(), because there is no CPU scan involved, per Yicong.

Changes since v2:

1. Peter suggested comparing the duration of waker and the cost to scan for an idle CPU: If the cost is higher than the task duration, do not waste time finding an idle CPU, choose the local or previous CPU directly. A prototype was created based on this suggestion. However, according to the test result, this prototype does not inhibit the cross CPU wakeup and did not bring improvement. Because the cost to find an idle CPU is small in the problematic scenario. The root cause of the problem is a race condition between scanning for an idle CPU and task enqueue(please refer to the commit log in PATCH 2/2). So v3 does not change the core logic of v2, with some refinement based on Peter's suggestion.

2. Simplify the logic to record the task duration per Peter and Abel's suggestion.

[1] https://lore.kernel.org/lkml/[email protected]/
[2] https://lore.kernel.org/all/[email protected]/

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

Chen Yu (2):
sched/fair: Record the average duration of a task sched/fair: Introduce SIS_SHORT to wake up short task on current CPU

 include/linux/sched.h   |  3 +++
 kernel/sched/core.c     |  2 ++
 kernel/sched/debug.c    |  1 +
 kernel/sched/fair.c     | 49 +++++++++++++++++++++++++++++++++++++++++
 kernel/sched/features.h |  1 +
 5 files changed, 56 insertions(+)
maintainer
#3 lore raw

Re: [PATCH v6 2/2] sched/fair: Introduce SIS_SHORT to wake up short task on current CPU

In reply to Chen Yu
Quoted 43 lines · Chen Yu

will-it-scale
=============
case load baseline compare%
context_switch1 224 groups 1.00 +946.68%

There is a huge improvement in fast context switch test case, especially when the number of groups equals the CPUs.

netperf
=======

case            	load    	baseline(std%)	compare%( std%)
TCP_RR          	56-threads	 1.00 (  1.12)	 -0.05 (  0.97)
TCP_RR          	112-threads	 1.00 (  0.50)	 +0.31 (  0.35)
TCP_RR          	168-threads	 1.00 (  3.46)	 +5.50 (  2.08)
TCP_RR          	224-threads	 1.00 (  2.52)	+665.38 (  3.38)
TCP_RR          	280-threads	 1.00 ( 38.59)	+22.12 ( 11.36)
TCP_RR          	336-threads	 1.00 ( 15.88)	 -0.00 ( 19.96)
TCP_RR          	392-threads	 1.00 ( 27.22)	 +0.26 ( 24.26)
TCP_RR          	448-threads	 1.00 ( 37.88)	 +0.04 ( 27.87)
UDP_RR          	56-threads	 1.00 (  2.39)	 -0.36 (  8.33)
UDP_RR          	112-threads	 1.00 ( 22.62)	 -0.65 ( 24.66)
UDP_RR          	168-threads	 1.00 ( 15.72)	 +3.97 (  5.02)
UDP_RR          	224-threads	 1.00 ( 15.90)	+134.98 ( 28.59)
UDP_RR          	280-threads	 1.00 ( 32.43)	 +0.26 ( 29.68)
UDP_RR          	336-threads	 1.00 ( 39.21)	 -0.05 ( 39.71)
UDP_RR          	392-threads	 1.00 ( 31.76)	 -0.22 ( 32.00)
UDP_RR          	448-threads	 1.00 ( 44.90)	 +0.06 ( 31.83)

There is significant 600+% improvement for TCP_RR and 100+% for UDP_RR when the number of threads equals the CPUs.

tbench
======

case            	load    	baseline(std%)	compare%( std%)
loopback        	56-threads	 1.00 (  0.15)	 +0.88 (  0.08)
loopback        	112-threads	 1.00 (  0.06)	 -0.41 (  0.52)
loopback        	168-threads	 1.00 (  0.17)	+45.42 ( 39.54)
loopback        	224-threads	 1.00 ( 36.93)	+24.10 (  0.06)
loopback        	280-threads	 1.00 (  0.04)	 -0.04 (  0.04)
loopback        	336-threads	 1.00 (  0.06)	 -0.16 (  0.14)
loopback        	392-threads	 1.00 (  0.05)	 +0.06 (  0.02)
loopback        	448-threads	 1.00 (  0.07)	 -0.02 (  0.07)
Quoted 2 lines

There is no noticeable impact on tbench. Although there is run-to-run variance in 168/224 threads case, with or without this patch applied.

So there is a very narrow, but significant, win at 4x overload. What about 3x/5x overload, they only have very marginal gains.

So these patches are briliant if you run at exactly 4x overload, and very meh otherwise.

Why do we care about 4x overload?

author
#4 lore raw

Re: [PATCH v6 2/2] sched/fair: Introduce SIS_SHORT to wake up short task on current CPU

Hi Peter,

Quoted 48 lines · Peter Zijlstra
Quoted 43 lines · Chen Yu

will-it-scale
=============
case load baseline compare%
context_switch1 224 groups 1.00 +946.68%

There is a huge improvement in fast context switch test case, especially when the number of groups equals the CPUs.

netperf
=======

case            	load    	baseline(std%)	compare%( std%)
TCP_RR          	56-threads	 1.00 (  1.12)	 -0.05 (  0.97)
TCP_RR          	112-threads	 1.00 (  0.50)	 +0.31 (  0.35)
TCP_RR          	168-threads	 1.00 (  3.46)	 +5.50 (  2.08)
TCP_RR          	224-threads	 1.00 (  2.52)	+665.38 (  3.38)
TCP_RR          	280-threads	 1.00 ( 38.59)	+22.12 ( 11.36)
TCP_RR          	336-threads	 1.00 ( 15.88)	 -0.00 ( 19.96)
TCP_RR          	392-threads	 1.00 ( 27.22)	 +0.26 ( 24.26)
TCP_RR          	448-threads	 1.00 ( 37.88)	 +0.04 ( 27.87)
UDP_RR          	56-threads	 1.00 (  2.39)	 -0.36 (  8.33)
UDP_RR          	112-threads	 1.00 ( 22.62)	 -0.65 ( 24.66)
UDP_RR          	168-threads	 1.00 ( 15.72)	 +3.97 (  5.02)
UDP_RR          	224-threads	 1.00 ( 15.90)	+134.98 ( 28.59)
UDP_RR          	280-threads	 1.00 ( 32.43)	 +0.26 ( 29.68)
UDP_RR          	336-threads	 1.00 ( 39.21)	 -0.05 ( 39.71)
UDP_RR          	392-threads	 1.00 ( 31.76)	 -0.22 ( 32.00)
UDP_RR          	448-threads	 1.00 ( 44.90)	 +0.06 ( 31.83)

There is significant 600+% improvement for TCP_RR and 100+% for UDP_RR when the number of threads equals the CPUs.

tbench
======

case            	load    	baseline(std%)	compare%( std%)
loopback        	56-threads	 1.00 (  0.15)	 +0.88 (  0.08)
loopback        	112-threads	 1.00 (  0.06)	 -0.41 (  0.52)
loopback        	168-threads	 1.00 (  0.17)	+45.42 ( 39.54)
loopback        	224-threads	 1.00 ( 36.93)	+24.10 (  0.06)
loopback        	280-threads	 1.00 (  0.04)	 -0.04 (  0.04)
loopback        	336-threads	 1.00 (  0.06)	 -0.16 (  0.14)
loopback        	392-threads	 1.00 (  0.05)	 +0.06 (  0.02)
loopback        	448-threads	 1.00 (  0.07)	 -0.02 (  0.07)
Quoted 2 lines

There is no noticeable impact on tbench. Although there is run-to-run variance in 168/224 threads case, with or without this patch applied.

Quoted 7 lines

So there is a very narrow, but significant, win at 4x overload. What about 3x/5x overload, they only have very marginal gains.

So these patches are briliant if you run at exactly 4x overload, and very meh otherwise.

Why do we care about 4x overload?

It was tested on a 224 CPUs system(2 sockets, 56 Cores per socket). So I guess the 4x here should be 1x?
That is when the number of workload instance equal to the number of online CPUs, it benefits a lot. I think this could be one of the most common use case:
every CPU has 1 instance.

The reason why 280/336/392/448 threads do not have benefit might be that, these overloaded case have been taken care of by SIS_UTIL. Because SIS_UTIL will inhibit idle CPU scan when the system is extremly busy.

The reason why 168 threads do not have benefit is because the system is not busy enough to trigger the short task wakeup optimization. Currently the threshold is >=50% utilization. The reason why 50% is chosen is because we don't want to break other platforms having less CPU within a LLC, and they prefer to spread the tasks rather than aggregating them.

Besides 224 threads case, I also tested other load around 224-threads:
netperf
=======

case                    load            baseline(std%)  compare%( std%)
TCP_RR                  210-threads      1.00 (  3.39)  +66.12 ( 72.21)
TCP_RR                  238-threads      1.00 (  3.48)  +752.93 (  9.58)
UDP_RR                  210-threads      1.00 (  9.85)   +7.33 ( 18.27)
UDP_RR                  238-threads      1.00 ( 19.02)  +178.96 ( 18.78)

And improvement are also observed.

thanks,
Chenyu

author
#8 lore raw
In reply to Yicong Yang
Quoted 42 lines · Yicong Yang

Hi Chenyu,

Quoted 31 lines · Chen Yu

The main purpose is to avoid too many cross CPU wake up when it is unnecessary. The frequent cross CPU wake up brings significant damage to some workloads, especially on high core count systems.

Inhibits the cross CPU wake-up by placing the wakee on waking CPU, if both the waker and wakee are short-duration tasks. The short duration task could become a trouble maker on high-load system, because it could bring frequent context switch. This strategy only takes effect when the system is busy. Because it is unreasonable to inhibit the idle CPU scan when there are still idle CPUs.

First, introduce the definition of a short-duration task. Then leverages the first patch to choose a local CPU for wakee.

Overall there is performance improvement on some overloaded case. Such as will-it-scale, netperf. And no noticeable impact on schbench, hackbench, tbench and a OLTP workload with a commercial RDBMS, tested on a Intel Xeon 2 x 56C machine.

Per the test on Zen3 from Prateek, most benchmarks result saw small wins or are comparable to sched:tip. SpecJBB Critical-jOps improved while Max-jOPS saw a small hit, but it might be in the expected range. ycsb-mongodb saw small uplift in NPS1 mode.

Throughput improvement of netperf(localhost) was observed on a Rome 2 x 64C machine, when the number of clients equals the CPUs.

Abel reported against a latency regression from Redis on an overloaded system. Inspired by his description, v5 added the check of wakee_flips to mitigate task stacking.

Quoted 7 lines

Changes since v5:
1. Check the wakee_flips of the waker/wakee. If the wakee_flips of waker/wakee are both 0, it indicates that the waker and the wakee are waking up each other. In this case, put them together on the same CPU. This is to avoid that too many wakees are stacked on one CPU, which might cause regression on redis.

Quoted 8 lines

The patch looks good to me. And for the v6 version there's no significant regression on our server. :)

Detailed results below. The setup are the same as what used on v4. There're some gain for UDP_RR. For mysql no significant regression, there're ~2% loss for 128 threads case but the proportion is within the fluctuation range so it should be ok.

Thanks Yicong for the test!

thanks,
Chenyu