게임으로 보는 8KiB에서 64B 캐시 라인까지

(포켓몬 그린, 독을 잘쓰기로 유명한 이상해꽃)

알면 좋은 사전지식

이 글은 비트 연산과 메모리 구조에 대한 최소한의 친숙함을 가정한다. 아래 네 가지만 기억해두면 본문을 따라오는 데 큰 문제는 없다.

1. 비트와 바이트

비트(bit)는 0과 1, 두 가지 값만 가질 수 있는 가장 작은 정보 단위다. 8비트가 모여 1바이트(byte)가 되고, 1바이트는 2⁸ = 256가지, 즉 0~255까지의 값을 표현할 수 있다.

이 글의 핵심은 “이 8비트 또는 32비트짜리 공간을 어떻게 쪼개서 여러 정보를 담을까”이다. 예를 들어 하위 3비트는 수면 턴수, 다음 1비트는 독, 그다음 1비트는 화상처럼 나눠 쓰는 식이다.

2. 비트 마스킹과 시프트

비트를 쪼개서 넣었으면, 다시 꺼내 써야 한다. 그때 쓰는 기본 연산이 마스킹(masking)과 시프트(shift)다.

마스킹은 특정 비트만 남기는 연산이다. 원하는 비트만 1로 켜 둔 값을 마스크라고 부르고, 원래 값과 & 연산을 하면 마스크에서 1인 자리만 남고 나머지는 0으로 지워진다.

예를 들어 status1이라는 32비트 값에서 비트 8~11에 맹독 카운터가 들어 있다고 하자. 이 네 비트만 꺼내는 마스크는 0xF00이다. 16진수 F는 이진수로 1111이므로, 0xF00은 비트 8~11만 1인 값이다.

status1 = 0x12345678;
mask    = 0x00000F00;

counterBits = status1 & mask; // 0x00000600

이렇게 하면 status1 안에서 비트 8~11만 남고 나머지는 전부 0이 된다.

하지만 결과값 0x600은 아직 실제 숫자 6이 아니다. “6”이라는 값이 8비트 왼쪽으로 밀린 상태다. 즉 내부에는 6 << 8 = 0x600 형태로 저장되어 있다.

그래서 실제 숫자로 쓰려면 오른쪽으로 8비트 밀어야 한다.

counter = (status1 & 0xF00) >> 8; // 6

본문에서 계속 나오는 패턴은 아래와 같다.(기억해두면 좋다)

value = (packed & mask) >> shift;

반대로 값을 집어넣을 때는 기존 값을 지우고, 새 값을 왼쪽으로 민 뒤, | 연산으로 합치는 것이다.

status1 = (status1 & ~0xF00) | (newCounter << 8);

즉, 읽을 때는 &와 >>, 쓸 때는 <<와 |가 기본이다.

3. 구조체 패딩

C 언어에서 구조체는 멤버를 메모리에 배치할 때 CPU가 접근하기 좋은 위치에 맞추기 위해 정렬(alignment)을 한다. 이 과정에서 멤버 사이에 빈 공간이 생기는데, 이를 패딩(padding)이라고 한다.

예를 들어 다음 구조체를 보자.

struct Example {
    char c;    // 1바이트
    int i;     // 4바이트
    bool b;    // 1바이트
};

겉으로 보면 데이터는 1 + 4 + 1 = 6바이트처럼 보인다. 하지만 많은 환경에서 int는 4바이트 경계에 놓이도록 정렬된다. 그래서 char 뒤에 3바이트 패딩이 들어가고, 구조체 전체 크기를 맞추기 위해 마지막에도 패딩이 붙을 수 있다.

결과적으로 실제 구조체 크기는 12바이트가 될 수 있다.

실제 데이터: 1 + 4 + 1 = 6바이트
패딩:       3 + 3     = 6바이트
총합:       12바이트

비트필드는 여러 개의 작은 플래그와 카운터를 한 워드 안에 몰아넣어 이런 낭비를 줄이는 방법이다.

쉽게 말하면, 여행 가방을 쌀때 가방 공간에 빈틈없이 꽉꽉 눌러담는 방식 정도로 이해해두면 문제 없다.

4. 캐시 라인

CPU는 메모리에서 데이터를 읽을 때 필요한 1바이트만 딱 가져오지 않는다. 보통 64바이트 단위의 덩어리를 한 번에 가져오는데, 이 단위를 캐시 라인(cache line)이라고 한다.

