The Elements of Cache Programming Style (2000)
usenix.org
usenix.org
This was written at a time when the Linux scheduler was a simple process loop. So Linux would come to a crawl when the process count hit like 64. I figured out the underlying but I didn't submit a patch. Then I really started looking at the problem, and the result of that investigation was this article which was/is a bit bombastic but a good tutorial on issues with caches nonetheless.
Weird that it's on the front page lo these many years later.
Maybe update the article to current times into two parts? :-) One explaining general Cache principles and how an "Application Programmer" can take advantage of them and the other on how the Linux Kernel does it; Theory and Practice!
PS: The Schimmel book (which you have also referenced) is the only place where i have seen all the cache issues explained comprehensively and clearly.
I'd like a tool, maybe part of Cachegrind, which said dude, this instruction is thrashing this L2 set. A profiling virtual machine (Valgrind) is kind of the ultimate lookaside to do this. It could easily (if expensively) evaluate these kinds of queries at each load/store. I think it's better to be able to find these problems than understand them from first principles.
I think something like Computer Organization And Design could have a section on cache programming and maybe a problem set. But if I was to revisit this, I'd write something like A Bestiary of Caches which would delineate all of the different caches in a modern CPU. Things like branch prediction target caches, the micro-op cache, the LSD, ... but all in one place.
You said it; now you gotta do it :-)
PS: Jokes aside, it is a sincere request. Most folks don't know about these issues and if they do, it is piecemeal, bringing them all together in one place by somebody who understands it all would be invaluable.
For anyone interested on similar patterns on performance or good memory access practices. I highly recommend this recent talk by Andrew Kelly on data oriented design. It's one (if not the best) talk about the topic.
https://media.handmade-seattle.com/practical-data-oriented-d...
But as pointed out by another comment, I don't think it's that mainstream. Outside HPC and game development. At least that's what came up when you google the relevant terms like cache, locality, etc.
You might look at something like the Arm® Cortex®-A75 Software Optimization Guide for a good picture of the microarchitecture. Unfortunately Apple doesn't put out that kind of information for the m1. The LLVM docs have a little information but the structure isn't that different from an A75 although the latencies are.
For instance, if you know a collection of things is going to be bounded by a reasonable quantity (e.g. less than 1mm) and that you will frequently need to perform a full linear scan of these things, you should consider using an array rather than some b-tree or other pointer-chasing type (List/Dictionary/etc). This is literally a simple "Should I use List<T> or T[MaxElements]" determination. The effects of this are very profound if many scans of these items need to be made per unit time (i.e. a game loop).
You can take this one step further by trying to make the type used in the collection a value type rather than a reference type. Depending on language/runtime/problem space, this can give you another order of magnitude uplift. And, its pretty much as simple as "public [readonly] struct" vs "public class".
This is because they were sequentially trying things in a loop and using exceptions for flow control.
If you use an APM, the overhead of this is monstrous.
This particular function is called in every authenticated Azure call by default. Using any such API turns the debug output into a wall of spurious errors scrolling past like the Matrix.
To top it off, they use asynchronous code in a sequential style, so the latency is strictly worse than naive synchronous code. This is a for a bunch of back to back HTTP API calls.
They closed the ticket with a “this is what the style guide says to do” and now millions of customers have to just live with this.
If you ever wondered why nothing takes less than a second in Azure, it’s just a handful of reasons like this.
An easy fix to reduce API response times from seconds to milliseconds… rejected.
Although constraint declaration is orthogonal to data-oriented development, I'd say that the philosophy of using generic constraint solvers (or other overly generalized CS ideas) goes against the spirit of DOD, which is to "just simply do the work". It is after all reacting against object-orientation (and even modern FP) which tended to think too much in the abstract and worrying too much about some form of taxonomy, as opposed to coding against plain data.
no need to reach for upcoming languages, it's doable directly in C++: https://github.com/celtera/ahsohtoa =)