Mastering Vector Internals for Game Development
GitHub Repository: https://github.com/alessandrobelli/MyVectorCpp
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.
- 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)));
- 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 singlenew 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.
- 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 placementnew
to construct eachT
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:
- Resource Transfer: The new
Vector
's members (size
,capacity
,elements
) are initialized directly fromother
's members. This is a shallow copy of pointers and integral types, which is very fast. - Nullifying the Source: Crucially,
other.elements
is set tonullptr
, andother.size
andother.capacity
are set to0
. This leaves the moved-fromother
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 newVector
. noexcept
Specification: Thenoexcept
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 (likestd::vector
when it reallocates, orstd::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 currentVector
(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, andrhs
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., duringPushBack
or an explicitReserve
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. TheVector.hpp
implementation uses_construct_move_from_range
internally for operations likeReserve
andshrink_to_fit
, which leverages move constructors if available. - Fast
PushBack
of Rvalues: Adding temporary objects or objects explicitly marked withstd::move
to a vector (e.g.,myVector.PushBack(GameObjectFactory::CreateLargeObject())
) can directly construct the new element by moving, avoiding a potentially expensive copy. YourVector.hpp
providesPushBack(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 theVector
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:
- Taking the last element in the vector.
- Moving it into the position of the element targeted for removal (
elements[index]
). This overwrites the element to be deleted. - 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, theif
condition is true, and the destructorelements[size - 1].~T()
is explicitly invoked. - If
T
has a trivial destructor, the condition is false. Withif constexpr
(in C++17 and later), the entireif
block (including the destructor call) is discarded at compile time, resulting in no runtime overhead. For C++14, a standardif
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.