왜 게임 엔진은 vector를 많이 사용할까?

자료구조를 공부할 때는 보통 시간 복잡도(Big-O)를 중심으로 배우게 됩니다.

그래서 linked list는 삽입/삭제가 빠르고, vector는 중간 삽입이 느리다고 배웁니다.

그리고 게임 엔진은 linked list 같은 구조를 굉장히 많이 사용할 것 같다는 생각을 했던 것 같습니다.

왜냐하면 게임은 오브젝트 생성과 삭제가 굉장히 많고, 실시간으로 데이터가 계속 바뀌는 프로그램이기 때문입니다.

그런데 실제 게임 엔진 코드를 보면 vector가 굉장히 많이 사용됩니다.

언리얼 엔진의 TArray도 결국 vector와 굉장히 비슷한 구조입니다.

Unity 내부 구조나 ECS 계열 구조들도 결국 연속된 메모리 구조를 굉장히 중요하게 생각합니다.

처음에는 “삽입/삭제가 느리다고 배웠는데 왜 vector를 이렇게 많이 사용할까?”싶기도 합니다.

그리고 게임 엔진 구조를 조금 더 깊게 보기 시작하면,
생각보다 많은 문제들이 결국 Cache 이야기로 다시 연결된다는 것을 알게 됩니다.

---

vector는 메모리가 연속적으로 배치된다

vector의 가장 큰 특징 중 하나는 메모리가 연속적으로 배치된다는 점입니다.

예를 들어 아래와 같은 코드가 있다고 해보겠습니다.

std::vector<int> values;

values.push_back(10);
values.push_back(20);
values.push_back(30);

vector 내부 메모리는 대략 아래와 같이 배치됩니다.

[10][20][30]

즉, 데이터가 메모리 상에 연속적으로 저장됩니다.

그래서 아래 코드와 같이 순차적으로 데이터를 읽는 작업이 굉장히 효율적입니다.

for (int value : values)
{
    std::cout << value << std::endl;
}

그리고 바로 이 특징이 게임 엔진에서 굉장히 중요합니다.

---

CPU는 연속된 데이터를 굉장히 좋아한다

이전 글에서 Cache와 Cache Locality에 대해 이야기했습니다.

CPU는 메모리에서 데이터를 읽을 때 필요한 데이터 하나만 가져오는 것이 아니라,
주변 데이터까지 함께 가져오는 경우가 많습니다.

왜냐하면 대부분의 프로그램은 연속된 데이터를 순차적으로 읽는 경우가 많기 때문입니다.

예를 들어 vector처럼 메모리가 연속적으로 배치된 구조에서는 10을 읽을 때 20과 30 같은 주변 데이터도 함께 Cache에 올라올 가능성이 높습니다.

[10][20][30][40][50]

그리고 다음 반복에서 20, 30을 읽게 되면 CPU는 이미 Cache에 있는 데이터를 빠르게 사용할 수 있습니다.

따라서 연속된 메모리 구조는 Cache 효율이 굉장히 좋아질 수 있습니다.

최근 게임 엔진들이 vector 구조를 중요하게 보는 이유도 결국 여기와 연결됩니다.

---

linked list는 구조적으로 조금 다르다

반면, linked list는 메모리가 연속적으로 배치되지 않을 가능성이 높습니다.

예를 들어, 아래와 같은 구조입니다.

struct Node
{
    int value;
    Node* next;
};

그리고 메모리는 대략 아래와 같이 배치될 수 있습니다.

[10] ----> [20] ----> [30]

겉보기에는 순서대로 연결되어 있지만, 실제 메모리 위치는 완전히 흩어져 있을 수도 있습니다.

0x1000 - [10]
0x5000 - [20]
0x9000 - [30]

이런 경우에 CPU는 다음 데이터를 읽기 위해 계속 새로운 메모리 위치로 이동해야 합니다.

이런 구조는 Cache 효율 측면에서 불리합니다.

---

게임 엔진은 읽기(Read)가 굉장히 많다

처음에는 “게임은 객체 생성/삭제가 많으니까 linked list가 더 유리하지 않을까?”싶을 수도 있습니다.

그런데 실제 게임 엔진에서는 삽입/삭제보다 조회(Read)가 훨씬 많이 발생합니다.

렌더링 시스템은 매 프레임 수많은 오브젝트를 순회합니다.

