Mastering Vector Internals for Game Development

GitHub Repository: https://github.com/alessandrobelli/MyVectorCpp

You can find a playground for this article at the end of it.

I've always been fascinated with games, especially on how data and function were working together to craft those actions and bits that, when taped together, form a game.

• How is an inventory optimized internally?
• How is a bullet spawned, travel in space, hit something and de-spawn? When and where calculations about physics take places?
• How we store abilities and skill trees?

And many more. That's why I'm now going deeper into how the C++ Standard Template Library works and try to replicate, and if possible, (understand how to) improve it.

My background in research software and open-source development taught me to question assumptions. When everyone said 'just use std::vector,' my instinct was to understand WHY it works and WHETHER I could do better for specific game scenarios.

std::vector is already a highly optimized and generally robust container for C++. Its benefits include automatic memory management, guaranteed contiguous element storage, adherence to RAII principles for resource safety, and seamless integration with STL algorithms.

We might argue that in high-performance, resource-constrained environment a need for custom vector implementation can arise, especially if there's a study on what kind of data type you need to work on in your vector.

Exception-Safe Construction in a Custom Vector

When a particle system spawns 10,000 bullets in a single frame and one constructor throws an exception, what happens to the 7,432 bullets that were successfully created before the failure?

Raw Memory vs. Object Construction

At the heart of safe dynamic array management in C++ lies the separation of memory allocation from object construction. This separation is fundamental to handling exceptions gracefully, especially when creating multiple objects.

1. Allocating Raw Memory: ::operator new[]

In the design of this Vector class as shown in Vector.hpp, the default constructor (Vector()) makes the choice to prepare an initial, usable space immediately upon creation. To achieve this, it acquires a chunk of uninitialized memory sized for a predefined DEFAULT_VECTOR_CAPACITY. The Vector.hpp implementation uses the global ::operator new[] for this raw memory allocation, as seen in its default constructor.

elements = static_cast<T *>(::operator new[](capacity * sizeof(T)));

2. Constructing Objects: Placement new

Once raw memory is available, objects must be constructed within it. This is where placement new comes into play. Placement new allows you to construct an object at a specific, pre-allocated memory address.

new (target_buffer + i) T(value_source);

Here, new (target_buffer + i) tells the compiler to call the constructor of T at the address target_buffer + i. It does not perform another memory allocation.

This two-step process (allocate then construct) provides fine-grained control, which is essential for:

• Efficiency: Objects are only constructed when and where needed.
• Exception Safety: If constructing an array of N objects and the kth object's constructor throws an exception, we need a mechanism to ensure the k−1 successfully constructed objects are properly destroyed. If we used a single new T[N] expression and an exception occurred, the language handles cleanup for array new, but for a custom container, manual management through placement new and explicit destructor calls gives explicit control and understanding.

3. The Helper Functions Pattern: Encapsulating Construction Logic

To manage the construction of multiple elements in an exception-safe manner, Vector.hpp employs private helper functions. These functions are responsible for the construction loop and immediate cleanup if an exception occurs during that loop.

_construct_fill_elements(T* target_buffer, int num_to_construct, const T& value_source) This function is designed to fill a given target_buffer with num_to_construct objects, each initialized as a copy of value_source.

• Mechanism: It iterates num_to_construct times, using placement new to construct each T object.
• Exception Handling: A try-catch block encloses the construction loop. A counter, successfully_constructed_count, tracks how many objects have been created successfully within this specific call.

// Inside _construct_fill_elements
int successfully_constructed_count = 0;
try
{
  for (int i = 0; i < num_to_construct; ++i)
  {
    new (target_buffer + i) T(value_source); // Placement new
    successfully_constructed_count++;
  }
}
catch (...)
{
  for (int i = 0; i < successfully_constructed_count; ++i)
  {
    (target_buffer + i)->~T(); // Explicitly call destructor
  }
  throw; // Re-throw to signal failure
}

If any T(value_source) constructor call throws, the catch block is entered. It then iterates through the successfully_constructed_count objects that this invocation managed to create and calls their destructors explicitly (->~T()). This is crucial because these objects exist in raw memory that the Vector class itself will manage (or deallocate if construction fails). After cleanup, the exception is re-thrown to inform the caller (e.g., a Vector constructor) that the operation failed.

These helper functions ensure that they themselves do not leak resources (i.e., constructed T objects without corresponding destructors called) if an exception occurs during their execution. They achieve a strong guarantee locally: either all requested objects are constructed, or any objects they did manage to construct are destroyed before failure is signaled.

