C++ 23 std::flat_map으로 게임 룩업 테이블의 캐시 미스 잡기

연관 컨테이너가 필요할 때 C++ 개발자가 가장 먼저 떠올리는 건 std::map이다. 키로 빠르게 찾고, 자동으로 정렬되고, 삽입과 삭제가 O(log n)이다. 교과서적으로는 흠잡을 데가 없다. 그런데 게임 코드에서 매 프레임 수백 번 순회하는 자료구조로 std::map을 쓰는 순간, 프로파일러는 캐시 미스로 새빨갛게 물든다.

이유는 알고리즘 복잡도가 아니라 메모리 레이아웃에 있다. std::map은 내부적으로 균형 이진 트리(보통 red-black tree)이고, 노드 하나하나가 힙에 따로 할당된다. 노드들이 메모리 여기저기 흩어져 있으니 순회할 때마다 포인터를 따라가야 하고, CPU는 매번 새 캐시 라인을 읽어와야 한다. 요즘 하드웨어에서 캐시 미스 한 번은 산술 연산 수백 개와 맞먹는 비용이다.

C++ 23은 이 문제를 정조준한 새 컨테이너 어댑터 std::flat_map과 std::flat_set을 표준에 넣었다. 이름 그대로 "평평한" 맵이다. 트리 대신 정렬된 연속 배열 위에서 동작한다.

flat_map은 왜 캐시 친화적인가

std::flat_map은 사실 컨테이너가 아니라 컨테이너 어댑터다. 내부에 정렬된 키 배열 하나와 값 배열 하나(기본은 std::vector 두 개)를 들고 있다. 키와 값을 분리해 저장하는 이 구조 덕분에, 키만 이진 탐색할 때 무거운 값 데이터가 캐시를 오염시키지 않는다.

인터페이스는 std::map과 거의 같아서 기존 코드를 옮기기 쉽다. 차이는 전부 내부에서 일어난다. find는 정렬된 배열에 이진 탐색을 하고, 순회는 연속 메모리를 죽 스캔하므로 하드웨어 프리페처가 제대로 일한다.

#include <flat_map>

// 몬스터 ID로 스탯을 찾는 룩업 테이블
std::flat_map<int, MonsterStats> monsterTable;

monsterTable.emplace(1001, MonsterStats{ .hp = 120, .atk = 18 });
monsterTable.emplace(1002, MonsterStats{ .hp =  80, .atk = 25 });

if (auto it = monsterTable.find(1001); it != monsterTable.end())
{
    Spawn(it->second);
}

매 프레임 순회되는 테이블에 적용하기

flat_map이 진짜로 빛나는 곳은 "한 번 채우고 자주 읽는" 테이블이다. 게임에는 이런 게 널렸다. 몬스터 스탯 테이블, 아이템 데이터, 스킬 쿨다운, AI 위협(threat) 테이블이 전부 여기에 속한다.

예를 들어 적 AI가 주변 플레이어에 대한 위협 수치를 관리하고, 매 프레임 전체를 훑어 가장 위협적인 타겟을 고른다고 하자.

std::flat_map<EntityId, float> threatTable;

// 매 프레임: 전체 순회로 최대 위협 타겟 찾기
EntityId SelectTarget(const std::flat_map<EntityId, float>& threats)
{
    EntityId best = kInvalidEntity;
    float    bestThreat = 0.0f;

    // 연속 메모리 순회라 프리페처가 미리 당겨온다
    for (const auto& [id, threat] : threats)
    {
        if (threat > bestThreat)
        {
            bestThreat = threat;
            best = id;
        }
    }
    return best;
}

같은 코드를 std::map으로 돌리면 순회 한 칸마다 트리 노드를 포인터로 따라가지만, flat_map은 배열을 한 줄로 훑는다. 엔티티가 수십에서 수백 개 수준만 돼도 이 차이가 프레임 타임에 그대로 찍힌다.

공짜는 아니다: 삽입 비용

flat_map의 대가는 삽입과 삭제다. 정렬된 배열 중간에 원소를 끼워 넣으려면 뒤쪽을 전부 밀어야 하니 O(n)이다. 그래서 flat_map은 "삽입은 드물고 조회는 잦은" 워크로드 전용이라고 생각해야 한다. 런타임에 끊임없이 추가삭제되는 테이블이라면 flat_map은 오히려 독이 된다.

반대로 로딩 시점에 한 번에 채우는 데이터라면, 원소를 모아 정렬해 둔 다음 정렬된 범위로 한꺼번에 넣는 패턴이 가장 빠르다.

std::vector<std::pair<int, MonsterStats>> rows = LoadFromTable();
std::ranges::sort(rows, {}, &std::pair<int, MonsterStats>::first);

// 정렬됐다고 약속하면 내부 재정렬을 건너뛴다
std::flat_map<int, MonsterStats> table(
    std::sorted_unique, rows.begin(), rows.end());

std::sorted_unique 태그는 "입력이 이미 정렬돼 있고 중복이 없다"고 라이브러리에 알려, 생성 시 정렬 비용을 통째로 생략하게 해준다.

형제 컨테이너인 std::flat_set도 같이 들어왔다. 충돌 후보 집합, 이번 프레임에 이미 처리한 엔티티 집합처럼 "포함 여부만 빠르게" 묻는 곳에 std::set 대신 쓰면 똑같은 캐시 이점을 가져간다.

언리얼을 쓴다면 이미 비슷한 무기가 손에 있다. TSortedMap이 정확히 같은 발상의 컨테이너다. 표준 코드와 언리얼 코드를 오갈 때 std::flat_map과 TSortedMap을 한 쌍으로 기억해두면 편하다.

정리

std::map의 진짜 비용은 O(log n)이라는 표기가 아니라, 흩어진 노드를 따라가며 발생하는 캐시 미스다. C++ 23의 std::flat_map은 정렬된 연속 배열을 써서 순회와 조회를 캐시 친화적으로 바꾼다. 몬스터 스탯, AI 위협 테이블, 아이템 데이터처럼 한 번 채우고 자주 읽는 룩업 테이블이라면 거의 항상 이득이다. 다만 삽입이 잦으면 O(n) 비용 때문에 역효과가 나므로, 런타임 갱신이 많은 자료구조에는 쓰지 말고 로딩 일괄 삽입에는 sorted_unique를 활용하자. 집합이 필요하면 std::flat_set, 언리얼이라면 TSortedMap이 같은 자리를 채워준다.