Game++. Cooking vectors (part 1)

Dynamic and static arrays serve as the primary tools for working with collections of objects in game development. Maps, sets, and other data structures are often built on top of vectors due to their simplicity and convenience, though this comes at a performance cost.

Core Concepts

std::vector and its analogs store everything from game entities to textures, network packets, and scheduler tasks. It's a container with contiguous memory that can store an arbitrary number of elements. When capacity increases, a new larger memory block is allocated and old elements are copied over — which becomes non-trivial with non-copyable classes.

Allocations

The C++ standard doesn't mandate specific behavior for empty std::vector memory allocation. Different implementations vary:

• Nintendo's implementation "always allocates space for 4 elements upon declaration"
• Nintendo's platform has a dedicated allocator for small allocations (up to 128 bytes); beyond that, you need the regular slower allocator or a custom one
• When elements exceed capacity, the vector grows by a multiplicative factor (implementation-dependent)
• Resizing requires copying all elements to a new block — expensive with complex constructors/destructors
• Unused allocated memory is a trade-off between memory efficiency and performance (e.g., 100 elements might have capacity for 150–200)

Memory Layout

One-shot composition with contiguous memory arrays offers the best cache locality and performance. However, a std::vector of std::vector does NOT produce contiguous memory — it creates a two-level structure similar to std::deque, which "almost guarantees CPU cache misses."

Allocation Costs

• A system call for memory allocation typically takes 1–10 ns without collision
• With collision: ~40 ns
• If new/malloc() triggers a system call to grow the heap: up to 120 ns
• Sony introduced a preview requirement that framerate "must not drop below 60 FPS" — giving roughly 16 milliseconds per frame
• In game development, "dynamic memory allocation is generally prohibited during gameplay — 95% of the time, such code will be rejected during review"

std::array

std::array contains exactly N elements initialized at creation. It's a static C++ array extended with STL capabilities, with size as a compile-time constant. Drawbacks include manual size management and constructor calls for all elements.

std::vector vec = {} // 1, 2, 3, 4, 5

std::array vec = { 0 };
int vec_size = 0;

Benchmark: quick-bench.com

PS4 to Switch Porting Story

A porting issue arose where PS4 allowed a 2MB stack, but Switch couldn't exceed 480KB per thread. A function with ~20 if branches creating temporary objects worked fine on PS4 but blew the stack on Switch when a 21st branch was needed — just ~20KB more was enough to overflow. Replacing std::vector with std::array can cause "128KB disappears into thin air."

Static vector

Custom stack-allocated vector implementations emerged due to std::array inconveniences. If the size won't exceed N, a statically-allocated vector can replace a dynamic one. These appeared in game engines early on; frameworks like EASTL, Boost, and Folly added them around 2014–2015, but they're still absent from the C++ Standard Library — even C++26 doesn't include them.

static_vector eliminates most in-function memory allocations but requires large stacks (often 2MB+).

pmr::vector alternative

template <typename T, size_t COUNT, size_t FIXEDSIZE = COUNT * sizeof(T)>
struct FixedMemoryResource : public std::pmr::memory_resource
{
    virtual void* do_allocate(size_t bytes, size_t align) override
    {
        void* currBuffer = &mFixedBuffer[FIXEDSIZE - mAvailableFixedSize];
        if (std::align(align, bytes, currBuffer, mAvailableFixedSize) == nullptr)
        {
            assert(false && "allocate more that expected");
            return ::operator new(bytes, static_cast<std::align_val_t>(align));
        }
        mAvailableFixedSize -= bytes;
        return currBuffer;
    }

    virtual void do_deallocate(void* ptr, size_t bytes, size_t align) override
    {
        if (ptr < &mFixedBuffer[0] || ptr >= &mFixedBuffer[FIXEDSIZE])
        {
            ::operator delete(ptr, bytes, static_cast<std::align_val_t>(align));
        }
    }

    virtual bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override
    { return this == &other; }

  private:
    alignas(T) uint8_t mFixedBuffer[FIXEDSIZE];
    std::size_t mAvailableFixedSize = FIXEDSIZE;
};

The project's own static_vector implementation is at src/core/svector.h.

The next evolution is the hybrid vector — covered in part 2.