for (const RenderObject& renderObject : renderObjects)
{
    Render(renderObject);
}

물리 시스템도 마찬가지입니다.

for (PhysicsBody& body : bodies)
{
    body.Update(deltaTime);
}

애니메이션 시스템, 파티클 시스템, AI 시스템도 대부분 비슷합니다.

이처럼 게임 엔진은 “데이터를 반복해서 읽는 작업”이 굉장히 많습니다.

그리고 이런 상황에서는 linked list의 삽입/삭제 성능보다, vector의 순차 접근 성능이 훨씬 중요해지는 경우가 많습니다.

---

vector의 중간 삽입은 정말 느릴까?

자료구조 시간에는 vector의 중간 삽입이 느리다고 배웠습니다.

실제로 아래 코드처럼 중간 위치에 데이터를 삽입하면 뒤에 있는 데이터들을 한 칸씩 뒤로 이동시켜야 할 수도 있습니다.

std::vector values = { 1, 2, 3, 4 };

values.insert(values.begin() + 1, 999);

이론적으로는 비용이 발생합니다.

반면, linked list는 포인터 연결만 바꾸면 되기 때문에 삽입/삭제가 빠르다고 배웠습니다.

그런데 실제 성능은 생각보다 조금 다르게 나오는 경우가 많습니다.

왜냐하면 vector는 메모리가 연속적으로 배치되어 있기 때문입니다.

즉, 데이터 이동 자체가 memcpy처럼 굉장히 빠르게 처리되는 경우가 많습니다.

반면, linked list는 삽입 자체는 빠를 수 있지만, 특정 위치까지 이동하기 위해 계속 포인터를 따라가야 합니다.

그리고 이 과정에서 Cache Miss가 반복적으로 발생할 가능성이 있습니다.

이론적인 시간 복잡도만 보면 linked list가 좋아 보일 수 있지만, 실제 CPU와 메모리 구조에서는 vector가 더 좋은 성능을 보여주는 경우도 굉장히 많습니다.

최근 게임 엔진들이 vector 기반 구조를 굉장히 많이 사용하는 이유 중 하나입니다.

---

그래서 최근 엔진 구조는 vector 중심으로 바뀌기 시작했다

최근 게임 엔진들, 대표적으로 언리얼 엔진의 Level을 보면, vector와 유사한 TArray 자료구조로 게임 객체를 다룹니다.

아래 코드는 언리얼 엔진의 소스 코드 일부를 발췌한 것입니다.

언리얼 엔진의 맵은 내부적으로 ULevel 클래스로 구성되어 있는데, ULevel은 월드에 배치된 모든 액터를 관리합니다.

아래 코드를 살펴보면 TArray<TObjectPtr<AActor>> Actors; 형태로 액터를 관리하는 것을 볼 수 있습니다.
(참고로 TObjectPtr은 원시 포인터와 비슷한 형태라고 보시면 됩니다.)

UCLASS(MinimalAPI)
class ULevel : public UObject, public IInterface_AssetUserData, public ITextureStreamingContainer, public IEditorPathObjectInterface
{
    GENERATED_BODY()

public:

    /** URL associated with this level. */
    FURL					URL;

    /** Array of all actors in this level, used by FActorIteratorBase and derived classes */
    TArray<TObjectPtr<AActor>> Actors;

    /** Array of actors to be exposed to GC in this level. All other actors will be referenced through ULevelActorContainer */
    TArray<TObjectPtr<AActor>> ActorsForGC;
...
}

아래 코드는 언리얼 엔진의 렌더링 코드 일부를 발췌한 것입니다.

FMeshCommandOneFrameArray를 순회하는데 헤더에 선언된 내용을 보면 TArray인 것을 확인할 수 있습니다.

