CPU Caches and Why You care
CC Attribution - NonCommercial - ShareAlike 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor and the work or content is shared also in adapted form only under the conditions of this
Meyers, Scott
No matter what programming language or technology you use, if your software fails to make effective use of the underlying CPU caches, your system's performance will suffer. A lot. This session provides a wide-ranging overview of CPU caches, how they operate, and how that affects high-level decisions on things like data structures and traversal strategies. Both single- and multi-threaded execution are considered. Specific topics include different cache types (data, instruction, TLB); private and shared caches; cache lines and speculative prefetching; false sharing; and cache-friendly program organization, data structures, and traversal strategies. If you care at all about performance, the information in this talk is essential.
 Okay. I'm Scott Myers. I want to talk about CPU caches and why you might want to care about them in the first place. So to build a certain degree of suspense into what we're talking about right here, usually I am in a situation where I can look back at the screen and sort of use my laser pointer and point at it, but if I try to do that I will literally fall to my death. So for those of you who find the talk particularly boring, bear in mind that at any moment I could die. So if that doesn't improve ratings, I don't know what will. I want to point out that a suitable way to express your appreciation for my failure to die or depending on your perspective, my dying would be to turn in a green card if I succeed one way or another. I want to talk about a couple of ways to traverse a raise. Now what I'm going to be showing here is a chunk of memory inside the machine. This is all about what's going on on the hardware. And before I go any further, how many people are working in a managed language? Okay, lots of people are working in a managed language. That's great. I have news for you. There is something below the virtual machine. There is the actual hardware. And the actual hardware does not care anything about what programming language you are using or whether it's running on top of a hypervisor or a supervisor or have some kind of abstract machine. The underlying hardware really has a very limited set of concerns. So let us suppose I have a chunk of memory which represents an array. And what I want to do is walk through that memory and maybe I want to add up the values in the entire matrix, let's say. Or maybe I want to count the number of odd values. The point is I want to traverse the matrix once looking at every individual element. And there's two ways I can do that. I can start on the first row and I can go row by row. That is known as a row major traversal. Or I can go column by column. That is known as a column major traversal. Both traversals touch exactly the same memory. They do exactly the same conceptual amount of work. If you write the code for these two kinds of traversals, you will find that the code is very similar for a row major or a column major traversal. It's basically a matter of when you have the nested for loops or the rows on the outside or the columns on the outside. So the code that is shown here happens to be C++ but it's going to look very, very similar in every other programming language. So basically the code on the top is showing you how a row major traversal works and the code in the else clause is showing how a column major traversal works and the red is showing you the difference between the two. So from a programming perspective, row major, column major, they touch the same chunks of memory. And in terms of writing the code, it's no more difficult to write one than the other. The source code looks about the same. So everything seems like it's, you know, about the same. What's interesting is the performance is not at all about the same. So what I did was I wrote a little benchmark here and what I was doing was plotting how much time it takes to simply traverse the matrix looking at every element exactly once as a function of the total size of the matrix. So if you look on the bottom, you see that the matrix starts with a size of zero and it goes up to 35 megabytes. Now, I did this with two compilers, happened to be Microsoft's compiler and the GCC compiler for C++. But again, you're going to get similar results in anything which is actually touched on the hardware. And what I want you to notice is that first we've got the sort of the magenta line that has that nice little bend in it. That's the brighter, higher line. That corresponds to a column major traversal. Now, what you can't see as well, but if you look very, very closely, there are little blue Xs next to most of those magenta data points. Those little blue Xs are for a different compiler. So basically we have two compilers. One of them is GCC, one of them is Microsoft's compiler. So independent people writing their own compiler, but you can see that the performance you're getting is about the same in both. Now, below that magenta line, you can see some look like dark black diamonds. It's a nice straight line and below that are some yellow triangles. Now, those both correspond to a column major traversal. Now, the first thing I want you to notice is those two lower lines down there, these two lines here, those are the row major traversal. They are much, much better than the column major traversal, regardless of the compiler. And the column major traversal here is bad compared to row major with both compilers. So this is not a compiler dependent phenomenon that we are looking on. Now, it turns out that the sort of the blueish black dots here, this happens to be for Microsoft's compiler and this happens to be for GCC's compiler. I do not want you to go, ah, I know what he's driving at, Microsoft's compiler sucks. That is not the conclusion I am asking you to come to. What I'm asking you to come to is the observation that a row major traversal with both compilers is noticeably faster than a column major traversal with either compiler, which strongly suggests that what we're looking at is a phenomenon that has to do with the underlying machine and not with how that code is compiled. So what we conclude is the traversal order matters. What's interesting is the question, well, why does it matter? We're touching the same amount of memory, but I'm not going to answer that question. I want to talk about something different for a moment. So Herb Sutter a number of years ago published an article where he wanted to find out the mac, excuse me, the number of odd elements in a square matrix. So this is some pseudocode that he put together. This is sequential pseudocode. So we have a square matrix. Each side has dim elements in it. So it's a dim by dim matrix. And what we want to do is figure out how many elements are odd numbers. So that's pretty straightforward here. What we just do is for, we go, we have a couple of nested loops and basically if the element we're looking at, modulo 2 is 0, then we increment the number of odds. So this will walk through that matrix, checking every element to see if it's odd. If so, it'll increment it. Works fine. However, if you have a very large matrix, gigabytes in size, for example, a very large matrix, then there's no reason to do it sequentially. You might as well do it in parallel. It's easy enough to break that matrix into a bunch of independent chunks and then have different threads look at different parts of the matrix and that should run a lot faster. So Herb wrote the following pseudocode. Now this happens to be pseudocode in pseudos C++. So if you don't know C++, trust me. And if you do know C++, I understand this is not real C++, blame Herb. But the important thing here is basically what we're doing is we're going to take this, take this matrix. And what I like to point out is you can tell the difference between somebody who publishes code that is supposed to be described orally and someone who publishes code that is only designed to be red. And one of the ways you can tell the difference is that you probably would not choose capital P and lowercase P if you were planning on talking about things orally. So I will attempt to convey this as follows. What we're going to do is we're going to assume that we have P workers and the individual one of those P workers will call P. As I said, this is what Herb is. So basically, if you take a look at the code, fundamentally what it's doing is it's taking the matrix, it's dividing it by the number of threads that we have. It's breaking it into a beginning point and an ending point for each one of those threads so they can operate on independent chunks of the matrix. It then spawns an individual thread for each one of the chunks. It has each one of the chunks look at its own section of the matrix, counts up the number of odd numbers, and then when they're all done, the threads get joined. And what is important to us here is we have an array here that has enough room for P elements. So every one of those threads is writing into its location in that array how many odd numbers it has found. So thread number eight will write into slot eight how many odd numbers it found on its portion of the matrix. And similarly for thread nine, ten, two, three, like that. And then after performing the join operation, so all the threads come together, so after performing all the join, we simply sequentially then add up all the numbers. And one of the reasons why I show Herb's data when talking about this particular problem is because Herb has access to a machine with 24 cores which makes me feel extremely inadequate. I don't have a machine with 24 cores. But what's cool about this is, so this is the scalability. So what we see here is this is how long it takes to get something done with one core. So if we double the number of cores, we give it twice as much computational horsepower. And it responds by immediately dropping by 42%. It's about half as fast. No problem. We have a 24 core machine. We will just keep adding more and more horsepower, which we do. And finally, when we get up to about, oh, 16, 17, 18 cores, we are back at 100% of the performance with one core. That's the kind of scalability result you want to show your managers. 15 times as many cores, it runs exactly as fast as when we only had one core. That's what we're really looking for. But that's okay. We have more core. Well, Herb has more cores. So we keep throwing more at it. And finally, we get up here. We finally peak at about 40% higher than a single core. But there's something distressing about showing, about throwing 20 times as much computational hardware at a problem and getting a 40% speedup on what is obviously an embarrassingly parallel problem. So we'd like to think that we could do a little better than that. So if we take the pseudo code for performing things in parallel and we make an extremely tiny change. Now, what we did before was we had an array of P elements where each one of the threads was going to write into the array how many values it found that were odd. We're still going to do that. However, what we're going to do is for each thread and this indentation level is in each individual thread, each individual thread is going to keep its own local counter of how many odd numbers it's found. It's initialized to zero. As it runs, it will then increment its local counter. And when it's finished with its portion of the matrix that it's supposed to look at, it's going to take its local counter, which it's then going to write into the location in that matrix. So the only difference is that instead of writing our results into the matrix as we go, we're going to keep track of them locally and then we're going to write them into the matrix, excuse me, into the array when we are done. That's the only difference. Conceptually, this can't change anything. I mean, the code is more complicated now. We're using an extra local variable. We're wasting memory. Well, it turns out this memory waste turns out to be worthwhile because now we get perfect scalability. That's kind of nice. Clearly, the access patterns that we get under multithreading makes a difference. But the question is why? And the answer has to do with CPU caches, which is the whole point of this talk here. CPU caches are small amounts of unusually fast memory. It's all caches. It's just unusually fast memory where unusually fast means faster than main memory. Also means more expensive or else we'd have it all over the place. That's what a CPU cache is. And the reason it's important for performance purposes is because the access latency is much smaller than it is for main memory. There are three common kinds of CPU caches. Hardware engineers are clever people. They come up with new kinds all the time. But fundamentally, on a day-to-day basis, the kinds of CPU caches you'll normally be dealing with are there's the data cache, also known as the D cache, and amongst the truly chic known as the D dollar sign. So that's the data cache. Stores data that's used by the program. There is the instruction cache, also known as the I cache or the I dollar sign. The instruction cache caches recently accessed instructions. And just when you thought that caches can be identified because they use the word cache in the name, we have the translation look-aside buffer, the TLB, which is also a cache. It just doesn't say so. And the TLB, and this is the only slide where I'm going to mention it, what it does is if you're running on a virtual memory system, you need to have a way to translate from the page, from the page value in your virtual address space into the page number of the physical memory page. And what the TLB does is it caches the most recent translation. So it's basically for doing quick look-ups of the result of a translation from your virtual memory page to your real memory page. And I'm not going to say anything more about TLBs from now on because it turns out that if you optimize for the data cache and the instruction cache, the TLB gets optimized at the same time. So that's the situation. If you read online commentary blogs and stuff from developers who work with caches, you come across some really interesting comments. So this is one from Sergey Solinik from Microsoft. So he talks about Linux was writing packets at about 30 megabits per second wired and wireless at about 20 at Linux. Windows CE was crawling at about 12 megabytes wired and six megabits per second wireless. Now let me put this in perspective for you. So what this comment is really saying is, so we work at Microsoft and all the power of Microsoft with all of the smart people and really powerful buildings was running at about half the speed of those open source weenies who work on Linux. From Microsoft's perspective, this is not a good thing. But he goes on, we found out that Windows CE had a lot more instruction cache mishes than Linux. So I want to point out this is talking about the instruction cache. And the reason I mention this is because usually when you hear about caching, it's almost always about the data cache. This is talking about the instruction cache, the forgotten cache that does in fact make a difference. So he goes after we change the routing algorithms to be more cache local. So they changed the way that they wrote the code so that it would work better with the underlying hardware. We started doing 35 megabits per second wired and 25 megabits per second wireless, 20% better than Linux and Microsoft live happily ever after. But the message I want you to take away is they had a performance problem and they rewrote the instructions to make better use of the instruction cache so it would work better with the hardware. Another quote, this one is from Dmitri Vukov. He did the Relacy Race Detector. I like this quote because this is a man with conviction and enthusiasm. Cache lines are the key. Exclamation mark. Undoubtedly, exclamation mark. If you will make even a single error in the data layout, you will get a 100 factor slower resolution, exclamation mark, and in case you think he's joking, no jokes, exclamation mark. That's about the data cache. That's not the instruction cache. He's talking about the data cache, different cache, different problem, still important. CPU caches are typically on modern hardware organized into cache hierarchies, what are usually known as multi-level caches. So to give you some specific numbers and talk about something specific, I'm going to be talking about a particular processor. It happens to be the Intel Core i7 900 series. And in case you are wondering why I chose this particular processor, it's because at the time I originally put these slides together, I was researching a new computer I was going to get. That's what's inside this thing, which these days can also be used as a weapon or a boat anchor. It's so big. But it's got a nice processor inside. So I want to point out, I want to talk a little bit about the characteristics of this particular processor, which is representative of lots of processors these days. So it has 32 kilobytes of 32 kilobytes. Remember kilobytes? Not megabytes, not giga kilobytes. That's how much memory it has in the level one cache, in particular the level one instruction cache. It has another 32 kilobytes of memory in the level one data cache. Now that's per core. This particular processor happens to have four cores. That 32 kilobytes level one instruction cache and that 32 kilobytes level one data cache is shared by two hardware threads. They basically compete for what goes into those two caches on this particular machine. After the level one cache, which is the, what the heck, I'll lie to you, it is the fastest memory in the machine, is the second fastest memory in the machine. That is the level two cache, the level two cache on this particular machine, 256 kilobytes of level two cache per core. However, it is shared for both instructions and data, and it's shared by two hardware threads. So it's quite a bit larger, but now we don't segregate instructions and data. Instead, they're sharing the same cache, and they're both used by two hardware threads. Finally, we get to the level three cache. Eight megabytes, megabytes, eight megabytes of level three cache holds instructions and data, but don't get too excited. It's shared by all four hardware cores, and that means eight hardware threads. So this is a picture. The caches are not drawn to scale. If you go back and look at the numbers, you're going to see that these don't match the scale, but this does show you basically what's going on here. So this particular machine, it's got four cores. Each core has two threads on it because it's using hyperthreading. Each one of those cores has a level one instruction cache, a level one data cache, which are independent. They share a level two cache. They share a level three cache with all the other cores. Oh, and by the way, in case you didn't remember, somewhere way off in the distance is main memory. There is actually main memory. That's where all those pesky gigabytes come in. Not that they do you any good, because if you are not running inside your cache hierarchy, you are waiting. I told you before that caches are small amounts of fast memory. I want to emphasize the part about caches being small. So let's assume I have a 100 megabyte program image, not terribly large, a 100 megabyte program image. That's code plus data. That means 8% of your entire image would fit into the level three cache on the particular machine that I'm talking about right here. But remember, that level three cache is shared by every process running on the machine, including the operating system. So the best you can possibly do is to get 8% of your program image in the level three cache, which remember is the slowest of the caches. That's not a lot. One quarter of 1% will fit into every level two cache. That's not much either. And a whopping three one hundredths of a percent will fit in each level one cache. Caches are small. That's important. There's not a lot of cache available. I said caches are small amounts of unusually fast memory. They're unusually fast compared to main memory. On this particular machine, the level one latency, you go to level one cache, is four cycles. Now I told you I was gonna lie and say it was the fastest memory on the machine. I feel guilty. I feel compelled to clarify that. The fastest memory on the machine are the registers. So the registers you can think of as level zero cache. But there's really not very many of those. But you can get to a register in one cycle. On this particular machine, going to level one cache costs you four cycles. So it's one fourth as fast. You go to level two cache, the latency is 11 cycles. It's about a third as fast as the level one. You go to the level three cache, it's 39 cycles. It's about one third as fast as the level two. If you go to main memory on this particular processor, it's 107 cycles, which means that it is 27 times slower than level one. And what's fun about this is if you run a profiler on your program to find out how busy things are, when a processor is waiting for data from memory, that is not considered an idle processor. It's considered to be busy with most CPU profilers. Which means it is entirely possible to have a machine that is idle 99% of the time that shows 100% CPU utilization. I like to give these kind of upbeat talks to put everybody in a really good mood. If you are interested in having programs that run quickly, if you're at all concerned about performance, forget all those gigabytes of memory. They don't count. The only thing that matters is cache. Everything else is so slow that it just doesn't make a difference. So in this particular case on this machine, we've got eight megabytes of fast memory. And remember, that includes the slow fast memory. Because everything else slows things down by orders of magnitude. Fundamentally, as far as the hardware is concerned, small is fast. You often hear about, well, you know, there's a time-space trade-off. You hear about time-space trade-offs when you go to school. The hardware did not go to school. The hardware is a souped-up toaster. The hardware thinks that small is fast and you're not going to convince it otherwise. This means, just with what we've talked about so far, compact code that is well localized, that tends to access the same instructions over and over and over, that fits in cache. So the loop fits entirely within your 32 kilobytes level one cache. That's fast. Anything else is slow. Compact data structures that are well localized and that fit in your cache will also be fastest. And data structure traversals that only touch cached data are going to be fastest. That's just dictated by the hardware. Caches aren't accessed the way normal memory is. Caches are accessed in terms of cache lines. So when you fetch an individual byte from main memory, conceptually you go, oh, I'm going to go and get a char, for example. You are not getting a char. What you are going to do on most modern machines is you're going to bring back a 64 byte cache line. It depends on the particular architecture you're working on, but that's pretty common. So on the Core i7, the processor I've been talking about, it has 64 byte cache lines. That seems to be very common these days for mainstream processors from Intel and from AMD. And to put things in perspective, that means that A cache line, that'll hold 16 32-bit values. So let's say 16 integers on a 32-bit machine, 16 elements of an array of int on a 32-bit machine, 8 64-bit values, so maybe eight floats or, excuse me, eight doubles. Main memory is read and written in terms of cache lines. If you ask for a single byte, you get a whole cache line. It keeps the bus busy. If you write a single byte, eventually that entire cache line, whatever cache line that contains that byte, is going to go back out to main memory. This becomes really important. You want to make sure, for example, if you go to the trouble to read in a cache line, you'd like to use the whole thing. If you go to the trouble to write out anything on a cache line, you'd like to write out more than one byte. This feeds into the notion of using compact data structures or using instructions which have as much stuff packed together as you can possibly get. So visually, to try to put things in perspective, this actually is to scale. That's a byte. That's 64 times as big. That's a cache line. So when you're programming with caches, you have to think in terms of cache lines rather than just thinking in terms of the individual elements of the cache. This explains, by the way, why a row major traversal is so much faster than a column major traversal. With a row major traversal, when I go to the first element of a row major traversal, then I'm going to go to the beginning of this cache line here. So, all right, maybe I twiddle my digital thumbs while I'm waiting for that cache line to be brought in. But once the cache line's there, I'm now walking down the hardware, picking up element after element. So I get one slow access and 60 some odd fast accesses. And then I get another slow one and then a whole bunch of fast ones. However, with a column major traversal, I bring in a cache line, read the first element. I then have to go to the next cache line, read another element. I go to the next cache line, read in the third element. So I get slow access, slow access, slow access, slow access. And in practice, what often happens is by the time you get down to the bottom here, it turns out that you couldn't fit all of these in your cache at the same time. So by the time you got down to these here, you started evicting the lines that were up on top, getting them out of the cache to make room for the lines that you needed, which means you can actually get a cache miss every single time you access something. This is the fast track to the slow lane. So that explains, just knowing how hardware works explains why it is that we got so much better performance with row major rather than column major traversals. It turns out the hardware, although dumb as a toaster, it's a fairly smart dumb toaster. So when you are making access to real memory addresses, the hardware is actually looking for trends. And when it begins to notice an access pattern, the simplest pattern would be, I'm walking down an array, element by element. But it could be, I'm walking down the array from the end to the beginning, element by element. It turns out the hardware knows about both directions. You can go forward, you can go backward. Hardware figures out, and it starts doing what's known as cache line prefetching. So with cache line prefetching, it's anticipating the cache lines you are likely to need in the future. And it starts bringing them into memory because who knows, you might need them. And it's even more sophisticated than that. For example, if you're reading every fifth element or every 12th element, it will begin to notice patterns doing that. And since you're probably running on a system with multi-threads, you personally may not be writing multi-threaded software, but you probably are. But something on the machine is probably running concurrently. There's probably an operating system running, for example. Turns out the hardware is smart enough to be able to track patterns by different threads and start doing prefetching for different threads all simultaneously. It's a brave little toaster. There are some implications of this behavior. Now, the first one is that locality is really important, in particular. If I have brought in some memory location A, some address A, because I either needed to read it or I needed to write it. That means that the other addresses near A are probably already in cache, either because they're on the same cache line, which means I brought them in when I brought in A itself, or possibly because they were prefetched because there was a pattern of accesses that the hardware was noticing, so it did some prefetching for me. Another implication, predictable access patterns count. So if you are walking through an array, for example, going through in some beginning to end, or end to beginning, those are the cache friendliest traversals, then the hardware is going to be able to pick up on it. On the other hand, if you have something like a linked data structure where you're following random pointers jumping around in memory, that is the equivalent of declaring war on the cache subsystem. It cannot predict what your next access is going to be, which means the prefetching is not working for you. You're probably jumping from cache line to cache line, and as a result, when you are trying to have the fastest possible data structures, you don't want a linked data structure. At the end of the day, the hardware is dumb, the only thing it knows about is an array. Arrays, good. Everything else, no idea what it means. This also means that a linear array traversal, usually from beginning to end, or from end to beginning, it doesn't really matter, is extremely cache friendly. It's got great locality, you're going from one element to the next, which means you're walking down a cache line. It's got a great set of patterns, which means that the hardware can figure out what you're doing and start prefetching for you. And what this means is that if I have a linear array, excuse me, if I have an array and I'm doing a linear search from beginning to end, that can be a lot faster in practice than a binary search, for example, on a sorted data structure, or I assume a heap-based data structure. If I have a sorted array and I do a look up inside the sorted array, which is log n, that can be faster than an O of 1 search, for example, of a heap-based hash table. Now, I want to point out that computer science is legitimate for a large enough amount of data than suddenly going from logarithmic lookup time to constant lookup time, constant lookup time is going to be faster. Talk to people who are dealing with large amounts of data, Google, Facebook, the NSA, all these places that are dealing with a large amount of data. By the way, I'd like to personally apologize for Google and Facebook. So people working on that amount of data, they have bigger, they literally have bigger problems to solve. All of them, you have to take this stuff into account at some level anyway. But as I like to put it, at the end of the day, big O is going to win, but hardware caching takes an early lead. So for more moderate amounts of data, the hardware makes a big difference. Now, on modern hardware, it is very common to have multiple cores in one processor. So I told you before that on the particular processor inside this machine, the Core i7 architecture, there's four cores. So let's suppose I've got a four core machine, and I just want to look at two of them right now. So here's a couple of cores here. Now, let's suppose that I've got a multi-threaded program, so two of the threads happen to be running on different cores. And it turns out that one of the threads has read a particular piece of data from the main memory into its cache. Maybe it was doing a read. So let's just assume for purposes of discussion that here it is living cosily in the level two cache on core number zero. But it turns out that another thread working on the same problem, perhaps, has also either read or written, let's just assume it was a read, this particular chunk of data. So it has also happened to be sitting in its level two cache, let's say. So now we have a situation where we have conceptually a single piece of data. There's only one conceptual piece of data. It just happens to have been duplicated into the caching subsystem as an optimization to reduce latency. So let's assume that core zero does a right to that address. And let's assume that core one does a read to that address at the same time. So the question is, what is the value that is going to be read by core one, the old address or the new address? I mean, there's two copies of the value here. But conceptually, as a programmer, we're not thinking, gee, I think I'll program this so that it gets spread across four levels of cache, three levels of cache on four different cores, which means 12 caches and suddenly I'm confused. How many people have to program like that? That is the correct answer, zero, perfect. All right, no one has to worry about that. The reason nobody has to worry about that is because caches are a latency reducing optimization that is inside the hardware. There is only one virtual memory location with the address A. From the mental model of programmers, there is only one chunk of memory that has the address A in it. And it only has one value. All that hardware stuff is supposed to be completely hidden from you. Now, it turns out that in the hardware, when one of the cores writes to its copy of the cached value, magic ensues that disables all the other copies simultaneously. And there's hardware engineers who devote their entire careers to finding ways to make that work quickly. There's more than one way to do it. So that happens automatically. As software developers, you do not need to worry about this, which is good because really life would be much more miserable if you did. Well, I need to qualify that. As long as you engage in the proper synchronization, so in every programming language that I'm familiar with, if you have one thread writing some data and another thread reading the data at the same time so you haven't used any kind of synchronization to keep them from stepping on one another, bad things happen. That's called a data race. So assuming that your programs don't have data races. So you're using a mutex or using an atomic. You're using some kind of a message passing scheme. Assuming that you are following the rules dictated by your programming language to make sure that you get well-defined behavior. As long as you do that, you never need to worry about the hardware. On the other hand, if you program in some lower level systems languages C++ or C or D or other languages as well, anything that kind of has to get down on the hardware. Most of those languages basically say if you have a data race in your program where one thread's doing a read, another thread's doing a write and it's not synchronized. Those languages usually say results are undefined. We cannot predict what you're going to see. The reason that they cannot predict what you're going to see is because the hardware is going to be doing all kinds of weird stuff because the fact is on the hardware there are multiple copies of this data. That is why the language doesn't say well this is what's going to happen because it literally does not know. So the underlying hardware is why you get undefined behavior. Now the thing is assuming that you have followed the appropriate synchronization so that you have no data races in your program, this notion of what is known as cash coherency, making sure that different caches offer your software a coherent view of the values in memory is handled completely automatically by the hardware. But it takes time. It's not free. I said there's hardware engineers who devote their careers to making sure that this stuff happens. Nobody's found a way to make it happen instantaneously. In some cases we are victims of the fact that the speed of light is limited but that's a whole problem. And this leads to a new problem. So let us suppose here on core zero, here's a cash line here. Now let's assume that core zero is only looking at address A. And let's assume that core one is only looking at address A plus one. So I have two cores. They are accessing independent pieces of memory. There is no data race here. One core is looking at address A. Another core is looking at address A plus one. There is no data race. There is no need for mutexes. There is no need for atomic instructions. Everything is hunky-dory from a behavioral point of view. The problem is if they both happen to end up on the same cash line, then the hardware can't tell that they're independent pieces of memory because cash lines are read and written as a unit. So if I have two cores, both for example writing the same cash line, the hardware is going to think that every individual write invalidates the other copy of the cash line in somebody else's cash. Herb Center refers to this as cash ping-ponging. So one thread does a right that invalidates this other cash's copy even though there is no conflict. This cash does a right, it invalidates this copy. And that means you're going back out to main memory or you're doing some other kind of synchronization at the hardware level in order to make sure you get a consistent view of memory. This is known as false sharing. False sharing arises when you have independent threads that are accessing the same cash line. There is no data race, you don't need to use a mutex or anything like that. The problem is the hardware doesn't know that. You're slamming on the same cash line. So that's false sharing. Any questions about false sharing? Pardon me? Alright, so the question is if you have false sharing, how do you address it? Fundamentally what you need to do is to either, well actually so let's talk about what, let me defer the question because I want to talk about the factors that contribute to false sharing because then we can say if any of these factors is not true then you have eliminated false sharing. So let's go back to Herb Sutter's example with this notion of false sharing. So this is the original code that Herb Sutter showed. So in this case here we have an array of results and every one of the threads, all 24 because Herb has 24 cores, are saying plus plus result of P whenever they find an odd number. Now that's a read modify right operation. But if you have two threads where one of them is doing plus plus on its index, maybe index number three in the array and another thread is doing plus plus on its index which is maybe number two in the array, they're independent so there's no conflict but they're probably on the same cash line. As a result this is slamming the underlying hardware system which is constantly trying to update all these different copies of this index. So with 24 cores that array is probably duplicated 24 times in 24 different caches and every individual reader right or every right is going to invalidate all 23 other caches even though there's no conflict. That also explains why the simple solution of creating a local counter inside the thread. Now this local counter is going to be on the individual threads stack which means it's probably not on the same cash line as anybody else's counter. And now all the work of incrementing the count is occurring on the local variable inside the threads stack which means it probably doesn't conflict with anybody else. There's no false sharing there and then when each thread is done yeah they still have to access results of P but instead of slamming on it the entire time that they're trying to count how many odd numbers what they're doing is making only one right. So there still could be some false sharing but it's going to be for a very short period of time. That explains why this seemingly peculiar optimization of going from writing directly to the array to going to writing through a temporary in some sense makes things run a whole lot faster. It's worth again taking a look at how this manifests itself in terms of scalability results. So this is the scalability or I guess I should say the lack of scalability if you have false sharing and this is the scalability if you do not have false sharing. Now in this particular case an example of how to solve it was to simply prevent all those threads from hitting that same chunk of memory simultaneously. So the problem of false sharing it tends to arise only as long as all of the following things are true. The first thing is you have to have independent variables or independent values falling on a single cache line. So if you have two things that are next to one another in memory and you separate them so that they're no longer next to one another in memory that is one way to eliminate false sharing. Where different cores are concurrently accessing that particular cache line. If somehow you can set things up so that only one core is accessing a cache line there's no such thing as false sharing within one core. It only happens if you have multiple copies because it's the cache coherency that's the problem. If there's only one core that's accessing a chunk of memory it'll only be in one cache. And this is only going to matter if it occurs frequently. If it's every once in a while it's not likely to be a performance problem which is why Herb's solution works. And at least one of them is a writer. Readers don't conflict. Only readers and writers or writers and writers conflict. So to get now to your particular question we now understand ways to eliminate this. Basically if we can get any of these four things to not be true we don't have to worry about false sharing any longer. So in the case of Herb Sutter's example what he did was he took two values which were close to one another in an array. First he separated them by putting essentially one of them in the thread stack frame. So that separated them and what that meant was when he did have the right to the array it wasn't frequent any longer. I want to point out that pretty much all kinds of data potentially are susceptible to false sharing. So anything that is statically allocated so for example global variables. If you say global int x not that you would but think about the people you work with who didn't come to the conference. What are they doing while you're learning about CPU cores. So if you say a global int x and a global int y they could very easily end up on the same cache line. So if it turns out that they're being hammered by different threads that fulfill these criteria you can have a false sharing problem. Or if they're static at file scope for example. A heap allocated. Normally people think well heap allocation I couldn't possibly have any problem with heap allocation. If it turns out that I heap allocate this and then maybe I allocate this and deallocate it and allocate it and deallocate it and allocate it and deallocate it and oops it it's sent over here. So I could have two completely independent, temporally independent chunks of memory that by bad luck end up on the same cache line. And the chances of this occurring increases if you are for example writing a clustering memory allocator. Assuming you're working in a language where you can do that kind of thing. But this can happen in languages with managed memory as well. Because the garbage collector doesn't know for sure or the compactor doesn't know for sure what the lifetimes of things are. It will try to avoid this but it is still possible for it to occur. If you have an automatic variable. So something which is local on your stack. Normally you're not going to get false sharing between some other thread. Remember you have to have multiple threads actually these things for them to be a problem. Normally things that are on the stack frame of an individual thread are invisible to other threads. Which means they don't suffer from false sharing. On the other hand if you have let's say something on your local stack frame to local variable and then you decide to spawn a thread and you pass a pointer or a reference to it. So now the other thread has a way to get at your chunk of memory. That can lead to false sharing as well. Any questions about false sharing? Okay so the observation here is that there's this lovely little performance jump right here. And so the question is I mean is that related in somehow or is that completely independent? I don't know for sure but here's my suspicion. My suspicion is that that jump right there corresponds to a break in a cache line. In other words the array was broken across two cache lines and that's the end of the first cache line and the beginning of the second cache line. So you'd have to do more experiments to find out for sure but that's my suspicion. Which means if you run it multiple times with multiple compilers you actually get different results. If you rearrange the order in which things are declared it might get moved around on the cache line and then the shape of that could change a little bit. All righty. So regarding false sharing this is a comment from one of the performance guys at Microsoft and some of these people wonder why I quote from Microsoft all the time. They blog more than other people. That's why. So anyway he says during beta one performance milestones and parallel extensions most of the performance problems came down to stamping out false sharing in numerous places which is kind of scary. Most of the performance problems not the occasional performance problem but most of the performance problems. So false sharing is worth knowing about plus it's just kind of a cool term. So to summarize where we are the first thing is that as far as the hardware is concerned small is the same as fast or what I really should say as big as the same as slow. There's no time space trade off in the hardware. Locality counts you want to stay in the cache both the instruction cache and the data cache and predictable access patterns count you want to be prefetch friendly. That's the general summary but what does that mean in terms of trying to get your programs to get along well with the hardware. The first thing is for data where it is practical consider employing a linear traversal of an array. That's what the hardware really likes. I was talking with a CTO of a particular of a guy at a particular financial services company. They do algorithmic trading which either is the end of the world or providing needed liquidity depending on your feeling about algorithmic trading. And he goes well I don't know about blah blah blah data structure but I know that an array is going to beat it. Which is not always true but to a first approximation it is actually true because the hardware loves array traversals. That in fact is the only data structure the hardware loves. So if you can employ a linear array traversal that's what you want to do. Second thing is you want to use as much of a cache line as you possibly can. What you don't want to do for example is read an entire cache line use only a tiny little piece of it and then move on to some other cache line. Now remember that was the problem we had with a column major traversal of a matrix but here is another example of it. So this one was contributed I am still alive I can't believe that. So this was contributed by Bruce Dawson he used to work for Microsoft and in particular he worked in the Xbox division. So he would work with developers and with companies who were developing video games. And so in video games it is not uncommon to have an object and objects can be alive or dead for any one of a number of reasons because it's a video game. So there'd be a Boolean saying whether this thing is live and might have actually been a bit field. So then we'd have for example a vector of objects and then what you would have imagine this is in your game loop in your rendering loop. Well you got to figure out what you have to draw on the screen or what you have to move or update the physics for whatever it happens to be. So for every one of those elements if the object is alive you want to do something with it. Now think about what this means. You're reading an object now the object has a multiple fields right. One of the fields is this Boolean but it probably has some data before the Boolean maybe some data after the Boolean. So when you read in the object you're probably occupying oh let's just assume it's a 64 byte cache line. You then check the Boolean which worst case might only be a bit field and if you find that it's zero you throw the entire cache line away and move on to the next object. So this has some interesting implications. Now let's suppose that your Bruce Dawson you're doing some performance analysis and you see this kind of thing in a game which he said was very common. How do you fix that? Yes. Pardon me? Arrays. Arrays of. Okay so I assume what you mean is you take those Booleans out of the objects you put them into some separate array for example of Booleans. So let me translate here because I this is the way that you do it. You go to object-oriented programming and you kick it in the teeth. You say this whole nonsense of taking data and functions and bundling them together. No we're going to rip out the data now and stick it in an array that nice high-level data structure. Why? Because the hardware likes it. Did you have a question? Okay so essentially we can split the object maybe into multiple pieces. The essential data which maybe is very small and something else and that's consistent with the same idea but the whole thing is what's interesting is that for many for decades now people have learned what you want to do is have objects they represent these really nice abstractions we're bundling the functions and the data together so it'll be really easy to read and write and reason about the programs all of which is true but remember the hardware toaster. So this is not friendly to the cache in many cases. So there's actually other schools of design which involve trying to take abstractions and yet at the bottom of the stack trying to make it so that the data is also very CPU friendly. Yeah. Okay so Kevlin's suggestion is that you can use the objects for state pattern. Thank you. Collections for state pattern. You can tell I'm not as familiar with it as I might be and which he says allows you to remain object oriented but is consistent with using the hardware without without going against the grain of the hardware. So nevertheless the observation is that if you want to get maximum performance you're going to have to take the behavior of the hardware into account when you are designing your data structures. And the last thing you can do is you need to be alert for false sharing in multi-threaded systems. I would love to be able to tell you that there is some great set of tools which will go oh you got some false sharing going on there. Let me tell you how to fix that. And currently we do have such a tool it's called an experienced senior engineer who looks at your scalability and goes oh you got some false sharing going on there. Let me show you how to fix that. There are tools which can give you some information for example Bruce Austin was talking about I guess Bruce here is. They had a special tool that they actually made at Microsoft for the Xbox division and what it would do is it actually showed when a cache line is brought into memory what percentage of the cache line is used before it gets evicted from memory. That is not a standard tool but that was something that they developed to be able to identify these kinds of problems. So currently you can get some information for example from Intel's V-Tune and there's some other things that you can do but alas this is still this is kind of at the level where if you are used to programming in an unmanaged language and you suddenly see completely weird results going on experienced people in an unmanaged language go oh it's probably a wild pointer pointer that's writing beyond the end of an array or has miscalculated an address. I mean it just it looks like that after a while. So false sharing you just have to be aware of its existence if nothing else. So that's for data for code the first thing is you want to fit your working set in the cache. So this also has some other interesting consequences. Let us suppose I have let's say an inheritance hierarchy got a base class and I've got three derived classes so we've got derived class one derived class two derived class three and what I want to do is I want to put them all in a collection so I've got a collection of base class objects or pointers to base class objects but it actually is gonna be of type one type two or type three and now what I want to do is walk down that collection invoking some virtual function some virtual method on every element of the container. So this is a classic use of polymorphism of runtime polymorphism in obfugrated systems. So let's assume the function we want to call is f because that's just what functions are called. So I go to the first element I make the polymorphic call to f let's assume it is an object of type one we go down to the class of type one guess what f's implementation for type one is not in the instruction cache no problem we fetch it from main memory we put it in instruction cache we execute f yes we go to the next element of the container because we are unlucky its type is number two alas we do not have f's implementation in number two in the instruction cache no problem we go to main memory we get the instructions we put them into the cache we execute them yes we go to the third element the third element of course is of type three we don't have f's implementation for type three we go to main memory we want to put it in the cache the cache is too small it will not fit no problem we evict all those old instructions from the f of type number one because we haven't used them in a long time we write in number three we execute number three we go to the next element of course it's now of type one you can see where this is going this is not by the way a theoretical problem many people especially in the video game industry have run into this kind of thing there's a variety of ways you can solve the problem but one of the ways for example is to sort the sequences by type so you could have three different containers all the type ones all the type twos all the type threes or you can actually put them all in the same container that'll still work as long as all the ones are at the beginning all the twos are in the middle and all the threes are at the end but again it has to do with keeping track of what's going on in the instruction cache that's the kind of thing you're trying to avoid you've often heard I hope that the fastest kind of code is straight line branch free code now you know why straight line branch free code is really really friendly to the pre-fetchor in the instruction cache if you're just going instruction instruction instruction no branches it's prefetching all the instructions that you're probably going to need so straight line code so if you know that you have some code that has to run really fast but there's a few cases that are exceptional that are unusual what you want to do is do some tests for those up front make them non inline function calls to get them out of the fast path so that everything else is straight line code that'll be fastest I will ask the questions answer with I'm almost out of time here so I'm going to defer the questions till the end of the talk inlining you want to inline cautiously the good thing about inlining when you inline a function call you're not making a jump to subroutine which means you got rid of a branch yes we hate branches branches are not good for instruction pre-fetch furthermore doing inlining allows compilers to perform additional optimizations have to do with context and call specific optimizations so that's really nice problem with inlining is that if I have a function call in 20 different places and I inline it in 20 different places I get the same code in 20 different places and now I can overflow the size of my instruction cache so trying to find the right balance with inlining can be tricky there's a couple of optimizations that compilers or build systems offer that are worth knowing about one of them is PGO PGO stands for profile guided optimization it is available for at least many compilers for unmanaged languages the nice thing about PGO is it actually does a lot of these optimizations for you automatically so you don't have to do them yourself and WPO stands for whole program optimization which again is a set of optimization so if you have tools in your build system which can perform instruction rearrangement figure out what is hot cold what is cold code that kind of stuff you want to take advantage of those things whenever it is possible so if you are interested in further information about CPU caches sort of the heart of the machine the first place I always go is what every programmer should know about memory which I it's where I go if I want really detailed information I'm not sure every programmer really needs to start on page one it starts with transistors and it goes from there and I didn't feel compelled to understand exactly how transistors work but it probably would have improved my understanding but if anything to do with CPU caches that's the first place I go that's that's that's really good and I think everything else though you can probably well take a look at it later so we have about one minute so any questions about CPU caches yes correct okay so the observation is let us suppose that I've got a thread running on a core and now we get swapped out for example so all of its instructions and all the data that it's using are in the cache for that core and then the next time it's time slice comes around it gets rescheduled to run on a different core because now everything is cold and this can make it obviously run slower so the question is what can you do about that kind of thing normally what you do is if you have a manual level of control there's something what's known as core affinity so for example if what you want to say is this thread should always run on this core and not be permitted to migrate then affinity is a way to express that now thread scheduling subsystems that have to do this kind of stuff they are well aware of that problem so they're going to try to avoid migrating a thread from core to core if they can avoid it but if you got a lot of threads and there's over a subscription sometimes you're gonna lose but I think the standard low-level approach assuming you have access to an API that gives it to you is to use core affinity we have time maybe for one more question yeah okay so the question essentially is I made the comment that straight line code is friendliest for the prefetchor and the question is isn't it also sort of friendly for the the cache itself because for example when you read in 64 bytes that might include several instructions with no branches and the answer is yes so the two things clearly they work in concert so the basically when you read in a cache line you're hoping to get multiple instructions on the cache line and as long as there's no branching you're going to be able to execute all of them and I think we are out of time now so thank you very much please let the conference as well as me know what you thought of the talk by picking up the little green pieces of paper or other colors and putting them in the bin thank you
 Okay. I'm Scott Myers. I want to talk about CPU caches and why you might want to  care about them in the first place. So to build a certain degree of suspense into  what we're talking about right here, usually I am in a situation where I can  look back at the screen and sort of use my laser pointer and point at it, but if  I try to do that I will literally fall to my death. So for those of you who find  the talk particularly boring, bear in mind that at any moment I could die. So if  that doesn't improve ratings, I don't know what will. I want to point out that a  suitable way to express your appreciation for my failure to die or  depending on your perspective, my dying would be to turn in a green card if I  succeed one way or another. I want to talk about a couple of ways to traverse a  raise. Now what I'm going to be showing here is a chunk of memory inside the  machine. This is all about what's going on on the hardware. And before I go any  further, how many people are working in a managed language? Okay, lots of people  are working in a managed language. That's great. I have news for you. There is  something below the virtual machine. There is the actual hardware. And the  actual hardware does not care anything about what programming language you are  using or whether it's running on top of a hypervisor or a supervisor or have some  kind of abstract machine. The underlying hardware really has a very limited set  of concerns. So let us suppose I have a chunk of memory which represents an  array. And what I want to do is walk through that memory and maybe I want to  add up the values in the entire matrix, let's say. Or maybe I want to count the  number of odd values. The point is I want to traverse the matrix once looking at  every individual element. And there's two ways I can do that. I can start on the  first row and I can go row by row. That is known as a row major traversal. Or I  can go column by column. That is known as a column major traversal. Both  traversals touch exactly the same memory. They do exactly the same conceptual  amount of work. If you write the code for these two kinds of traversals, you will  find that the code is very similar for a row major or a column major traversal.  It's basically a matter of when you have the nested for loops or the rows on the  outside or the columns on the outside. So the code that is shown here happens to  be C++ but it's going to look very, very similar in every other programming  language. So basically the code on the top is showing you how a row major  traversal works and the code in the else clause is showing how a column major  traversal works and the red is showing you the difference between the two. So  from a programming perspective, row major, column major, they touch the same  chunks of memory. And in terms of writing the code, it's no more difficult to  write one than the other. The source code looks about the same. So everything seems  like it's, you know, about the same. What's interesting is the performance is not  at all about the same. So what I did was I wrote a little benchmark here and what  I was doing was plotting how much time it takes to simply traverse the matrix  looking at every element exactly once as a function of the total size of the  matrix. So if you look on the bottom, you see that the matrix starts with a size of  zero and it goes up to 35 megabytes. Now, I did this with two compilers, happened  to be Microsoft's compiler and the GCC compiler for C++. But again, you're going  to get similar results in anything which is actually touched on the hardware. And  what I want you to notice is that first we've got the sort of the magenta line  that has that nice little bend in it. That's the brighter, higher line. That  corresponds to a column major traversal. Now, what you can't see as well, but if  you look very, very closely, there are little blue Xs next to most of those  magenta data points. Those little blue Xs are for a different compiler. So  basically we have two compilers. One of them is GCC, one of them is Microsoft's  compiler. So independent people writing their own compiler, but you can see that  the performance you're getting is about the same in both. Now, below that magenta  line, you can see some look like dark black diamonds. It's a nice straight line  and below that are some yellow triangles. Now, those both correspond to a column  major traversal. Now, the first thing I want you to notice is those two lower  lines down there, these two lines here, those are the row major traversal. They  are much, much better than the column major traversal, regardless of the  compiler. And the column major traversal here is bad compared to row major with  both compilers. So this is not a compiler dependent phenomenon that we are  looking on. Now, it turns out that the sort of the blueish black dots here,  this happens to be for Microsoft's compiler and this happens to be for GCC's  compiler. I do not want you to go, ah, I know what he's driving at, Microsoft's  compiler sucks. That is not the conclusion I am asking you to come to. What I'm  asking you to come to is the observation that a row major traversal with both  compilers is noticeably faster than a column major traversal with either  compiler, which strongly suggests that what we're looking at is a phenomenon that  has to do with the underlying machine and not with how that code is compiled. So  what we conclude is the traversal order matters. What's interesting is the  question, well, why does it matter? We're touching the same amount of memory, but  I'm not going to answer that question. I want to talk about something different for  a moment. So Herb Sutter a number of years ago published an article where he  wanted to find out the mac, excuse me, the number of odd elements in a square  matrix. So this is some pseudocode that he put together. This is sequential  pseudocode. So we have a square matrix. Each side has dim elements in it. So it's  a dim by dim matrix. And what we want to do is figure out how many elements are  odd numbers. So that's pretty straightforward here. What we just do is  for, we go, we have a couple of nested loops and basically if the element we're  looking at, modulo 2 is 0, then we increment the number of odds. So this will  walk through that matrix, checking every element to see if it's odd. If so, it'll  increment it. Works fine. However, if you have a very large matrix, gigabytes in  size, for example, a very large matrix, then there's no reason to do it  sequentially. You might as well do it in parallel. It's easy enough to break that  matrix into a bunch of independent chunks and then have different threads look  at different parts of the matrix and that should run a lot faster. So Herb wrote  the following pseudocode. Now this happens to be pseudocode in pseudos C++. So if  you don't know C++, trust me. And if you do know C++, I understand this is not  real C++, blame Herb. But the important thing here is basically what we're doing  is we're going to take this, take this matrix. And what I like to point out is  you can tell the difference between somebody who publishes code that is  supposed to be described orally and someone who publishes code that is only  designed to be red. And one of the ways you can tell the difference is that you  probably would not choose capital P and lowercase P if you were planning on  talking about things orally. So I will attempt to convey this as follows. What  we're going to do is we're going to assume that we have P workers and the  individual one of those P workers will call P. As I said, this is what Herb  is. So basically, if you take a look at the code, fundamentally what it's doing  is it's taking the matrix, it's dividing it by the number of threads that we  have. It's breaking it into a beginning point and an ending point for each one of  those threads so they can operate on independent chunks of the matrix. It then  spawns an individual thread for each one of the chunks. It has each one of the  chunks look at its own section of the matrix, counts up the number of odd  numbers, and then when they're all done, the threads get joined. And what is  important to us here is we have an array here that has enough room for P  elements. So every one of those threads is writing into its location in that  array how many odd numbers it has found. So thread number eight will write into  slot eight how many odd numbers it found on its portion of the matrix. And  similarly for thread nine, ten, two, three, like that. And then after performing  the join operation, so all the threads come together, so after performing all  the join, we simply sequentially then add up all the numbers. And one of the  reasons why I show Herb's data when talking about this particular problem is  because Herb has access to a machine with 24 cores which makes me feel  extremely inadequate. I don't have a machine with 24 cores. But what's cool  about this is, so this is the scalability. So what we see here is this is how long  it takes to get something done with one core. So if we double the number of  cores, we give it twice as much computational horsepower. And it responds  by immediately dropping by 42%. It's about half as fast. No problem. We have a 24  core machine. We will just keep adding more and more horsepower, which we do.  And finally, when we get up to about, oh, 16, 17, 18 cores, we are back at 100% of  the performance with one core. That's the kind of scalability result you want to  show your managers. 15 times as many cores, it runs exactly as fast as when we  only had one core. That's what we're really looking for. But that's okay. We have  more core. Well, Herb has more cores. So we keep throwing more at it. And finally,  we get up here. We finally peak at about 40% higher than a single core. But  there's something distressing about showing, about throwing 20 times as much  computational hardware at a problem and getting a 40% speedup on what is  obviously an embarrassingly parallel problem. So we'd like to think that we  could do a little better than that. So if we take the pseudo code for performing  things in parallel and we make an extremely tiny change. Now, what we did  before was we had an array of P elements where each one of the threads was  going to write into the array how many values it found that were odd. We're  still going to do that. However, what we're going to do is for each thread and  this indentation level is in each individual thread, each individual thread  is going to keep its own local counter of how many odd numbers it's found. It's  initialized to zero. As it runs, it will then increment its local counter. And  when it's finished with its portion of the matrix that it's supposed to look  at, it's going to take its local counter, which it's then going to write into the  location in that matrix. So the only difference is that instead of writing our  results into the matrix as we go, we're going to keep track of them locally and  then we're going to write them into the matrix, excuse me, into the array when we  are done. That's the only difference. Conceptually, this can't change anything.  I mean, the code is more complicated now. We're using an extra local variable.  We're wasting memory. Well, it turns out this memory waste turns out to be  worthwhile because now we get perfect scalability. That's kind of nice. Clearly,  the access patterns that we get under multithreading makes a difference. But the  question is why? And the answer has to do with CPU caches, which is the whole point  of this talk here. CPU caches are small amounts of unusually fast memory. It's all  caches. It's just unusually fast memory where unusually fast means faster than  main memory. Also means more expensive or else we'd have it all over the place.  That's what a CPU cache is. And the reason it's important for performance  purposes is because the access latency is much smaller than it is for main memory.  There are three common kinds of CPU caches. Hardware engineers are clever people.  They come up with new kinds all the time. But fundamentally, on a day-to-day basis,  the kinds of CPU caches you'll normally be dealing with are there's the data cache,  also known as the D cache, and amongst the truly chic known as the D dollar sign.  So that's the data cache. Stores data that's used by the program.  There is the instruction cache, also known as the I cache or the I dollar sign.  The instruction cache caches recently accessed instructions.  And just when you thought that caches can be identified because they use the word  cache in the name, we have the translation look-aside buffer, the TLB,  which is also a cache. It just doesn't say so. And the TLB, and this is the only  slide where I'm going to mention it, what it does is if you're running on a  virtual memory system, you need to have a way to translate from the page, from the  page value in your virtual address space into the page number of the physical  memory page. And what the TLB does is it caches the most recent translation.  So it's basically for doing quick look-ups of the result of a translation  from your virtual memory page to your real memory page. And I'm not going to say  anything more about TLBs from now on because it turns out that if you  optimize for the data cache and the instruction cache, the TLB gets optimized  at the same time. So that's the situation. If you read online commentary blogs and  stuff from developers who work with caches, you come across some really  interesting comments. So this is one from Sergey Solinik from Microsoft. So he  talks about Linux was writing packets at about 30 megabits per second wired and  wireless at about 20 at Linux. Windows CE was crawling at about 12 megabytes  wired and six megabits per second wireless. Now let me put this in  perspective for you. So what this comment is really saying is, so we work at  Microsoft and all the power of Microsoft with all of the smart people and really  powerful buildings was running at about half the speed of those open source  weenies who work on Linux. From Microsoft's perspective, this is not a good  thing. But he goes on, we found out that Windows CE had a lot more instruction  cache mishes than Linux. So I want to point out this is talking about the  instruction cache. And the reason I mention this is because usually when you  hear about caching, it's almost always about the data cache. This is talking  about the instruction cache, the forgotten cache that does in fact make a  difference. So he goes after we change the routing algorithms to be more cache  local. So they changed the way that they wrote the code so that it would work  better with the underlying hardware. We started doing 35 megabits per second  wired and 25 megabits per second wireless, 20% better than Linux and  Microsoft live happily ever after. But the message I want you to take away is  they had a performance problem and they rewrote the instructions to make better  use of the instruction cache so it would work better with the hardware. Another  quote, this one is from Dmitri Vukov. He did the Relacy Race Detector. I like this  quote because this is a man with conviction and enthusiasm. Cache lines  are the key. Exclamation mark. Undoubtedly, exclamation mark. If you will make even a  single error in the data layout, you will get a 100 factor slower resolution,  exclamation mark, and in case you think he's joking, no jokes, exclamation mark.  That's about the data cache. That's not the instruction cache. He's talking about  the data cache, different cache, different problem, still important. CPU caches are  typically on modern hardware organized into cache hierarchies, what are usually  known as multi-level caches. So to give you some specific numbers and talk about  something specific, I'm going to be talking about a particular processor.  It happens to be the Intel Core i7 900 series. And in case you are wondering why  I chose this particular processor, it's because at the time I originally put these  slides together, I was researching a new computer I was going to get. That's what's  inside this thing, which these days can also be used as a weapon or a boat anchor.  It's so big. But it's got a nice processor inside. So I want to point out, I want to  talk a little bit about the characteristics of this particular processor, which is  representative of lots of processors these days. So it has 32 kilobytes of 32  kilobytes. Remember kilobytes? Not megabytes, not giga kilobytes. That's how  much memory it has in the level one cache, in particular the level one  instruction cache. It has another 32 kilobytes of memory in the level one data  cache. Now that's per core. This particular processor happens to have four cores.  That 32 kilobytes level one instruction cache and that 32 kilobytes level one  data cache is shared by two hardware threads. They basically compete for what  goes into those two caches on this particular machine. After the level one  cache, which is the, what the heck, I'll lie to you, it is the fastest memory in  the machine, is the second fastest memory in the machine. That is the level two  cache, the level two cache on this particular machine, 256 kilobytes of  level two cache per core. However, it is shared for both instructions and data,  and it's shared by two hardware threads. So it's quite a bit larger, but now we  don't segregate instructions and data. Instead, they're sharing the same cache,  and they're both used by two hardware threads. Finally, we get to the level  three cache. Eight megabytes, megabytes, eight megabytes of level three cache holds  instructions and data, but don't get too excited. It's shared by all four hardware  cores, and that means eight hardware threads. So this is a picture. The caches  are not drawn to scale. If you go back and look at the numbers, you're going to  see that these don't match the scale, but this does show you basically what's  going on here. So this particular machine, it's got four cores. Each core has two  threads on it because it's using hyperthreading. Each one of those cores  has a level one instruction cache, a level one data cache, which are independent.  They share a level two cache. They share a level three cache with all the other  cores. Oh, and by the way, in case you didn't remember, somewhere way off in the  distance is main memory. There is actually main memory. That's where all those  pesky gigabytes come in. Not that they do you any good, because if you are not  running inside your cache hierarchy, you are waiting. I told you before that  caches are small amounts of fast memory. I want to emphasize the part about caches  being small. So let's assume I have a 100 megabyte program image, not terribly  large, a 100 megabyte program image. That's code plus data. That means 8% of  your entire image would fit into the level three cache on the particular  machine that I'm talking about right here. But remember, that level three cache is  shared by every process running on the machine, including the operating system.  So the best you can possibly do is to get 8% of your program image in the level  three cache, which remember is the slowest of the caches. That's not a lot.  One quarter of 1% will fit into every level two cache. That's not much either.  And a whopping three one hundredths of a percent will fit in each level one cache.  Caches are small. That's important. There's not a lot of cache available. I said  caches are small amounts of unusually fast memory. They're unusually fast  compared to main memory. On this particular machine, the level one latency,  you go to level one cache, is four cycles. Now I told you I was gonna lie and say it  was the fastest memory on the machine. I feel guilty. I feel compelled to clarify  that. The fastest memory on the machine are the registers. So the registers you  can think of as level zero cache. But there's really not very many of those.  But you can get to a register in one cycle. On this particular machine,  going to level one cache costs you four cycles. So it's one fourth as fast. You go  to level two cache, the latency is 11 cycles. It's about a third as fast as the  level one. You go to the level three cache, it's 39 cycles. It's about one  third as fast as the level two. If you go to main memory on this particular  processor, it's 107 cycles, which means that it is 27 times slower than level one.  And what's fun about this is if you run a profiler on your program to find out  how busy things are, when a processor is waiting for data from memory, that is not  considered an idle processor. It's considered to be busy with most CPU  profilers. Which means it is entirely possible to have a machine that is idle  99% of the time that shows 100% CPU utilization. I like to give these kind of  upbeat talks to put everybody in a really good mood. If you are interested in  having programs that run quickly, if you're at all concerned about performance,  forget all those gigabytes of memory. They don't count. The only thing that  matters is cache. Everything else is so slow that it just doesn't make a  difference. So in this particular case on this machine, we've got eight megabytes  of fast memory. And remember, that includes the slow fast memory. Because  everything else slows things down by orders of magnitude. Fundamentally, as  far as the hardware is concerned, small is fast. You often hear about, well, you  know, there's a time-space trade-off. You hear about time-space trade-offs when you  go to school. The hardware did not go to school. The hardware is a souped-up  toaster. The hardware thinks that small is fast and you're not going to convince  it otherwise. This means, just with what we've talked about so far,  compact code that is well localized, that tends to access the same instructions  over and over and over, that fits in cache. So the loop fits entirely within  your 32 kilobytes level one cache. That's fast. Anything else is slow.  Compact data structures that are well localized and that fit in your cache  will also be fastest. And data structure traversals that only touch cached data  are going to be fastest. That's just dictated by the hardware. Caches aren't  accessed the way normal memory is. Caches are accessed in terms of cache lines. So  when you fetch an individual byte from main memory, conceptually you go, oh, I'm  going to go and get a char, for example. You are not getting a char. What you are  going to do on most modern machines is you're going to bring back a 64 byte  cache line. It depends on the particular architecture you're working on, but that's  pretty common. So on the Core i7, the processor I've been talking about, it has  64 byte cache lines. That seems to be very common these days for mainstream  processors from Intel and from AMD. And to put things in perspective, that means  that A cache line, that'll hold 16 32-bit values. So let's say 16 integers on a  32-bit machine, 16 elements of an array of int on a 32-bit machine, 8 64-bit  values, so maybe eight floats or, excuse me, eight doubles. Main memory is read and  written in terms of cache lines. If you ask for a single byte, you get a whole  cache line. It keeps the bus busy. If you write a single byte, eventually that  entire cache line, whatever cache line that contains that byte, is going to go  back out to main memory. This becomes really important. You want to make sure,  for example, if you go to the trouble to read in a cache line, you'd like to use  the whole thing. If you go to the trouble to write out anything on a cache line,  you'd like to write out more than one byte. This feeds into the notion of using  compact data structures or using instructions which have as much stuff  packed together as you can possibly get. So visually, to try to put things in  perspective, this actually is to scale. That's a byte. That's 64 times as big.  That's a cache line. So when you're programming with caches, you have to  think in terms of cache lines rather than just thinking in terms of the  individual elements of the cache. This explains, by the way, why a row major  traversal is so much faster than a column major traversal. With a row major  traversal, when I go to the first element of a row major traversal, then I'm  going to go to the beginning of this cache line here. So, all right, maybe I  twiddle my digital thumbs while I'm waiting for that cache line to be brought  in. But once the cache line's there, I'm now walking down the hardware, picking up  element after element. So I get one slow access and 60 some odd fast accesses.  And then I get another slow one and then a whole bunch of fast ones. However, with  a column major traversal, I bring in a cache line, read the first element. I then  have to go to the next cache line, read another element. I go to the next cache  line, read in the third element. So I get slow access, slow access, slow access,  slow access. And in practice, what often happens is by the time you get down to  the bottom here, it turns out that you couldn't fit all of these in your cache  at the same time. So by the time you got down to these here, you started evicting  the lines that were up on top, getting them out of the cache to make room for  the lines that you needed, which means you can actually get a cache miss every  single time you access something. This is the fast track to the slow lane. So that  explains, just knowing how hardware works explains why it is that we got so  much better performance with row major rather than column major traversals. It  turns out the hardware, although dumb as a toaster, it's a fairly smart dumb  toaster. So when you are making access to real memory addresses, the hardware is  actually looking for trends. And when it begins to notice an access pattern, the  simplest pattern would be, I'm walking down an array, element by element. But it  could be, I'm walking down the array from the end to the beginning, element by  element. It turns out the hardware knows about both directions. You can go forward,  you can go backward. Hardware figures out, and it starts doing what's known as  cache line prefetching. So with cache line prefetching, it's anticipating the  cache lines you are likely to need in the future. And it starts bringing them into  memory because who knows, you might need them. And it's even more sophisticated  than that. For example, if you're reading every fifth element or every 12th  element, it will begin to notice patterns doing that. And since you're probably  running on a system with multi-threads, you personally may not be writing  multi-threaded software, but you probably are. But something on the machine is  probably running concurrently. There's probably an operating system running,  for example. Turns out the hardware is smart enough to be able to track patterns  by different threads and start doing prefetching for different threads all  simultaneously. It's a brave little toaster. There are some implications of  this behavior. Now, the first one is that locality is really important, in  particular. If I have brought in some memory location A, some address A,  because I either needed to read it or I needed to write it. That means that the  other addresses near A are probably already in cache, either because they're  on the same cache line, which means I brought them in when I brought in A  itself, or possibly because they were prefetched because there was a pattern  of accesses that the hardware was noticing, so it did some prefetching for  me. Another implication, predictable access patterns count. So if you are  walking through an array, for example, going through in some beginning to end,  or end to beginning, those are the cache friendliest traversals, then the  hardware is going to be able to pick up on it. On the other hand, if you have  something like a linked data structure where you're following random pointers  jumping around in memory, that is the equivalent of declaring war on the cache  subsystem. It cannot predict what your next access is going to be,  which means the prefetching is not working for you. You're probably jumping  from cache line to cache line, and as a result, when you are trying to have the  fastest possible data structures, you don't want a linked data structure. At the  end of the day, the hardware is dumb, the only thing it knows about is an array.  Arrays, good. Everything else, no idea what it means. This also means that a  linear array traversal, usually from beginning to end, or from end to beginning,  it doesn't really matter, is extremely cache friendly. It's got great locality,  you're going from one element to the next, which means you're walking down a  cache line. It's got a great set of patterns, which means that the hardware  can figure out what you're doing and start prefetching for you. And what this  means is that if I have a linear array, excuse me, if I have an array and I'm  doing a linear search from beginning to end, that can be a lot faster in  practice than a binary search, for example, on a sorted data structure, or I  assume a heap-based data structure. If I have a sorted array and I do a look up  inside the sorted array, which is log n, that can be faster than an O of 1  search, for example, of a heap-based hash table. Now, I want to point out that  computer science is legitimate for a large enough amount of data than suddenly  going from logarithmic lookup time to constant lookup time, constant lookup  time is going to be faster. Talk to people who are dealing with large amounts  of data, Google, Facebook, the NSA, all these places that are dealing with a  large amount of data. By the way, I'd like to personally apologize for Google and  Facebook. So people working on that amount of data, they have bigger, they  literally have bigger problems to solve. All of them, you have to take this stuff  into account at some level anyway. But as I like to put it, at the end of the day,  big O is going to win, but hardware caching takes an early lead. So for more  moderate amounts of data, the hardware makes a big difference. Now, on modern  hardware, it is very common to have multiple cores in one processor. So I  told you before that on the particular processor inside this machine, the Core  i7 architecture, there's four cores. So let's suppose I've got a four core  machine, and I just want to look at two of them right now. So here's a couple of  cores here. Now, let's suppose that I've got a multi-threaded program, so two of  the threads happen to be running on different cores. And it turns out that  one of the threads has read a particular piece of data from the main memory  into its cache. Maybe it was doing a read. So let's just assume for purposes of  discussion that here it is living cosily in the level two cache on core number  zero. But it turns out that another thread working on the same problem,  perhaps, has also either read or written, let's just assume it was a read, this  particular chunk of data. So it has also happened to be sitting in its level two  cache, let's say. So now we have a situation where we have conceptually a  single piece of data. There's only one conceptual piece of data. It just happens  to have been duplicated into the caching subsystem as an optimization to  reduce latency. So let's assume that core zero does a right to that address. And  let's assume that core one does a read to that address at the same time. So the  question is, what is the value that is going to be read by core one, the old  address or the new address? I mean, there's two copies of the value here. But  conceptually, as a programmer, we're not thinking, gee, I think I'll program this  so that it gets spread across four levels of cache, three levels of cache on four  different cores, which means 12 caches and suddenly I'm confused. How many people  have to program like that? That is the correct answer, zero, perfect. All right,  no one has to worry about that. The reason nobody has to worry about that is  because caches are a latency reducing optimization that is inside the hardware.  There is only one virtual memory location with the address A. From the mental  model of programmers, there is only one chunk of memory that has the address A  in it. And it only has one value. All that hardware stuff is supposed to be  completely hidden from you. Now, it turns out that in the hardware, when one of the  cores writes to its copy of the cached value, magic ensues that disables all  the other copies simultaneously. And there's hardware engineers who devote  their entire careers to finding ways to make that work quickly. There's more than  one way to do it. So that happens automatically. As software developers,  you do not need to worry about this, which is good because really life would be  much more miserable if you did. Well, I need to qualify that. As long as you  engage in the proper synchronization, so in every programming language that I'm  familiar with, if you have one thread writing some data and another thread  reading the data at the same time so you haven't used any kind of synchronization  to keep them from stepping on one another, bad things happen. That's called a  data race. So assuming that your programs don't have data races. So you're using a  mutex or using an atomic. You're using some kind of a message passing scheme.  Assuming that you are following the rules dictated by your programming language  to make sure that you get well-defined behavior. As long as you do that, you  never need to worry about the hardware. On the other hand, if you program in some  lower level systems languages C++ or C or D or other languages as well, anything  that kind of has to get down on the hardware. Most of those languages basically  say if you have a data race in your program where one thread's doing a read,  another thread's doing a write and it's not synchronized. Those languages usually  say results are undefined. We cannot predict what you're going to see. The  reason that they cannot predict what you're going to see is because the  hardware is going to be doing all kinds of weird stuff because the fact is on  the hardware there are multiple copies of this data. That is why the language  doesn't say well this is what's going to happen because it literally does not know.  So the underlying hardware is why you get undefined behavior. Now the thing is  assuming that you have followed the appropriate synchronization so that you  have no data races in your program, this notion of what is known as cash  coherency, making sure that different caches offer your software a coherent  view of the values in memory is handled completely automatically by the hardware.  But it takes time. It's not free. I said there's hardware engineers who devote  their careers to making sure that this stuff happens. Nobody's found a way to  make it happen instantaneously. In some cases we are victims of the fact that the  speed of light is limited but that's a whole problem. And this leads to a new  problem. So let us suppose here on core zero, here's a cash line here. Now let's  assume that core zero is only looking at address A. And let's assume that core one  is only looking at address A plus one. So I have two cores. They are accessing  independent pieces of memory. There is no data race here. One core is looking at  address A. Another core is looking at address A plus one. There is no data  race. There is no need for mutexes. There is no need for atomic instructions.  Everything is hunky-dory from a behavioral point of view. The problem is if  they both happen to end up on the same cash line, then the hardware can't tell  that they're independent pieces of memory because cash lines are read and  written as a unit. So if I have two cores, both for example writing the same  cash line, the hardware is going to think that every individual write invalidates  the other copy of the cash line in somebody else's cash. Herb Center refers  to this as cash ping-ponging. So one thread does a right that invalidates this  other cash's copy even though there is no conflict. This cash does a right, it  invalidates this copy. And that means you're going back out to main memory or  you're doing some other kind of synchronization at the hardware level in  order to make sure you get a consistent view of memory. This is known as false  sharing. False sharing arises when you have independent threads that are  accessing the same cash line. There is no data race, you don't need to use a  mutex or anything like that. The problem is the hardware doesn't know that.  You're slamming on the same cash line. So that's false sharing. Any questions about  false sharing? Pardon me? Alright, so the question is if you have false sharing, how  do you address it? Fundamentally what you need to do is to either, well actually  so let's talk about what, let me defer the question because I want to talk about  the factors that contribute to false sharing because then we can say if any  of these factors is not true then you have eliminated false sharing. So let's go  back to Herb Sutter's example with this notion of false sharing. So this is the  original code that Herb Sutter showed. So in this case here we have an array of  results and every one of the threads, all 24 because Herb has 24 cores, are saying  plus plus result of P whenever they find an odd number. Now that's a read modify  right operation. But if you have two threads where one of them is doing plus  plus on its index, maybe index number three in the array and another thread is  doing plus plus on its index which is maybe number two in the array, they're  independent so there's no conflict but they're probably on the same cash line.  As a result this is slamming the underlying hardware system which is  constantly trying to update all these different copies of this index. So with  24 cores that array is probably duplicated 24 times in 24 different  caches and every individual reader right or every right is going to invalidate  all 23 other caches even though there's no conflict. That also explains why the  simple solution of creating a local counter inside the thread. Now this local  counter is going to be on the individual threads stack which means it's probably  not on the same cash line as anybody else's counter. And now all the work of  incrementing the count is occurring on the local variable inside the threads  stack which means it probably doesn't conflict with anybody else. There's no  false sharing there and then when each thread is done yeah they still have to  access results of P but instead of slamming on it the entire time that  they're trying to count how many odd numbers what they're doing is making  only one right. So there still could be some false sharing but it's going to be  for a very short period of time. That explains why this seemingly peculiar  optimization of going from writing directly to the array to going to writing  through a temporary in some sense makes things run a whole lot faster. It's  worth again taking a look at how this manifests itself in terms of scalability  results. So this is the scalability or I guess I should say the lack of  scalability if you have false sharing and this is the scalability if you do not  have false sharing. Now in this particular case an example of how to solve it  was to simply prevent all those threads from hitting that same chunk of memory  simultaneously. So the problem of false sharing it tends to arise only as long  as all of the following things are true. The first thing is you have to have  independent variables or independent values falling on a single cache line. So  if you have two things that are next to one another in memory and you separate  them so that they're no longer next to one another in memory that is one way to  eliminate false sharing. Where different cores are concurrently accessing that  particular cache line. If somehow you can set things up so that only one core is  accessing a cache line there's no such thing as false sharing within one core.  It only happens if you have multiple copies because it's the cache  coherency that's the problem. If there's only one core that's accessing a chunk of  memory it'll only be in one cache. And this is only going to matter if it occurs  frequently. If it's every once in a while it's not likely to be a performance  problem which is why Herb's solution works. And at least one of them is a  writer. Readers don't conflict. Only readers and writers or writers and writers  conflict. So to get now to your particular question we now understand ways to  eliminate this. Basically if we can get any of these four things to not be true  we don't have to worry about false sharing any longer. So in the case of  Herb Sutter's example what he did was he took two values which were close to one  another in an array. First he separated them by putting essentially one of them  in the thread stack frame. So that separated them and what that meant was  when he did have the right to the array it wasn't frequent any longer. I want to  point out that pretty much all kinds of data potentially are susceptible to  false sharing. So anything that is statically allocated so for example  global variables. If you say global int x not that you would but think about the  people you work with who didn't come to the conference. What are they doing while  you're learning about CPU cores. So if you say a global int x and a global  int y they could very easily end up on the same cache line. So if it turns out  that they're being hammered by different threads that fulfill these criteria you  can have a false sharing problem. Or if they're static at file scope for example.  A heap allocated. Normally people think well heap allocation I couldn't possibly  have any problem with heap allocation. If it turns out that I heap allocate this  and then maybe I allocate this and deallocate it and allocate it and  deallocate it and allocate it and deallocate it and oops it it's sent over here.  So I could have two completely independent, temporally independent chunks of  memory that by bad luck end up on the same cache line. And the chances of this  occurring increases if you are for example writing a clustering memory  allocator. Assuming you're working in a language where you can do that kind of  thing. But this can happen in languages with managed memory as well. Because the  garbage collector doesn't know for sure or the compactor doesn't know for sure  what the lifetimes of things are. It will try to avoid this but it is still  possible for it to occur. If you have an automatic variable. So something which is  local on your stack. Normally you're not going to get false sharing between some  other thread. Remember you have to have multiple threads actually these things  for them to be a problem. Normally things that are on the stack frame of an  individual thread are invisible to other threads. Which means they don't suffer  from false sharing. On the other hand if you have let's say something on your  local stack frame to local variable and then you decide to spawn a thread and you  pass a pointer or a reference to it. So now the other thread has a way to get at  your chunk of memory. That can lead to false sharing as well.  Any questions about false sharing? Okay so the observation here is that there's  this lovely little performance jump right here. And so the question is I mean is  that related in somehow or is that completely independent? I don't know  for sure but here's my suspicion. My suspicion is that that jump right there  corresponds to a break in a cache line. In other words the array was broken  across two cache lines and that's the end of the first cache line and the  beginning of the second cache line. So you'd have to do more experiments to  find out for sure but that's my suspicion. Which means if you run it  multiple times with multiple compilers you actually get different results. If you  rearrange the order in which things are declared it might get moved around on  the cache line and then the shape of that could change a little bit.  All righty. So regarding false sharing this is a comment from one of the  performance guys at Microsoft and some of these people wonder why I quote from  Microsoft all the time. They blog more than other people. That's why. So anyway  he says during beta one performance milestones and parallel extensions most  of the performance problems came down to stamping out false sharing in numerous  places which is kind of scary. Most of the performance problems not the  occasional performance problem but most of the performance problems. So false  sharing is worth knowing about plus it's just kind of a cool term. So to  summarize where we are the first thing is that as far as the hardware is  concerned small is the same as fast or what I really should say as big as the  same as slow. There's no time space trade off in the hardware. Locality counts  you want to stay in the cache both the instruction cache and the data cache and  predictable access patterns count you want to be prefetch friendly. That's the  general summary but what does that mean in terms of trying to get your programs  to get along well with the hardware. The first thing is for data where it is  practical consider employing a linear traversal of an array. That's what the  hardware really likes. I was talking with a CTO of a particular of a guy at a  particular financial services company. They do algorithmic trading which either  is the end of the world or providing needed liquidity depending on your  feeling about algorithmic trading. And he goes well I don't know about blah blah  blah data structure but I know that an array is going to beat it. Which is not  always true but to a first approximation it is actually true because the  hardware loves array traversals. That in fact is the only data structure the  hardware loves. So if you can employ a linear array traversal that's what you  want to do. Second thing is you want to use as much of a cache line as you  possibly can. What you don't want to do for example is read an entire cache line  use only a tiny little piece of it and then move on to some other cache line.  Now remember that was the problem we had with a column major traversal of a  matrix but here is another example of it. So this one was contributed I am still  alive I can't believe that. So this was contributed by Bruce Dawson he used to  work for Microsoft and in particular he worked in the Xbox division. So he would  work with developers and with companies who were developing video games. And so  in video games it is not uncommon to have an object and objects can be alive  or dead for any one of a number of reasons because it's a video game. So  there'd be a Boolean saying whether this thing is live and might have actually  been a bit field. So then we'd have for example a vector of objects and then what  you would have imagine this is in your game loop in your rendering loop. Well  you got to figure out what you have to draw on the screen or what you have to  move or update the physics for whatever it happens to be. So for every one of  those elements if the object is alive you want to do something with it. Now think  about what this means. You're reading an object now the object has a multiple  fields right. One of the fields is this Boolean but it probably has some data  before the Boolean maybe some data after the Boolean. So when you read in the  object you're probably occupying oh let's just assume it's a 64 byte cache  line. You then check the Boolean which worst case might only be a bit field and  if you find that it's zero you throw the entire cache line away and move on to the  next object. So this has some interesting implications. Now let's suppose that your  Bruce Dawson you're doing some performance analysis and you see this  kind of thing in a game which he said was very common. How do you fix that?  Yes. Pardon me? Arrays. Arrays of. Okay so I assume what you mean is you take those  Booleans out of the objects you put them into some separate array for example of  Booleans. So let me translate here because I this is the way that you do it. You go  to object-oriented programming and you kick it in the teeth. You say this whole  nonsense of taking data and functions and bundling them together. No we're going  to rip out the data now and stick it in an array that nice high-level data  structure. Why? Because the hardware likes it. Did you have a question?  Okay so essentially we can split the object maybe into multiple  pieces. The essential data which maybe is very small and something else and  that's consistent with the same idea but the whole thing is what's interesting is  that for many for decades now people have learned what you want to do is have  objects they represent these really nice abstractions we're bundling the  functions and the data together so it'll be really easy to read and write and  reason about the programs all of which is true but remember the hardware toaster.  So this is not friendly to the cache in many cases. So there's actually other  schools of design which involve trying to take abstractions and yet at the bottom  of the stack trying to make it so that the data is also very CPU friendly.  Yeah.  Okay so Kevlin's suggestion is that you can use the objects for state pattern.  Thank you. Collections for state pattern. You can tell I'm not as familiar with it  as I might be and which he says allows you to remain object oriented but is  consistent with using the hardware without without going against the grain  of the hardware. So nevertheless the observation is that if you want to get  maximum performance you're going to have to take the behavior of the hardware  into account when you are designing your data structures. And the last thing you  can do is you need to be alert for false sharing in multi-threaded systems.  I would love to be able to tell you that there is some great set of tools which  will go oh you got some false sharing going on there. Let me tell you how to  fix that. And currently we do have such a tool it's called an experienced senior  engineer who looks at your scalability and goes oh you got some false sharing  going on there. Let me show you how to fix that. There are tools which can give  you some information for example Bruce Austin was talking about I guess Bruce  here is. They had a special tool that they actually made at Microsoft for the  Xbox division and what it would do is it actually showed when a cache line is  brought into memory what percentage of the cache line is used before it gets  evicted from memory. That is not a standard tool but that was something that  they developed to be able to identify these kinds of problems. So currently you  can get some information for example from Intel's V-Tune and there's some  other things that you can do but alas this is still this is kind of at the  level where if you are used to programming in an unmanaged language  and you suddenly see completely weird results going on experienced people in  an unmanaged language go oh it's probably a wild pointer pointer that's  writing beyond the end of an array or has miscalculated an address. I mean it  just it looks like that after a while. So false sharing you just have to be  aware of its existence if nothing else. So that's for data for code the first  thing is you want to fit your working set in the cache. So this also has some  other interesting consequences. Let us suppose I have let's say an inheritance  hierarchy got a base class and I've got three derived classes so we've got derived  class one derived class two derived class three and what I want to do is I  want to put them all in a collection so I've got a collection of base class  objects or pointers to base class objects but it actually is gonna be of type  one type two or type three and now what I want to do is walk down that collection  invoking some virtual function some virtual method on every element of the  container. So this is a classic use of polymorphism of runtime polymorphism in  obfugrated systems. So let's assume the function we want to call is f because  that's just what functions are called. So I go to the first element I make the  polymorphic call to f let's assume it is an object of type one we go down to the  class of type one guess what f's implementation for type one is not in  the instruction cache no problem we fetch it from main memory we put it in  instruction cache we execute f yes we go to the next element of the container  because we are unlucky its type is number two alas we do not have f's  implementation in number two in the instruction cache no problem we go to  main memory we get the instructions we put them into the cache we execute them  yes we go to the third element the third element of course is of type three we  don't have f's implementation for type three we go to main memory we want to  put it in the cache the cache is too small it will not fit no problem we  evict all those old instructions from the f of type number one because we  haven't used them in a long time we write in number three we execute number  three we go to the next element of course it's now of type one you can see  where this is going this is not by the way a theoretical problem many people  especially in the video game industry have run into this kind of thing there's  a variety of ways you can solve the problem but one of the ways for example  is to sort the sequences by type so you could have three different containers  all the type ones all the type twos all the type threes or you can actually put  them all in the same container that'll still work as long as all the ones are  at the beginning all the twos are in the middle and all the threes are at the  end but again it has to do with keeping track of what's going on in the  instruction cache that's the kind of thing you're trying to avoid you've  often heard I hope that the fastest kind of code is straight line branch free  code now you know why straight line branch free code is really really  friendly to the pre-fetchor in the instruction cache if you're just going  instruction instruction instruction no branches it's prefetching all the  instructions that you're probably going to need so straight line code so if you  know that you have some code that has to run really fast but there's a few cases  that are exceptional that are unusual what you want to do is do some tests for  those up front make them non inline function calls to get them out of the  fast path so that everything else is straight line code that'll be fastest I  will ask the questions answer with I'm almost out of time here so I'm going to  defer the questions till the end of the talk inlining you want to inline  cautiously the good thing about inlining when you inline a function call  you're not making a jump to subroutine which means you got rid of a branch yes  we hate branches branches are not good for instruction pre-fetch furthermore  doing inlining allows compilers to perform additional optimizations have  to do with context and call specific optimizations so that's really nice  problem with inlining is that if I have a function call in 20 different places  and I inline it in 20 different places I get the same code in 20 different places  and now I can overflow the size of my instruction cache so trying to find the  right balance with inlining can be tricky there's a couple of optimizations  that compilers or build systems offer that are worth knowing about one of them  is PGO PGO stands for profile guided optimization it is available for at  least many compilers for unmanaged languages the nice thing about PGO is  it actually does a lot of these optimizations for you automatically so  you don't have to do them yourself and WPO stands for whole program  optimization which again is a set of optimization so if you have tools in your  build system which can perform instruction rearrangement figure out  what is hot cold what is cold code that kind of stuff you want to take advantage  of those things whenever it is possible so if you are interested in further  information about CPU caches sort of the heart of the machine the first place I  always go is what every programmer should know about memory which I it's  where I go if I want really detailed information I'm not sure every programmer  really needs to start on page one it starts with transistors and it goes  from there and I didn't feel compelled to understand exactly how transistors work  but it probably would have improved my understanding but if anything to do with  CPU caches that's the first place I go that's that's that's really good and I  think everything else though you can probably well take a look at it later  so we have about one minute so any questions about CPU caches yes  correct okay so the observation is let us suppose that I've got a thread running  on a core and now we get swapped out for example so all of its instructions and  all the data that it's using are in the cache for that core and then the next  time it's time slice comes around it gets rescheduled to run on a different  core because now everything is cold and this can make it obviously run slower  so the question is what can you do about that kind of thing normally what you do  is if you have a manual level of control there's something what's known as core  affinity so for example if what you want to say is this thread should always run  on this core and not be permitted to migrate then affinity is a way to express  that now thread scheduling subsystems that have to do this kind of stuff they  are well aware of that problem so they're going to try to avoid migrating a  thread from core to core if they can avoid it but if you got a lot of threads  and there's over a subscription sometimes you're gonna lose but I think the  standard low-level approach assuming you have access to an API that gives it to  you is to use core affinity we have time maybe for one more question yeah okay so  the question essentially is I made the comment that straight line code is  friendliest for the prefetchor and the question is isn't it also sort of  friendly for the the cache itself because for example when you read in 64  bytes that might include several instructions with no branches and the  answer is yes so the two things clearly they work in concert so the basically  when you read in a cache line you're hoping to get multiple instructions on  the cache line and as long as there's no branching you're going to be able to  execute all of them and I think we are out of time now so thank you very much  please let the conference as well as me know what you thought of the talk by  picking up the little green pieces of paper or other colors and putting them  in the bin thank you
