Re:Overhauling Mario 64's code to reach 30 FPS and render 6x...
by fps_doug on Thursday April 21, 2022 @12:14PM
(#31111395)
Some of that doesn't have to do with C even. Like, changing memory layout of variables, or the way you access data.
A simple example is if you have a 2D array, and you have the data from the individual rows consecutively in memory, but then you loop over the columns in your outer for-loop and over the rows in your inner for-loop. This means you access the first element from the first row, then the first element from the second row, then the first element from the third row, and so on. All these elements are far apart in memory, but every time you access one element, let's assume it's an uint32_t, the CPU fetches a whole cache lane of e.g. 64 bytes and puts it in the CPU cache in anticipation that you access data close to this in the near future. But you don't, so the CPU has to fetch another 64 bytes block for the first element of the second row, uses only 4 bytes from that, and so on. If your 2D array is large enough, by the time you finish the first iteration of the inner loop and start reading the second element of every row, the 64 byte cache lane that was fetched when you read the first element of the first row has already been evicted from the CPU cache again when you read the first element of row 2000, so the same 64 byte block has to be fetched from RAM again. This makes a huge performance difference, and is applicable to pretty much every programming language.
A simple example is if you have a 2D array, and you have the data from the individual rows consecutively in memory, but then you loop over the columns in your outer for-loop and over the rows in your inner for-loop. This means you access the first element from the first row, then the first element from the second row, then the first element from the third row, and so on. All these elements are far apart in memory, but every time you access one element, let's assume it's an uint32_t, the CPU fetches a whole cache lane of e.g. 64 bytes and puts it in the CPU cache in anticipation that you access data close to this in the near future. But you don't, so the CPU has to fetch another 64 bytes block for the first element of the second row, uses only 4 bytes from that, and so on. If your 2D array is large enough, by the time you finish the first iteration of the inner loop and start reading the second element of every row, the 64 byte cache lane that was fetched when you read the first element of the first row has already been evicted from the CPU cache again when you read the first element of row 2000, so the same 64 byte block has to be fetched from RAM again. This makes a huge performance difference, and is applicable to pretty much every programming language.