These helper functions, by managing their own scope of construction and cleanup, provide a crucial foundation. However, for the Vector class itself to achieve strong exception safety during its construction, its constructors (such as the fill constructor Vector(int n, const T& value) and the copy constructor Vector(const Vector& rhs)) must take further responsibility. If a helper function signals an unrecoverable error during element construction (by re-throwing an exception), the calling Vector constructor catches this exception. Crucially, the constructor then deallocates any raw memory it had previously reserved (e.g., using ::operator delete[] on its elements buffer) and resets its internal state (size, capacity, pointers) to represent a safe, typically empty, and valid state before allowing the exception to propagate further. This two-tiered approach—local cleanup by helpers, followed by global resource cleanup by the main constructors—ensures that the Vector is either fully and correctly initialized or, if an error occurs, no resources are leaked, and the object remains in a destructible and consistent (often empty) state, thereby upholding the strong exception safety guarantee.

Move Fast, Don't Break Things: Implementing Move Semantics for Game Performance

In modern game engines, copying a 50MB texture object or a complex game entity simply because an underlying array needs to resize is often an unacceptable performance hit. Such operations can lead to noticeable stutters or frame drops. C++11's introduction of move semantics provided a powerful way to transform these expensive copy operations into cheap resource transfers. Implementing move semantics correctly in a custom container, however, requires a clear understanding of resource ownership and object validity.

The Essence of Moving: Transferring Ownership

At its core, move semantics allow an object to transfer ownership of its underlying resources (like dynamically allocated memory) to another object. Instead of making a deep copy of the data, the "moved-from" object is left in a valid but typically empty or undefined state, while the "moved-to" object now manages the resources. This is particularly beneficial for objects that are expensive to copy but cheap to move—like a vector managing a large block of memory.

Move Constructor: Efficient Resource Pilfering

The move constructor is designed to efficiently create a new Vector by "stealing" the resources from a temporary (rvalue) Vector object.

Vector(Vector &&other) noexcept
    : size(other.size),
      capacity(other.capacity),
      elements(other.elements)
{
  // Leave 'other' in a valid, destructible, but empty state
  other.elements = nullptr;
  other.size = 0;
  other.capacity = 0;
}

Key Mechanics:

1. Resource Transfer: The new Vector's members (size, capacity, elements) are initialized directly from other's members. This is a shallow copy of pointers and integral types, which is very fast.
2. Nullifying the Source: Crucially, other.elements is set to nullptr, and other.size and other.capacity are set to 0. This leaves the moved-from other object in a well-defined, destructible state. Its destructor can now run safely without trying to deallocate memory that has been taken over by the new Vector.
3. noexcept Specification: The noexcept keyword is a critical part of the move constructor's signature. It guarantees that the move constructor will not throw any exceptions. This is important because standard library containers and algorithms (like std::vector when it reallocates, or std::move_if_noexcept) can leverage this guarantee to use move operations in situations where they would otherwise have to fall back to slower copy operations to maintain exception safety guarantees.

Move Assignment Operator: Taking Over Resources

Similar to the move constructor, the move assignment operator reassigns an existing Vector by taking ownership of another Vector's resources, ensuring proper cleanup of its own old resources.

Vector &operator=(Vector &&rhs) noexcept
{
  if (this != &rhs) // Prevent self-assignment
  {
    _destroy_range(elements, size); // Call destructors for existing elements in 'this'
    ::operator delete[](elements);  // Deallocate 'this' vector's raw memory

    // Now proceed to take rhs's resources
    elements = rhs.elements;
    size = rhs.size;
    capacity = rhs.capacity;

    rhs.elements = nullptr;
    rhs.size = 0;
    rhs.capacity = 0;
  }
  return *this;
}

• Cleanup Existing Resources: Before taking over rhs's resources, the current Vector (this) must release its own. This involves destructing all currently held elements (using _destroy_range) and then deallocating its memory buffer (::operator delete[]).
• Resource Transfer and Nullification: The resources from rhs are then pilfered, and rhs is nullified, just like in the move constructor.

Impact on Game Performance: Why Moving Matters

In game development, managing collections of potentially large or complex objects (e.g., character entities, scene nodes, particle data, UI elements with graphical resources) is common. Move semantics offer significant performance advantages:

