Memory System: Part II
Note: These Game Engine blogs are a series of write-ups I did when I was in school for my master’s degree. I took a series of three courses run by Ed Keenan where we built a game engine from scratch in C++.
Now that we have a base memory system up and running, we’re going to make some optimizations to it that will allow it to be even faster. This will allow the users to force some certain formats to their data in order for it to be read even quicker.
N-Byte aligned data
Right now in our memory system, users will allocate from a heap and an address is returned for that user to place their data. If we are able to align that address to a particular alignment (that the user sets), then the CPU will be able to process the data even faster.
What Do You Mean By Aligned?
Addresses can be 1-byte, 4-byte, 8-byte, 16-byte, 32-byte, etc.. aligned.
Per Wikipedia: A memory address a, is said to be n-byte aligned when a is a multiple of n bytes (where n is a power of 2). But what does that mean in English? Well it’s difficult to explain without some binary math knowledge, but it basically means that our data is aligned to those addresses and that the data doesn’t sit on awkward addresses. Let’s look at a diagram as to why this is important. It’ll make more sense this way.
The top portion shows what happens when an unaligned data is pushed into the CPUs register to be used. You can see that it doesn’t fit nicely and the CPU will have to shift the register window down to read the entire 4-byte data structure.
The bottom portion shows what happens if the data is aligned. The register won’t need to be shifted so this data can be processed in a single cycle by the CPU. This is exactly what we want. If the data is unaligned it will take many more cycles to process because of the register shifts.
Less cycles = faster. Faster memory = better.
How Do We Implement This?
By allocating a little extra memory (exactly the size of alignment we’re looking for. If we want 8-byte aligned, we ask for 8 extra bytes). So every time we ask for some memory we grab a little extra and shift the address down until it’s aligned. We can check if it’s aligned by doing some fun binary math tricks.
Here’s an article by IBM on why memory alignment is important in software engineering: Data alignment: Straighten up and fly right
Fixed-block Heap
The Heaps we created in Week 2 are what we’re considering to be a normal heap. In a normal heap, programmers will be able to allocate blocks of various sizes. This is all fine and dandy, but if we’re able to make some assumptions about the data that will be used in a particular heap — then we can make it go faster. Enter the fixed-block heap.
A fixed block heap will be able to create n amount of blocks of x size. Both n and x will be defined by the user when the fixed-block heap is created.
Because every allocation from within that Heap will be of the same size, we can read this data in larger chunks. Why is that helpful? Well, for one its faster. But how could this be used in practice? Well, what if we allocated all of the Yoshi Question Blocks in Super Mario World into one heap. All of those objects are exactly the same except for their position so if we put them into a fixed-block heap, we can write an iterator of sorts to process this memory in batches because we know the size of these data objects.
*Morgan Freeman voice* Next time on “Building A Game Engine From Scratch”
We’re building a math library to deal with Vectors, Matrices, Scalars, and other stuff.