캐시에 없는 데이터를 읽으면 메인 메모리까지 다녀와야 하고, 이 지연은 수십~수백 사이클까지 커질 수 있다. 반대로 이미 L1/L2 캐시에 올라와 있는 데이터는 훨씬 빠르게 접근할 수 있다.

그래서 자주 함께 쓰는 데이터는 같은 캐시 라인 안에 모아두는 것이 중요하다. 데이터가 흩어져 있으면 여러 캐시 라인을 불러와야 하지만, 한곳에 모여 있으면 한 번의 캐시 라인 로드로 필요한 값들을 같이 가져올 수 있다.

여기서 캐시라인은 메모리보다 좀 더 빠르게 가져올 수 있는 공간 정도로만 이해해두면 아래 글을 이해하는데 아무런 문제가 없다.

들어가며: 메모리가 남아도는데 왜 비트를 깎나

"램이 32기가인데, 왜 굳이 이 불리언 값들을 비트필드로 욱여넣고 있지?"

현대 소프트웨어 엔지니어라면 한 번쯤 고민해봤을 질문이다. 패딩이 줄줄 새든 말든 1바이트 넉넉히 쓰면 될 텐데, 게임 엔진과 ECS 라이브러리들은 여전히 작은 값들을 한 워드 안에 욱여넣는다.

아마 이렇게 생각할 수도 있다.
"AI 시대에 메모리 값이 천정부지로 올라가는 지금, 한 바이트라도 아껴야 하니까 그런 거 아니야?" 실제로 AI 시대에 메모리 값은 천정부지로 올랐고, 드디어 내 주머니 사정으로는 컴퓨터 교체가 힘들어질 시기까지 왔다.

하지만 혹자는 이렇게 반문할 수도 있다. "하드웨어가 계속 발전하는데, 이런 레트로 기법이 언제까지 필요할까? 캐시도 커지고 RAM도 빨라지는데, 결국엔 해결되지 않을까?"

하지만 진짜 답은 그 어디에도 없을 것이다. 여러 오픈소스가 비트를 깎는 이유는 RAM 용량도, 하드웨어 발전의 역행도 아니다. 그것은 더 근본적이고, 더 오래된 질문과 연결되어 있다.

이 질문에 답하기 위해 가장 직접적으로 필요성을 볼 수 있는 곳으로 시간 여행해보자.

1996년, 게임보이의 8KB RAM.

포켓몬이 그 단적인 예다. 수면 턴수는 3비트, 독·화상·얼음·마비는 각각 1비트로 쪼개져 1바이트에 우겨 넣어졌다. 맹독은 턴마다 데미지가 커져야 했기에 누적 횟수를 세는 카운터가 따로 필요했고, 1바이트 상태 바이트 안에는 자리가 없어 전투 중 별도 메모리로 분리됐다.

그런데 GBA(2002년)로 넘어가면서 RAM은 256KB로 32배가 늘었고, STATUS1 필드는 32비트로 커졌다. 그럼에도 맹독 카운터는 별도 정수 필드로 풀리지 않았다.

여기서 의문이 생긴다. 용량이 해결됐는데도, 대체 왜?

그리고 다시 현대로 돌아오면 더 큰 의문이 생긴다. 30년이 지난 지금도 게임 엔진들은 여전히 비트를 쪼갠다.

이 글은 그 의문을 쫓는다. 1996년의 8KB에서 시작해, 2026년의 64바이트 캐시 라인을 공간, 설계, 그리고 대역폭의 순서대로 따라가 보자.

1. 공간의 제약: 게임보이의 1바이트 (1996)

초대 포켓몬이 돌던 게임보이의 작업 RAM은 8KiB다.

8,192바이트.

지금 이 글을 저장하는 텍스트 파일 하나가 수십 킬로바이트인 시대에, 게임보이는 그 절반도 안 되는 공간에 게임 상태를 굴려야 했다.

6마리 파티의 종족값·개체값·기술·HP·상태이상 전투 중인 몬스터 두 마리의 모든 상태, 그리고 화면에 띄울 버퍼까지, 이 모든 것이 8KiB 안에 들어가야 했다. 몬스터 한 마리의 상태이상에 할당된 건 겨우 1바이트. 비트 8개짜리 패널 하나가 전부였다.

