\r\nclass SpaceMarine\r\n{\r\n bool dead;\r\n char[8] name;\r\n Vector3 position;\r\n float stubble;\r\n short bullets;\r\n short kills;\r\n short dead_wives;\r\n bool cigar;\r\n};<\/pre>\nThis is a contrived example, but it’s good enough for illustration. This is what the data structure looks like for a single space marine. Here is that same list of fields, except I’ve color-coded them and made boxes illustrating how much memory each field takes up:<\/p>\n
<\/p>\n
<\/div><\/div><\/p>\nYou can see that the name takes up 8 bytes of data. The position is a collection of X, Y, and Z values. Each of those is 4 bytes, so the total size of position is 12. We’re using 4 bytes to store how much chin stubble he has and 2 bytes for his bullet supply. You get the idea. If you add these all up, we need 32 bytes to store a single marine.\u00a0<\/p>\n
When these are stored in memory, they’ll be packed together like so:<\/p>\n
<\/div><\/div><\/p>\nJust remember that memory addresses aren’t arranged in a grid like this. Memory is a linear thing, which would mean it’s just one row that stretches on for billions of bytes. But that’s kind of hard to show in an image, so I’m having the memory wrap to another line to make this readable.<\/p>\n
Conceptually, this is how programmers want to think of a space marine. He’s this self-contained thing and we manipulate his data every frame to make gameplay stuff happen. We run some sort of game update on him and change his position, subtract some bullets as he shoots stuff, add to his kill counter, and maybe grow out his chin stubble a little. Whatever.\u00a0<\/p>\n
But this probably isn’t the most common use-case for a space marine. This most common thing isn’t updating the marine, but checking for interactions with other objects in the scene.<\/p>\n
The Most Common Operation<\/h3>\n
<\/div>Judging by Gears of War, I'm betting the most common operation is Marine.Shout()<\/div><\/p>\nLet’s say in our scene, we’ve got a bunch of shit flying around that needs to interact with space marines. Bullets and lasers need to damage themAfter creating the above diagrams, I’m finally noticing I didn’t give the marines a hitpoint variable. So I guess all hits are an insta-kill in this game?<\/span>. Explosions need to shove them around. Debris and physics objects need to bounce off of them. Particles need to avoid passing through them. Crushy machinery should squish them. Vehicles should run them over. Landmines should go off if a space marine stands on them. And so on.<\/p>\nSo every frame, every one of these objects needs to crank through the entire list of space marines and test to see where it is so it can decide if an interaction is needed. For the vast majority of these tests, the answer will be “no”.\u00a0<\/p>\n
Like I said earlier in this series, your processor has a tiny pool of memory called the L1 cache. If the L1 cache is 64 bytes, then it can hold exactly 2 space marines at a time. So as all those game objects are cranking through the list, it will look like this:<\/p>\n
check SpaceMarine #1<\/p>\n
check SpaceMarine #2<\/p>\n
(cache miss)<\/p>\n
check SpaceMarine #3<\/p>\n
check SpaceMarine #4<\/p>\n
(cache miss)<\/p>\n
check SpaceMarine #5<\/p>\n
check SpaceMarine #6<\/p>\n
(cache miss)<\/tt><\/p>\n
And so on…<\/p>\n
If there are 16 SpaceMarines and 100 gameplay objects that need to interact with them, then you need to crank through the list of marines 100 times. That means we’re going to do 1,600 position checks, which will result in 800 cache missesActually, the L2 cache is really important and will help us out a lot here, but I’m trying to keep this as simple as possible.<\/span>.<\/p>\nThese cache misses are invisible in the code. The programmer doesn’t write a line of code saying to get another block of memory. That’s all handled by the compiler. They just write a couple of lines to loop through all the space marines and check their positions. This invisibility is one of the reasons that programmers like me are often blind to their true cost. The thinking will go something like this:<\/p>\n
“Man, all these landmines are doing a distance calculation every frame, and that involves doing a square root. Those are expensive! Maybe I should optimize that somehow.” But meanwhile the square root operation is a minority of the cost. Most processor cycles are being spent idle while waiting for things to arrive from main memory.<\/p>\n
So What is the Programmer Supposed to Do?<\/h3>\n
Here’s the problem you’re trying to solve:<\/p>\n
All of your various game objects (landmines, bullets, explosions, etc) need to do per-frame checks to see if they’re interacting with space marines. Every object needs to check itself against every marine. At this stage, you don’t care about anything except the marine’s position. The problem is that you’ve got all this other data – like the marine’s name and number of wives – mixed in with those position values. You don’t care about that data, but it winds up taking up space in the cache and causing performance-destroying cache misses.<\/p>\n
A list of three SpaceMarines would look like this in memory:<\/p>\n
<\/div><\/div><\/p>\nThe long distance between the address of the position variable for SpaceMarine #1 and the position variable of SpaceMarine #2 is the problem. Keep in mind that this is a very<\/b> simplified structure. In GoodRobot, each robot had dozens<\/b> of properties. And that was just a simple 2D game. Your real-world 3D game is going to have a huge distance between the position of SpaceMarine #1 and the position of SpaceMarine #2. Very likely, you’ll get a cache miss for every one.<\/p>\n
I’ve never worked on a AAA project like this, but based on discussions I get the sense that the most common way to handle this is to copy the data into an array.\u00a0 Just before you do your checks, you copy all the position values into a temporary buffer. Then you do your checks against the buffer. In the rareRare from the program’s point of view. To the player, bullets are hitting marines CONSTANTLY. To the program, it did tens of thousands of checks before it found a case where a bullet hit somebody.<\/span> occasion that a bullet actually hits someone, it can then interact with the full SpaceMarine data structure to see what happens.<\/p>\nThe problem is that there’s an overhead to copying this data into a buffer. You’re now storing the same data in two different places. If the position of a SpaceMarine changesExplosions are notoriously shove-y.<\/span> then you have to synchronize the data with the temp buffer or you might get weird behavior. This adds a lot of complexity to the code, particularly if you’re interacting with many different data values, some of those values need to change, and sometimes you have to deal with cascading changes like I discussed earlier in this series.<\/p>\nThis is messy. Isn’t there some way we can have the best of both worlds? Is there any way we can skip this messy, confusing step with the temp buffer without all the performance problems?<\/p>\n
Like I said, a list of three SpaceMarines would look like this:<\/p>\n
<\/div><\/div><\/p>\nIf all of the SpaceMarines were packed in such a way that similar variables were stored together, then it wouldn’t be a big deal to crank through the list and check all the positions. A list of three SpaceMarines would be packed like so:<\/p>\n
<\/div><\/div><\/p>\nIf the L1 cache is 64 bytes and a single position value is 12, then the positions of five consecutive SpaceMarines could be held in the L1 cache at the same time. Instead of triggering a cache miss with every other check, you’d get this:<\/p>\n
check SpaceMarine #1<\/p>\n
check SpaceMarine #2<\/p>\n
check SpaceMarine #3<\/p>\n
check SpaceMarine #4<\/p>\n
check SpaceMarine #5<\/p>\n
(cache miss)<\/p>\n
That’s going to be more than twice as fast!\u00a0<\/p>\n
So why can’t they be packed like this?<\/p>\n
Well, they can. Sort of.<\/p>\n
Vexation #6: Refactoring Code is Not Programming<\/h3>\n
The problem is that in C++, packing the attributes of your marines together would require you to completely re-write the code. Everything<\/b> related to SpaceMarines – every allocation, every check, every interaction, every deletion – would need to be changed. You’d have to give up your object-oriented class structure and break the variables into seperate lists. You’ll no longer have a list of 50 SpaceMarines. Instead you’ll have a list of 50 names, 50 positions, 50 cigar flags, and so on. Instead of deleting marine #5, you’ll have to delete name #5, position #5, stubble #5, bullets #5, and so on. If you forget one, then the lists will get out of sync with each other and you’ll get a bunch of strange bugs. If another programmer comes along, they won’t have that nice class definition to help them understand how this part of the code works.<\/p>\n
In short, doing things the “right” way makes for lousy, verbose, clumsy, confusing code. Worse, switching between these two memory layouts is not easy. If you’re trying to compare the two, then it’s going to take a lot of fussing to gather the data.\u00a0<\/p>\n
These two different ways of storing data are referred to this:<\/p>\n
Array of Structs:(AoS)\u00a0 A list of objects (like marines) where objects are stored one after another.<\/p>\n
Struct of Arrays: (SoA) An object that contains lists of fields, so similar fields are stored together.<\/p>\n
You can think of this as a list of containers vs. a container of lists. These are two conceptually different ideas and the implementation for them is very different. If you realize your project needs to use the other memory layoutOr if you’re curious and want to compare the two.<\/span> then you need to re-write basically everything.<\/p>\nIn gaming, you’re very often doing batch operations where you only care about one part of a large structure. Like, maybe we have a series of loops that look over all of the space marines and checks for a particular situation.\u00a0<\/p>\n
\r\n\/\/Some C-ish pseudo-code\r\n\/\/Let's assume these marines have a hitpoint value, even though the earlier ones didn't.\r\nforeach (SpaceMarine Jack in MarineList) {\r\n\u00a0\u00a0if (Jack.Hitpoints () <= 0)\r\n\u00a0\u00a0\u00a0\u00a0Jack.die ();\u00a0\r\n}<\/pre>\nIf you have a list of 50 space marines and you're using AoS, then you get a cache miss every single time you check a marine. However, if you do happen to find a marine that needs to die(), the die() function will probably run nice and fast because the entire soon-to-be-dead marine will already be loaded into the L1 cache. If that same list is stored in SoA format, then checking marines will be blazing fast, but processing the death of a particular marine will be slow because his individual fields are all scattered around in memory.<\/p>\n
So to know which system is best, we need to ask ourselves: Which is the most common operation, checking or die()ing?<\/strong>\u00a0<\/p>\nAssuming this is your typical video game, then obviously checking will be massively more common than die()ing. If you're got 50 marines, the game runs at 60fps, you check for death every frame, and marines die an average of one every ten seconds or so, then you will need to check hitpoints 30,000 times for every time you need to call die(). Checking hitpoints is massively more common than calling die(), so it makes sense to optimize for checking.<\/p>\n
Sadly, none of the C languages offer a way to store your data as a SoA without giving up all of your object-oriented design. To the best of my knowledge, no major language does.<\/p>\n
I don't know why this is. I'm not being snarky. I'm not saying, \"I don't know why those dum-dum language designers didn't think of this.\" There's probably a shining good reason why compilers work this way, it's just that those reasons fall outside of my area of knowledge. My guess is that our modern-day concerns over cache misses are relatively new in terms of language development.\u00a0<\/p>\n
If a language designed for games offered you a way to switch between a SoA and AoS as needed, then it would be really useful in cases where you need to do bulk checking on game objects.<\/p>\n
JAI will supposedly have this feature, and I wonder if it's not going to pop up in some other languages in the next few years. I find it hard to believe that video games are the only domain that would benefit from this.<\/p>\n","protected":false},"excerpt":{"rendered":"
In previous entries, I talked about how you sometimes need to worry about small blocks of memory. In some cases, you may even want to worry about how the data is arranged in memory. To show how this works, let’s look at our old friend the space marine: Space Marines class SpaceMarine { bool dead; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-48683","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/48683","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=48683"}],"version-history":[{"count":15,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/48683\/revisions"}],"predecessor-version":[{"id":48700,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/48683\/revisions\/48700"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=48683"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=48683"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=48683"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}