Scott_Meyers_-_CPU_Caches_and_Why_You_care_0_155.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_156_851.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_852_1115.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_1116_3299.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_3300_4535.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_4536_4775.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_4776_5099.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_5100_5159.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_5160_5255.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_5256_5303.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_5304_5675.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_5676_5759.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_5760_5927.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_5928_6503.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_6504_6551.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_6552_6755.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_6756_7427.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_7428_8099.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_8100_8399.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_8400_8723.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_8724_10355.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_10356_13679.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_13680_15839.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_15840_17891.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_17892_18131.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_18132_18419.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_18420_19127.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_19128_21179.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_21180_24575.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_24576_28319.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_28320_29423.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_29424_33143.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_33144_33671.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_33672_33839.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_33840_35519.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_35520_38315.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_38316_40283.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_40284_42335.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_42336_47123.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_47124_50051.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_50052_54911.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_54912_58355.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_58356_60155.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_60156_61595.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_61596_62351.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_62352_68135.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_68136_68423.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_68424_69743.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_69744_69791.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_69792_70643.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_70644_71327.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_71328_75479.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_75480_80927.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_80928_87863.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_87864_88655.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_88656_88703.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_88704_88751.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_88752_92243.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_92244_92399.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_92400_92447.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_92448_92579.png Scott_Meyers_-_CPU_Caches_and_Why_You_care_92580_92871.png