[MUSIC]. Hello. Let's see now why caches work, which the principle of locality. So why do caches work? There's something programs called locality, which says that they tends to use data and instructions set at either. Nearby in space, they're close by, addresses are close by. Or, they tend to be written to reuse data, the same data over and over again. So this is called locality because it tends to stay close by, either in space, or in time, okay? So we have two types of locality. One is called temporal locality. That says that data items that were referenced recently. Are likely to be referenced again, in the near future. So if you gotta a given data in a, in a block here, I give you piece of data that start a new that, that is accessed by your program. You tend to access it over and over again in time, 'kay. Then there's another thing called spacial locality. That says that if you have a piece of data that you're interested in. It's likely that you're also going to you're also going to need a piece of data that that happens to be located very nearby in the address space. 'Kay. So how do caches take advantage of temporal locality? Well, just by storing recently accessed data we take advantage of temporal locality. 'Kay. But now. How, how do caches take as either spatial locality, take space, or do the spatial locality by bringing entire blocks of data from memory, as opposed to a single byte at a time. So, essentially, if you need say, address A, when you go to the cache, you're not only going to get A, but you're also going to get A plus 1, A plus 2, and so on. Up up to a certain limit. So let's see an example of a program that has locality. Suppose you have this loop here, and this loop is iterating over a rate a and adding it to the sum variable. Where is locality here? Where's locality, locality here? Let's start with data. Well, so with data the variable sum, is referenced multiple times. Okay? We act so, we act over and over again here inside our loop. At each iteration of the loop read it, and write it. It reads it because you're doing sum, equals sum, plus a of i. Now, we also have spatial locality because we're accessing array a in all of it's elements. So if you have memory here, so we're going to have your a of a and then right next to it, you're going to have a of one. And then we're going to have a. Of two and so on. They're all near by in memory. So since they're close by, we can, we can take advantage of spacial locality. So the other, type of locality that we have here is instructional locality, okay? So we have instructions, well remember that instructions are just stored in memory. It means the processors have to read them, right? And system tend to read one instruction after the other, right? So in, I mean, so we already have special locality right off the bat, because, you know, we read, we read references. We, we read instructions in the sequence that they appear in the program, okay? So when you have a series of instructions one after the other in your program, they're going to reside close by memory, right next to each other. So when you bring one, you might as well just bring a few instructions ahead as well, okay. And we also have temporal locality because we have things like, loops. See this loop here is just executing it's body over and over and over again. If we have a cache that stores the code for the body of the loop, it's going to be very effective, right? Because instead of going to memory every time you execute a body of the loop, you can just go, to the cache, and and get the data. Okay? So it's very important to be able to assess locality of your program effectively. Because it will help you lay out data and memory in a way that's more effective for cad, that makes caches more effective for your program. Okay? So if you know that there's a certain way of accessing your data structures, such that it can take advantage of spatial locality, you should definitely do it, because it is going to make your program faster. And, same way, if there was, if there's a way of writing your program that increases the possibility of taking advantage of temporal locality. It's also very important. So let me give you an example here. Suppose I have this piece of code here. It's a, it, it, it recieves. an array. A three-dimensional array, okay? A three-dimensional matrix as as a parameter. And then we trade over the entire array. That's why we have three loops, okay? One loop that varies i, which is one of the index here. The other one varies j, which is this index here. And then another that varies k, which is this index here. And the way C lays out matrices in memory is just by putting an entire row at a time. 'Kay, but since this program here is not accessing all of the elements of a row before moving to the next one, right? So then we see the inner loop here is varying the outer most dimension. Now we're just, going all over memory, instead of, reading memory one after the other here, we're going to read one place, another place, another place, another place, and it's just not going to take advantage of locality, especially if the, matrix does not fit in cache. 'Kay. I know this was quick, but we're going to show you another example later on as we teach you more about caches, it's going to make this make sense. This is mainly to show that if you, you have to pay attention to your code to understand how we can take individual locality and whether you might have, be having performance issues because of that. 'Kay. So what's wrong with this code is that we're accessing it out of order. So, how can we fix it? Well, we should first loop through the last dimension, then the middle dimension then the first dimension. Because we access we access data in a way that that follows how it's laid out in memory. Okay? See you soon.