It is extremely important to be able to protect our work from being stolen, and against low effort near reproductions being made and claimed to belong to someone else. The law is not protecting us as it should be, and we are left to fend for ourselves. I agree this is a problem, and this is the problem that data poisoning aims to address. How then could the concept of data poisoners annoy me? Certainly I should be a fan, and even more, perhaps I should use my graphics programming / computer science / research knowledge to help advance the technology?
Absolutely not, and I will tell you why: It makes people believe their work is safe, when it isn’t. That makes it dangerous, and it is not fixable, unfortunately.
For data poisoning to work, there needs to be some mechanism of perception where a machine would fail, but a human would succeed.
Data poisoners work by finding instances of this being true in specific models. That doesn’t protect from other models though, or from future models – and the future goes on for a long while (for better or worse).
Captchas are similarly doomed to ultimately fail, but the difference there is we can keep updating them in an arms race to keep up (essentially captchas being the adversary part of a GAN). With data poisoning, as soon as you need an iteration on the poisoning tool, this is a sign that the previous poisoning is no longer effective against the current models, which means all “protected” data is now unprotected.
If we want lasting protection, we need to find some perceptual mechanism that a human has but a machine does not have, and could never have. We can think about where something like that could come from. Anything that is biology based, chemistry based, or physics based can essentially be done by a machine.
Beyond that only lies concepts like the soul and free will. These things are untestable, and thus have no actual effect that us engineers can exploit to separate humans from nonhumans, or biology from machines. This is why I say the problem is ultimately unfixable.
Yeah sure, we can try to make things have prohibitive cost or difficulty to deal with – this is the age old battle in security after all – but even if we get that, the real problem is that poisoned data is not universally poisoned and does not stay poisoned. That is a shame, but that’s reality.
Also, here’s a paper on arxiv about the weaknesses of a specific type of data poisoning, even for models it was meant to poison. https://arxiv.org/abs/2406.12027
UPDATE 10/26
I’ve had a few comments from people that they use poisoning not to protect their work, but to instead hope that their work causes some damage to the training process which tries to consume it. Effective or not, this seems like a noble goal. This may have reversed my opinion on poisoning, I’ll have to think it over for a while!
While it doesn’t solve all the needs I called out in my original blog post, it solves many of them, and features can be added by myself or others at time goes on. I made it with the features that I needed for my current personal game project, but also spent the extra effort needed to make it usable by others. “I’m not just the president, I’m also a client”.
This blog post shows some of the technical decisions I made and why I made them. In particular, I like the solution I came up with for serializing static vs dynamic sized data, so we are going to start with that.
Serializing Fixed Sized Data vs Variable Sized Data.
If you have an array of objects, where the object type only contains simple data types and no pointers, writing them to a binary file is pretty easy: you write how many there are (as a uint32 perhaps) and then you write each object, one after the other.
When you read this data later, you can read the count, and then getting to each object is a easy calculation. The offset is index * sizeof(object). If you keep the file contents in memory, you can make a pointer of type object* to that location in memory and index it like a normal array.
That would be the end of the discussion if we were only dealing with fixed size data. That is almost every data type a person could ask for except for variable sized arrays, and strings which can be thought of as variable sized arrays of characters. These exceptions are important so we have to increase the complexity a bit.
One way to deal with dynamic sized objects would be to write the size of each object before the object. Unfortunately, if we wanted to get to a specific object by index, we would need to scan through the entire list of objects until we got to the one we wanted.
We lose the ability to just index into an array and get any object in O(1) time. Constant time access is really important for performance so let’s find a way to bring it back.
Variable Sized Data
A common way to deal with strings is instead of writing the whole string as part of an object, you put the string somewhere else in the file (like, at the end) and write the offset of where that string is as part of the object.
That makes an object with a string be a fixed size. This is also how strings work in memory: your object has a char* in it, but the actual string itself lives somewhere else. The size of an object containing a string doesn’t grow as the string grows.
When loading binary data that includes a string, you can use the offset to get the actual string itself. If you loaded your entire binary file into memory, you can add the starting memory address to the string offset to get an actual pointer to the string. This “pointer fixup” is a common thing in binary serialization, and is really nice for efficiently loading and using binary data files.
With strings solved, we can do the same for variable sized arrays. Instead of writing a variable sized array out as part of an object, we instead write the variable sized array data somewhere else in the file, and just write the item count and offset to the dynamic array as part of the object. Once again this is how variable sized arrays work in memory. Your object has a T* in it, but the actual data itself lives somewhere else. String length is determined by a null character, so strings don’t need to serialize the size, but dynamic arrays are not null terminated, so they do need a size serialized.
You can do the same pointer fixup on load to turn the dynamic array offset back into an actual pointer.
One way to implement this separation of fixed sized and dynamic sized data could be to have two std::vector<char>’s. The first one is where fixed sized data is written to, and the second one is where dynamic data is written to.
While you are filling out the binary data, you don’t know the offset of where a specific string is going to live in the file, since that offset is going to be the size of the entire fixed size data, plus the string’s offset in the dynamic sized data.
A way to deal with this is to defer writing the actual dynamic data offset until you are done making all the binary data. I do this by keeping a table where each entry has two numbers: The location of the offset in the fixed size data, and the dynamic data offset to be written there. After you are done making the binary data, you can loop through this table and write all the necessary offsets into the fixed data, pointing at the dynamic data. The dynamic data offset just has the static data size added to it, to make the offset to write into the static data area.
Fractal Complexity Tamed With A Data Stack
This sounds great, but what happens if we have a variable sized array of an object that includes strings? If you are in the middle of writing a dynamic array of objects into the dynamic data, and then you hit the string, you can’t write the string in the middle of the dynamic object. We’ll lose our ability to random access our dynamic array objects by index if they are different sizes. We hit the same problem again!
The solution I came up with was to generalize the solution from the previous section. Instead of having only two vectors where one is for fixed sized data and the other is for variable sized data, the strategy changes a bit. There is a stack of vectors that is arbitrarily deep. Whenever you are writing fixed size data, you write it to the current data stack index. When you write variable sized data, you write it to the data stack index + 1, and write the offset to it at data stack index.
At every level of the stack, there is fixed data which has O(1) random access by index, but it can support arbitrarily nested fixed and dynamic sized data.
To actually set the offsets, we keep a table like we did in the last section. Instead of only storing the fixed sized data location, and the dynamic sized data location it wants an offset to, it instead stores the stack index and offset of where it wants an offset written, and it stores the stack index and offset that it wants to get the offset of.
After all the data stacks have been written, it’s trivial to calculate and write the offsets, then dump the data to disk.
Null Pointers
When writing offsets, the offset of “stack 0, offset 0” has a special meaning. It calculates to a file offset of 0, and when the binary data file is read in, file offsets of 0 are translated into null pointers (left alone as null pointers), instead of having the base address added to them. The fourcc is at offset 0 in the file, and no data has a valid reason for pointing at it.
The ability to have offsets which translate to null pointers means that you can have optional data fields, which is a nice feature to have, and comes without too much effort or complexity.
With fixed / dynamic sized binary serialization solved, let’s talk about some of the other things.
Basic Functionality of df_game_data
In df_game data, you:
Describe a schema in a .def file using C/C++ style type definitions for structs, unions and enums.
Make and edit data records of the root data type you specified.
Compile the data to generate a .bin file, and also a .h file which is a “header only library” which loads the .bin file. Currently you can choose C or C++ for the language of the generated header.
Before writing my own schema language and binary serialization / deserialization, I looked into a couple different existing technologies like protobuffers and flatbuffers. Flatbuffers were very close to what I needed, but I felt chafed by what I felt were strange limitations – like dynamic arrays only being allowed to be in tables, and static arrays only being allowed to be in structs. I was nearly at the finish line when I made the call to take out flatbuffers and roll my own. I’m a lot happier with the result, so no regrets.
The Data Model
Whether we are talking about loading a .dbroot file in the editor, or loading a binary file off disk, the conceptual root object of the data is “The Database”.
The database is made up of one or more tables.
A table contains an array of named entries, where each entry in a table is the same struct type.
union – a data type that allows a field to be one of a specific list of types. Can be null (none of the fields).
link – a link to a table entry. Can be null.
Each struct field can also be a static or dynamic sized array of any of the above.
No special rules about what can go in what.
Loading The .bin Binary Data File
The file format has 4 main sections:
Fourcc
Version
Schema Hash
Data
Fourcc
The first four bytes in the file are a fourcc (four character code) “DFGD”. This is used to identify that the file type is a valid file, but also because if we read that in as a uint32 and it comes in backwards as “DGFD”, we know that means we need to do endian swapping.
Some machines store bytes of multi byte types in different order than others. The machine you are using is likely little endian, and modern consoles are as well, but some machines are big endian. The code doesn’t need to know if it’s running on a big endian machine or a little endian machine – it just needs to know if it’s the opposite endian. If so, it needs to reverse the byte order in multi byte types. This used to be a bigger topic in game dev than it is now.
Note there is also a cursed middle endian, but we’re ignoring that for now.
Version
The version is written as 3 bytes: Major.Minor.Patch.
The version doesn’t currently do anything, but in every piece of software that works with custom file formats, a day will come when you need to do special logic based on version number. It’s there in the file, ready to be used when it’s needed.
Schema Hash
After the fourcc is a uint64 hash which is a hash of the schema. The generated header file checks that this hash matches what it expects. If it doesn’t match, it won’t load the data and will return failure.
It would have been easy to hash the .def file (and any file it includes, recursively) for this hash, but a kindness I made for myself and other users was that it hashes the in memory representation of the schema instead. This way, if you add comments to the .def file or similar, it won’t invalidate / update the .bin and .h files you already have generated. This also lets me exclude field default values from the hash, since those don’t affect either the .bin file or the generated .h file. Default values are essentially an editor only feature.
Some compilation settings are also included in that hash though. You can opt into or out of various features, such as hot reloading, or being able to look up records by name, or whether the data is obfuscated. The features that affect the contents of the .h or .bin are included in the hash.
Data
After that comes the data. The data on disk is the same size / layout as the data in memory once loaded, but all pointers are uint64_t offsets into the file. They are written as uint64s because when running a 64 bit program, pointers are 64 bits in size. When running a 32 bit program, they are 32 bits in size, and they can just ignore the top 32 bits. Writing 64 bits allows us to have space for either a 32 or 64 bit pointer, depending on what flavor the loading program is running in. In the generated loading code, I make unions between the correct pointer type, and a uint64 to be able to enforce type safety of pointer types, while also making sure there is room for 64 bit pointers in the serialized data.
A pass is done through all the data fields recursively to first do endian swapping if needed, and then do pointer fixup.
Endian swapping is just reversing the order of bytes in multi byte data types like I said before.
Pointer fixup is converting the uint64 file offsets into pointers in memory. This is done by knowing the address of where the file data start in memory, and adding that to each offset. An offset of 0 is left at 0 though, so we can have null pointers.
Data Record Objects And Hot Reloading (C++)
When you get a record from a table in the database, it gives back a “Record” object, which internally stores a pointer to where that data lives. You can call .Get() on the record object to get a const reference to the object. The type is templated to know what struct type to give back.
If you have a record object which doesn’t point at a valid record, calling .Get() gives you a const reference to a default constructed static object of that type. You can also call .Valid() to see if a record is valid. A record is just a thin wrapper around a single pointer though, so it’s very light weight and fast to interact with.
When hot reloading support is on, it makes record objects a bit heavier weight by adding a dynamic allocation to store the name of the record they point at, a pointer to the database they are from, and an integer specifying what generation of database they are from.
If the database does hot reloading, it increments a generation integer. When you call .Get() on a record, the record will compare the generation integer it has versus the generation integer of the database. If they don’t match, the record will look up its record again in the database using the name it stored. If it can’t find that record, it becomes an invalid record.
So, when hot reloading support is on, record objects get heavier weight.
Calling Tick() on the database will cause it to look at the .bin file on disk and see if the modification time stamp has changed. If it has changed, it reloads the file and increments the generation integer.
Hot Reloading (C)
In C, hot reloading works differently. You still call a Tick() function which reloads the file when needed, and returns true when it does, but there are no concepts of records in the generated C code.
In C, when Tick() returns true, that is your notification that you need to update any data you have cached off from the database, if any.
Compilation Settings & Multiple Compilation Target Support
Different games have different needs, so there are few compilation options you can set.
The main ones right now are:
Record lookup by name support
Hot reloading support
Obfuscation
Looking up records by name can be useful (It uses a binary search), but it also means that the record names are plain text in the file, pointing at where the data for that record is. It makes it easier for players to edit data files. Turning this feature off makes those names not be emitted, and it makes the header file not have the ability to look up records by name.
Hot reloading support is useful if you want to do hot reloading, but it requires the record lookup by name to be on, and it also makes Record heavier weight like we talked about in the last section.
Because of this, it may be that a game wants to build a debug version of the data and header file which has hot reloading support on, but also a release version which has hot reloading and name lookup turned off. The editor lets you specify multiple compilation settings, and every time you compile data, it will compile all targets.
Obfuscation is an anti cheat option that was developed in part by Manoj MJ, who identified the need in the utility. When obfuscation is on, a pseudo random number generator will generate the same number of bytes as your data, and xor the data against it. This is a simple non cryptographic stream cipher. This feature just makes it a bit harder for people to read or modify the game data while it is on disk. Once it is deobfuscated in memory, they have full read/write access to it though.
Record lookup by name support can be useful, but you can do just fine without it too.
A common approach to this is to have one data table be a “singleton” with only one entry, and have this be the “configuration” object which points at the root of the most interesting objects. From there, you follow the links outwards to find the data you want.
For instance, in an RTS game, the singleton may have an array of links to building types, and each building type internally has an array of links to requirements for unlocking the building. If there is a special building, such as “What is the building that when destroyed means game over?”, you can make a singular link there in the settings that points at that building.
No need for magic strings (or indices, or hashes of names) there in the code. It all goes through data, starting from the singleton settings object.
Some games rely heavily on looking up data records by name though. In these situations, instead of doing a binary search in a sorted array of strings, these strings are either mapped to unique IDs for faster lookups, or they are hashed. A fun alternative is to use “minimal perfect hashing”, where you start with a known list of strings, and get a hash function that will turn those N strings into unique integers [0, N). If that need comes up, that would be a fun feature to add.
Enums, Links, Unions
All enums are serialized and defined as uint16s. Many enums could instead be serialized and defined as uint8s when they have 256 items or less. A future version may use “the smallest unsigned int needed to represent the enum” but for now they are all just uint16.
Links (Link<T> types) allow you to link to entries in tables. In the data, they become pointers to whatever entry you’ve linked to. If no link is specified in the source data, these become null pointers in the loaded data.
Unions work similarly to links. In C++, a union uses as much memory as it’s largest field. In fb_game data, we know at data compile time what type is used, and since the data is read only, we know that the type can’t change. So, we store an enum (uint16) for which field is the active field, and we store a pointer to the actual value, in dynamic memory, which is only as big as actually needed. Unions can also be null, so when a union is “none”, there would just be a null pointer in static memory, and nothing in dynamic memory.
Anti Cheat
When a game is running on a player’s computer, the game’s code has to be able to load that data. The player has full control over their own machine, and can read/write values in memory, and can even look at the machine code / assembly / disassembled C++ of the game to see what it’s doing. This means we can’t actually protect the data from reading and writing beyond cursory protection.
It would be easy to say the problem is that df_game_data is open sourced, but that isn’t the problem. Every game faces this issue and the only thing we can do is try to make it more effort than is worth while.
Right now the only things we have in the realm of “anti cheat” are:
The file needs to begin with the fourcc “DFGD” (or the endian swapped “DGFD”).
The next uint64 schema hash needs to be the expected value found in the header file.
You can opt out of having record names in the bin file, which could help a person understand what data was where in the file.
You can obfuscate the data on disk, which XORs it against a PRNG one time pad. (Added in part by Manoj MJ).
Aside from that, there is no validation that the data hasn’t been tampered with, and there is no attempt to obfuscate the game data.
However, more features can be added!
An option to compress the bin file could be added. This compression should happen before obfuscation if they are both on, since the one time pad obfuscation should turn the file into incompressible white noise. The main point of compression isn’t for obfuscation, it’s for reducing file size, but it would have a secondary benefit of obfuscating the data a bit more.
There could be a hash of the contents of the file after the schema hash field. When loading the file, this hash could be performed and compared to the contents hash stored in the file itself. If they don’t match, refuse to load the file. This would help protect the bin files from being written to while on disk. But again, it doesn’t protect them from being written to once they are in memory.
Any other ideas? File an issue, or better yet a pull request!
df_game_data Vs. a Real Game Engine
I’ve worked on a lot of games, most using custom engines, such as Starcraft 2, Heroes of the Storm, and Diablo 4.
Having game data solutions is very common, and there is a lot of variety in how they function.
I designed df_game_data to be standalone, low drama (easy to use, stays out of your way), and useful not only for myself, but for others as well.
Normally though, game data solutions are deeply integrated into the game, and not a modular component. For instance, in the Starcraft 2 engine, there were serialization functions for all serializable object types, and they would be called to save data to disk, to load data from disk, to send and recieve data over the network, to hash data, and probably some other things as well.
df_game_data is meant to be a standalone solution which has no knowledge of your game. This changes some things about it, but not in any real meaningful way IMO.
You may have to write your own serialization routines if you want to re-use structures for network messages or similar, but you could also add a feature to df_game_data which called a provided templated lambda on each data field in a struct, recursively.
In short, this is basically how game data systems work in most games, if you squint a bit.
Other Misc Things
When reading binary files into structs, you have to be careful of automatic struct padding. By default, padding will be added between fields to make them line up at a multiple of their size. A struct will also be padded to be a multiple of the largest sized member. See the struct definition below to see how a struct that looks like it should be 6 bites big is actually 12 bytes:
structMyStruct
{
chara; // 1 byte
//char padding[3]; // 3 bytes of invisible padding so that b can start on a 4 byte boundary
intb; // 4 bytes
charc; // 1 byte
//char padding[3]; // 3 more bytes of invisible padding so the struct size is a multiple of the largest size: 4
};
A way to get around the padding is to put #pragma pack(push, 1) before the struct, and #pragma pack(pop) after the struct to force packing to be 1 byte aligned, and thus add no padding.
You might be wondering how the loading headers are generated. I’m not doing anything very fancy, it’s just string replacement. If you look at the file output_cpp.h you can find the template for the c++ code generation. https://github.com/Atrix256/df_game_data/blob/main/loader/output_cpp_h.h.
In that file are tokens such as /*$Dtor$*/ which is where the object destruction logic goes, and /*$ClassName$*/ which is where the name of the class goes. The code generator generates strings to go where these tokens are, and it just does a find and replace to do that.
Adding backwards/forward compatibility of the data files could be nice to add. That and some other nice to have features are filed as issues in the repo.
Lastly, there is automated testing. I made the examples double as automated tests. A batch file runs each example and ensures that it exits with a code of 0. I have a batch file to run all tests and report the results. I also have a yaml file which makes github run that batch file, and requires it to return 0, for the build (& PRs) to be considered good.
This post has been a bit of a shotgun blast of binary serialization topics, but hopefully you found it useful!
First up, who the heck am *I* to have an opinion on this?
Well, I am a computer scientist specializing in deterministic sequences used in randomized algorithms.
Read my peer reviewed published papers on blue noise, read my blog posts on irrational numbers and the benefit of using them as pseudorandom number sources, read what I’ve written about using light weight cryptography to shuffle and group objects in constant time, with random access and inverse lookups using the Chinese remainder theorem. Watch my YouTube videos of the same. I find these things fascinating, so if you are interested, here are some of my favorites:
Ok so i know about determinism, but do I know about AI and ML? I stick to the bare metal of ML and don’t like to go into the highly abstracted levels that most modern ML people do, but yes. I know backprop, dual numbers (forward mode AD), ADAM, and other random things. During the AI winter, I kept myself warm implementing neural networks in excel (when I wasn’t working on game dev).
I also have an ML patent (pending) I won’t describe here, that is pretty interesting. Unfortunately, I fear it would help something like terminator’s skynet to exist. I tried to park the patent at a game company, thinking that would be safe, but now the American Fascist Party’s very own Jared Kushner and the Saudi prince who ordered the murder and dismemberment of Jamal Khashoggi own EA, and my patent, so RIP to humanity i guess.
Funny thing – a core feature of that patent is deterministic ML.
So yes, I do lift, bro.
The Determinism Argument
Ok so it annoys me that people complain that LLMs aren’t deterministic. I am annoyed because it isn’t that they want it to be deterministic, it’s that they want it to be RIGHT, and they don’t even realize it.
Let’s look at a 2×2 permutation matrix.
Considering each square, “When asked the same question multiple times”… :
#1 – it gives random answers and is wrong.
#2 – It gives the same answer every time and is wrong.
#3 – It gives random answers, but they are correct.
#4 – It gives the same answer every time, and is correct.
The argument that determinism is the problem with LLMs says that you want option #2 or #4 and are fine with either. You are saying “I don’t care if it’s right, I just want it to do the same thing every time”. If you are thinking this, good job: you are now breathing manually. (Note this feeling: This is what it feels like to be wrong. Do you feel it often?)
What people really want is #3 and #4. They don’t care if it’s random or not, they just want it to be CORRECT.
Any “random variation” within being correct doesn’t make it any less correct. If it did, you wouldn’t consider it correct, and it wouldn’t be part of box #3.
Yes i even am talking about LLMs generating code or executing some set of steps that a python script is probably better suited to. If you are in box #4, you are 100% happy. If you are in box #3, you are still fully happy because what it is doing is CORRECT. If you say “yeah but i need zero variation in the code generation or the utility execution”, ok so that’s part of your definition of CORRECT and you get that. If you don’t get what you consider correct, it is in a different box.
Another Way of Looking At It
You can run an LLM deterministically – both during training, and during inference. Set the seed of all pseudorandom number generators used, make sure nothing runs on CPU or GPU threads in a way that is non deterministic. This is fully possible and not even a big stretch. If you only know vibe coding you might think this is magic, but unfortunately it’s mundane as heck.
Would that make you happy? Of course not. It puts you into box 2 or 4 for every question you ask, but you don’t get to choose which box you end up in. The only variation in the network output comes from your input.
(Oh no, did i forget rounding modes? Go learn how an RTS works before you have an opinion about the feasibility of program determinism across different machines and compilers.)
Yet Another Way of Looking At It
I can hear you saying it:
“But bro – you are mixing up terms. The network represents a distribution in high dimensional space and the output is a single sample. You taking one sample using a a single pseudorandom value as input doesn’t make it deterministic.”
Bro, you are so correct.
Think about square number 3 in my lovely MS Paint ™ diagram. It gives random but correct answers when asked the same question repeatedly. How is that possible? BECAUSE IT’S A PROBABILITY DISTRIBUTION WITH WIDER SUPPORT.
Square #4 has a ~dirac delta as a distribution. That is the only difference.
Yes, I know it’s a distribution, so what.
Yet Another Way of Looking At It
There’s a debate about whether the universe is deterministic or not.
As best as we can tell, it is absolutely deterministic, except perhaps at the quantum level, which somehow seems to get laundered into determinism at large scales. Maybe through the central limit theorem, for all we know.
If that’s true, it is deterministic already so you can relax. Everything is exactly as you say you want it to be. Still not happy? THAT’S BECAUSE YOU DON’T CARE ABOUT DETERMINISM, YOU WANT IT TO BE RIGHT.
Also, maybe take a couple steps back from the kool-aid bowl. That stuff is bad for your health.
When programming high performance applications, such as video games, you learn neat tricks for writing fast code that makes the most of limited resources.
Memory allocation is a huge topic for performance critical code that needs a variable amount of memory.
When you hear “stack allocator” you might think of “alloca” which lets you allocate memory from the actual program stack. That is super useful in a pinch, but that is not what today’s post is about. Another name for the type of stack allocator we are talking about today is “bump allocator”.
The Stack Allocator
Around 2010 I was working at Surreal Software (Midway Seattle) on an open world game “This is Vegas” which unfortunately was cancelled when Midway went out of business.
On that project, one of my duties was animation programming. Animation worked by having a state machine for sets of bones, where each state was a tree of animation blends. When states changed, they would blend out from the old state into the new state to preserve continuity.
There was a lot of blending going on, and it used a large number of dynamic memory allocations for these animations to be evaluated and blended on the CPU. These allocations were all transient though and only needed to exist for part of the frame. Furthermore, these allocations had to happen per frame, as things could change drastically from one frame to the next, as to which characters were being animated that frame – based on the camera frustum for example. The allocator showed up as a hot spot in profiling this section of code.
To solve this problem, we implemented a “stack allocator” where allocation is just an integer add, and deallocation is even cheaper.
To do this, you allocate and keep some amount of memory that is the maximum amount you will need, like say 1MB. This is your stack. You also keep an integer “tos” variable to know where the top of the stack is.
When you want to allocate memory, your memory is the memory at the top of the stack, and you add the number of bytes you want to allocate to the tos variable so that the next allocation comes after yours:
In a real implementation, you would also want to know how big the memory was, so that you could handle the tos hitting the end of the memory – by returning null, or asserting, or something else.
When you are done with the memory, you just set the tos variable to 0.
tos = 0; // deallocate all stack allocations
In our case, we set the tos to 0 after animation blending was finished and we had copied the results into the buffers that were heading to the vertex shader for skinning. If you were using a stack allocator more generally for all transient memory allocations during a game’s frame, you may set it back to 0 when the frame starts.
The result was night and day. Allocation no longer took any measurable time in the profiler, because allocation was an integer addition, and freeing all memory was a single integer assigment. It doesn’t get faster than that.
One thing to note is that as written, this allocator does not call destructors or destructors. Using placement new for constructors would be easy enough. Calling destructors would be harder, as it would have to be a manual process, which is error prone. You might be able to use some RAII pattern, but stack allocators work best for simpler types.
Another great thing about stack allocators is that they can work in multi threaded environments. If the tos variable uses atomic addition, multiple threads can allocate from the same stack allocator. This can be nice in a fork/join situation on the CPU, or for a complex algorithm running on the GPU.
You can also do “partial deallocations” with stack allocators. For instance, if you had some recursive process where each level needed dynamic allocation, you could remember where the tos was when that level started, and set it back to that value when that level of processing finished.
The Double Headed Stack Allocator
A few years later, I found myself at Blizzard on the StarCraft 2 team. My boss James Anhalt was (and still is) a really smart dude who introduced me to shader toy, and shared a bunch of really cool techniques that have been previous blog posts. He told me about double headed stack allocators as a solution to a memory fragmentation problem he had hit in the past.
Imagine that you had a streaming world game where as the player ran around the world, old level geometry would deallocate, and new level geometry would allocate and stream in from disk.
At the same time, imagine the player character could shape shift into different forms – and each time they changed forms, the old form was deallocated, and the new form was allocated and streamed in from disk.
A challenge is, when you have these two systems allocating and deallocating random amounts of memory, on their own timelines, your memory is going to get fragmented.
Lets walk through a simple example. Let’s say you have 100 MB total memory for the level (red) and the character (green). The level allocates 20MB, then the character allocates 30MB, then the level allocates 20MB and the character allocates the final 30MB.
Level data (red) allocations interleaved with character allocations (green).
Now let’s say that the player runs to a new section, so the old level data memory is freed. The new level data only needs to make a single 30MB allocation. We do have 40MB memory free, but it isn’t in one chunk! We only have two blocks of 20MB. So even though the new level data is smaller, we can’t allocate space for it. This is memory fragmentation, and it’s a big problem in memory constrained environments.
Level data freed, leaving only character allocations. No room for a 30MB (3 block) allocation for new level data, despite having 40MB free!
So, James told me what they did in this type of situation was to have a chunk of memory like a normal stack allocator, but the level data had a tos which grew upwards from 0, and the character data had a tos which grew downward from the end of the memory. You knew you were out of memory when they crossed over each other and the level tos was greater than the character tos.
Let’s see how that works:
Level data (red) allocations and character allocations (green).Level data freed, leaving only character allocations.Level data is able to allocate the 30MB it needs by keeping a separate stack allocator in the same memory block. No memory fragmentation.
This made it so when the level data needed to change, it could reset the level tos back to 0, and reallocate the memory it needed, without any fragmentation whatsoever. Similarly, when the character freed its memory, it would reset its tos back to the end of memory, and could then reallocate the memory it needed, also without any fragmentation.
Once again, these allocators work fine in multithreaded environments, even when each thread might allocate from either side. Atomic add to the tos indices is all you need.
You might ask “why not have two stack allocators instead of a double headed one?” The main benefit is when you are memory constrained and know that the size of one stack allocator is enough to serve two systems, but the proportion of memory that goes to one side vs the other is flexible. In a game situation like described above, that means some levels could use more memory, but in those situations, the character would need to have reduced memory usage. A bit of a contrived example but hopefully you get what I mean.
Storing Variable Sized Objects In A Finite Region
There is a variation of this when you are trying to store a number of variable sized objects in a fixed amount of memory, but you want random access by index. An example may be that you want to send network packets of a specific size for efficiency reason, and you want to that memory to encode a variable number of variable sized network commands in it. You want to be able to easily iterate through the messages, but you want to support them having variable sizes too.
What you do is have a double headed stack allocator where one stack is for the dynamic allocations, and the other stack is for an array of integers that are an offset in the memory to the dynamic allocations.
Let me show you what I mean with an example. Starting with an empty double headed stack allocator:
You want to allocate 24 bytes. Stack 0 has a tos of 0, so that is where you write your 24 byte object. You add 24 to stack 0’s tos and it is now 24, where the next free region of memory is. You also allocate an integer from stack 1 and write 0 there, as the offset for where this first item lives.
Next you want to allocate 14 bytes. Stack 0 has a tos of 24, so that is where you write your 12 byte object. You add 12 to stack 0’s tos and it is now 38. You also allocate an integer from stack 1 and write 24 there, as the offset for where this second item lives.
and so on…
you also have to somehow keep track of how many objects there are. You could have a separate integer keeping count of how many offsets there are in the offset table, or maybe you could have a sentinel value in the offset table to indicate where the end of the offsets are. Perhaps ~0 (all 1s in binary) could be the sentinel value.
Just like the other stack allocators we talked about, this one can also work in a multi threaded environment. You might be tempted to make the two updates transactional – like with a compare and swap loop – but it isn’t needed.
Lastly, this configuration allows you to remove items, or move them around in memory, which is another way of reducing fragmentation – you just need to update the offset table to match reality when you do so.
