So loop fusion is when you take multiple loops and you combine them into a single loop. And loop fission is when you take a single loop and split it into multiple loops that iterate over the same uh the same index range as the original loop.
ConorWelcome to ADSP The Podcast, episode 51, recorded on November 5th, 2021. My name is Connor, and today with my co-host Bryce, we talk about the difference between efficiency and speed. Now, listener, uh, strap in for Bryce's explanation of the difference between efficiency and speed. And actually, I'll give a little 30-second intro. A couple episodes ago, on I think it was the combinatory logic episode, I was saying how if you fuse two algorithms into one using combinators, you're gonna end up with faster code because doing uh a minimum element and maximum element separately versus you know min-max element, which Ben Dean very you know astutely pointed out that you know you're never actually gonna match that because the performance of min-max element has three over two n operations, which uh a fused one is still gonna have two n. Uh but anyways, that's besides the point. But thank you, Ben, for for uh clarifying that. Uh Bryce pointed out that like, well, it'll be twice as efficient, but not necessarily twice as fast. And in that episode, I don't think, I think in listening back to it, I don't think I fully grokked what Bryce meant by that. So now enter Bryce with his elaboration on efficiency versus speed.
BryceYeah. So so I um I like to think of this as uh I'm not surprised that we um are coming at this from different angles because I think you are much more of a theorist, uh uh pure computer scientist, whereas I am much more of a um a software engineer, and maybe that's even like too haughty a title, like a software plumber. You know, I sort of come at it from like the grounds up, like how does how does this thing actually run and work in production? Whereas you're much more the person to think about um you know the the whiteboard solution. Um and that's not that's not meant as a dig. It's not meant as a dig, it's a little bit of a dig, a little bit of a dig. But um so so let's start off with um an a an argument that I know you will find compelling because I've made it before, um, which is the question of efficiency when it comes to paralyzation. So uh we've told this story a few times on the podcast, but um uh uh once on a drive from the the South uh San Francisco Bay up to San Francisco, um I explained to Connor how you could paralyze an inclusive scan. Um and the the reason that Connor thought that it could not be paralyzed is because Connor was thinking about paralyzing the most efficient version of a parallel sc of a scan algorithm. And I explained to him how you could implement a parallel scan that is work inefficient. That is, it's less efficient, it does more operations than a serial scan. But it doesn't matter that it does more operations because they can be done in parallel. So, you know, if you if if you do n work in serial for some algorithm um and you can paralyze it, and um, you know, paralyzing it means that you actually end up doing two times n work, that might be perfectly okay. Um because you can't if your goal is you know to get an answer faster, it doesn't matter if you're doing more work, um, if that work can be done quicker because it's being done across multiple threads. So you you you understand that argument. Yes, you understand that in the case of um you know thread parallelism, uh uh you know being inefficient might be faster.
ConorCorrect, yes. Okay.
BryceUm but the thing is that applies to like almost every case that we encounter in the field because um even when you're programming for a single thread, the hardware that you are running on is still actually parallel under the hood. Um you know that there is a part of your processor that loads data. There's a part of your processor that fetches instructions, that decodes instructions, there's a part of your processor that does adds, there's a part that does multiplies, etc. etc. Um and those parts can run in parallel. Um and so on every modern processor, your your ser your single-threaded code um is actually being parallelized under the hood at a level that you don't really see. Um in that the actual things that need to happen to make that serial thread, you know, the serial set of operations that you want to do to make that um uh actually execute, those things don't strictly happen in order, and some of them are overlapped and asynchronous. Um and and so then again we get to this idea that in some cases um things that are less efficient might uh uh actually be um faster because efficiency isn't really our goal. Our goal is time to execution. Um so let's move on to the this particular case of loop fusion and loop fission. Do you know what those terms mean?
ConorUh we'll pretend for the sake of the listener that I don't know what loop fission is because this is the first time we were are recording this. Um I do know what loop fusion is, though. Um but tell me, what is what is the what are they both and what is the difference?
BryceUh so loop fusion is when you take multiple loops and you combine them into a single loop. And loop fission is when you take a single loop and split it into multiple loops that iterate over the same uh the same index range as the original loop, um or order of magnitude the same range as the original loop. Um and so you said you know you you were pr familiar with loop fusion prior to this conversation. And I that's not surprising because I think that loop fusion is perhaps the more intuitive of these optimizations. If I take two things that are um iterations over n elements and I combine them together, um uh you know, that's that's probably a win, especially if if the n elements that they're iterating over are the same set. If like if if the iterations are always accessing the same data, then combining those those two loops together, you know, it seems like it'd just be a win. Right? You're doing you instead of doing um uh iterating through two n times, you're just iterating through n times. Um but in practice that's not always the case. Um and sometimes it's better to have loops, the loops be separate, um, or to even take existing loops that you have and to split them. Um and the primary reason why you do this um is to get better locality of reference. Um I'll make the bold assertion that the vast majority of code in the wild is either memory latency or memory bandwidth bound, which essentially means that all of your software is pretty much a fancy version of memcopy. Um the the reason for this is because uh we've gotten very good at um building processors that have a lot of compute uh throughput at a fairly low latency. Um the problem is getting the data to that execution hardware. Um and if you have a ton of data reuse, like for example, you know, a matrix multiplication uh which um has an ON squared complexity, um, and therefore you there's a lot of data reuse, um, then yeah, you might be able to saturate your execution hardware, but that that's not what the majority of applications look like. Uh the majority of applications are, you know, I read some sequence of data and I do something with it, and then you know, I go on and do something else, um, or something like that. Um and so for most code, the determiner of your performance is going to be your memory access patterns. Um and in particular, um, how efficiently you make use of your cache and your processor's ability to prefetch, etc., is going to have a huge impact on application performance. Um I'll give you a simple example. Let's imagine that we had two loops. The first loop um applies a transformation to one data, to one data array. Um the second loop um also iterates over that same array, but it iterates over two other arrays, let's say, as well. Um the first one accesses one array, the second one accesses three arrays, and one of those is the same as the first one. So you might think, okay, well we should we should fuse those because then we only have to access each element of that array, the array that both of them access, a single time, right?
ConorYes.
BryceOkay. Now here's the problem. When you fuse those loops, you might end up um disrupting your memory access patterns. So one thing that you might end up doing is you might cause memory accesses that were that would current that would previously hit in the cache to no longer hit in the cache. Um so pretty much all processors today um uh do a pretty good job of pre-fetching the data that you need into the cache. Um and if you combine those two loops, now we have to pre-fetch even more data. Um and because of that, it's it's possible that um uh that we might have cache misses instead of going through the cache. So maybe that first loop, which just accessed the you know one array, maybe that loop was actually like really optimal. And that that uh loop, the the compiler and the processor were gonna always ensure that um uh all of the uh data was prefetched before each iteration, and so it would always run out of cache and it'd be super fast. But by combining it with the second loop, now um you're gonna have a cache miss um every time. And that's gonna that's going to make your code uh uh run slower. And of course, this is even more likely to ha to occur if you have loops that have completely unrelated data that you try to fuse together. Um, because then there's like there's really no data reuse. You're just increasing the pressure on the cache of how many different things do I need to fit in the cache with no real over uh reuse between the two. Um but there's another thing that can happen too, which is um uh a larger loop body can have increased register pressure. And you should really think about registers as being like an even faster type of cache. You know, let's say you got like a processor that has like six registers. Um well if if each loop iteration um only needs six temporary variables for its operations, then that's great. You never have to go to stack memory. Um stack memory is always going to be slower than registers. Hopefully your your stack will be in cache, it usually is. Um but on a processor like a GPU, um the the difference in memory bandwidth and latency between registers and even the first tier of um cache is pretty bad. Like on a GPU, spilling to stack is like really not good. You never want to do that. And that's why there's like a ton of registers on uh uh GPUs uh so that you can avoid doing that. So by combining those two loops, um uh you might have uh caused operations that previously did not spill to the stack to have to spill to the stack. Um and that will mean that there is more main memory traffic, um and also that there are more things that need to be stored in the cache. Um and therefore there's less room in the cache for the data arrays that um uh you're you're accessing through. Um and there's another thing that can happen. Um so as I said, the modern processors are pretty uh pretty good at pre-fetching all your data. Um and one of the ways they do this is they look at your access patterns and they can figure out linear and strided access patterns. They can be like, oh yeah, you know, like the last like 10 iterations, you accessed like this chunk of memory sequentially, or you access this chunk of memory with some fixed stride between um each access. And so I better, I better just assume that you're gonna continue accessing that uh uh uh stream of memory. Um, and I'll just fetch where I think the next element's gonna be. Um but if you're accessing a whole bunch of different um uh streams of memory, um the processor has a limit to how many different streams it can track. Um and so it might, you know, it might reach that limit and it might no longer be able to uh uh uh to keep track of all of your linear access patterns and and pre-fetch accordingly. Uh and then again, you'll have more cache misses. Um yeah, and and and there's uh there's a few other you know ways and places in which these sorts of effects can come up. If you've got multidimensional loops, um uh you can you know these these caching effects can be even more pronounced because in the multidimensional loop um uh you will have a lot greater potential for um uh reuse in the inner loop. And also if you have something like an adjacent difference or any sort of stenciled operation where each iteration you don't just access one element, but you access you know three or four or five different consecutive elements, like a window of elements. Um you know, if you fuse a bunch of loops together, then again, that's increasing pressure on the cache. Um and then it's possible that uh that you know you're accessing these five consecutive elements, and maybe because of this loop fusion, the um the last of those consecutive elements got pushed out of cache by something else that you uh uh uh that got pre-fetched into cache because of all of the stuff that you're trying to do in this one loop. Um now this isn't to say that loop fusion isn't ever a good optimization. I mean, it in many cases it is. Um it's not always the right thing to do. Um in every compiler that does loop fusion has heuristics for when it's profitable to do so. Um and in some cases it the compiler will split your loops because it determined, hey, you know, if I take this complex loop that's doing like, you know, a ton of things, and if I just split it into like three loops that are much simpler, those three loops are gonna run faster than the complex loop because um uh those three loops um are gonna have really good, really simple and easy memory access patterns. Um and the processor is gonna do a great job of pre-fetching the data for those three loops, and there's never gonna be a cache miss. Whereas this one giant loop that I have, it's a mess, and it's gonna end up with, you know, a whole bunch of cache misses.
ConorSo that makes sense uh for the most part. Although I will say your example where you had three arrays, you know, one loop that was going over the first one, and then another loop that was going over uh all three, including the first one. Uh I mean I would guess that uh fusion in that case, in most cases, like it would end up being faster, right? Because like in if you had said, you know, a loop over uh array A and then a second loop over array B and C where the index is the same. So you could still fuse it, to me that's a lot more obvious that you could end up with cache misses, whereas where the first loop is just a subset of the data of the second loop. Isn't that isn't like the second loop gonna end up with just as like fusing the first loop because it's a subset of like the data that you're fetching? Isn't that you're gonna have the exact same cache miss whatever ratio, or like am I missing something?
BryceFusing that for that first fusing that first loop into the second loop might mean that the for the first loop, let's say that that first loop as written um has great memory access patterns and is gonna always pre-fetch great and um run very fast. Fusing it into the second loop could mean that um the operations that were that can that constituted that first loop will now cache miss because the this uh second loop has more complex memory access patterns and it's trying to load more stuff into cache and you know some of the stuff starts to fall out of cache and in and isn't not like isn't isn't there when we expect it to be there. Um so it might make the first loop um uh uh uh slower. Um it might also complicate the second loop. It it might it will add additional register pressure to the second loop because there's a new new operation that you have to perform. Um and it might that additional register pressure might mean that there's um spills to stack, which might mean that uh now the uh the stack has to be in cache uh where it previously didn't, and that means that fewer of the data elements would need to be in cache. Um and uh it you know the the combination of those two loops could also throw off the compiler's um ability to uh uh recognize that it should uh uh not the compilers, it might throw off the processor's ability to pre-fetch the right data because it's it's a more complex um access pattern. Um you know, it it especially it could be the case if that if that first loop was something like an adjacent difference where it's stenciled, where it needs to access consecutive elements. Um if you have a loop that is accessing consecutive elements, um you need to not only have the next element in cache. Need to have some of the last elements in cache. And you might need to have like the next one or two elements in cache and the last two or three elements in cache. And so combining those loops, you know, maybe the second loop only needs to have, you know, each iteration it only accesses one element from that array. You see what I'm saying? Right.
ConorNo, yeah. So I guess that, yeah, the register pressure stuff makes total sense because of the increased operations. I guess you had not said this, but I in my head, when I you were explaining that example, was thinking that uh you had a single index i, uh, and that was the only index that was being used for each of the arrays A, B, and C. But uh, if in the first loop, like you said, you you're looking at both index i plus you know two before and two afterwards, and then in the second loop, you're only using, you know, single, like, like you said, if you're changing the data access pattern and it becomes more complex, then that can I can see that, yeah. So that's I think I added uh criteria to your example that you'd never stated, which was what the caused the confusion.
BryceYou asked me a question the other day, which was um you know, don't you have to pay for the cost of the memory loads and stores anywhere, like in both cases? Like, you know, what why does it matter?
ConorUh the way that I had phrased the question, because it was uh related to a slightly different example, is that you've got one example where you have two loops and you're gonna be loading things, so you and you're iterating over an array, and however many times you need to load things into cache, you're gonna have to do that twice because you've got uh two different loops. So n times for the first loop, n times for the second loop. And in the fused example, that potentially results in some cache misses. Uh anytime there's a cache miss, that's gonna result in another, you know, loading things into cache. So, like, you know, worst case or whatever, you're gonna end up with two n, you know, of having to load things into cache. So in both examples, you have two n uh, you know, times of loading things into the cache. Why is one more like say, and you're saying, like, oh, if we split it into two loops, that's gonna be potentially faster. And my question was like, I don't understand. Like, if we're loading things into cache the same number of times, sure, one of them is due to some cache misses, but like why does it end up being so much more performant when you split it into two loops? Like that didn't make sense to me.
BryceAnd and that brings uh that brings us back to the start of our discussion where we talked about um efficiency in the context of parallelism. Um and the intuition here is you are assuming that I have to wait for those memory loads and stores. That like, you know, there's some fixed cost that I always have to pay for those memory loads and stores. But the thing is the processor, all processors essentially, um are parallel. There's this unit that's going to do the load in the store, and there's a unit that's going to do my computation, and there and they can operate asynchronously. And most modern processors, you know, a a laptop or a phone CPU or server CPU, maybe not an embedded CPU, but most modern processors, GPUs too, um will pre-fetch data for you. Um and many of them are uh do this thing called out-of-order execution. Um and what that means is that in the best case, yes, you have to pay the cost for that load in the store, but it's it's it's hidden from you because the processor has started that load before the data was needed. Like let's say that that load takes a minute. Okay, let's say it takes a minute to load from main memory every time you do it. I don't care about that minute if the processor initiated the load a minute before I needed it. And if the load is happening asynchronously in the background and the data just happens to be there when I need it, then we're good. Um and that's you know, that's the power of pre-fetching, is the data just gets there into the cache when I need it. Um and you compare that to the case of the cache miss, where um uh I have to actually go into main memory and I have to wait for that operation. And like I have to pay, I have to wait for the full latency of that operation. Uh and this doesn't just come up with um uh data uh load and stores too. Um division, for example, which is notoriously an expensive arithmetic operation on most processors. Um usually your processor these days can usually do multiple um adds and and subtracts and multiplies per cycle. But usually something like a division can take you know uh 10, 20, 30 cycles, could even be a lot more than that. But if if you only need to do a division every 30 cycles, then that's that's okay. You won't actually have to wait for it because assuming that that you can have the data ready for that division, 30 cycles ahead of time, then you can start it and you can go do 30 cycles of other work, and then like you your division will be done, and then you're good. Whereas if you don't have that work to overlap, then you do you know have to spend the time waiting for that operation to come back. Um and we call this latency hiding. Um and you know, the parallelism at this level um is not something that's visible and exposed to programmers. You don't have to think about like how you how you write this, um, because it's something that the processor and the compiler do for you. Um but I do think it's important to have the mental model of how this works and to understand that all processors are inherently parallel, even if you're programming to a single thread. Um and that can really have a big impact on your performance.
ConorYeah, so basically, yeah, cache misses can mess up prefetching, and if prefetching's messed up, it's not going to be the same performance profile, obviously.
BryceYeah, and I mean usually it's more the other way around. It's it usually the reason that you have a there's two reasons to have it that you'd have a cache miss. Reason number one is that the data that you needed to have was not pre-fetched because the processor did not figure out that it needed to uh pre-fetch it, or because the processor figured out it needed to prefetch it, but the prefetch did not, it did not figure it out early enough. And and then reason number two is the data was in the cache, but it got evicted from the cache because there's a lot of pressure on the cache because you you you need um uh a lot more data than you can fit into your cache. Um and there's a number of strategies that you can use uh uh in that case. Like for example, one that comes up a lot in multi-dimensional loops is something called tiling, uh which gives you better control over um uh the amount of data that you need to have um uh in cache. Uh by controlling the size of your tile, you can uh uh control uh how many elements you need to um to have in cache. And then that therefore you can make sure that you you you can fit all the things that you need in cache um uh and not uh not have to spell to the next level of cache or the main memory.
ConorYep. Makes sense. And more importantly, I think you nailed it, Bryce. Ten minutes.
BryceYeah, although I I uh I gotta go get dressed and then run to my thing.
ConorThanks for listening. We hope you enjoyed and have a great day.