Studying Linux Schedulers, and Why Metrics Matter
A cruel reminder that measuring stuff is hard

The classical advice goes that you prefer to keep processes on the same core for as long as possible (without inducing unfairness) so that you can keep their data warm in the caches, and Linux's EEVDF scheduler does a pretty good job of that. What isn't taken into account is making sure processes are arranged across the CPU(s) in such a way that you minimize the number of levels in the cache hierarchy you have to traverse to service accesses to shared memory.

As an illustrative example – consider a dual-socket Xeon system (which was our testing configuration). If a process makes an access to shared memory, let's be pessimistic and suppose that another process has recently accessed this memory as well, has performed a write, and that the dirty data is still in the cache hierarchy. What are the possible coherence actions that could occur? It depends on where the process was scheduled:

1. If the process was running on the same core (in a separate scheduling quantum), nothing! We have the data! Yippee! We will find it somewhere in our L1/L2 private cache hierarchy, and require no coherence actions.
2. If the process ran on another core, then on modern Xeon systems there are two ways this can pan out.
   1. The process was scheduled onto another core in our socket. This means that we will force a write-back from the other core's private cache hierarchy into the fully-shared L3, and either pull data from DRAM or directly from the other core's private cache hierarchy via the coherency fabric.
   2. The process was scheduled on the other socket. This is the worst-case, as the other socket's L3 will need to transfer data across the chipset (or we go to DRAM), at which point we can pull the data all the way through our own cache hierarchy to use it… yikes!

As we can see, there is a fairly asymmetric penalty here to service a cache miss when dealing with multi-threaded programs. So really, our goal is to minimize the number of times we have to deal with case 2.2. If we were only read-sharing across cores, everything would be hunky-dory since data is much more likely to stay cache-resident. It's really this pessimistic write-sharing behavior that starts to be annoying. Ideally, we generally prefer to trigger case 2.1 in this situation, since it balances cache miss penalties with scheduling flexibility and maximizing available compute.

The granularity of this decision tree will inevitably change depending on the CPU/configuration we are using. Zen 1 and 2, for example, would have a third branch here, as some SKUs contained separated L3 caches per CCX, so you could get away with faster access times if you managed to schedule your data-sharing processes on the same CCX.

So with some fairly strict caveats – no sub-NUMA clustering, ignoring memory residency, etc. – we set out to answer three questions:

1. How much of a benefit is there from successfully scheduling multi-threaded processes fully within one LLC domain?
2. Do current schedulers do a good job of ensuring that this happens?
3. How can they be improved to actually make this happen?

Our study mostly focused on points 1 and 2, with 3 being a "we hope this can happen", until we realized that CAS was starting to address point 3. So at this point we thought, "what if we just test CAS and EEVDF and find the gaps?". Okay, fair enough. But then we realized that we couldn't actually do that on shared lab resources and instead pivoted to profiling LAVD. It obviously exhibits very different behaviors and priorities, but the hope was that the second-order effects of LAVD would emulate that of CAS. I'm not totally sure how accurate that hypothesis ended up being, but EOTD we needed some testing methodology so this would have to do.

There's a lot more background about the internals of these schedulers about how various Linux schedulers work and our evaluation methods, but I'll fast forward to the mishaps in the next section for (relative) brevity. More fine-grained details can be found in our final report, either in PDF or web format.

So at this point, our study is clear! We want to characterize how performance is impacted by scheduling threads auto-magically with the default Linux scheduler, with a "cache-optimized" scheduler, and with manual restriction of thread positions.

As many school projects go, we started a little close to the deadline, and followed a fairly linear train of thought to start testing right away. Our experimental setup was to track coherence actions (via read-for-ownership requests sent across the socket) and to track latency figures with the various configurations, and try to drill down exactly what aspect of runtime changing had contributed to performance increases/decreases. Since our benchmarks were all run with a thread count at/under the capacity of a single socket, our proxy for an "idealized" placement across cores was to simply restrict benchmarks to a single socket via numactl as a control.

This led to one of the most striking results of our entire study: both the standard Linux scheduler and specialized LAVD scheduler perform approximately the same on our benchmarks, but using numactl to restrict thread scheduling to a single socket improved runtime by as much as 3x!

