Handles are the better pointers

28-Nov-2018: I’ve added a small update at the end on how to prevent ‘handle collisions’ with a per-slot generation counter Original Post: …wherein I talk a bit about how I’m doing dynamic memory management in C and C++ these days which basically replaces raw- and smart-pointers with ‘index-handles’. In my last blog post I was mentioning pointer- and allocation-free programming, but was skipping over the details. This is what the following blog post is about. This is all based on the (sometimes painful) experience of wrestling for 15+ years with fairly big C++ code bases (0.5 to around 1 mloc) where memory is often managed through smart pointers. The worst case being tens- to hundreds-of-thousands of small C++ objects, each in its own heap allocation, pointing to each other through smart pointers. While such code is quite robust in terms of memory corruption (segfaults and corruption rarely happens, since most attempts are caught by asserts when dereferencing smart pointers), this type of ‘object spiderweb code’ is also dog-slow without obvious starting points for optimization, since the entire code is full of cache misses. Other typical problems are memory fragmentation and ‘fake memory leaks’ because a forgotten smart pointer prevents freeing the underlying memory (I call them ‘fake leaks’ because this type of leaks cannot be caught by memory debugging tools). Nothing presented here is particularly new or clever, it’s just a collection of a few simple ideas which together work fairly well in bigger code bases to prevent (or at least detect early) a number of common memory-related problems in C and C++, and may even be useful in higher-level garbage-collected languages to reduce pressure on the garbage collector. However, the underlying design philosophy doesn’t fit very well into a classical OOP world where applications are built from small autonomous objects interacting with each other. That’s why it’s also quite tricky to implement those ideas in a big existing OOP code base, where object creation and destruction happens ‘decentralized’ all over the code. The approach described here works very well though with a data-oriented architecture, where central systems work on arrays of data items packed tightly in memory. Most of the following blog post is written from a game developer’s perspective, but should also apply to other areas where a program needs to juggle a few hundred to a few million objects (or generally ‘data items’) in memory, and where such items are created and destroyed frequently. The gist is: move all memory management into centralized systems (like rendering, physics, animation, …), with the systems being the sole owner of their memory allocations group items of the same type into arrays, and treat the array base pointer as system-private when creating an item, only return an ‘index-handle’ to the outside world, not a pointer to the item in the index-handles, only use as many bits as needed for the array index, and use the remaining bits for additional memory safety checks only convert a handle to a pointer when absolutely needed, and don’t store the pointer anywhere I’ll explain each of those points in detail below. But the idea is basically that common ‘user-level’ code doesn’t directly call memory allocation functions (like malloc, new or make_shared/make_unique), and reduces the use of pointers to an absolute minimum (only as short-lived references when direct memory access to an item is absolutely needed). Most importantly, pointers are never the ‘owner’ of an item’s underlying memory. Instead, direct memory manipulation happens as much as possible inside a few centralized systems where memory-related problems are easier to debug and optimize. Move memory management into central systems In this blog post, a ‘system’ is a (usually fairly big) part of a code base which takes care of a number of related tasks, like ‘rendering’, ‘physics’, ‘AI’, ‘character animation’ and so on. Such a system is separated from other systems and ‘user-code’ through a clearly defined function API, and the work that happens on the system’s data is performed in tight central loops instead of being spread out all over the code base. Systems often work on items created and destroyed under control of user code (but note that creation and destruction of items is different from allocating and freeing the memory used by those items!). For instance a rendering system might deal with vertex buffers, textures, shaders and pipeline state objects. A physics system works with rigid bodies, joints and collision primitives, and an animation system works with animation keys and curves. It makes sense to move the memory management for such items into the systems themselves, because a general memory allocator doesn’t have the system-specific ‘domain knowledge’ about how data items are processed and the relationships between data items. This allows the system to optimize memory allocations, perform additional validation checks when creating and destroying items, and arrange items in memory for making best use of the CPU’s data caches. A good example for this ‘system domain knowledge’ is the destruction of rendering resource objects with modern 3D APIs: a resource object can not simply be destroyed immediately when the user code says so because the resource might still be referenced in a command list waiting to be consumed by the GPU. Instead the rendering system would only mark the resource object for destruction when the user code requests its destruction, but the actual destruction happens at a later time when the GPU no longer uses the resource. Group items of the same type into arrays Once all memory management has moved into systems, the system can optimize memory allocations and memory layout with its additional knowledge about how items are used. One obvious optimization is to reduce the number of general memory allocations by grouping items of the same type into arrays, and allocate those arrays at system startup. Instead of performing a memory allocation each time a new item is created, the system keeps track of free array slots, and picks the next free slot. When the user code no longer needs the item, the system simply marks the slot as free again instead of performing a deallocation (not different from a typical pool allocator). This pool allocation is most likely a little bit faster than performing a memory allocation per item, but this is not even the main reason for keeping items in arrays (modern general allocators are quite fast too for small allocations). A few additional advantages are: items are guaranteed to be packed tightly in memory, general allocators sometimes need to keep some housekeeping data next to the actual item memory it’s easier to keep ‘hot items’ in continuous memory ranges, so that the CPU can make better use of its data caches it’s also possible to split the data of a single item into several subitems in different arrays for even tighter packing and better data cache usage (AoS vs SoA and everything inbetween), and all those data layout details remain private to the system and are trivial to change without affecting ‘outside code’ as long as the system doesn’t need to reallocate arrays, it is guaranteed that there will be no memory fragmentation (although this is less of an issue in a 64-bit address space) it’s easier to detect memory leaks early, and provide more useful error messages: when a new item is created a system can trivially check the current number of items against an expected upper bound (for instance a game might know that there should never be more than 1024 textures alive at a time, and since all textures are created through the rendering system, the system can print out a more useful warning message when this number is exceeded) Public index-handles instead of pointers Keeping system items in arrays instead of unique allocations has the advantage that an item can be identified through an array index instead of requiring a full pointer. This is very useful for memory safety. Instead of handing memory pointers to the outside world, the system can treat the array base pointers as ‘private knowledge’, and only hand out array indices to the public. Without the base pointer to compute an item’s memory location, the outside code can’t access the item’s memory, even with a lot of criminal energy. This has a number of further advantages: In many situations, code outside the system never even needs to directly access memory of an item, only the system does. In such an ‘ideal’ situation, user code never accesses memory through pointers, and can never cause memory corruption. Since only the system knows the array base pointers, it’s free to move or reallocate the item arrays at will without invalidating existing index handles. Array indices need fewer bits than full pointers, and a smaller data type can be picked for them, which in turn allows tighter packing of data structures and better data cache usage (this has the caveat that additional handle bits can be used to increase memory safety, more about this below) If user code needs to access the memory of an item directly it needs to obtain a pointer through a ‘lookup function’ which takes a handle as input and returns a pointer. As soon as such a lookup function exists, the fairly watertight memory safety scenario outlined above is no longer guaranteed, and the user code should adhere to a few rules: pointers should never be stored anywhere, since the next time the pointer is used it may no longer point to the same item, or even to valid memory a pointer should only be used in a simple code block, and not ‘across’ function calls Every time a handle is converted into a pointer, the system can guarantee that the returned pointer still points to the same item that the handle was originally created for (more on this below), but this guarantee ‘decays’ over time since the item under the pointer may have been destroyed, or the underlying