Custom Data Structures in the Rookery

Intro

I’ve made some choices while implementing data structures in the Rookery. Here, I’m not going to go into the specifics about how my hash table or any other data structure operates, but I’ll talk about some implementation decisions that affect all data structures in the Rookery (strings, arrays, sets, maps, and so on).

Why not the STL?

The STL is the product of a monumental amount of effort. It has its good aspects (correctness, interoperability across libraries). It also has a number of drawbacks. I think many gamedevs would probably cite performance as the main reason not to use the STL, but while STL performance does leave a lot on the table (in part due to ABI stability constraints or to honor specific API contracts), I actually think there are other equally pressing issues that make them unsuitable for most real-time game engines.

STL functionality gap

A container (e.g. std::unordered_map) typically supports querying, insertion, deletion, and iteration – ultimately honoring whatever properties are stipulated by the container type. This is, understandably, the bare minimum, and for most engines, the bare minimum is pretty far from sufficient.

First, all primary engine data structures need to be serializable. While you could tack serialization functionality on top of std::string, std::vector and so on, there are additional improvements you can make if you stipulate the serializable requirement at the design phase, as we will see.

Next, data structures in a game engine need to handle proper memory accounting. Memory leaks are among the trickiest issues to diagnose, in part because they may occur gradually over many frames. Good engine data structures have some amount of instrumentation in place so that if, say, some map resized to occupy 100s of MBs, you’d be able to identify which subsystem was responsible. This memory accounting is typically built into the engine’s allocator (which I will write about in the future), but some cooperation between the allocator and the data structures can be useful.

Finally, there are a number of what I consider to be “API defects” in the STL, that either aren’t important enough to be addressed in the standard, or can’t be addressed due to ABI compatibility or some other reason. Without going into any specific issue, here are some example defects:

• There isn’t a way to accelerate map and set operations when the hash is already known.
• Associative containers don’t support “heterogeneous lookup” without changing the type signature to possess a custom transparent hasher and void comparator (without heterogeneous lookup, checking the existence of a char const* string literal in a std::unordered_set<std::string> would require an initial conversion from char const* to std::string as an example).
• Similarly, changing the allocator of a container also requires a type signature change unless you’re willing to commit to using polymorphic allocators everywhere.
• STL implementations may allocate memory in the default constructor (which may be unacceptable if the engine wants a reasonable guarantee that no allocations occur at static initialization time).
• The std::deque interface doesn’t support setting the block size.
• The std::string interface lacks an append_sprintf or append_format interface.
• While not a defect per se, the STL was authored assuming that exceptions are enabled, and most game engines are built expressly without C++ exceptions enabled for a number of reasons I won’t delve into here.
• STL container queries for sizes and capacities returned unsigned integers instead of signed integers (see note below).

I could continue, but the point here isn’t that any of these specific interfaces are dealbreakers per se. The point is that if you own these data structures, you have the freedom to just change the API as needed, depending on the needs of your project.

STL container code size and compilation time

Simply put, the STL makes pretty much no attempt to optimize for code size or compilation time (often correlated metrics). In pretty much every STL implementation, the majority of the functionality lives across a number of template functions, all of which is fully instantiated in each referencing translation unit.

For example, invoking std::unordered_set::contains on a simple std::unordered_set will emit on the order of 60 instructions or so with optimizations on (and more like 400-500 instructions with optimizations off). Amplified over an entire codebase with thousands of compilands, especially in debug builds, the effect is quite pronounced! Performance aside, amplified code size will also increase your object file sizes which result in slower link times, increase your PDB sizes, which then tax your symbol servers more and impact debugger startup time, etc. etc. Code size is one of those things that has a real impact on both performance and productivity, but I don’t think is properly considered because it’s difficult to measure what proportion of a studio’s issues are attributable to poor decisions in this area.

Poor STL debug performance

Related to the point above, yet another aspect that was not much of an STL priority is performance in unoptimized builds. For the record, I don’t put this on STL maintainers much at all. Debug performance is one of those things that seem to be uniquely a game dev concern, and commercial engines like Unreal commonly operate in a “DebugGame” configuration where the engine itself is compiled with optimization enabled, but the game code is compiled with optimizations off.

Actually improving code performance in debug builds requires conscious effort that would be wasted for most users. After all, debug builds are generally used for debugging. Improving over the STL in this area is quite achievable in a few ways that will be touched on later.

Lack of STL determinism and platform independence