그럼 대체 어떻게 과거의 프로그래머는 이걸 해냈는지 보자. 코드는 아래 깃 주소에서 가져왔다.

github.com

pokered/constants/battle_constants.asm at master · pret/pokered

Disassembly of Pokémon Red/Blue. Contribute to pret/pokered development by creating an account on GitHub.

pret의 게임보이 디스어셈블 pokered의 constants/battle_constants.asm을 보면 과거 프로그래머의 천재성이 보이는데, 그 1바이트가 이렇게 쪼개져 있다.

DEF SLP_MASK EQU %111 ; 비트 0-2, 수면 턴수
        const PSN ; 비트 3, 독
        const BRN ; 비트 4, 화상
        const FRZ ; 비트 5, 얼음
        const PAR ; 비트 6, 마비

눈치빠른 독자라면 비트 0~2가 다른 것과 다르다는 것을 눈치 챌 것이다.

독, 화상, 얼음, 마비는 단순하다. 걸렸는지 아닌지만 알면 되므로 각각 1비트면 충분하다. 비트 하나는 0 또는 1만 표현하므로, “독인가 아닌가”, “화상인가 아닌가” 같은 상태로 표시할 수 있다.

하지만 수면은 다르다. 수면은 단순히 “자고 있다”가 아니라 “몇 턴 더 자는가”를 저장해야 한다. 즉 켜짐/꺼짐이 아니라 숫자가 필요하다.
최대 7턴까지 표현하려면 0~7을 담을 수 있어야 하고, 0~7은 정확히 3비트로 표현된다.

1비트 = 0~1
2비트 = 0~3
3비트 = 0~7

그래서 초대 포켓몬의 상태이상 1바이트에서 비트 0~2는 수면 턴수에 배정됐다. 그다음 비트들에는 독, 화상, 얼음, 마비가 각각 하나씩 들어간다.

결국 비트 폭을 정하는 것은 표현해야 할 값의 범위가 비트 폭을 정한다. 독처럼 참/거짓이면 1비트면 되고, 수면처럼 0~7의 숫자가 필요하면 3비트가 필요하다.

하지만 포켓몬을 잘 아는 독자라면 이렇게 말할 것이다.

'맹독이 없는데?'

맹독은 무엇인가, 독이지만 턴 수가 지날수록 데미지가 강해지는 독이다.

맹독은 일반 독과 다르다. 일반 독은 턴마다 일정한 데미지를 받지만, 맹독은 턴이 지날수록 데미지가 커진다. 일반 독은 “독에 걸렸는가”만 알면 되므로 PSN 비트 하나면 충분하다. 하지만 맹독은 “맹독인가?”뿐 아니라 “지금 몇 번째 맹독 턴인가?”도 따로 세어야 한다. 즉 맹독은 단순한 1비트 상태가 아니라, 플래그 하나와 카운터 하나가 함께 필요한 상태다.

초대 포켓몬의 기본 상태이상 바이트에는 이미 수면 3비트, 독·화상·얼음·마비 플래그가 들어가 있었다. 여기에 맹독 카운터까지 넣을 공간은 없었다. 그래서 맹독은 저장용 상태 바이트 안에 억지로 들어가지 않고, 전투 중에만 쓰는 별도 플래그와 카운터로 분리됐다.

실제 코드도 그렇게 나뉘어 있다. BADLY_POISONED는 기본 상태이상 바이트가 아니라 wPlayerBattleStatus3 또는 wEnemyBattleStatus3의 비트 플래그로 정의되어 있다.

; wPlayerBattleStatus3 or wEnemyBattleStatus3 bit flags
	const_def
	const BADLY_POISONED      ; 0 ; Toxic
	const HAS_LIGHT_SCREEN_UP ; 1
	const HAS_REFLECT_UP      ; 2
	const TRANSFORMED         ; 3

이 비트는 “현재 이 독이 맹독인가?”를 표시한다. 하지만 이것만으로도 아직 부족하다. 맹독은 턴마다 데미지가 커져야 하므로, 몇 번째 맹독 턴인지 세는 카운터가 따로 필요하다.

그 카운터는 pokered/engine/battle/core.asm의 전투 데미지 처리 코드에서 등장한다. 플레이어 쪽이면 wPlayerToxicCounter, 상대 쪽이면 wEnemyToxicCounter를 사용한다.

