sched/fair: Optimize idle core discovery algorithm via LLC-wide bitmask
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
@@ -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
@@ -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
Peter Zijlstra
maintainerQuoted 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' tosched_domain_sharedfor 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.