Given the same sequence of inputs to a hash table (on one thread), having traversal order be identical on an Xbox, Playstation, Switch, and PC can be quite important in various game dev contexts. Similarly, when serializing data, it can be quite useful for the serialization outcome to not depend on, say, specific STL library version or compiler toolchain. Hashes computed from the same data structures should also be bit-identical across various platforms. This determinism is quite meaningful both in ensuring that different platforms have similar play experiences, and also in netcode contexts where determinism is needed to avoid potential desynchronization.

As an aside, it is extremely valuable to able to step into the code of any container on any platform and have it function the same. Knowing the underlying memory representation of, say, a string or set can also be really useful in diagnosing tricky bugs. Figuring this out per-platform (and remembering it!) is not a fun exercise. On the other hand, STL debugging ergonomics don’t really exist. The STL is, true-to-its-name, extremely template-heavy. STL symbols necessarily leverage reserved name conventions with leading underscores, which results in a suboptimal debugging experience.

Rookery containers

Let’s shift gears now and talk about the data structures in the Rookery and how some of these shortcomings are addressed!

Addressing code size and debug performance with polymorphism

All templated containers (e.g. Array, Set, Map) are very thin typesafe wrappers that inherit an underlying storage class (e.g. ArrayStorage, and SetStorage in the case of both Set and Map). The storage classes accept a TraitSummary object which is generated from the type T like so:

struct TraitSummary
{
  template <typename T>
  static constexpr TraitSummary create()
  {
    TraitSummary summary;
    summary.relocatable_             = is_relocatable_v<T>;
    summary.trivially_comparable_    = is_trivially_comparable_v<T>;
    summary.trivially_constructible_ = std::is_trivially_constructible_v<T>;
    summary.trivially_destructible_  = std::is_trivially_destructible_v<T>;
    summary.trivially_copyable_      = std::is_trivially_copyable_v<T>;
    summary.copyable_                = std::is_copy_constructible_v<T>;
    summary.trivially_movable_ = std::is_trivially_move_constructible_v<T>;
    summary.movable_           = std::is_move_constructible_v<T>;

    return summary;
  }

  bool relocatable_             : 1;
  bool trivially_comparable_    : 1;
  bool trivially_constructible_ : 1;
  bool trivially_destructible_  : 1;
  bool trivially_copyable_      : 1;
  bool copyable_                : 1;
  bool trivially_movable_       : 1;
  bool movable_                 : 1;
};

In a single byte of information, we can encode much of the information a storage class needs to implement most of the data structure functionality for many types immediately. Along with this trait summary, we can also pass along the type size and alignment, all of which can be packed into 32 bits (some static asserts ensure that the type size fits in a signed 16-bit integer, which has not been a constraint I’ve run into yet).

struct TypeSummary
{
    i16 size_;
    i8 alignment_;
    TraitSummary traits_;
};

The TypeSummary lets us implement an array, set, or map for everything except types that have a non-trivial constructor, copy, or move operation. To handle such types, storage classes expose a virtual interface like the following:

// ArrayStorage virtual interface
virtual void construct_element(void* ptr) {}
virtual void destroy_element(void* ptr) {}
virtual void move_element(void* dst, void* src) {}
virtual void copy_element(void* dst, void* src) {}

The various parameters here correspond to type-erased addresses that refer to objects of the underlying type. For the Array specifically, the implementation of a couple of these virtuals looks like this:

template <typename T>
class Array final : public ArrayStorage
{
  // public interface...

private:

  void construct_element(void* ptr) final
  {
    if constexpr (!std::is_trivially_constructible_v<T>)
    {
      new (ptr) T;
    }
  }
  
  void destroy_element(void* ptr) final
  {
    if constexpr (!std::is_trivially_destructible_v<T>)
    {
      ((T*)ptr)->~T();
    }
  }
  
  // Similar implementation for the other virtuals
};

Within array storage, these virtual functions are only invoked when needed, depending on the bits set or unset in the trait summary. For example, in this implementation of ArrayStorage::pop_back, the virtual destroy_element method is called only needed:

void ArrayStorage::pop_back()
{
  RK_CHECK(
    count_ > 0,
    "Attempting to pop an element from an empty array");

  --count_;

  if (!type_summary_.traits_.trivially_destructible_)
  {
    destroy_element(data_.address() + count_ * type_summary_.size_);
  }
}

The expression passed to destroy_element is the address of the array element that is about to be removed from the container.

You can imagine using similar checks to invoke the other virtual members on an as-needed basis also.

Compared to the array, the SetStorage class which acts as a hash-table backing implementation for both Map and Set needs a couple additional virtual methods in its interface:

virtual Hash compute_hash(void const* key) const = 0;
virtual bool compare_keys(void const* a, void const* b) const = 0;

