Linux Randomly Picking Idle CPU Cores Shows Modest Win On High Core Count Systems

Arm engineer Christian Loehle sent out a patch series today proposing that the Linux scheduler code randomize its picking of equally shallow idle CPU cores. This randomization is showing to deliver a win at least for high CPU core counts for better distributing workloads. Loehle found that the Linux kernel scheduler's behavior with concurrent slow-path selectors can converge on the same idle CPU cores before either task is enqueued. To avoid that pitfall of potentially converging tasks on the same idle CPU core(s), his proposed approach is to randomize the equally shallow idle CPU cores. Testing on a dual aging Ampere Altra with 160 CPU cores found up to a few percent throughput improvement in benchmarking with Stress-NG. The patches go on to elaborate: "The slow-path CPU picker favours the most recently idle CPU as a proxy for cache warmth. A more recent idle stamp may make ongoing entry more likely. Among CPUs with equal advertised exit latency, this may favour the one with the highest wakeup cost: if entry cannot be aborted, it must finish entry and then exit, while an already-resident CPU only needs to exit. The same advertised worst-case latency covers both cases. idle_stamp does not track the current CPUIdle entry, so an older scheduler-idle CPU may also be re-entering. ... Picking the first eligible idle CPU leaves a scan-order bias. Concurrent slow-path selectors can choose the same CPU before either task is enqueued. Use reservoir sampling in the tie branch, resetting the candidate count when a lower advertised exit latency is found. Use the per-CPU scheduler PRNG and reciprocal_scale() to avoid variable division or a second scan. This reduces deterministic convergence without reserving the chosen CPU." The patches for introducing this randomness are out on the kernel mailing list. Some initial questions on this work revolve around the benefit of the randomness on lower core count CPUs. And with this randomization could lead to some non-predictable behavior. We'll see where this work ends up but at least for today's high core count CPUs with the likes of the new AMD EPYC 9006 series going up to 256 cores per socket could prove beneficial if other scheduler improvements can't be made for addressing the scan-order bias.