sched: Avoid SMT siblings in select_idle_sibling() if possible

I did some experiments with volanomark and it does turn out to be sensitive to SD_BALANCE_WAKE, while the other wake-heavy benchmark that I am dealing with (Trade) benefits from it.

Normalized results for both benchmarks provided below.

Machine : 2 Quad-core Intel X5570 CPU (H/T enabled) Kernel : tip (HEAD at b86148a)

Before patch After patch

Trade thr'put 1 2.17 (~200% improvement)
volanomark 1 0.8 (20% degradation)

Quick description of benchmarks
===============================

Trade was run inside a 8-vcpu VM (cgroup). 4 other 4-vcpu VMs running cpu hogs were also present, leading to this cgroup setup:

	/cgroup/sys (1024 shares - hosts all system tasks)
	/cgroup/libvirt (20000 shares)
	/cgroup/libvirt/qemu/VM1 (8192 cpu shares)
	/cgroup/libvirt/qemu/VM2-5 (1024 shares)

Volanomark server/client programs were run in root cgroup.

The patch essentially does balance on wake to look for any idle cpu in same cache domain as its prev_cpu (or cur_cpu if wake_affine obliges), failing to find looks for least loaded cpu. This helps minimize latencies for trade workload (and thus boost its score). For volanomark, it seems to hurt because of waking on a colder L2 cache. The tradeoff seems to be between latency and cache-misses. Short of adding another tunable, are there better suggestions on how we can address this sort of tradeoff?

---
 include/linux/topology.h |    4 ++--
 kernel/sched/fair.c      |   26 +++++++++++++++++++++-----
 2 files changed, 23 insertions(+), 7 deletions(-)

Index: current/include/linux/topology.h
===================================================================
@@ -96,7 +96,7 @@ int arch_update_cpu_topology(void);
 				| 1*SD_BALANCE_NEWIDLE			\
 				| 1*SD_BALANCE_EXEC			\
 				| 1*SD_BALANCE_FORK			\
-				| 0*SD_BALANCE_WAKE			\
+				| 1*SD_BALANCE_WAKE			\
 				| 1*SD_WAKE_AFFINE			\
 				| 1*SD_SHARE_CPUPOWER			\
 				| 0*SD_POWERSAVINGS_BALANCE		\

@@ -129,7 +129,7 @@ int arch_update_cpu_topology(void);
 				| 1*SD_BALANCE_NEWIDLE			\
 				| 1*SD_BALANCE_EXEC			\
 				| 1*SD_BALANCE_FORK			\
-				| 0*SD_BALANCE_WAKE			\
+				| 1*SD_BALANCE_WAKE			\
 				| 1*SD_WAKE_AFFINE			\
 				| 0*SD_PREFER_LOCAL			\
 				| 0*SD_SHARE_CPUPOWER			\