The compute_hash function is needed to compute the Hash of an element key, which may be the entire element in the case of a Set, but only part of the element in the case of a Map. The compare_keys function does an equality check, but only if the two keys are not trivially comparable.

So, what did we get for all this effort? Well first, over 95% of all the code for a given container lives in that container’s .cpp file. This gives my container the following advantages:

• My containers generate over an order of magnitude less code than their STL equivalents.
• Empirically, my code compiles much faster after completely ditching the STL, although I cannot say what fraction of the speedup is due to this choice vs many other compile-time optimizations I’ve made. The sheer reduction in code size is a good causative indicator however.
• Because my data structures are contained in just a few .cpp files, I can choose to selectively optimize these compilands at build time to enjoy comfortably realtime performance across the majority of the codebase. Note that I don’t even bother doing this most of the time. Because my containers don’t contain as much call overhead as the STL in debug builds, they perform better when unoptimized also.

Aren’t virtuals slow?

Invariably, when the topic of virtual interfaces and polymorphism comes up, this point gets brought up. By way of a brief apologia, here’s why the use of polymorphism in this context has a positive impact on perf:

• As mentioned, there is a dramatic reduction in code size with this approach. Polymorphism here is used as a form of code compression, which means a much hotter I$.
• For many data structures, the virtual methods aren’t invoked at all, since the trait summary is used to accelerate fast paths for types that possess trivial constructor and comparison operations.
• For data structures containing elements that have non-trivial traits, the cost of a single indirection is paid once for a mutation of the full collection, at which point the actual virtual implementation itself will reside in I$. This indirection is generally negligible relative to the container operation itself.
• Virtual invocations using this technique are all operating on the same vtable for a container of a given type. This means that unlike other usages of virtual dispatch, we aren’t invoking a different virtual function implementation each time we need to operate on an element. Uniform virtual dispatch is far more performant, and the context where virtual dispatch gets a bad rap is when operating on collections of heterogeneous derived types.

Is it possible to implement a data structure without virtuals that is locally more performant? Sure. The best way to game a microbenchmark will always be to inline everything so the optimizer can “see” as much as possible. However, I put this type of thing firmly in the camp of “selfish optimizations” that might improve one thing at the expense of global system performance. In my case, I think the tradeoff in having much more compact code as a global accelerant on top of having much faster iteration times is well worth it.

Memory layout

One real cost with this polymorphic approach is that I pay an extra 8-bytes per container instance in order to store the vtable pointer, in addition to 4-bytes per container instance to store the type summary.

It turns out that my Array is the same size as a typical std::vector, while my Set and Map occupy 32 bytes per instance compared to a typical std::unordered_set or std::unordered_map, each of which occupies 64 bytes per instance.

There are a few tricks I’m relying on to keep my data structures lean:

• First, when I store element counts, I just opt for signed 4-byte integers. I can get away with this, because I happen to know I’ll never saturate a container with this many elements, and leverage different more specialized structures for “bulk” data (meshes and textures and so on). A 4-byte element count packs neatly adjacent to the type summary described earlier.
• Second, I never store capacity on the instance itself. The Rookery leverages a custom allocator that prepends all allocations with an allocation header. This header contains allocation size information. This is nice because if a data structure hasn’t yet made an allocation, the capacity is implicitly 0 and there’s no need to store the capacity separately.
• Third, the allocation header also embeds information about the allocator used to actually make the allocation. As with the capacity, this means that if a container hasn’t yet made an allocation, it also doesn’t pay anything to store an allocator. I’ll elaborate on this more in the next section.

A counterpoint might be “aren’t you just shifting the storage of the capacity and allocator elsewhere?” Well, yes, but this still works out well because that is information I want to store for all allocations anyways, and as mentioned, I certainly don’t want to store that information before an allocation is made.

Moving away from typed allocator interfaces

Most STL containers have a signature like the following:

template <
  typename T,
  typename Allocator = std::allocator<T>>
class vector;

// Or the polymorphic variant
namespace pmr {
  template <typename T>
  using vector = std::vector<T, polymorphic_allocator<T>>;
}

IMO, this interface is unfortunate for a few reasons:

• First, the non-polymorphic version is particularly unergonomic because the choice of allocator is annealed into the type directly. Containers leveraging different allocators are type-incompatible, so this approach inhibits code reuse and is generally unpleasant to work with.
• The polymorphic version is better, but is still incompatible with the container leveraging the default allocator, so the only way to bypass this incompatibility is to pass the default polymorphic memory resource everywhere or wrap containers using the default allocator somehow.

From a type-modeling perspective, I don’t think the allocator should be part of the container’s type signature at all. Ultimately, the way the container behaves is mostly identical except for how it allocates and frees memory.