• Efficient Resizing and Reallocation: When a Vector needs to grow its capacity (e.g., during PushBack or an explicit Reserve call), it often needs to allocate a new, larger memory block and transfer existing elements. If these elements can be moved instead of copied, this process becomes vastly faster. The Vector.hpp implementation uses _construct_move_from_range internally for operations like Reserve and shrink_to_fit, which leverages move constructors if available.
• Fast PushBack of Rvalues: Adding temporary objects or objects explicitly marked with std::move to a vector (e.g., myVector.PushBack(GameObjectFactory::CreateLargeObject())) can directly construct the new element by moving, avoiding a potentially expensive copy. Your Vector.hpp provides PushBack(T&& object) for this purpose.
• Returning Vectors from Functions: Returning a Vector by value from a function can be very efficient due to guaranteed copy elision or implicit moves in modern C++, avoiding any overhead if the Vector itself is movable.

Targeted Optimizations: Efficient Deletion and Type-Aware Destruction

Fine-tuning data structures for specific game-related tasks can unlock crucial performance gains. Vector.hpp incorporates such targeted improvements, particularly evident in its approach to element deletion in scenarios where order is secondary, and in its compile-time handling of object destruction.

UnorderedErase: The O(1) Deletion Advantage

In many game systems, such as managing active particles, projectiles, or other entities where the sequence isn't critical, maintaining element order upon deletion is unnecessary overhead. A standard Erase operation that preserves order typically costs O(N) time due to the need to shift subsequent elements. For frequently changing collections, this can become a performance bottleneck.

void UnorderedErase(int index)
{
  elements[index] = std::move(elements[size - 1]); // Move last element into the gap
  PopBack();                                      // Remove the (now duplicate) last element
}

This method cleverly bypasses the costly shift. It works by:

1. Taking the last element in the vector.
2. Moving it into the position of the element targeted for removal (elements[index]). This overwrites the element to be deleted.
3. Calling PopBack() to then remove this last element (which is now effectively a duplicate or in an empty state if it was moved from).

The core of this operation—the move and the preparation for pop—is O(1), or constant time. The PopBack() operation itself is also typically O(1) (amortized, not considering potential destructor costs for the element, which we'll touch on next). This makes UnorderedErase significantly faster for scenarios where element order can be sacrificed for speed.

Type-Aware Destruction with std::is_trivially_destructible_v

Not all data types require the same cleanup. Simple Plain Old Data (POD) types or structs with trivial destructors (e.g., a 2D point with just float members) don't need an explicit destructor call; their memory can simply be reclaimed. Conversely, complex types that manage resources (like file handles, heap allocations, or other RAII objects) have non-trivial destructors that must be called to prevent resource leaks.

Vector.hpp handles this by using C++ type traits to perform conditional destruction. This is evident in PopBack() and also utilized by the internal _destroy_range helper, which is called by Clear(), the destructor, and reallocation logic.

void PopBack()
{
  if (size > 0)
  {
#if __cplusplus >= 201703L // C++17 and later
    if constexpr (!std::is_trivially_destructible_v<T>)
      elements[size - 1].~T();
#else // C++14 
    if (!std::is_trivially_destructible<T>::value)
      elements[size - 1].~T();
#endif
    size--;
  }
}

Here, std::is_trivially_destructible_v<T> (or its C++14 ::value counterpart) is a compile-time check.

• If T has a non-trivial destructor, the if condition is true, and the destructor elements[size - 1].~T() is explicitly invoked.
• If T has a trivial destructor, the condition is false. With if constexpr (in C++17 and later), the entire if block (including the destructor call) is discarded at compile time, resulting in no runtime overhead. For C++14, a standard if would still evaluate the condition at runtime, but a good compiler might optimize away the check if the result is known.

This is a powerful micro-optimization that ensures correctness by always calling necessary destructors for complex types, while simultaneously providing efficiency by avoiding unnecessary operations for simpler types.

This pairing of rapid, order-agnostic removal via UnorderedErase with the meticulous, type-sensitive cleanup seen in conditional destruction showcases a comprehensive strategy within Vector.hpp to optimize performance from different angles for game-specific demands.

This journey into crafting a custom Vector has been a good exercise in C++ syntax, as well as a practical exploration that deeply reinforces the connection between low-level code implementation and high-level game development principles.

It was a very well needed re-exploration of concepts that are frequently "given", but less frequently implemented.

See the Pen Vector Memory optimization by Alessandro Belli (@alessandrobelli) on CodePen.