.nonZeroDamage
	ld hl, wPlayerBattleStatus3
	ld de, wPlayerToxicCounter
	ldh a, [hWhoseTurn]
	and a
	jr z, .playersTurn
	ld hl, wEnemyBattleStatus3
	ld de, wEnemyToxicCounter
.playersTurn
	bit BADLY_POISONED, [hl]
	jr z, .noToxic
	ld a, [de]    ; increment toxic counter
	inc a
	ld [de], a
	ld hl, 0

순서대로 보면 더 분명하다. 자 그럼 보기 쉽게 순서를 정리해보자

1. PSN 비트 - 저장용 상태이상 바이트에 있음 - “독에 걸렸다”를 표시

2. BADLY_POISONED 비트 - BattleStatus3에 있음 - “이 독은 맹독이다”를 표시

3. ToxicCounter - wPlayerToxicCounter / wEnemyToxicCounter - “몇 번째 맹독 턴인가”를 저장

먼저 기본 상태이상 바이트의 PSN 비트가 “독에 걸렸다”는 사실을 표시한다. 그다음 BattleStatus3의 BADLY_POISONED 비트가 “그 독은 일반 독이 아니라 맹독이다”를 표시한다. 마지막으로 wPlayerToxicCounter 또는 wEnemyToxicCounter가 “지금 몇 번째 맹독 턴인가”를 센다.

이 얼마나 귀찮고 번거로운가. 정말 프로그래머로서 저 시대를 살지 않음에 감사하게 고, 저 시대를 산 프로그래머 선배들에 감탄하게 된다.

어쨌건 이 단계의 패킹에는 거창한 명분이 필요 없다. 게임보이의 작업 RAM은 8 KiB뿐이었다. 상태 하나를 표현할 때도 “이 값은 몇 비트면 충분한가”를 계속 계산해야 했다. 이때의 비트 패킹은 멋이 아니라 생존이었다.

2. 설계의 제약: 32비트가 생겨도 비트를 쪼갠 이유

그다음 포켓몬은 GB(Game Boy)에서 GBC(Game Boy Color)로 넘어갔다. 2세대 골드/실버의 작업 RAM은 32KiB로, 초대 게임보이의 8KiB보다 4배 늘어났다.

하지만 기본 상태이상 바이트는 거의 변하지 않았다. 수면은 여전히 하위 3비트, 독·화상·얼음·마비는 각각 1비트였다. 맹독도 아직 이 바이트 안으로 들어오지 않았다. 일반 독 여부는 PSN 비트가 들고, “이 독이 맹독인가”는 SubStatus5의 SUBSTATUS_TOXIC 비트가 들며, 누적 횟수는 wPlayerToxicCount와 wEnemyToxicCount라는 별도 카운터가 센다.

github.com

pokegold/constants/battle_constants.asm at master · pret/pokegold

Disassembly of Pokémon Gold/Silver. Contribute to pret/pokegold development by creating an account on GitHub.

; wPlayerSubStatus5 or wEnemySubStatus5 bit flags
	const_def
	const SUBSTATUS_TOXIC
	const_skip
	const_skip
	const SUBSTATUS_TRANSFORMED
	const SUBSTATUS_ENCORED
	const SUBSTATUS_LOCK_ON
	const SUBSTATUS_DESTINY_BOND
	const SUBSTATUS_CANT_RUN

실제로 2세대 포켓몬 코드를 보면 알 수 있다.

여기서 중요한 것은 “RAM이 4배로 늘었는데도 왜 여전히 이런 식인가”다.
일본의 포켓몬 개발자가 밝힌 적이 없어 자세한 것은 알 수 없으나, 개인적으로 추측하건데, 엔진 코드를 직계로 물려받아서 그런게 아닐까 한다.
거기에 더해서 골드/실버와 같은 2세대와 레드/그린/블루같은 1세대는 타임캡슐로 교환할 수 있어야하기에 데이터들의 형식이 비슷할수록 추후 구현에 유리했을 것이다.
물론 2세대 포켓몬이나 2세대 기술을 배운 포켓몬은 보낼 수 없었다. 1세대가 이해할 수 있는 데이터만 통과해야 했기 때문이다.

그리고 결국 한번 박제된 데이터 레이아웃은 사실상 '하드코딩된 API 명세'가 된다.
레이아웃을 바꾸는 순간 1세대의 데이터가 2세대로 넘어오며 시스템은 붕괴한다. 이것이 우리가 현업에서 겪는 '레거시의 늪'이자, 과거의 제약이 미래의 계약이 되는 순간이다.