typedef TArray<FVisibleMeshDrawCommand, SceneRenderingAllocator> FMeshCommandOneFrameArray;
...
void SubmitMeshDrawCommandsRange(
    const FMeshCommandOneFrameArray& VisibleMeshDrawCommands,
    const FGraphicsMinimalPipelineStateSet& GraphicsMinimalPipelineStateSet,
    const FMeshDrawCommandSceneArgs& InSceneArgs,
    uint32 PrimitiveIdBufferStride,
    bool bDynamicInstancing,
    int32 StartIndex,
    int32 NumMeshDrawCommands,
    uint32 InstanceFactor,
    FRHICommandList& RHICmdList)
{
...

    for (int32 DrawCommandIndex = StartIndex; DrawCommandIndex < StartIndex + NumMeshDrawCommands; DrawCommandIndex++)
    {
        SCOPED_CONDITIONAL_DRAW_EVENTF(RHICmdList, MeshEvent, GEmitMeshDrawEvent != 0, TEXT("Mesh Draw"));

        const FVisibleMeshDrawCommand& VisibleMeshDrawCommand = VisibleMeshDrawCommands[DrawCommandIndex];
        LocalSceneArgs.PrimitiveIdOffset = InSceneArgs.PrimitiveIdOffset + (bDynamicInstancing ? VisibleMeshDrawCommand.PrimitiveIdBufferOffset : DrawCommandIndex) * PrimitiveIdBufferStride;
        checkSlow(!bDynamicInstancing || VisibleMeshDrawCommand.PrimitiveIdBufferOffset >= 0);
        FMeshDrawCommand::SubmitDraw(*VisibleMeshDrawCommand.MeshDrawCommand, GraphicsMinimalPipelineStateSet, LocalSceneArgs, InstanceFactor, RHICmdList, StateCache);
    }
}

앞서 설명했던 것처럼, 월드에 배치된 액터를 관리하는 레벨과 렌더 오브젝트를 관리하는 렌더러 모두 TArray 즉, vector와 비슷한 자료구조를 사용하는 것을 확인할 수 있습니다.

ECS, Data Oriented Design, SoA 같은 구조들도 결국 “데이터를 연속적으로 배치해서 효율적으로 읽자”는 방향과 연결됩니다.

이처럼 최근 게임 엔진들은 점점 “삽입/삭제 최적화”보다, “데이터를 얼마나 빠르게 순회할 수 있는가”를 더 중요하게 고려합니다.

그리고 vector는 이런 구조와 굉장히 잘 맞습니다.

---

그렇다고 linked list가 쓸모없다는 뜻은 아니다

여기서 중요한 부분이 있습니다.

linked list가 나쁜 자료구조라는 뜻은 아닙니다.

이 부분은 정말 중요합니다.

실제로 linked list가 더 적합한 상황도 분명 존재합니다.

삽입과 삭제가 굉장히 자주 발생하고, 순차 접근보다 연결 구조 자체가 중요한 경우에는 linked list가 더 자연스러울 수도 있습니다.

중요한 것은 “무조건 vector가 좋다”가 아닙니다.

내 프로그램에서는 어떤 자료구조가 더 적합한지를 판단할 수 있는 능력이 중요합니다.

어떤 데이터를 다루는지,
데이터를 얼마나 자주 순회하는지,
Cache 효율이 중요한지,
삽입과 삭제가 얼마나 자주 발생하는지 같은 요소들을 함께 고려해야 합니다.

예를 들어 “게임 엔진은 왜 vector를 많이 사용할까?”라는 질문을 던졌을 때,

단순히 “요즘은 vector가 좋다고 하더라”정도로 받아들이는 것이 아니라,

게임 엔진에서는 삽입과 삭제보다, 오히려 데이터를 반복적으로 순회하는 작업이 훨씬 더 자주 발생하고,
이런 상황에서는 메모리가 연속적으로 배치되는 vector 구조가 Cache 효율 측면에서 더 유리할 수 있겠구나

처럼 이유와 맥락을 이해할 수 있어야 합니다.

자료구조의 이름이나 특징 자체를 외우고 이해하는 것도 중요하지만, 실제로 자료구조가 선택되는 이유를 이해하는 것이 더 중요하다고 할 수 있습니다.

---

마무리

처음 자료구조를 공부할 때는 linked list가 vector보다 더 고급 자료구조처럼 느껴질 수도 있습니다.

그런데 실제 게임 엔진은 많은 시스템들이 vector 기반 구조 위에서 동작하고 있다는 것을 알게 됩니다.

그리고 이 내용 역시 결국 Cache, Cache Locality, Data Oriented Design, ECS 같은 키워드와 자연스럽게 연결됩니다.

최근 게임 엔진들은 점점 “자료구조 이론”보다, “실제 CPU와 메모리 구조에서 얼마나 효율적으로 동작하는가”를 더 중요하게 고려합니다.

그리고 vector는 이런 방향과 굉장히 잘 맞는 자료구조입니다.

---