Micro-optimization tutorial
This tutorial was originally posted as a mini tutorial on Twitter and is aimed as an introduction to struct packing at a beginner level.
These two structs have the same variables but the one on the bottom is 8 bytes larger. If you don't know why that's the case, let's take a very simple look at the forgotten art of 'Struct Packing’:
A computer typically reads and writes to sequential memory addresses in chunks such as 16 bytes (CPU dependent). As such it will fetch 16 bytes of data in 1 cycle. 32 bytes in 2 cycles.
To make sure we access this data in 16 byte “aligned” chunks, computer scientists came up with the idea of automatically adding extra bytes as padding. Most modern compilers do this automatically.
The downside is sometimes we have structs bigger than they need to be :(
However, we can remove unnecessary padding by simply ordering our variables within a struct so they align to the largest member (A.K.A packing a struct).
The easiest way to pack a struct is to order them from largest to smallest, as a struct is always aligned to their largest data type. E.g. this structs largest member is a pointer (8 bytes on 64 bit architecture). So it aligns to 8 bytes.
As with the original example, the reason why the struct on the top is 8 bytes smaller is because we ordered the members from largest to smallest. A.K.A we packed the struct!
That’s struct packing! I left out a lot of detail but remember, better algorithms > micro-optimizations. Good habits means you can have both. I wasn’t taught this in my Comp Sci course so I figured others may have missed out as well. Let me know if you want more of these!
Also a big shout out to my co-worker Ewen Vowels, Sledgehammer Games for fact checking this and correcting my mistakes along the way :)
Amendments
After putting out the Twitter article there was a lot of helpful feedback on some clarifications and helpful things to include. Here's a sample of the ones I felt were worth sharing below:
Viewing padding from the compiler
Padding can be viewed with adding the command line options: /d1reportSingleClassLayout in your cpp file.
In Visual Studio, right click on your .cpp file and go: properities->C/C++->Command Line. In additional options paste /d1reportSingleClassLayoutXXX where XXX is your struct name.
In the build output, notice that padding shows up as (size=N) where N is the number of bytes used for padding.
Where does the padding go?
In the original article I left out some detail on padding:
The easiest way to pack a struct is to order them from largest to smallest, as a struct is always aligned to their largest data type.
Just as a clarification, although structures are aligned to their biggest member, native types still need to be aligned to their own size as well! This may clear some confusion on why padding doesn't always just go at the end of the struct.
Thanks to Bruce Sutherland, Sledgehammer Games for the tips!
Caveats
There are lots of caveats to how this all works depending on architecture, compiler, 32 vs 64 bit etc. There are also attributes that allow you to disable padding all together. Look at #pragma pack as an example.
Thanks to Matt Stafford, Pub Games for the help!
Do I always want to pack my structs?
Surely since it saves memory we always want to pack our structs... right?
"Other factors to consider is ordering commonly used members at the beginning for run time performance reasons. Sometimes a little bit of memory waste is worth it, if run-time performance is better in the end :)"
Thanks to James Tan, Digital Confectioners for the advice!