그리고 GBA로 2002년 루비 사파이어가 발매된다.

github.com

pokeruby/include/constants/battle.h at master · pret/pokeruby

Decompilation of Pokémon Ruby/Sapphire. Contribute to pret/pokeruby development by creating an account on GitHub.

pret의 pokeruby include/constants/battle.h를 보면 상태이상 워드가 이렇다.

// Non-volatile status conditions
// These persist remain outside of battle and after switching out
#define STATUS1_NONE             0
#define STATUS1_SLEEP            (1 << 0 | 1 << 1 | 1 << 2) // 수면 턴수
#define STATUS1_SLEEP_TURN(num)  ((num) << 0) // Just for readability (or if rearranging statuses)
#define STATUS1_POISON           (1 << 3)
#define STATUS1_BURN             (1 << 4)
#define STATUS1_FREEZE           (1 << 5)
#define STATUS1_PARALYSIS        (1 << 6)
#define STATUS1_TOXIC_POISON     (1 << 7)
#define STATUS1_TOXIC_COUNTER    (1 << 8 | 1 << 9 | 1 << 10 | 1 << 11)
#define STATUS1_TOXIC_TURN(num)  ((num) << 8)

GBA의 STATUS1은 32비트다. 그런데 하위 비트 배치는 게임보이의 1바이트 상태 바이트를 거의 그대로 가져온다.

비트 0~2는 수면 턴수,
비트 3~6은 독·화상·얼음·마비다.
달라진 것은 비트 7에 맹독 여부가 들어가고, 비트 8~11에 맹독 누적 카운터가 들어갔다는 점이다.

그런데 이 status1 필드는 u32다. 실제로 쓰는 것은 비트 0~11, 즉 12비트뿐이고 상위 20비트는 비어 있다. GBA의 EWRAM은 256KiB로, 초대 게임보이의 8KiB보다 32배 크다. 즉 이 시점의 패킹은 더 이상 “한 바이트라도 아껴야 해서”만으로 설명되지 않는다. 20비트를 놀릴 만큼 여유가 있는데도, 여전히 상태는 비트 단위로 쪼개져 있다.

여기서 비트 패킹의 성격이 바뀐다. 초대 포켓몬의 패킹이 8KiB RAM 안에 데이터를 밀어 넣기 위한 생존 기술이었다면, 루비/사파이어의 패킹은 상태를 하나의 워드 안에서 다루기 위한 레이아웃에 가깝다. 수면 턴수, 독, 화상, 얼음, 마비, 맹독 여부, 맹독 누적 횟수가 모두 STATUS1이라는 한 워드 안에 들어온다.

실제로 맹독 데미지를 처리하는 코드를 보면 이 의도가 더 분명해진다. 루비/사파이어의 턴 종료 처리에서는 맹독 데미지를 이렇게 계산한다. 원문 전체가 아니라 핵심만 줄이면 다음과 같다.

case ENDTURN_BAD_POISON:  // toxic poison
    if ((gBattleMons[gActiveBattler].status1 & STATUS1_TOXIC_POISON)
        && gBattleMons[gActiveBattler].hp != 0)
    {
        gBattleMoveDamage = gBattleMons[gActiveBattler].maxHP / 16;

        if (gBattleMoveDamage == 0)
            gBattleMoveDamage = 1;

        if ((gBattleMons[gActiveBattler].status1 & STATUS1_TOXIC_COUNTER)
            != STATUS1_TOXIC_TURN(15)) // not 16 turns
            gBattleMons[gActiveBattler].status1 += STATUS1_TOXIC_TURN(1);

        gBattleMoveDamage *=
            (gBattleMons[gActiveBattler].status1 & STATUS1_TOXIC_COUNTER) >> 8;

        BattleScriptExecute(BattleScript_PoisonTurnDmg);
        effect++;
    }

    gBattleStruct->turnEffectsTracker++;
    break;