So I guess if any of you are currently using a multi-socketed machine to run workloads in an under-subscribed fashion, I would recommend at least trying to use numactl to pin workloads to a single LLC domain or a set of cores – you can gain extreme speedup in multi-threaded shared-memory programs. This is mostly due to the fact that the Linux load balancer will try to ensure that all sockets are approximately equally loaded as thread count permits, even if that actively disadvantages the host program.

The salient exception to this observation was the mediawiki benchmark, which we sourced from DCPerf – how had the runtime barely moved at all? Maybe it was the fact that cache hitrates hadn't really improved?

Okay, we can check whether that's true. Let's take a look at if the number of read-for-ownership misses (e.g L3 wants to write to something but it doesn't have the data, so it asks the other core to let it own data) has changed. When we have strong write sharing, we expect that number to go up since shared cachelines should bounce between the two sockets' L3 caches.

Whelp. Now we have two mysteries.

1. How has mediawiki not sped up at all, even with an improvement in L3 RFOs?
2. What the hell is going on with perlbench? What is making it speed up so much?

We didn't end up being able to answer either of these questions prior to the deadline unfortunately – in fact, we found this relationship the day our paper was due! So with a severe sleep deficit and copious amounts of caffeine in our bloodstreams, we wrote that we hadn't been able to pin down the issue in our final report, and continued slogging through more graphs and writing. We ended up finishing the report at exactly 11:45PM, scampered over to Siebel and slid the report under our professor's door as fast as possible. And I don't think any of us really gave it another thought after submission.

Cut to a couple weeks after end-of-semester, and I was cleaning up the traces we'd used for this project. And for some reason I have since forgotten, I was curious what the MIPS was for each of these benchmarks.

Well that makes… no sense. Throughput has gone up significantly but runtime hasn't changed?? What command did we use to run the benchmark?

cd /home/pradyun/pg_work/dcperf/
sudo ./perf_collect_mw "$JOBNAME" ./benchpress_cli.py run oss_performance_mediawiki_mlp \
    -i '{"scale_out": 1, "client_threads": 32, "duration": "10m"}' &

… Oh boy. Duration was fixed to 10 minutes. This directive was buried so deeply in our testing infrastructure, and reused so many times over the course of this project that we'd completely forgotten about it.

So in one shot, several mistakes have been made. Speedup was calculated with the assumption that instructions have been held constant, which was not the case for this benchmark. And not only have we accidentally reported another single-socket speedup as having been a phantom "no-change", we've also somehow masked the one datapoint that made LAVD look better. For the latter bit, my theory is that the nature of mediawiki suits the chain-of-tasks model that LAVD was designed for.

Side Note: LAVD was designed and optimized for the Steam Deck by Changwoo Min and the great folks over at Igalia. He had a pretty great talk about LAVD at OSPM25 which you can find here, would recommend watching!

So that was… long-winded. I hope it was at the very least entertaining! Regardless, this is one of those experiences that I hope sticks with me. For one, I hope it teaches me to stop procrastinating schoolwork so much sometimes, but also that the choice of metrics can very easily disguise results as something they're not. That can both be in the negative direction (this study) but also the positive direction. Both of these directions can be pretty dangerous, especially in environments where you fix the benchmarks and tests early on and forget about them going forwards (e.g performance engineering CI pipelines). I guess the long and short of what I'm trying to say is this:

Picking good metrics to communicate your results helps not only present findings better, but also lets your work be resilient to mistakes or oversights made in experimental design.

At a more meta-level, I feel kind of obligated to take more care with experimental methodology in future profiling studies. This was really the first time I'd profiled anything on a computer without pre-rolled tooling to do it (e.g NVIDIA's SoL tools), and it definitely showed in some of the rougher edges of our evaluation. But at the very least, I'm glad that this saga occurred within the confines of a school project rather than an actual research paper, and that I can carry the lessons here into future research.

If you're interested in some of the finer-grain details of our evaluation methodology, more performance counters from our testing, or a fairly long expository section about how LAVD and EEVDF work in Linux, I'd recommend reading our final report. It's not the most well-refined study ever, but we all learned a lot from it!

AI Disclosure: This post was written by hand and then later proofread/fact-checked with the help of an LLM. I have been an abuser of -- for longer than I can remember, and I will continue to use it – unfortunately, it gets converted into an em-dash by my Org export engine! It's truly unfortunate that hyphenation has been broadly conflated with "AI slop", yet I will continue to use it at will.