The way I manage this is that memory allocations in the Rookery don’t return void* at all (moving away from a long tradition of malloc’s function signature). Instead, memory allocations are encapsulated in an Allocation struct that encodes metadata about the allocator that should be used in the low bits of the allocation address. The memory referred to by an Allocation is always preceded with an AllocationHeader that contains information about the allocation capacity and the allocator used to perform the allocation.

An important detail is how a container understands what allocator to use for the first allocation. After all, if the allocation header embeds allocator information, won’t all allocations just leverage the default heap? The way this works in the Rookery is that specifying a custom allocator is possible with the reserve method for each container. This method accepts an optional allocator as an additional argument. It does mean that upfront reservation is needed to specify a custom allocator, but this isn’t a “real” issue, since custom allocators are typically always used for a fixed size arena, bump allocator, or some other memory segment where suballocations are nearly free. One big benefit of this interface is that I can freely change where data is allocated at will, which requires a bit more finessing if the allocator is embedded directly in the container.

Mappable data structures

This is one bit I’m particularly proud of, and haven’t seen in any engine I’ve worked with. In the Rookery, deserializing data structures from desk or network has zero cost (modulo costs of decompression and page faults).

Reading a type from disk looks like this:

// Ignore the details of how this struct is reflected for now.
struct MyReflectedStruct
{
  Array<int> x;
  Map<int, Set<float>> y;
};

File file;

// This will map the file in memory.
file.open(path_to_file, FileFlags::ReadOnly);

byte const* data = file.cdata();

// Size and magic number live in the first 16 bytes,
// useful for validation that is skipped here for brevity.
MyReflectedStruct const& s =
  *(MyReflectedStruct const*)(data + 16);

// At this point, s.x and s.y are all fully accessible,
// including all nested elements within each data structure.

This should seem somewhat… impossible. After all, arrays, maps, and sets generally refer to heap allocated elements, so simply casting the data pointer to a MyReflectedStruct pointer shouldn’t work.

And yet it does. Here’s how:

• First, the Allocation object embedded in each container reserves a single bit to indicate if the address stored is a relative address or not.
• Accessing the memory address of an Allocation is done by invoking The byte* Allocation::address() member function. This function checks if the relative_ bit is set, and if so, interprets the high bits not as an absolute address, but an offset to the address of the Allocation instance itself.
• During serialization, as data is written to a file or memory buffer, the allocations are serialized with the relative_ bit set and the offsets in the high bits, as the address() function would expect.
• Container destructors are no-ops if the relative_ bit is set, and they won’t attempt to free relatively addressed memory or invoke element destructors.

This mechanism should be familiar to anyone that has seen RIP-relative instruction encoding, which is how shared libaries are mostly handled on non-Windows platforms.

One neat thing about this mechanism is that it works for any Allocation. The Allocation object is used within Unique and Shared (my versions of std::unique_ptr and std::shared_ptr), so that means I can also serialize object graphs that contain references to heap-allocated objects.

But what about vtables?

Stare at this snippet again:

MyReflectedStruct const& s =
  *(MyReflectedStruct const*)(data + 16);

This should evoke some degree of fear deep within your being. After all, this is undefined behavior because at no point was the constructor MyReflectedStruct invoked. Earlier I had mentioned that all the data structures are actually polymorphic. How can the struct s possibly be accessed safely, given that we can’t serialize vtable addresses and interpret them in any meaningful way?

Well, the example mentioned works because the elements stored in all the nested data structures of MyReflectedStruct are trivial types. As such, any operation such as a map lookup don’t actually invoke the virtual interface at all. When serialized, the vtable entry is just left as an 8-byte zero value, but because no code is ever invoked that would access the vtable, nothing breaks.

Handling more complicated types

Restricting the serialization capabilities to only simple types is an option, but just for fun let’s try to be a bit more ambitious. What I’m about to describe is not something I’m actively endorsing, since it leverages fairly undefined behavior. For now though, let’s proceed with a thought experiment of how we might implement things if we wanted to serialize and deserialize polymorphic types as well.

Try to imagine directly mapping MyReflectedStruct again, but with a different data format this time.

struct DifferentStruct
{
  String x;
  float y;
    
  bool operator==(DifferentStruct const&) const
  {
    // Some custom comparison function
  }
  
  Hash hash() const
  {
    // Some custom hash function
  }
};

struct MyReflectedStruct
{
  Array<DifferentStruct> x;
  Map<int, Set<DifferentStruct>> y;
};

// File mapping code...

MyReflectedStruct const& s =
  *(MyReflectedStruct const*)(data + 16);