gBattleMoveDamage = gBattleMons[gActiveBattler].maxHP / 16;을 보면 맹독의 기본 피해량을 최대 HP의 1/16로 잡는다. 그다음 STATUS1_TOXIC_COUNTER를 검사한다. 이 마스크는 비트 8~11만 남긴다. 값이 STATUS1_TOXIC_TURN(15)가 아니면, 즉 카운터가 아직 15에 도달하지 않았다면 STATUS1_TOXIC_TURN(1)만큼 더한다. STATUS1_TOXIC_TURN(n)은 n << 8이므로, 실제로는 비트 8~11에 들어 있는 작은 숫자를 하나 올리는 셈이다.

마지막 줄이 이 레이아웃의 핵심이다.

(gBattleMons[gActiveBattler].status1 & STATUS1_TOXIC_COUNTER) >> 8
먼저 & STATUS1_TOXIC_COUNTER로 비트 8~11만 꺼낸다.
하지만 그 값은 아직 8비트 왼쪽으로 밀려 있다.
그래서 >> 8로 다시 오른쪽으로 당겨서 실제 턴 수로 바꾼다.
그리고 그 값을 최대 HP의 1/16에 곱한다. 1턴째는 1/16, 2턴째는 2/16, 3턴째는 3/16이 된다.
이 과정에서 '4비트인가'에 대한 답을 유추할 수 있다.

왜 하필 4비트인가. 맹독의 누적 데미지는 무한정 커질 수 없다. 4비트가 할당된 이유는 0에서 15까지면 충분하다.
체력 회복이 진행되지 않는다면, 6/16의 데미지를 먹는 6번째 턴에 21/16 데미지를 입어 쓰러지고, 일반적인 회복기를 고려한다해도 15턴이면 차고 넘친다.

코드 역시 15에서 포화(Saturate)되도록 막아두어, 카운터가 더 커져 상위 비트를 침범하는 사고를 원천 차단한다.

결국 비트의 폭은 담아야 할 값의 범위(Domain Range)가 결정한다. 참/거짓이면 1비트면 충분하고, 0~15의 숫자가 필요하면 정확히 4비트가 필요하다.
4비트는 포켓몬 한마리를 중독시켜 포켓몬 센터로 보내는데 충분한 범위인 것이다.

그래서 이 단계의 제약은 공간의 제약이 아니다. 레이아웃의 제약이다. 한때 RAM 부족 때문에 시작된 비트 배치가, 메모리가 넉넉해진 뒤에는 상태를 표현하고 접근하는 방식 자체로 살아남은 것이다.

레이아웃은 한번 직렬화 포맷과 통신 프로토콜에 박히면 쉽게 못 바꾼다. 비트 위치 하나를 옮기는 순간 세이브 호환과 통신 호환이 깨지기 때문이다. 8 KiB의 강제로 시작된 레이아웃이, 제약이 사라진 뒤에도 기술 부채이자 계약으로 살아남았다.
실제로 우리는 살면서 기존의 관습을 개선할 수 있음에도 불구하고 충분히 잘 동작하기때문이라는 이유로 쓰는 경우가 잦다.
혹자는 관습의 제약이라고도 부르겠지만, 필자는 설계의 제약이라고 하고 싶다.

3. 대역폭의 제약: 캐시 라인을 위한 패킹 (현대)

세 번째 제약은 무엇일까?
메모리는 남아돈다. 대신 CPU와 메모리 사이의 속도 격차가 병목이 됐고, 그 격차를 메우는 게 캐시다.

CPU는 메모리를 64바이트 캐시 라인 단위로 읽는다.
필요한 데이터가 캐시에 없으면(캐시 미스) 메인 메모리까지 다녀와야 하고, 그건 수백 사이클짜리 지연이다. 캐시 라인이 어떻게 동작하고 왜 데이터 레이아웃이 성능을 가르는지는 Ulrich Drepper의 "What Every Programmer Should Know About Memory"가 고전적으로 정리해 뒀다.

너무 풀어쓰면 글이 늘어지니까 짧게 설명하자면, CPU가 데이터를 가져올때 데이터가 촘촘할수록(밀도가 높을수록) 한 번의 캐시 라인 로드에 더 많은 유효 정보가 실린다. 반대로 데이터가 듬성듬성 흩어져 있으면, 캐시 라인 속엔 '쓸모없는 공백'만 가득해지고 CPU는 하릴없이 메인 메모리를 들락거리며 수백 사이클을 허비한다. 비트 패킹은 CPU가 한번 메모리를 가져 올 때 얼마나 유효한 데이터를 전달해 주는지 방식인 것이다

