들어가며
게임 엔진과 시뮬레이션 시스템에서는 표준 컨테이너만으로 성능 요구를 맞추기 어려운 상황이 자주 등장한다. 60FPS를 유지하며 수만 엔티티를 갱신해야 하는 게임, 초당 수천 패킷을 처리하는 서버, 수백만 파티클을 렌더하는 이펙트 시스템 같은 워크로드는 동적 할당의 비결정성과 캐시 미스에 정면으로 부딪힌다.
이 글은 그런 워크로드에서 자주 등장하는 다섯 가지 자료구조 — Ring Buffer, Object Pool, Sparse Set, Slot Map, Archetype 기반 ECS — 를 각자의 설계 동기와 구현, 트레이드오프 관점에서 정리한다. 특히 절 3의 Sparse Set과 절 5의 Archetype은 현대 ECS의 두 축으로, 이 글의 무게 중심도 그쪽에 있다.
마지막에는 다섯 자료구조의 성능 특성을 한 표에 정리하고, 실제 게임 엔진이 이들을 어떻게 조합해서 쓰는지 본다.
목차
- Ring Buffer: 고정 크기 스트리밍의 정석
- Object Pool: 할당 비용의 제거
- Sparse Set: ECS의 핵심 자료구조
- Slot Map: 오래된 핸들 검출
- Archetype 기반 ECS: 극한의 성능
- 종합 비교 및 선택 가이드
1. Ring Buffer: 고정 크기 스트리밍의 정석
왜 Ring Buffer인가?
오디오 처리, 네트워크 패킷 버퍼링, 입력 이벤트 처리와 같은 스트리밍 작업에서는 FIFO(First-In-First-Out) 큐가 필요하다. std::queue를 사용할 수도 있지만, 실시간 시스템에서는 다음과 같은 문제가 발생한다:
- 동적 할당의 예측 불가능성:
std::queue의 내부 컨테이너(std::deque)는 메모리를 동적으로 할당하므로, 할당 시간이 일정하지 않다. - 메모리 단편화: 빈번한 할당과 해제로 인해 메모리 단편화가 발생할 수 있다.
- 캐시 미스: 데이터가 메모리 상에서 연속적이지 않을 수 있다.
Ring Buffer는 고정 크기의 배열을 원형으로 재사용하여 이러한 문제를 해결한다. Head와 Tail 포인터만 조작하면 되므로, 모든 연산이 O(1) 시간에 수행된다.
기본 구현
template<typename T, size_t Size>
class RingBuffer {
private:
T buffer[Size];
size_t head; // 쓰기 위치
size_t tail; // 읽기 위치
size_t count; // 현재 요소 개수
public:
RingBuffer() : head(0), tail(0), count(0) {}
bool push(const T& item) {
if (count == Size) return false; // 버퍼 가득참
buffer[head] = item;
head = (head + 1) % Size;
++count;
return true;
}
bool pop(T& item) {
if (count == 0) return false; // 버퍼 비어있음
item = buffer[tail];
tail = (tail + 1) % Size;
--count;
return true;
}
bool isFull() const { return count == Size; }
bool isEmpty() const { return count == 0; }
size_t size() const { return count; }
};이 구현은 간결하지만, count 변수로 인해 생산자와 소비자가 동일한 변수를 수정하게 되어 멀티스레드 환경에서는 동기화 오버헤드가 발생한다.
Lock-Free 구현 (SPSC 전용)
다음 구현은 단일 생산자 / 단일 소비자(SPSC) 전용이다. 생산자가 한 명이라 head를 단독으로 갱신할 수 있고, 소비자도 마찬가지로 tail을 단독으로 갱신할 수 있다는 가정에서 락 없이 안전하다. 다중 생산자나 다중 소비자(MPMC) 환경에서는 head/tail 예약을 위한 별도의 CAS 루프가 필요하며, 그렇지 않으면 같은 슬롯에 두 producer가 동시에 쓰는 race가 발생한다. MPMC가 필요하면 moodycamel/concurrentqueue 같은 검증된 구현을 쓰거나 Vyukov MPMC 큐를 별도로 작성해야 한다.
template<typename T, size_t Size>
class SPSCRingBuffer {
private:
T buffer[Size];
std::atomic<size_t> head; // producer만 store
std::atomic<size_t> tail; // consumer만 store
public:
SPSCRingBuffer() : head(0), tail(0) {}
bool push(const T& item) { // 생산자 한 명만 호출 가능
size_t current_head = head.load(std::memory_order_relaxed);
size_t next_head = (current_head + 1) % Size;
if (next_head == tail.load(std::memory_order_acquire)) {
return false; // 가득참
}
buffer[current_head] = item;
head.store(next_head, std::memory_order_release);
return true;
}
bool pop(T& item) { // 소비자 한 명만 호출 가능
size_t current_tail = tail.load(std::memory_order_relaxed);
if (current_tail == head.load(std::memory_order_acquire)) {
return false; // 비어있음
}
item = buffer[current_tail];
tail.store((current_tail + 1) % Size, std::memory_order_release);
return true;
}
};여기서 주목할 점은 메모리 순서(memory ordering) 지정이다:
memory_order_relaxed: 같은 스레드 안의 단독 갱신이라 순서 보장이 필요 없는 자기 인덱스 읽기memory_order_acquire: 상대 인덱스를 읽어 슬롯의 가시성을 보장memory_order_release: 슬롯에 쓴 데이터를 상대 스레드가 acquire로 볼 수 있도록 게시
이 메모리 순서 제어가 SPSC에서 락 없이도 안전한 이유다. MPMC에서는 같은 head를 두 생산자가 동시에 갱신해 추가 동기화 없이는 안전하지 않다.
성능 최적화: 2의 거듭제곱 크기
버퍼 크기를 2의 거듭제곱으로 제한하면 wrap-around를 비트 마스크로 표현할 수 있다:
template<typename T, size_t Size>
class OptimizedRingBuffer {
static_assert((Size & (Size - 1)) == 0, "Size must be power of 2");
private:
T buffer[Size];
size_t head = 0;
size_t tail = 0;
static constexpr size_t MASK = Size - 1;
public:
bool push(const T& item) {
size_t next_head = (head + 1) & MASK; // % Size 대신 비트 마스크
if (next_head == tail) return false;
buffer[head] = item;
head = next_head;
return true;
}
bool pop(T& item) {
if (tail == head) return false;
item = buffer[tail];
tail = (tail + 1) & MASK;
return true;
}
};Size가 템플릿 상수이고 2의 거듭제곱임을 컴파일러가 알면 % Size도 같은 마스크로 최적화될 수 있다. 따라서 수동 치환의 고정 성능 이득을 기대하기보다 power-of-two라는 불변식을 명시하고 생성된 코드를 확인하는 데 의미가 있다.
실전 응용: 오디오 버퍼
실시간 오디오 처리는 Ring Buffer의 대표적인 응용 사례이다:
constexpr size_t SAMPLE_RATE = 48000;
constexpr size_t BUFFER_SIZE = 4096;
class AudioBuffer {
RingBuffer<float, BUFFER_SIZE> leftChannel;
RingBuffer<float, BUFFER_SIZE> rightChannel;
public:
// 오디오 콜백에서 호출 (생산자)
void write(float left, float right) {
leftChannel.push(left);
rightChannel.push(right);
}
// 재생 스레드에서 호출 (소비자)
bool read(float& left, float& right) {
return leftChannel.pop(left) && rightChannel.pop(right);
}
// 언더런 체크
bool hasEnoughData(size_t minSamples) const {
return leftChannel.size() >= minSamples;
}
};오디오 시스템에서는 버퍼 언더런이 발생하면 끊김이나 잡음이 생길 수 있다. 버퍼를 키우면 scheduler jitter에 강해지지만 입력부터 출력까지의 latency가 늘어난다. 필요한 frame 수와 callback block 수는 오디오 API, 장치, 장르의 반응성 요구와 최악 실행 시간을 측정해 정한다.
2. Object Pool: 할당 비용의 제거
메모리 할당의 숨겨진 비용
게임에서 파티클 시스템을 구현한다고 가정해보자. 폭발 이펙트 하나에 수천 개의 파티클이 생성되었다가 1-2초 내에 소멸한다. 순진한 구현은 다음과 같을 것이다:
// 나쁜 예시
void emitParticle() {
Particle* p = new Particle(); // 매번 힙 할당
p->lifetime = 1.0f;
activeParticles.push_back(p);
}
void updateParticles(float dt) {
for (auto it = activeParticles.begin(); it != activeParticles.end();) {
(*it)->age += dt;
if ((*it)->age >= (*it)->lifetime) {
delete *it; // 매번 힙 해제
it = activeParticles.erase(it);
} else {
++it;
}
}
}이 코드의 문제점:
1. 할당 비용: new는 보통 사용자 공간 할당자를 거치며, 로컬 캐시 miss에서 공유 풀이나 OS 경로로 확장될 수 있다.
2. 해제 비용: delete는 메모리를 반환하고 메타데이터를 업데이트해야 한다.
3. 메모리 단편화: 작은 객체의 빈번한 할당/해제는 힙을 조각낸다.
4. 캐시 미스: 파티클들이 메모리 상에서 흩어져 있어 순회 시 캐시 미스가 빈번하다.
Object Pool은 미리 객체를 할당해두고 재사용함으로써 이러한 문제를 해결한다.
Object Pool 구현
template<typename T, size_t PoolSize>
class ObjectPool {
private:
// 실제 객체 저장소
std::array<T, PoolSize> objects;
// 사용 가능한 객체의 인덱스 스택
std::array<size_t, PoolSize> freeList;
size_t freeCount;
// 사용 중인지 추적
std::bitset<PoolSize> inUse;
public:
ObjectPool() : freeCount(PoolSize) {
// 모든 인덱스를 free list에 추가
for (size_t i = 0; i < PoolSize; ++i) {
freeList[i] = i;
}
}
// 객체 할당
T* acquire() {
if (freeCount == 0) return nullptr;
size_t index = freeList[--freeCount];
inUse.set(index);
// Placement new로 객체 재초기화
return new (&objects[index]) T();
}
// 객체 반환
void release(T* obj) {
// 포인터로부터 인덱스 계산
size_t index = obj - objects.data();
if (index >= PoolSize || !inUse[index]) {
// 잘못된 객체 또는 이중 해제
return;
}
// 소멸자 명시적 호출
obj->~T();
inUse.reset(index);
freeList[freeCount++] = index;
}
size_t available() const { return freeCount; }
size_t capacity() const { return PoolSize; }
};여기서 핵심은 placement new이다. 이미 할당된 메모리에 생성자만 호출하므로, 힙 할당 오버헤드가 발생하지 않는다.
한 가지 주의점이 있다. std::array<T, N>은 풀 생성 시점에 모든 요소를 이미 생성하므로, 첫 acquire에서 살아있는 객체 위에 placement new를 하는 셈이 된다. 비자명한 소멸자를 가진 타입에서는 엄밀하지 않으므로, 정석은 alignas(T) std::byte storage[N * sizeof(T)] 같은 원시 버퍼를 두고 생성/소멸을 풀이 전담하는 것이다.
RAII 스타일 핸들
매번 수동으로 release를 호출하는 것은 실수하기 쉽다. RAII 패턴을 적용하여 자동으로 반환되도록 만들 수 있다:
template<typename T>
class PoolHandle {
ObjectPool<T>* pool;
T* object;
public:
PoolHandle(ObjectPool<T>* p, T* obj) : pool(p), object(obj) {}
~PoolHandle() {
if (object) pool->release(object);
}
// 이동 시맨틱
PoolHandle(PoolHandle&& other) noexcept
: pool(other.pool), object(other.object) {
other.object = nullptr;
}
PoolHandle& operator=(PoolHandle&& other) noexcept {
if (this != &other) {
if (object) pool->release(object);
pool = other.pool;
object = other.object;
other.object = nullptr;
}
return *this;
}
// 복사 금지
PoolHandle(const PoolHandle&) = delete;
PoolHandle& operator=(const PoolHandle&) = delete;
T* operator->() { return object; }
T& operator*() { return *object; }
bool valid() const { return object != nullptr; }
};
// 사용 예시
auto particleHandle = pool.acquireHandle();
if (particleHandle.valid()) {
particleHandle->position = {0, 0, 0};
particleHandle->velocity = {1, 2, 3};
} // 스코프를 벗어나면 자동으로 풀에 반환실전 파티클 시스템
struct Particle {
glm::vec3 position;
glm::vec3 velocity;
glm::vec4 color;
float lifetime;
float age;
float size;
void reset() {
position = {0, 0, 0};
velocity = {0, 0, 0};
color = {1, 1, 1, 1};
lifetime = 1.0f;
age = 0.0f;
size = 1.0f;
}
};
class ParticleSystem {
private:
static constexpr size_t MAX_PARTICLES = 10000;
ObjectPool<Particle, MAX_PARTICLES> pool;
std::vector<Particle*> activeParticles;
public:
void emit(const glm::vec3& position, const glm::vec3& velocity, float lifetime) {
Particle* p = pool.acquire();
if (!p) {
// 풀이 가득참 - 가장 오래된 파티클 재활용
if (!activeParticles.empty()) {
p = activeParticles.front();
activeParticles.erase(activeParticles.begin());
} else {
return; // 완전히 가득참
}
}
p->position = position;
p->velocity = velocity;
p->lifetime = lifetime;
p->age = 0.0f;
activeParticles.push_back(p);
}
void update(float deltaTime) {
// 역순 순회 (제거 시 효율적)
for (int i = activeParticles.size() - 1; i >= 0; --i) {
Particle* p = activeParticles[i];
p->age += deltaTime;
if (p->age >= p->lifetime) {
// 파티클 수명 종료
pool.release(p);
activeParticles.erase(activeParticles.begin() + i);
} else {
// 물리 업데이트
p->velocity.y -= 9.8f * deltaTime; // 중력
p->position += p->velocity * deltaTime;
// 페이드 아웃
float t = p->age / p->lifetime;
p->color.a = 1.0f - t;
}
}
}
void render() {
// 인스턴싱으로 한 번에 렌더링
std::vector<glm::mat4> transforms;
std::vector<glm::vec4> colors;
transforms.reserve(activeParticles.size());
colors.reserve(activeParticles.size());
for (const Particle* p : activeParticles) {
glm::mat4 transform = glm::translate(glm::mat4(1.0f), p->position);
transform = glm::scale(transform, glm::vec3(p->size));
transforms.push_back(transform);
colors.push_back(p->color);
}
// GPU 인스턴스 렌더링
renderInstanced(transforms, colors);
}
};이 구현은 pool backing storage를 준비한 뒤 개별 파티클의 일반 힙 할당을 피한다. 대신 고정 최대 개수, pool 초기화 비용, 빈 슬롯 관리와 초과 정책을 부담한다. 이득은 기존 할당자의 fast-path hit 비율과 파티클 수명 분포에 따라 측정해야 한다.
3. Sparse Set: ECS의 핵심 자료구조
ECS란 무엇인가?
Entity Component System(ECS)은 전통적인 객체 지향 상속 구조의 대안으로 떠오른 아키텍처 패턴이다. 게임 오브젝트를 다음 세 가지 요소로 분리한다:
- Entity: 고유 ID만 가진 빈 컨테이너 (단순히 정수)
- Component: 데이터만 담은 구조체 (Position, Velocity, Health 등)
- System: 컴포넌트에 대한 로직 (MovementSystem, RenderSystem 등)
전통적인 객체 지향 방식과 비교해보자:
// 전통적 OOP
class GameObject {
glm::vec3 position;
glm::vec3 velocity;
int health;
virtual void update(float dt) {
position += velocity * dt;
}
};
class Enemy : public GameObject {
AI* aiController;
void update(float dt) override {
GameObject::update(dt);
aiController->think();
}
};이 방식의 문제:
1. 다이아몬드 상속 문제: 다중 상속 시 복잡도 증가
2. 캐시 미스: 가상 함수 호출과 흩어진 데이터
3. 유연성 부족: 런타임에 기능 추가/제거 어려움
ECS 방식:
// Entity는 단순히 uint32_t
uint32_t entity = registry.create();
// 컴포넌트는 데이터만 담음
struct Position { float x, y, z; };
struct Velocity { float dx, dy, dz; };
struct Health { int current, max; };
// 엔티티에 컴포넌트 부착
registry.add<Position>(entity, {0, 0, 0});
registry.add<Velocity>(entity, {1, 0, 0});
registry.add<Health>(entity, {100, 100});
// 시스템은 컴포넌트를 순회
void MovementSystem(Registry& reg, float dt) {
reg.view<Position, Velocity>([dt](Position& pos, Velocity& vel) {
pos.x += vel.dx * dt;
pos.y += vel.dy * dt;
pos.z += vel.dz * dt;
});
}Sparse Set: 양쪽의 장점을 취하다
ECS에서 핵심 문제는 "어떤 엔티티가 어떤 컴포넌트를 가지고 있는가?"를 효율적으로 저장하고 조회하는 것이다. Sparse Set은 컴포넌트 종류별로 빠른 membership 검사와 조밀한 순회를 함께 얻는 대표적인 선택이다. 다만 sparse 배열 비용이 엔티티 ID 공간의 상한에 비례하고, 여러 컴포넌트 조합 질의는 가장 작은 집합을 순회하며 나머지를 검사해야 한다. 조합 단위 순회가 지배적이면 archetype chunk가 더 유리할 수 있다.
핵심 아이디어:
- Sparse Array: entity_id를 인덱스로 사용하여 dense 배열의 위치를 저장 (O(1) 조회)
- Dense Array: 실제로 컴포넌트를 가진 엔티티만 압축 저장 (O(n) 순회, n은 실제 엔티티 수)
template<typename T>
class SparseSet {
private:
// Sparse: entity_id → dense array의 인덱스
std::vector<uint32_t> sparse;
// Dense: 압축된 엔티티 ID 배열
std::vector<uint32_t> dense;
// Components: 실제 컴포넌트 데이터 (dense와 동일한 순서)
std::vector<T> components;
static constexpr uint32_t NULL_INDEX = UINT32_MAX;
public:
// 엔티티가 컴포넌트를 가지는지 확인: O(1)
bool has(uint32_t entity) const {
if (entity >= sparse.size()) return false;
uint32_t denseIdx = sparse[entity];
return denseIdx < dense.size() && dense[denseIdx] == entity;
}
// 컴포넌트 가져오기: O(1)
T* get(uint32_t entity) {
if (!has(entity)) return nullptr;
return &components[sparse[entity]];
}
// 컴포넌트 추가: O(1) 평균
T& add(uint32_t entity, const T& component = T{}) {
if (has(entity)) {
// 이미 존재 - 덮어쓰기
components[sparse[entity]] = component;
return components[sparse[entity]];
}
// Sparse 배열 확장 (필요시)
if (entity >= sparse.size()) {
sparse.resize(entity + 1, NULL_INDEX);
}
// Dense 배열 끝에 추가
uint32_t denseIdx = dense.size();
sparse[entity] = denseIdx;
dense.push_back(entity);
components.push_back(component);
return components.back();
}
// 컴포넌트 제거: O(1)
void remove(uint32_t entity) {
if (!has(entity)) return;
uint32_t denseIdx = sparse[entity];
uint32_t lastIdx = dense.size() - 1;
if (denseIdx != lastIdx) {
// Swap-and-pop: 마지막 요소와 교체
uint32_t lastEntity = dense[lastIdx];
dense[denseIdx] = lastEntity;
components[denseIdx] = std::move(components[lastIdx]);
sparse[lastEntity] = denseIdx;
}
dense.pop_back();
components.pop_back();
sparse[entity] = NULL_INDEX;
}
// 모든 컴포넌트 순회: 캐시 친화적
void forEach(std::function<void(uint32_t entity, T& component)> callback) {
for (size_t i = 0; i < dense.size(); ++i) {
callback(dense[i], components[i]);
}
}
size_t size() const { return dense.size(); }
};왜 Sparse Set이 빠른가?
Sparse Set의 성능 비결은 데이터 지역성에 있다. 순회할 때는 dense 배열만 접근하므로:
- 순차 메모리 접근: CPU 프리페처가 다음 캐시 라인을 미리 가져온다.
- 분기 예측: iterator가 tombstone이나 bucket chain을 건너뛰는 분기를 줄일 수 있다.
- 벡터화 가능: 컴파일러가 SIMD 명령어로 최적화할 수 있다.
두 순회 형태의 핵심 차이:
// std::unordered_map<uint32_t, Component> 사용 시
for (auto& [entity, comp] : hashMap) {
comp.value += 1; // 순회 자체는 재해시하지 않지만 node chain을 따라갈 수 있음
}
// SparseSet 사용 시
sparseSet.forEach([](uint32_t entity, Component& comp) {
comp.value += 1; // dense 배열을 순차 접근
});unordered_map의 range-for가 각 원소마다 hash lookup을 수행하는 것은 아니다. 차이는 node-based 배치와 dense 배열의 locality, prefetch, vectorization 가능성에서 생긴다. 배율은 component 크기와 iteration body가 가벼울수록 크게 보이고, 본문 계산이 무거우면 작아진다.
EnTT: 실전 ECS 라이브러리
EnTT는 sparse set 계열 storage와 view/group 질의를 제공하는 header-only C++ ECS 라이브러리다. 라이브러리 선택은 공개되지 않은 제품 채택 사례나 단일 순위보다 필요한 storage 안정성, 구조 변경 비용, scheduler 통합과 버전 API를 기준으로 판단한다.
#include <entt/entt.hpp>
struct Position { float x, y, z; };
struct Velocity { float dx, dy, dz; };
int main() {
entt::registry registry;
// 엔티티 생성
auto entity = registry.create();
registry.emplace<Position>(entity, 0.0f, 0.0f, 0.0f);
registry.emplace<Velocity>(entity, 1.0f, 0.0f, 0.0f);
// 1000개 엔티티 생성
for (int i = 0; i < 1000; ++i) {
auto e = registry.create();
registry.emplace<Position>(e, float(i), 0.0f, 0.0f);
registry.emplace<Velocity>(e, 1.0f, 1.0f, 0.0f);
}
// 뷰를 사용한 순회
auto view = registry.view<Position, Velocity>();
for (auto entity : view) {
auto& pos = view.get<Position>(entity);
auto& vel = view.get<Velocity>(entity);
pos.x += vel.dx * 0.016f;
pos.y += vel.dy * 0.016f;
}
// 또는 람다로 더 간결하게
view.each([](auto& pos, auto& vel) {
pos.x += vel.dx * 0.016f;
pos.y += vel.dy * 0.016f;
});
return 0;
}성능을 비교할 때는 entity 생성, component attach/detach, single-component 순회, multi-component join과 구조 변경을 분리한다. 같은 entity 수라도 component 조합과 view 구성 방식이 비용을 바꾸므로 "100만 개 몇 ms"를 라이브러리의 고정 속도로 사용하지 않는다.
4. Slot Map: 오래된 핸들 검출
ID 재사용 문제
객체 풀이나 엔티티 시스템에서 숫자 ID를 재사용하면 오래된 참조가 새 객체를 가리킬 수 있다. 모양은 lock-free 알고리즘의 ABA와 비슷하지만 여기서 해결하려는 문제는 애플리케이션 핸들의 세대 검증이다. 원자적 CAS의 ABA와 안전한 메모리 회수는 별도의 동시성 문제다.
EntityID enemy = spawnEnemy(); // ID = 5
Projectile* bullet = shootAt(enemy); // 총알이 enemy(5)를 추적
destroyEnemy(enemy); // ID 5 삭제
EntityID newEnemy = spawnEnemy(); // ID 5 재사용
// 문제: 총알이 새로운 적을 가리키게 됨!
bullet->update(); // 엉뚱한 적을 향해 날아감이는 다음 상황에서 심각한 버그를 유발한다:
1. 지연된 참조: 이벤트 큐에 저장된 오래된 ID
2. 비동기 처리: 다른 스레드가 이미 삭제된 ID 참조
3. 네트워크 게임: 클라이언트가 오래된 엔티티 ID 사용
Generational Index: 세대로 구분하다
해결책은 각 슬롯에 "세대(generation)" 카운터를 추가하는 것이다:
template<typename T>
class SlotMap {
private:
struct Slot {
uint32_t generation; // 현재 세대
uint32_t index; // data 배열의 인덱스 (사용 중일 때)
bool occupied;
};
std::vector<Slot> slots;
std::vector<T> data;
std::vector<uint32_t> indices; // data → slot 역매핑
std::vector<uint32_t> freeSlots;
public:
struct Key {
uint32_t index;
uint32_t generation;
bool operator==(const Key& other) const {
return index == other.index && generation == other.generation;
}
};
// 새 요소 추가
Key insert(const T& value) {
uint32_t slotIndex;
if (!freeSlots.empty()) {
// 빈 슬롯 재사용
slotIndex = freeSlots.back();
freeSlots.pop_back();
} else {
// 새 슬롯 생성
slotIndex = slots.size();
slots.push_back({0, 0, false});
}
Slot& slot = slots[slotIndex];
slot.index = data.size();
slot.occupied = true;
data.push_back(value);
indices.push_back(slotIndex);
return {slotIndex, slot.generation};
}
// 요소 제거
bool erase(Key key) {
if (key.index >= slots.size()) return false;
Slot& slot = slots[key.index];
// 세대 확인 (오래된 핸들 거부)
if (!slot.occupied || slot.generation != key.generation) {
return false;
}
// Swap-and-pop
uint32_t dataIndex = slot.index;
uint32_t lastIndex = data.size() - 1;
if (dataIndex != lastIndex) {
data[dataIndex] = std::move(data[lastIndex]);
indices[dataIndex] = indices[lastIndex];
slots[indices[dataIndex]].index = dataIndex;
}
data.pop_back();
indices.pop_back();
// 슬롯 비우기 및 세대 증가
slot.occupied = false;
slot.generation++; // 핵심: 세대 증가
freeSlots.push_back(key.index);
return true;
}
// 요소 접근
T* get(Key key) {
if (key.index >= slots.size()) return nullptr;
const Slot& slot = slots[key.index];
if (!slot.occupied || slot.generation != key.generation) {
return nullptr; // 오래된 키
}
return &data[slot.index];
}
// 유효성 검사
bool isValid(Key key) const {
return key.index < slots.size() &&
slots[key.index].occupied &&
slots[key.index].generation == key.generation;
}
};실전 활용 예시
struct Enemy {
float health;
glm::vec3 position;
SlotMap<Enemy>::Key target; // 다른 적을 타겟팅할 수도 있음
};
class GameWorld {
SlotMap<Enemy> enemies;
public:
SlotMap<Enemy>::Key spawnEnemy(const glm::vec3& pos) {
Enemy enemy;
enemy.health = 100.0f;
enemy.position = pos;
return enemies.insert(enemy);
}
void damageEnemy(SlotMap<Enemy>::Key key, float damage) {
Enemy* enemy = enemies.get(key);
if (!enemy) {
// 이미 죽었거나 유효하지 않은 키
return;
}
enemy->health -= damage;
if (enemy->health <= 0) {
enemies.erase(key);
// 이제 이 키는 무효화됨
}
}
void update(float dt) {
enemies.forEach([this, dt](auto key, Enemy& enemy) {
// AI 업데이트
enemy.position += glm::vec3(1, 0, 0) * dt;
// 다른 적을 공격
if (shouldAttackOther(enemy)) {
auto otherKey = findNearestEnemy(enemy.position);
damageEnemy(otherKey, 10.0f); // 유효한 세대의 핸들만 허용
}
});
}
};이제 적이 죽고 같은 슬롯에 새 적이 생성되더라도 세대가 다른 오래된 키는 거부된다. 단, 세대 카운터가 래핑해 과거 값으로 돌아오면 같은 키가 다시 나타날 수 있다. 비트 폭은 슬롯의 예상 재사용 횟수와 프로그램 수명에 맞춰 정하고, 래핑을 실질적으로 불가능하게 만들거나 해당 슬롯을 영구 폐기하는 정책이 필요하다. 또한 이 컨테이너 자체가 자동으로 thread-safe가 되는 것은 아니다.
메모리 최적화: Compact Key
32비트 인덱스 + 32비트 세대 = 64비트는 포인터만큼 크다. 대부분의 경우 이보다 작은 키면 충분하다:
struct CompactKey {
uint32_t index : 20; // 100만 엔티티
uint32_t generation : 12; // 4096번 뒤 래핑하므로 수명 조건을 검토해야 함
};또는:
struct BalancedKey {
uint16_t index; // 65536 엔티티
uint16_t generation; // 65536번 재사용
};프로젝트의 요구사항에 따라 비트 수를 조절하여 메모리를 절약할 수 있다.
5. Archetype 기반 ECS: 극한의 성능
Sparse Set의 한계
Sparse Set 기반 ECS는 충분히 빠르지만, 대규모 게임(엔티티 수십만 개)에서는 여전히 개선의 여지가 있다:
- 간접 참조: Sparse 배열을 거쳐 dense 배열에 접근
- 분산된 메모리: 각 컴포넌트 타입이 별도 배열에 저장
- SIMD 활용 부족: 다른 타입의 컴포넌트가 섞여 있음
Unity DOTS, Flecs 등 현대 ECS 엔진은 Archetype 기반 아키텍처를 사용하여 이를 해결한다.
Archetype이란?
Archetype: 동일한 컴포넌트 조합을 가진 엔티티의 집합
예를 들어:
- Archetype A: [Position, Velocity]
- Archetype B: [Position, Velocity, Health]
- Archetype C: [Position, Renderable]
각 Archetype은 컴포넌트를 Structure of Arrays (SoA) 레이아웃으로 저장한다.
SoA vs AoS: 메모리 레이아웃의 중요성
Array of Structures (AoS) - 전통적 방식
struct Entity {
Position position;
Velocity velocity;
Health health;
};
std::vector<Entity> entities;
// 메모리: [P|V|H][P|V|H][P|V|H]...
// 물리 시스템: Position과 Velocity만 필요
for (auto& entity : entities) {
entity.position += entity.velocity * dt;
// Health도 캐시에 로드됨 (낭비!)
}CPU는 캐시 라인 단위(64바이트)로 메모리를 가져온다. 위 코드에서는 Health 데이터도 함께 로드되지만 사용하지 않으므로 낭비이다.
Structure of Arrays (SoA) - Archetype 방식
struct Archetype_PosVel {
std::vector<Position> positions; // [P][P][P]...
std::vector<Velocity> velocities; // [V][V][V]...
};
// 물리 시스템: 필요한 데이터만 순차 접근
for (size_t i = 0; i < archetype.positions.size(); ++i) {
archetype.positions[i] += archetype.velocities[i] * dt;
// 이 시스템이 사용하는 필드만 별도 스트림으로 순회
}SoA는 일부 필드만 대량 순회할 때 불필요한 바이트 전송을 줄이고 각 스트림의 벡터화를 쉽게 한다. 반대로 한 객체의 모든 필드를 함께 사용하는 코드에서는 여러 배열을 함께 따라가야 하므로 AoS가 더 단순하거나 유리할 수 있다. 비교는 실제 시스템의 필드 접근 집합과 byte/element를 기준으로 한다.
Archetype ECS 구현 (간소화 버전)
class ArchetypeECS {
private:
using ArchetypeID = size_t;
struct ArchetypeStorage {
std::vector<uint32_t> entities;
std::unordered_map<std::type_index, void*> componentArrays;
template<typename T>
std::vector<T>& getArray() {
auto typeIdx = std::type_index(typeid(T));
if (componentArrays.find(typeIdx) == componentArrays.end()) {
componentArrays[typeIdx] = new std::vector<T>();
}
return *static_cast<std::vector<T>*>(componentArrays[typeIdx]);
}
};
std::unordered_map<ArchetypeID, ArchetypeStorage> archetypes;
std::unordered_map<uint32_t, ArchetypeID> entityToArchetype;
uint32_t nextEntity = 0;
// 컴포넌트 타입 조합으로 Archetype ID 계산
template<typename... Components>
ArchetypeID getArchetypeID() {
std::vector<std::type_index> types = {std::type_index(typeid(Components))...};
std::sort(types.begin(), types.end());
size_t hash = 0;
for (const auto& type : types) {
hash ^= type.hash_code() + 0x9e3779b9 + (hash << 6) + (hash >> 2);
}
return hash;
}
public:
// 엔티티 생성 (컴포넌트와 함께)
template<typename... Components>
uint32_t create(Components&&... components) {
uint32_t entity = nextEntity++;
ArchetypeID archetypeID = getArchetypeID<Components...>();
auto& archetype = archetypes[archetypeID];
archetype.entities.push_back(entity);
(archetype.getArray<Components>().push_back(std::forward<Components>(components)), ...);
entityToArchetype[entity] = archetypeID;
return entity;
}
// 쿼리: 특정 컴포넌트를 가진 모든 엔티티 순회
template<typename... Components>
void query(std::function<void(Components&...)> callback) {
for (auto& [archetypeID, storage] : archetypes) {
if (!hasAllComponents<Components...>(storage)) continue;
// 순회 (각 컴포넌트의 SoA 배열을 같은 인덱스로 접근)
size_t count = storage.entities.size();
for (size_t i = 0; i < count; ++i) {
callback(storage.getArray<Components>()[i]...);
}
}
}
private:
template<typename... Components>
bool hasAllComponents(const ArchetypeStorage& storage) {
return (storage.componentArrays.find(std::type_index(typeid(Components))) !=
storage.componentArrays.end() && ...);
}
};Unity DOTS의 실제 구현
Unity DOTS는 Archetype ECS의 대표적인 산업 구현이다:
// 컴포넌트 정의
public struct Position : IComponentData {
public float3 Value;
}
public struct Velocity : IComponentData {
public float3 Value;
}
// 시스템 정의
[BurstCompile] // LLVM 기반 최적화
public partial struct MovementSystem : IJobEntity {
public float DeltaTime;
// 자동으로 [Position, Velocity] Archetype만 쿼리
void Execute(ref Position position, in Velocity velocity) {
position.Value += velocity.Value * DeltaTime;
}
}
// 시스템 실행
public partial class MovementSystemGroup : SystemBase {
protected override void OnUpdate() {
new MovementSystem {
DeltaTime = Time.DeltaTime
}.ScheduleParallel(); // 멀티스레드 병렬 실행!
}
}Unity DOTS의 핵심 기능:
1. Burst Compiler: C# 코드를 LLVM IR로 컴파일하여 네이티브 성능
2. Job System: CPU 코어를 활용한 자동 병렬화
3. Chunk 기반 메모리: 같은 archetype의 component를 chunk에 모아 반복 처리와 scheduling의 단위를 만든다. 구체적인 chunk 용량과 헤더 배치는 Entities 패키지 버전의 구현 세부사항이다.
DOTS가 GameObject 기반 코드보다 얼마나 빠른지는 component 구성, structural change 빈도, chunk occupancy, Burst가 생성한 코드와 job scheduling 비용에 따라 달라진다. 비교할 때는 같은 동작과 같은 결과를 구현하고 main-thread time, worker utilization, cache miss, frame-time 분포를 함께 측정해야 한다. 홍보 사례의 최대 배수는 일반적인 보장이 아니다.
SIMD 최적화
SoA 레이아웃은 SIMD(Single Instruction Multiple Data) 벡터화에 최적이다:
// 순차 코드 (자동 벡터화 가능)
void updatePositions(std::vector<Position>& positions,
const std::vector<Velocity>& velocities,
float dt) {
size_t count = positions.size();
#pragma omp simd // 컴파일러에게 벡터화 힌트
for (size_t i = 0; i < count; ++i) {
positions[i].x += velocities[i].x * dt;
positions[i].y += velocities[i].y * dt;
positions[i].z += velocities[i].z * dt;
}
}
// AVX2 명시적 사용 (8개씩 처리)
void updatePositionsAVX2(float* posX, const float* velX, size_t count, float dt) {
__m256 dt_vec = _mm256_set1_ps(dt);
// 정렬 미보장 시 loadu/storeu 사용 (aligned 버전은 32바이트 정렬 필수)
for (size_t i = 0; i < count; i += 8) {
__m256 px = _mm256_loadu_ps(&posX[i]);
__m256 vx = _mm256_loadu_ps(&velX[i]);
px = _mm256_fmadd_ps(vx, dt_vec, px); // px += vx * dt
_mm256_storeu_ps(&posX[i], px);
}
}AVX2 레지스터는 8개의 float lane을 담지만 그것이 곧 8배의 함수 속도를 뜻하지 않는다. 스칼라 baseline도 자동 벡터화될 수 있고, load/store 대역폭, FMA 처리량, tail 처리, 정렬과 CPU 주파수 변화가 상한을 결정한다. 생성된 명령과 elements/cycle을 측정해 비교한다.
6. 종합 비교 및 선택 가이드
성능 특성 비교
| 자료구조 | 삽입 | 삭제 | 조회 | 순회 | 캐시 친화성 | 메모리 오버헤드 |
|---|---|---|---|---|---|---|
| Ring Buffer | O(1) | O(1) | O(1) | O(n) | 매우 높음 | 없음 |
| Object Pool | O(1) | O(1) | O(1) | O(n) | 높음 | 낮음 (비트셋) |
| Sparse Set | O(1) | O(1) | O(1) | O(n) | 높음 | 중간 (sparse 배열) |
| Slot Map | O(1) | O(1) | O(1) | O(n) | 높음 | 중간 (세대 카운터) |
| Archetype ECS | O(1)* | O(n)** | O(1) | O(n) | 매우 높음 | 높음 (청크 메타데이터) |
* 동일 Archetype 내에서
** Archetype 변경 시 모든 컴포넌트 이동 필요
언제 무엇을 사용할 것인가?
Ring Buffer
- 최적: 스트리밍 데이터, 오디오/비디오 버퍼, 네트워크 패킷, 입력 큐
- 피할 것: 랜덤 액세스 필요, 동적 크기 필요
Object Pool
- 최적: 수명이 짧은 객체 (파티클, 총알), 빈번한 생성/소멸
- 피할 것: 객체 크기 차이가 큼, 생성 비용이 낮음
Sparse Set
- 최적: 단순한 ECS, 프로토타이핑, 중소규모 엔티티 (<10만)
- 피할 것: 극한의 성능 필요, 수백만 엔티티
Slot Map
- 최적: 장시간 유지되는 참조, 네트워크 게임, 비동기 시스템
- 피할 것: 메모리 극도로 제한적, 간접 참조 비용 민감
Archetype ECS
- 최적: 대규모 엔티티 (10만+), SIMD 최적화, 멀티스레딩, AAA 게임
- 피할 것: 컴포넌트 자주 변경, 단순한 게임, 복잡도 회피
실전 조합 전략
대부분의 프로젝트는 여러 자료구조를 조합하여 사용한다:
class GameEngine {
// 엔티티 관리
ArchetypeECS entitySystem; // 대규모 엔티티
// 파티클 시스템
ObjectPool<Particle, 100000> particlePool;
// 네트워크
RingBuffer<Packet, 1024> recvBuffer;
RingBuffer<Packet, 1024> sendBuffer;
// 안전한 핸들
SlotMap<NetworkPlayer> players;
SlotMap<GameObject> gameObjects;
public:
void update(float dt) {
// 네트워크 패킷 처리
Packet packet;
while (recvBuffer.pop(packet)) {
handlePacket(packet);
}
// 엔티티 시스템 업데이트
entitySystem.query<Position, Velocity>([dt](auto& pos, auto& vel) {
pos += vel * dt;
});
// 파티클 업데이트
updateParticles(dt);
}
};성능 프로파일링 필수
"조기 최적화는 만악의 근원"이라는 말을 기억하라. 항상 프로파일링을 통해 실제 병목을 확인한 후 최적화하라:
#include <chrono>
void benchmark() {
constexpr size_t ITERATIONS = 1000000;
// Sparse Set
{
SparseSet<Position> sparseSet;
auto start = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < ITERATIONS; ++i) {
sparseSet.add(i, Position{0, 0, 0});
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Sparse Set insert: " << duration.count() << " us\n";
}
// Archetype ECS
{
ArchetypeECS ecs;
auto start = std::chrono::high_resolution_clock::now();
for (size_t i = 0; i < ITERATIONS; ++i) {
ecs.create<Position>(Position{0, 0, 0});
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Archetype ECS insert: " << duration.count() << " us\n";
}
}결론
다섯 자료구조의 공통점은 단순하다. 동적 할당의 비결정성을 걷어내고, 메모리 레이아웃을 데이터 흐름에 맞게 정렬해 캐시 라인의 활용을 끌어올린다. Ring Buffer는 고정 메모리 위에서 FIFO를 만들고, Object Pool은 placement new로 할당을 줄이며, Sparse Set은 sparse-dense 이중 배열로 과 캐시 친화적 순회를 동시에 챙긴다. Slot Map은 generational index로 오래된 애플리케이션 핸들을 검출하고, Archetype은 SoA 레이아웃 위에서 연속 순회와 벡터화에 유리한 조건을 만든다.
현대 게임 엔진의 흐름은 Archetype 기반 ECS 쪽이다. Unity DOTS, Unreal의 Mass Entity, Bevy 모두 같은 방향으로 가고 있다. 다만 모든 프로젝트가 그 정도의 복잡도를 요구하는 것은 아니다. 엔티티가 수만 단위라면 Sparse Set만으로 충분하고, 객체 생성이 빈번한 시스템이라면 Object Pool만으로도 큰 차이를 만든다. 프로젝트의 규모와 데이터 패턴을 먼저 측정한 뒤 그에 맞는 추상의 단계를 고르는 것이 순서다.
이 컨테이너들의 복잡도와 캐시 이점은 단일 스레드 모델만으로는 충분하지 않다. 실제 병렬 실행에서는 컴포넌트 접근 집합, 구조 변경 시점, 작업 간 의존성을 별도 불변식으로 두어야 하며, 컨테이너의 연산만으로 동시성 안전성과 확장성이 따라오지는 않는다.
더 읽을거리
- EnTT — Sparse Set 기반 헤더 온리 ECS, Minecraft Bedrock에서 사용
- Unity DOTS — Archetype 기반, Burst/Job System
- Flecs — Archetype 기반 관계형 ECS
- Robert Nystrom, Game Programming Patterns
- Richard Fabian, Data-Oriented Design
- Jason Gregory, Game Engine Architecture
- Mike Acton, "Data-Oriented Design and C++" (CppCon 2014) — https://www.youtube.com/watch?v=rX0ItVEVjHc
- "Overwatch Gameplay Architecture and Netcode" (GDC 2017)
- Ulrich Drepper, "What Every Programmer Should Know About Memory"
- ECS 벤치마크 모음 — https://github.com/abeimler/ecs_benchmark