Now, the types stored in the Array and Set are decidedly non-trivial. However, the Array is actually still safe to access. This is because the struct s is an immutable reference, and none of the array querying methods actually rely on the virtual interface which is strictly needed for array mutation. For the same reason, element lookup and traversal in the map y is also safe.

The Set field is a different case however. Data here cannot be queried directly because the hash computation and element comparison operators are virtual. To circumvent this, we need one more post-processing step to occur after the memory has been mapped. Namely, we need to patch in vtable pointers directly. This is done by walking pregenerated tables of offsets produced by the reflection system, and filling in vtable entries with valid in-memory vtable addresses populated at engine startup.

This obviously only works if the vtable address locations are known for every object, which is actually quite simple provided that multiple inheritance and vtable hardening isn’t involved. The first mechanism is easy to control – my reflection system doesn’t support multiple inheritance at all. The second case is a primary limitation of this technique in a secure computing environment, but not something I’m concered with presently.

So to recap, in addition to mapping the data directly, we also need to walk the data in the payload according to a pregenerated scheme to patch vtable pointers strictly for the objects that need it (sets with non-trivial elements, or maps with non-trivial key-elements). In practice, this occurs so quickly that the time spent even for large payloads is negligible. This is still a full order of magnitude faster than the fastest serializer I’ve written, because there’s just so little work to do. The main cost here is that mapped memory needs copy-on-write behavior, and we have to pay for copying pages dirtied with the vtable patching process.

If you choose to do this, you might as make your mapped data structures mutable also. The way this can work is a scheme like the following:

• When mapping your files into memory, map them with the FILE_MAP_COPY access parameter (or equivalent on a different OS) so that the mapped pages have copy-on-write semantics.
• As mentioned, all data structures should have their vtable pointers patched.
• The first time a mutation happens, the data of an associated container is first copied elsewhere on the heap, and the address is turned into an absolute address instead of a relative one.

Other affordances

This post is getting a bit long, so I’m just going to consolidate a bunch of other departures from the STL here for future reference.

• All the STL deficiences mentioned earlier are addressed in the Rookery. The most important change here was to ensure that the data structures never allocate within any default constructors.
• Rookery data structures properly integrate with the ASAN interface. This way, reserved but unused slack memory within a container is always poisoned and will trigger an exception on access when ASAN is enabled.
• The implementation of the Set is a big departure from std::unordered_set in a few ways that translate to large efficiency wins. Beating std::unordered_set isn’t particularly noteworthy these days, but the Rookery set does well against other solutions as well. One thing I’ll mention is that while a common prevailing recommendation is to use Robin Hood hashing (pdf link) for probing in an open addressing hash table, I was actually not very overly impressed with this scheme. I may change my mind on this in the future, but in testing, Robin Hood hashing worked great in synthetic tests, but less well in real-world scenarios due to the amount of data motion occurring during backwards-shift and swapping operations.

Quick note on debugger visualization

Aside from improving over existing solutions like the STL, the basics need to work also. If you choose to embark on this endeavor yourself, you’ll invariably need to visualize your data structure elements in the debugger using Natvis.

When working with Natvis, have your .natvis file in some directory visible to the debugger as opposed to embedding it directly with the linker. Natvis hot-reloading does not work otherwise. In Visual Studio, you can also change a setting to log Natvis warnings and errors to the debugger’s output console (one of the many reasons the VS debugger is to be preferred over the debugger integrated in VSCode).

If you use a different debugger like LLDB, you can leverage LLDB’s Python API to format variables. Compared to Natvis, I found it is significantly more challenging to do “easy” things in lldb, but Python certainly has an edge when trying to do more complicated visualizations.

Frankly, even after getting it all working with Natvis and LLDB, I found myself fairly dissatisfied with both options and have some future plans to write my own debugger… but that’s a story for another day.

Outro

While the Rookery engine is only a few months old at the time of this writing, investing in a set of custom data structures has already paid off in more ways than one. It’s quite liberating to be able to just modify code within a data structure you own to add some conditional programmatic breakpoint when debugging a tough problem, for example. The tight integration with the reflection system, serialization, and other systems in the engine is, without a doubt, the best thing about “rolling your own” data structures if you choose to build an engine.

Assuming ownership over your data structures isn’t without its drawbacks of course. Tethered to the Siren’s song of potential benefits is the undeniable burden of ensuring the implementations are sound. My suggestion? If you’re even remotely interested in this kind of thing, just do it with reckless abandon. Contrary to what anyone says, these data structures are anything but “solved problems,” and there is a lot of room for improvements over existing solutions in several axes. Hopefully, this post has shed some light on just some of the interesting opportunities available for creative solutions!

Discuss this post on Patreon.