12 ms·
Myths Programmers Believe about CPU Caches (2018)
- dragontamer 7y agoA good, introductory, high-level overview of what is going on with cache coherence... albeit specific to x86. ARM systems are more relaxed, and therefore need more barriers than on x86. Memory barriers (which also function as "compiler barriers" for the memory / register thing discussed in the article) are handled as long as you properly use locks (or other synchronization primitives like semaphores or mutexes). Its good to know how things work "under the covers" for performance reasons at least. Especially if you ever write a lock-free data-structure (not allowed to use... well... mutexes or locks), so you need to place the barriers in the appropriate spot. ------ I think the acquire/release model of consistency will become more important in the coming years. PCIe 4.0 is showing signs of supporting acquire/release... ARM and POWER have added acquire/release model instructions, and even CUDA has acquire/release semantics being built. As high-performance code demands faster-and-faster systems, the more-and-more relaxed our systems will become. Acquire/release is quickly becoming the standard model.
- cwzwarich 7y ago> As high-performance code demands faster-and-faster systems, the more-and-more relaxed our systems will become. Acquire/release is quickly becoming the standard model. Linux relies heavily on performant RCU for scalability, which a pure acquire/release SW programming model can't support.
- dragontamer 7y agoThere must be some kind of communication error going on. I don't know much about RCU, so I just pulled up this webpage: https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt https://www.kernel.org/doc/Documentation/RCU/whatisRCU.txt In it is: > The rcu_read_lock() and rcu_read_unlock() primitive read-acquire and release a global reader-writer lock. Seems like RCU-operations in the Linux kernel are defined in acquire-barrier and release-barrier terms. I heard a while ago that RCU could be discussed in terms of release-consume semantics (which are slightly faster but harder to understand...) but very few people understand release-consume. As such, release-acquire is probably the memory model of the future. I'm not really aware of anything aside from: Fully Relaxed (unordered), the obscure release-consume, release-acquire, and finally sequentially consistent (too slow for modern systems) --------- Are you perhaps confusing "acquire-release" semantics (which is a memory-barrier / cache coherence principle) with spinlocks perchance? Acquire-release seems to be the "Fastest-practical" memory consistency model. (Since Relaxed doesn't work, and release-consume is too confusing) For more info on acquire-release, Preshing's blogposts are great: https://preshing.com/20130922/acquire-and-release-fences/ https://preshing.com/20130922/acquire-and-release-fences/
- jabl 7y ago> I'm not really aware of anything aside from: Fully Relaxed (unordered), the obscure release-consume, release-acquire, and finally sequentially consistent (too slow for modern systems) What about Total Store Ordering (TSO), which is what e.g. the obscure and rare x86(-64) architecture implements (and SPARC as well)?
- gpderetta 7y agoIn TSO every store is a release and every load is a acquire, so it maps very efficiently to the acquire/release model.
- jabl 7y agoSure, since it's a stronger model, so code which works on weaker acquire/release hw will work on TSO hw as well. You might as well say that sequential consistency maps very efficiently to a acquire/release model too in the same way.
- gpderetta 7y agoIsn't TSO the closest practical implementation to a acquire/release model? What are the practical differences? I know that TSO allows more easily to recover sequential consistency with additional barriers (Intel strengthened their original memory model to TSO for this reason).
- jabl 7y agoNo, acquire/release is a much weaker model than TSO. TSO is basically sequential consistency (SEQCST) + a store buffer. I.e. stores don't go immediately to main memory, but rather via a store buffer. Loads first peek into the store buffer of the local CPU core before going to memory. The practical effect is that in contrast to SEQCST stores may be reordered after loads ("store->load" reordering more formally). Acquire-release consistency allows many more reorderings in addition to store->load (load->load, load->store, store->store). For more info see e.g. Table 5 in http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf http://www.rdrop.com/users/paulmck/scalability/paper/whymb.2...
- jabl 7y ago> ARM and POWER have added acquire/release model instructions They have implemented the acquire-release consistency model since day one (or, the day they started supporting multi-processors). Yes, there are some subtleties there that have in some cases been tightened later on, e.g. multi-copy atomicity.
- dragontamer 7y agoIIRC, there was a big stink because ARM and POWER historically implemented consume/release semantics, which is very slightly more relaxed than the now de-facto standard acquire/release semantics. ARM and POWERPC CPU devs worked very hard to get consume/release into C++11, but no compiler writer actually implemented that part of the standard. As such, consume/release can be safely forgotten into the annals of computer history (much like DEC Alpha's fully relaxed semantics) Then in ARM8, ARM simply added LDAR (Load-acquire) and STLR (Store-release) instructions. https://developer.arm.com/docs/100941/0100/barriers https://developer.arm.com/docs/100941/0100/barriers . So the ARM CPU how fully supports the acquire/release model. Apparently IBM's POWER instruction set was similarly strengthened to acquire/release (either POWER8 or POWER9). ARM / POWER "normal" loads and stores are still consume/release semantics. But compilers can simply emit LDAR (load-acquire) for the stronger guarantee. ---------- I remember at least one talk that showed that consume/release is ideal for things like Linux's RCU or something like that (that acquire/release is actually "too strong" for RCU, and therefore suboptimal). But because compiler-writers found consume/release too hard to reason about in practice, we're stuck with acquire/release. It seems like the C++ standard continues to evolve to push for memory_order_consume (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0750r1.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p075...), but all the details are still up for discussion.
- jabl 7y ago> ARM and POWERPC CPU devs worked very hard to get consume/release into C++11 AFAIR Paul McKenney was the primus motor, and the motivation was largely RCU. Then again, McKenney also worked for IBM at the time and certainly had an interest in pushing a model that mapped well to POWER. But it turned out to be both somewhat mis-specified and hard to implement cleanly, so most compilers just implemented it as an acquire. As you mention, there is ongoing work to fix it. As for ARM, it seems the big thing they've done since the initial release of ARMv8 is to banish non-multicopy atomicity. See https://www.cl.cam.ac.uk/~pes20/armv8-mca/armv8-mca-draft.pdf https://www.cl.cam.ac.uk/~pes20/armv8-mca/armv8-mca-draft.pd...
- gpderetta 7y agoI don't see anything x86 specific on the article. It focuses on cache coherency, which is applicable to ARM and POWER, and there isn't much about memory model. Even the description of MOESI is just an introduction and, as the article mentions, actual systems use more complicated protocols. Edit: if anything, the misconception is that memory barriers have anything to do with cache coherency.
- nostrademons 7y agoAnyone else start thinking of Rust's mutable/immutable borrow system when reading the MESI algorithm? It's not quite the same - with Rust, mutable borrows are never shared, and you can never mutate a shared read-only borrow - but the principle seems like a simplification of the full MESI protocol. It seems like this would be generally applicable for a wide variety of distributed & concurrent applications.
- xakahnx 7y agoKeeping the directory coherent is the difficult part when translating directory-based cache coherence protocols to other distributed systems problems. The directory is like an oracle that sees every transaction in order. This is hard in most network distributed systems problems where you have to worry about availability, network partitioning, or durability of this node.
- yvdriess 7y agoIndeed, the evolution will probably in the other direction, with the on chip network adopting algorithms from wider networks to deal with scaling problems. DRAM interfaces use to be pretty simple, now they are being trained almost like a DSL line.
- nemothekid 7y agoI've never heard of the MESI protocol before so that was really interesting to read, and I liked the comparison to distributed systems. I'm wondering if the MESI protocol could be used in a networked database manner? I feel like you need master node though to coordinate everything though (like the L2 does in the example).
- cperciva 7y agoThe essential point of MESI is that it doesn't need a single master. In a sense, anyone who has exclusive ownership of a cache line is the "master" for that one cache line. The downsides of MESI are that (a) it requires broadcasts, which don't scale very well; and (b) it doesn't tolerate partitions -- which also imposes an effective scaling limit, since large systems are always partitioned (usually with a partition of N-k and k partitions of 1, due to k nodes having failed).
- xakahnx 7y agoMore than just broadcasts as we think of them in networked systems, it requires serialized/transactional broadcasts. Network distributed systems also have problems with ordering which is something made easier when you have a single bus with all transactions in sequence.
- jabl 7y ago> The downsides of MESI are that (a) it requires broadcasts No, it can be implemented with directory instead, e.g. https://en.wikipedia.org/wiki/Directory-based_cache_coherence https://en.wikipedia.org/wiki/Directory-based_cache_coherenc... Or various combinations of snooping and directories ("snoop filters", or directories that act as "bridges" between broadcast domains, etc.). In current Xeon processors (and presumably AMD EPYC as well, thought I don't yet have first-hand experience with those), you have a couple of directories per CPU with snoop filtering, as with tens of cores broadcasting becomes a scalability bottleneck. In the BIOS you can change the mode how it operates, with slightly different names and semantics depending on the CPU generation.
- jlokier 7y ago
- lettergram 7y agoFor those interested (in 2014!) I did a rather simple analysis of CPU caches and for loops to point out some pitfalls: https://austingwalters.com/the-cache-and-multithreading/ https://austingwalters.com/the-cache-and-multithreading/ Hope it helps someone, I tend to link it to my co-workers when they ask me why I PR'd re-ordering of loops & functions OR when they ask how I get speedups without changing functionality.
- 1e1f 7y agoShould include tl;dr your concurrency fears are real, but for registers and not caches.
- simpsond 7y agoIf you have two threads reading then writing values in memory, you still need synchronization/atomic changes at the software level.
- strstr 7y agoIf cache coherence is relevant to you, I strongly recommend the book “A Primer on Memory Consistency and Cache Coherence”. It’s much easier to understand the details of coherency from a broader perspective, than an incremental read-a-bunch-of-blogs perspective. I found that book very readable, and it cleared up most misconceptions I had. It also teaches a universal vocabulary for discussing coherency/consistency, which is useful for conveying the nuances of the topic. Cache coherence is not super relevant to most programmers though. Every language provides an abstraction on top of caches, and nearly every language uses the “data race free -> sequentially consistent”. Having an understanding of data races and sequential consistency is much more important than understanding caching: the compiler/runtime has more freedom to mess with your code than your CPU (unless you are on something like the DEC Alpha, which you probably aren't). If you are writing an OS/Hypervisor/Compiler (or any other situation where you touch asm), cache coherence is a subject you probably need a solid grasp of.
- jblow 7y agoDisagree on that last part. If more programmers understood cache coherency, maybe their programs would not run like a giant turd.
- codetrotter 7y agoI agree with you Jonathan but am wondering, will Jai help programmers write programs with better cache coherency even if said programmers don’t understand cache coherency well? Or is that orthogonal to the goals of Jai?
- cma 7y agoIf it still plans on wrapping SOA in something that looks in use like AOS, it could make people less aware of how their code is impacting cache (would now have to look at the definitions instead of seeing the array form at point of usage). But if it is enough more ergonomic to write AOS code it might still be worth it and increase uptake.
- dang 7y agoDiscussed last year: https://news.ycombinator.com/item?id=17670095 https://news.ycombinator.com/item?id=17670095
- tyingq 7y agoAMD's Rome processors are an interesting case, with 8MB of L3 cache per core. So the 64 core processor has 512MB of L3 cache. It wasn't that long ago that 512MB was a respectable amount of DRAM in a big server. An early 90's fridge sized Sun 690MP maxed out at 1GB of DRAM and had 1MB of L2 cache, no L3.
- zamadatix 7y agoHalf that - 4 MB per core so the 64 core CPU has 256 MB (dual socket is where the 512 number comes from but that's 128 cores and NUMA). It's also not fully accessible, each core can only directly access the 16 MB in its group of 4. Everything else is the same as a cross cache read.
- tyingq 7y agoAh, yeah. Mixed up their CCD and CCX terms. The 690MP was dual socket though, so still a somewhat valid comparison.
- zozbot234 7y ago> It wasn't that long ago that 512MB was a respectable amount of DRAM in a big server. Whereas today, 512MB is a bare minimum amount of DRAM in a general-purpose desktop. Times change.
- blattimwind 7y agoI don't think you can run a modern Linux or Windows 10 desktop on 512 MB RAM. Even my slim Linux desktop (no DE) consumes about 400 MB of RAM after login. Web-browsing with less than ~2 GB of memory doesn't seem feasible.
- mrich 7y agoNote that this is quite specific to x86, on other architectures like Power there are much weaker guarantees that will lead to problems when assuming the same model.
- gpderetta 7y agowhich part is x86 specific?
- mrich 7y agoTo quote from https://fgiesen.wordpress.com/2014/07/07/cache-coherency/ https://fgiesen.wordpress.com/2014/07/07/cache-coherency/ "Memory models Different architectures provide different memory models. As of this writing, ARM and POWER architecture machines have comparatively “weak” memory models: the CPU core has considerable leeway in reordering load and store operations in ways that might change the semantics of programs in a multi-core context, along with “memory barrier” instructions that can be used by the program to specify constraints: “do not reorder memory operations across this line”. By contrast, x86 comes with a quite strong memory model."
- gpderetta 7y agoYes, I know the difference between the memory model of x86 and, say, ARM. I'm asking what's x86 specific on this article about cache coherency.
- mrich 7y agoThe article explicitly mentions two times things that are only true for x86 (grep for it). In addition, the statement at the end is definitely not true for POWER: "As soon as the data is read/written to the L1 cache, the hardware-coherency protocol takes over and provides guaranteed coherency across all global threads. Thus ensuring that if multiple threads are reading/writing to the same variable, they are all kept in sync with one another."
- praptak 7y agoThe one-line summary seems to be that one should never worry about caches themselves introducing concurrency bugs. I mean after we account for memory operations reordering on each core, the memory address storing a single value that is visible to all cores is a correct model from the concurrency-correctness point of view, right?
- Tuna-Fish 7y agoOn x86, the correct model is that on any core, all reads are in order, all writes are in order, and no write will ever be moved earlier than a read on that core. Or in other words, the only kind of visible reordering that is allowed to occur is that writes can be delayed past reads. An example of a situation where this is significant: thread 1 thread 2 mov [X], 0 mov [Y], 0 mov [X], 1 mov [Y], 1 mov r1, [Y] mov r2, [X] After this sequence of code, r1 == r2 == 0 is legal. (As is any other combination of 1 and 0.) (edit:) And just to add, all this reordering is of course impossible to detect on just one core, as when a read request hits a recent write on the same core, it reads it out of the store queue. This can sometimes be really bad for performance, though, as if you read a value that is partially in the store queue (such as, write 16-bit value to x, the immediately read 32 bits from x), some cpus will stall that read, and all that follow it, until the entire store queue is flushed. Since the store queue can easily take tens if not hundreds of cycles to clear, this can be very expensive.
- musicale 7y ago> “different cores can have different/stale values in their individual caches”. Different processes can certainly have different versions of the same state, different values for the same variable, and different values at the same virtual address. And what about virtual caches? Non-coherent cache lines? Moreover, even in the face of cache coherency you can still have race conditions.
- gpderetta 7y ago> Different processes can certainly have different versions of the same state, different values for the same variable, and different values at the same virtual address. what do you mean? Either two caches agree on the content of a cacheline or one of the cacheline is marked invalid (and the stale content is irrelevant). There are components of a core that might not respect coherency, like load and store buffers and arguably registers, but not caches (on cache-coherent systems of course). Virtually addressed caches are an issue and that's why they have fallen out of favor.
- sherincall 7y agoOne thing not mentioned here (nor in previous discussions of the article, it seems) is that DMA is typically not coherent with the CPU caches. This is kinda visible from the little diagram at the top, with the disk sitting on the other side of the memory, but it should be explicitly spelled out. If you're using a DMA device (memory<->device or memory<->memory copies), you might end up in a state where the DMA and the CPU see different values. This usually means data transfer to/from a Disk or GPU, though other peripherals might use it too. Your options here are either to manually invalidate your caches and synchronize with the DMA (e.g. via interrupts), or to request from the OS that the given memory section be entirely uncached; or in some cases, you can get away with a write-through cache policy, if the DMA is only ever reading the memory.
- AllanHoustonSt 7y agoI think DPDK does some user-level trickery to achieve per-core caching through DMA, do you happen to know how they go about it?
- dakom 7y agoSomething I don't understand is how to deal with cache coherency when you need the same data in a bunch of different configurations. Take a typical game loop and assume we have a list of Transforms (e.g. world matrix, translation/rotation/scale, whatever - each Transform is a collection of floats in contiguous memory) Different systems that run in that loop need those transforms in different orders. Rendering may want to organize it by material (to avoid shader switching), AI may want to organize it by type of state machine, Collision by geometric proximity, Culling for physics and lighting might be different, and the list goes on. Naive answer is "just duplicate the transforms when they are updated" but that introduces its own complexity and comes at its own cost of fetching data from the cache. I guess what I'm getting at is: 1) I would love to learn more about how this problem is tackled by robust game engines (I guess games too - but games have more specific knowledge than engines and can have unique code to handle it) 2) Does it all just come out in the wash at the end of the day? Not saying just throw it all on the heap and don't care... but, maybe say optimizing for one path, like "updating world transforms for rendering", is worth it and then whatever the cost is to jump around elsewhere doesn't really matter? Sorry if my question is a bit vague... any insight is appreciated
- yvdriess 7y agoAssuming that once determined at the start of the frame (e.g. camera position changes after user input handling), the transform matrices are not written to. They can then be freely shared across multiple cores without causing problems with coherency. The cache lines associated with the transform will be set to 'Shared' across all cores. Cache coherency will start to bite you in the ass in this situation if you start mutating the transforms while other threads are reading it, causing cache invalidations and pipeline flushes across all caches owning those lines. In short, write a transform once and treat it as immutable. Do not reuse the Transform allocation for a good while for subsequent frames to ensure that its cache lines are no longer in cache. If you do need to reuse right away, you can force invalidate cache lines by addresses, so that the single-writer in the next step is the single (O)wner and no other caches need to invalidate anything.
- dakom 7y ago
- gchokov 7y agoHalf a decade - woow! Sounds like the author has spent half a century there..
- vagab0nd 7y agoThis might be a naive question: how did we decide as an industry that cache should be controlled by the hardware, but registers and main memory by the compiler?
- dspillett 7y agoJust a guess here, but I'm thinking it has something to do with the registers being an internal core component of the CPU that have been there in some form the whole time whereas cache was a little more of an afterthought when CPUs and other processing units stopped being the bottleneck and started to significantly outstrip the performance of (practical/affordable) memory and memory controllers. It used to be that the memory sub-systems had artificial wait states as the processors could not keep up otherwise, rather than processors siting around waiting for responses. Also, cache is essentially optional, and its configuration (not just sizes, but how it is shared amongst cores and other units, speeds relative to other memory levels, even how many levels there are (and each level can have different properties) how cache rows are arranged and mapped, their size, ..., etc.) can and will vary between otherwise identical looking systems. If you are compiling to optimise for cache use you end up either having to JiT compile, or compile several versions of some routines and include them all so which one is used can be chosen at run-time, or have different versions of the whole compiled output for different systems. All of those things happen at times anyway for other reasons, but presumably the overall pay-off of doing the same for cache variances isn't high enough for it to be worthwhile building into general purpose compilers (though the cases for/against this sort of work in domain specific compilers and other tool chains may be quite different). Some designs argue that we shouldn't need to care about the implementation details of any memory let alone L1/2/3/? cache - just access storage and let the OS & hardware make use of the faster memory levels it has access to as it sees fit to optimise that storage access.
- yvdriess 7y agoWhat do you mean by 'controlled by hardware'? The registers the compiler chooses for you are an abstraction themselves, one of the first things a CPU does is register renaming. Same for main memory, you are presented mostly an abstraction of main memory, with a ton of layers in-between (load/store buffers, write-combine buffers, coherent caches, etc) Turning the argument the other way, you as a programmer can control a lot about caches: you can prefetch cache lines, invalidate them and use streaming instructions to bypass them.
- blattimwind 7y agoIt's worth pointing out that the L1 cache and its associated logic is the only* way a core talks to the outside world, including all I/O ever. With that in mind it is easy to understand why it is so crucial to performance. * there might be some minor exceptions
- johnthescott 7y agothe entire design of unix is realized in a moment when a motherboard is seen as a network.
- wildmanx 7y agoThe biggest myth is that any of this matters to anybody but a tiny fraction of niche programmers. The reason some "app" is slow is not because of cache coherence traffic. It's because somebody chose the wrong data structure, created some stupid architecture, wrote incomprehensible code that the next guy extended in a horribly inefficient way cause they didn't understand the original. My web browsing experience is slow because people include heaps of bloated JS crap and trackers and ad networks so I have to load 15 megabytes of nonsense and wait for JS to render stuff I don't want to see. None of this was any better if anybody involved understood CPU caches better. Even in the kernel or HPC applications, most code is not in the hot path. Programmers should rather focus on clean architectures and understandable code. How does it help if you hand-optimize some stuff that nobody understands, nobody can fix a bug, nobody can extend it. That's horrible code, even if it's 5% faster than what somebody else wrote. TL;DR: This is interesting, but likely totally irrelevant to your day job. In the list of things to do to improve your code, it comes so far down that you'll never get there.