Index: current/kernel/sched/fair.c
===================================================================
@@ -2638,7 +2638,7 @@ static int select_idle_sibling(struct ta
 	int prev_cpu = task_cpu(p);
 	struct sched_domain *sd;
 	struct sched_group *sg;
-	int i;
+	int i, some_idle_cpu = -1;
 
 	/*
 	 * If the task is going to be woken-up on this cpu and if it is

@@ -2661,15 +2661,25 @@ static int select_idle_sibling(struct ta
 	for_each_lower_domain(sd) {
 		sg = sd->groups;
 		do {
+			int skip = 0;
+
 			if (!cpumask_intersects(sched_group_cpus(sg),
 						tsk_cpus_allowed(p)))
 				goto next;
 
-			for_each_cpu(i, sched_group_cpus(sg)) {
-				if (!idle_cpu(i))
-					goto next;
+			for_each_cpu_and(i, sched_group_cpus(sg),
+							 tsk_cpus_allowed(p)) {
+				if (!idle_cpu(i)) {
+					if (some_idle_cpu >= 0)
+						goto next;
+					skip = 1;
+				} else
+					some_idle_cpu = i;
 			}
 
+			if (skip)
+				goto next;
+
 			target = cpumask_first_and(sched_group_cpus(sg),
 					tsk_cpus_allowed(p));
 			goto done;

@@ -2677,6 +2687,9 @@ next:
 			sg = sg->next;
 		} while (sg != sd->groups);
 	}
+
+	if (some_idle_cpu >= 0)
+		target = some_idle_cpu;
 done:
 	return target;
 }

@@ -2766,7 +2779,10 @@ select_task_rq_fair(struct task_struct *
 			prev_cpu = cpu;
 
 		new_cpu = select_idle_sibling(p, prev_cpu);
-		goto unlock;
+		if (idle_cpu(new_cpu))
+			goto unlock;
+		sd = rcu_dereference(per_cpu(sd_llc, prev_cpu));
+		cpu = prev_cpu;
 	}
 
 	while (sd) {

Does volanomark still do yield(), thereby invoking a random shuffle of thread scheduling and pretty much voluntarily ejecting itself from most scheduler performance considerations?

If it uses a real locking primitive such as futexes then its performance matters more.

Thanks,

Ingo

I could count 3.5M yield() calls across 16 cpus over a period of 5.4sec, so yes it does seem to make very good use of yeild()!

Good point ..I will gather more data for additional benchmarks (tbench, sysbench) and post shortly.

- vatsa

Some more interesting results on more recent tip kernel.

Machine : 2 Quad-core Intel X5570 CPU w/ H/T enabled (16 cpus) Kernel : tip (HEAD at ee415e2)
guest VM : 2.6.18 linux kernel based enterprise guest

Benchmarks are run in two scenarios:

1. BM -> Bare Metal. Benchmark is run on bare metal in root cgroup
2. VM -> Benchmark is run inside a guest VM. Several cpu hogs (in various cgroups) are run on host. Cgroup setup is as below:

	/sys (cpu.shares = 1024, hosts all system tasks)
	/libvirt (cpu.shares = 20000)

/libvirt/qemu/VM (cpu.shares = 8192. guest VM w/ 8 vcpus) /libvirt/qemu/hoga (cpu.shares = 1024. hosts 4 cpu hogs) /libvirt/qemu/hogb (cpu.shares = 1024. hosts 4 cpu hogs) /libvirt/qemu/hogc (cpu.shares = 1024. hosts 4 cpu hogs) /libvirt/qemu/hogd (cpu.shares = 1024. hosts 4 cpu hogs)

First BM (bare metal) scenario:

tip tip + patch

volano 1 0.955 (4.5% degradation)
sysbench [n1] 1 0.9984 (0.16% degradation)
tbench 1 [n2] 1 0.9096 (9% degradation)

Now the more interesting VM scenario:

tip tip + patch

volano 1 1.29 (29% improvement)

sysbench [n3]	1	2      (100% improvement)
tbench 1 [n4] 	1       1.07   (7% improvement)
tbench 8 [n5] 	1       1.26   (26% improvement)

httperf [n6] 1 1.05 (5% improvement)
Trade 1 1.31 (31% improvement)

Notes:

n1. sysbench was run with 16 threads.
n2. tbench was run on localhost with 1 client
n3. sysbench was run with 8 threads
n4. tbench was run on localhost with 1 client
n5. tbench was run over network with 8 clients
n6. httperf was run as with burst-length of 100 and wsess of 100,500,0

So the patch seems to be a wholesome win when VCPU threads are waking up (in a highly contended environment). One reason could be that any assumption of better cache hits by running (vcpu) threads on its prev_cpu may not be fully correct as vcpu threads could represent many different threads internally?

Anyway, there are degradations as well, considering which I see several possibilities:

1. Do balance-on-wake for vcpu threads only.
2. Document tuning possibility to improve performance in virtualized environment:
- Either via sched_domain flags (disable SD_WAKE_AFFINE at all levels and enable SD_BALANCE_WAKE at SMT/MC levels)
- Or via a new sched_feat(BALANCE_WAKE) tunable

Any other thoughts or suggestions for more experiments?

--

Balance threads on wakeup to let it run on least-loaded CPU in the same cache domain as its prev_cpu (or cur_cpu if wake_affine() test obliges).

---
 include/linux/topology.h |    4 ++--
 kernel/sched/fair.c      |    5 ++++-
 2 files changed, 6 insertions(+), 3 deletions(-)

Index: current/include/linux/topology.h
===================================================================
@@ -96,7 +96,7 @@ int arch_update_cpu_topology(void);
 				| 1*SD_BALANCE_NEWIDLE			\
 				| 1*SD_BALANCE_EXEC			\
 				| 1*SD_BALANCE_FORK			\
-				| 0*SD_BALANCE_WAKE			\
+				| 1*SD_BALANCE_WAKE			\
 				| 1*SD_WAKE_AFFINE			\
 				| 1*SD_SHARE_CPUPOWER			\
 				| 0*SD_POWERSAVINGS_BALANCE		\

@@ -129,7 +129,7 @@ int arch_update_cpu_topology(void);
 				| 1*SD_BALANCE_NEWIDLE			\
 				| 1*SD_BALANCE_EXEC			\
 				| 1*SD_BALANCE_FORK			\
-				| 0*SD_BALANCE_WAKE			\
+				| 1*SD_BALANCE_WAKE			\
 				| 1*SD_WAKE_AFFINE			\
 				| 0*SD_PREFER_LOCAL			\
 				| 0*SD_SHARE_CPUPOWER			\

Index: current/kernel/sched/fair.c
===================================================================
@@ -2766,7 +2766,10 @@ select_task_rq_fair(struct task_struct *
 			prev_cpu = cpu;
 
 		new_cpu = select_idle_sibling(p, prev_cpu);
-		goto unlock;
+		if (idle_cpu(new_cpu))
+			goto unlock;
+		sd = rcu_dereference(per_cpu(sd_llc, prev_cpu));
+		cpu = prev_cpu;
 	}
 
 	while (sd) {

Yeah, interesting. I find myself ever returning to this message, as gears grind away trying to imagine what's going on in those vcpus.

Those make sense, fast path cycles added.

That's what your numbers say to me with this patch. I'm not getting the why, but your patch appears to reduce vcpu internal latencies hugely.

Other than nuke select_idle_sibling() entirely instead, none here.

-Mike

Hell no ;-) we're not going to special case some threads over others.

But domain flags are not exported -- except under SCHED_DEBUG and that sysctl mess.. also SD_flags are not stable.

sched_feat() is not a stable ABI and shouldn't ever be used for anything but debugging (hence it lives in debugfs and goes away if you disable SCHED_DEBUG).

I would very much like more information on why things are a loss. Is it really related to what cpu you pick, or is it the cost of doing the balance thing?

More interesting for whoem? I still think virt is an utter waste of time ;-)

That smells like there's more to the story, a 100% improvement is too much..

Yeah I have rubbed my eyes several times to make sure its true and ran the same benchmark (sysbench) again now! I can recreate that ~100% improvement with the patch even now.

To quickly re-cap my environment, I have a 16-cpu machine w/ 5 cgroups. 1 cgroup (8192 shares) hosts sysbench inside 8-vcpu VM while remaining 4 cgroups (1024 shares each) hosts 4 cpu hogs running on bare metal. Given this overcommittment, select_idle_sibling() should mostly be a no-op (i.e it won't find any idle cores and thus defaults to prev_cpu). Also the only tasks that will (sleep and) wakeup are the VM tasks.

Since the patch potentially affects (improves) scheduling latencies, I measured Sum(se.statistics.wait_sum) for the VM tasks over the benchmark run (5 iterations of sysbench).

tip : 987240 ms
tip + patch : 280275 ms

I will get more comprehensive perf data shortly and post.

reduced latencies for its VM tasks.

The hard part to figure out (when we are inside select_task_rq_fair()) is whether any potential improvement in latencies (because of waking up on a less loaded cpu) will offshoot the cost of potentially more L2-cache misses, for which IMHO we don't have enough data to make a good decision.

- vatsa

But if the machine is pegged latency should not impact throughput (since there's always work to do), so are you creating extra idle time some place?

Are you running against lock-inversion in the vcpus? Or that tlb shootdown issue we had in the gang scheduling thread? Both are typically busy-wait time, which is of course harder to spot that actual idle time :/

Then again, reducing latency is good, so I don't object to that per-se, but that flips the question, why does it regress those other loads?

The biggest regression came from tbench, wasn't that mostly a random number generator anyway? How stable are those results, do you have a variance measure on the results?

That's dbench ;-) Tbench does wiggle around more than you'd like though. I've never tracked, but in lots of running the thing, 2-3% you can forget chasing, and I once bisected a 5% regression to an unrelated change, reverted and re-applied the suspect a few times in disbelief, and it tracked. You can't trust it _too_ much. I consider it a reliable indicator that I'd better do more testing. If others agree, it's a real regression, if not, it's those damn Elves 'n Gremlins ;-)

-Mike