이것도 포켓몬으로 가져오면 좋겠지만, 스위치 세대(소드실드, 스칼렛바이올렛)는 공식 디컴파일이 없어 상태이상이 여전히 비트필드 워드인지 평범한 필드로 풀렸는지 알 수 없기에 현대 게임 엔진의 변화를 통해 비트패킹의 변화를 보자.

게임·시뮬레이션 쪽 데이터 지향 설계(DOP)와 ECS도 동기가 같다.

github.com

entt/src/entt/entity/entity.hpp at main · skypjack/entt

Gaming meets modern C++ - a fast and reliable entity component system (ECS) and much more - skypjack/entt

현대 C++ ECS 라이브러리 EnTT는 엔티티 식별자를 두 필드로 풀지 않고 정수 하나에 id와 version을 비트로 함께 넣는다.

[[nodiscard]] static constexpr value_type construct(
    const entity_type entity,
    const version_type version
) noexcept
{
    if constexpr(Traits::version_mask == 0u) {
        return value_type{entity & entity_mask};
    } else {
        return value_type{
            (entity & entity_mask)
            | (static_cast<entity_type>(version & version_mask) << length)
        };
    }
}

이 코드는 포켓몬의 STATUS1_TOXIC_COUNTER와 같은 방식을 쓴다. entity & entity_mask로 id 영역만 남기고, version & version_mask를 length만큼 왼쪽으로 밀어 상위 비트에 넣는다. 꺼낼 때도 마찬가지다. id는 마스크로 꺼내고, version은 시프트와 마스크로 꺼낸다.

우리가 흔히 객체 지향 관습대로 isPoisoned, toxicTurnCount 같은 필드를 객체마다 흩뿌려 두면 접근마다 캐시 미스가 터질 수 있다.
상태 플래그 여럿과 카운터를 한 워드에 패킹해 두면 한 번의 캐시 라인 로드와 비트 마스킹으로 상태를 판별할 수 있고, 경우에 따라 SIMD 같은 병렬 처리 전략으로 이어질 여지도 생긴다.
Eric Raymond가 "The Lost Art of Structure Packing"에서 짚은 그대로 불리언을 1비트로 모으면 약간의 접근 비용이 붙지만 그 비용은 줄어든 캐시 미스에 묻힌다.
Mike Acton의 CppCon 2014 "Data-Oriented Design and C++"은 게임 엔진에서 데이터 배치가 성능을 얼마나 크게 바꿀 수 있는지 보여준다.

정리하면 이렇다. 1996년의 게임보이는 8KiB RAM에 데이터를 넣기 위해 비트를 깎았다. 하지만 2002년의 루비/사파이어는 그 상태 표현을 32비트 STATUS1 안으로 접어 넣었다.
현대의 게임 엔진과 ECS는 캐시 라인 안에 더 많은 유효 정보를 태우기 위해 다시 비트를 깎는다.

기법은 같다. 마스크, 시프트, 작은 필드.
프로그래밍 기법들을 보면 항상 최소 단위로 쪼개면 쉬워보인다.
하지만 이 최소단위로 쪼개고 그 방법을 현대화하는 것은 늘 어렵다.

포켓몬의 상태이상 비트필드와 EnTT의 엔티티 식별자는 전혀 다른 시대와 전혀 다른 문제를 다룬다. 하지만 기계어에 가까운 층에서 보면 같은 문법을 공유한다. 작은 값들을 하나의 워드 안에 배치하고, 마스크와 시프트로 꺼내 쓴다. 메모리 공간이 부족해서가 아니라, 데이터가 놓인 방식이 실행 비용을 결정하기 때문이다.
이렇게 말하면 과거의 개발자의 방식만이 옳다라고 생각하지만, 사실 꼭 그렇지만은 않다.

(옛날 개발자는 개쩔었지만, 요즘 개발자는 멍청하다는 밈)

현대의 멀티코어 환경에서는 '밀도'가 오히려 독이 되기도 하기때문이다.

CPU 캐시는 데이터를 64바이트 단위의 '캐시 라인'으로 통째로 관리한다. 만약 여러 스레드가 동시에 실행되는데, 서로 다른 코어에서 수정하는 필드들이 공교롭게도 같은 캐시 라인에 옹기종기 모여 있다면 어떻게 될까? 논리적으로는 서로 다른 필드임에도 불구하고, 한쪽이 값을 쓰는 순간 해당 캐시 라인 전체가 무효화된다. 이른바 '거짓 공유(False Sharing)' 현상이다.

