Skip to contentSkip to conversation

sched/fair: Optimize idle core discovery algorithm via LLC-wide bitmask

PATCH In review Qiliang Yuan 2 participants 2 messages Jan 22 – Jan 23 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched/fair: Optimize idle core discovery algorithm via LLC-wide bitmask

The current select_idle_cpu() employs a linear O(N) scan to find idle cores, which scales poorly on modern high-core-count systems.

This patch optimizes the discovery algorithm by:
1. Adding a per-LLC 'idle_cores_mask' to sched_domain_shared for tracking core-level idle status.
2. Converting the linear search into an efficient bitmask iteration, reducing typical search complexity towards O(1) in sparse scenarios.
3. Implementing a lazy-clear mechanism during the scan to maintain efficiency without expensive global synchronization.

This algorithmic refinement minimizes the search space in the critical wakeup path, effectively mitigating linear scaling overhead on large SMT machines.

---
 include/linux/sched/topology.h |  1 +
 kernel/sched/fair.c            | 49 ++++++++++++++++++++++++----------
 kernel/sched/topology.c        |  2 +-
 3 files changed, 37 insertions(+), 15 deletions(-)
include/linux/sched/topology.h +1 -0
index 45c0022b91ce..4223f2cd7eb8 100644
@@ -68,6 +68,7 @@ struct sched_domain_shared {
 	atomic_t	nr_busy_cpus;
 	int		has_idle_cores;
 	int		nr_idle_scan;
+	unsigned long	idle_cores_mask[];
 };
 
 struct sched_domain {
kernel/sched/fair.c +35 -14

66 lines not on this page · raw message

kernel/sched/topology.c +1 -1
index cf643a5ddedd..5a3f29a26bdb 100644
@@ -2392,7 +2392,7 @@ static int __sdt_alloc(const struct cpumask *cpu_map)
 
 			*per_cpu_ptr(sdd->sd, j) = sd;
 
-			sds = kzalloc_node(sizeof(struct sched_domain_shared),
+			sds = kzalloc_node(sizeof(struct sched_domain_shared) + cpumask_size(),
 					GFP_KERNEL, cpu_to_node(j));
 			if (!sds)
 				return -ENOMEM;
Signature · 1 line
2.51.0
maintainer
#1 lore raw
Quoted 11 lines · Qiliang Yuan

The current select_idle_cpu() employs a linear O(N) scan to find idle cores, which scales poorly on modern high-core-count systems.

This patch optimizes the discovery algorithm by:
1. Adding a per-LLC 'idle_cores_mask' to sched_domain_shared for tracking core-level idle status.
2. Converting the linear search into an efficient bitmask iteration, reducing typical search complexity towards O(1) in sparse scenarios.
3. Implementing a lazy-clear mechanism during the scan to maintain efficiency without expensive global synchronization.

Quoted 3 lines

This algorithmic refinement minimizes the search space in the critical wakeup path, effectively mitigating linear scaling overhead on large SMT machines.

Since this is a performance patch; what is missing here is the actual performance data.

This can be in the form of a micro-benchmark, or perf numbers showing the improvement for this code-path.

Also, what kind of topologies have you tested this on; typically Intel has a few very large LLC domains while AMD has more smaller ones.