비트 패킹은 읽기 위주의 단일 스레드 순회에서는 '데이터 밀도'를 높여 압도적인 성능을 내지만, 멀티 스레드 환경에서는 정반대의 전략이 필요하다. 이때는 오히려 패킹을 풀어헤치고, 핫 필드를 alignas(64)와 같은 지정자로 아예 다른 캐시 라인에 떼어 놓아야 한다.

결국 "비트 단위로 빡빡하게 몰아넣어 캐시 적중률을 높일 것인가" 혹은 "스레드 경합을 피하기 위해 캐시 라인 단위로 데이터를 격리할 것인가"는, 데이터가 어떤 경로(Access Pattern)로 흐르느냐에 따라 결정되는 아키텍트의 정교한 판단 영역이다.

결론

처음에는 공간이었다.
게임보이의 8KiB RAM 안에서 수면 턴수와 상태이상을 표현하려면, 1바이트 안의 비트 하나하나를 계산해야 했다. 독은 1비트면 충분했지만, 수면은 턴 수가 필요했기에 3비트가 필요했다. 맹독은 독 여부만으로는 부족했고, 누적 턴수를 세는 별도 카운터가 필요했다. 이때의 비트 패킹 생존을 위한 발버둥이었다.

그다음에는 레이아웃이었다.
골드/실버로 넘어가며 RAM은 늘어났지만, 기본 상태이상 바이트는 초대의 형태를 거의 그대로 유지했다. 루비/사파이어에서는 STATUS1이 32비트가 되었고, 맹독 여부와 맹독 카운터까지 그 안으로 접혀 들어갔다. 상위 20비트가 비어 있는데도 상태는 여전히 비트 단위로 배치됐다. 이 시점의 패킹은 더 이상 순수한 용량 절약이 아니었다. 누군가는 관성이라고 할 수 있지만, 코드가 상태를 이해하는 방식이라는 점에서 그것은 레이아웃의 문제였다.

현대에는 대역폭이다.
메모리는 커졌지만 CPU와 메모리 사이의 거리는 여전히 비싸다. 현대 게임 엔진과 ECS는 수많은 엔티티를 매 프레임 훑는다. 이때 데이터가 캐시 라인 안에 얼마나 촘촘하게 들어가느냐가 성능을 가른다. EnTT가 엔티티 id와 version을 하나의 정수 안에 넣는 것도 같은 계열의 판단이다. 작은 값을 한 워드 안에 배치하고, 마스크와 시프트로 꺼내 쓴다.

그렇다고 사라진 제약 때문에 비트를 깎고 있다면 그것은 카고 컬트다.
캐시가 병목인데 데이터를 느슨하게 흩뿌리고 있다면 성능을 흘리는 것이다.
여러 스레드가 같은 캐시 라인을 두고 다투는데 더 촘촘하게 몰아넣고 있다면 거짓 공유로 자멸할 수 있다.

결국 제약에 따라 다르게 설계 되야한다.

나는 프로그래머의 사고방식이란 무얼까 항상 고민한다.
그리고 이 글을 쓰면서 나름의 결론을 내보았다. 일단 글을 끝내야하니까.
나에게 프로그래머의 사고방식은 이러하다.
나에게 주어진 제약이 무엇이고, 그 환경 내에서 최적의 해를 내는 발버둥의 방식

어쩌면 그게 프로그래머의 자세가 아닐까?

참고

• Eric S. Raymond, "The Lost Art of Structure Packing" (catb.org/esr/structure-packing) — 정렬·패딩과 비트필드 패킹의 사실상 표준 레퍼런스.

• Ulrich Drepper, "What Every Programmer Should Know About Memory" (LWN, 2007; lwn.net/Articles/250967) — 캐시 라인이 어떻게 동작하고 왜 데이터 레이아웃이 성능을 가르는지에 대한 고전. 5장 캐시 주장의 근거.

• Mike Acton, "Data-Oriented Design and C++", CppCon 2014 (youtube.com/watch?v=rX0ItVEVjHc) — 데이터를 캐시 라인에 맞게 구조화해 게임 엔진에서 속도를 끌어올리는 DOP 강연.

• 포켓몬 코드 참조 pret의 깃허브

  github.com

  pret

  pret has 30 repositories available. Follow their code on GitHub.