게임 프로그래밍 개념 정리

Kyu_·어제

개인공부

목록 보기

4/4

게임 프로그래밍 개념 정리

성능 병목 분석, 멀티스레딩, 네트워크 위치 동기화, 객체 설계, std::vector 삭제 전략, 메모리 할당과 캐시 지역성을 한 번에 정리한 글이다.

CPU / GPU 병목 분석

목표

Frame Time 확인 -> Game / Draw / GPU 중 무엇이 프레임을 제한하는지 확인 -> 해당 영역을 더 깊게 프로파일링 -> 가설을 실험으로 검증

질문

프레임 드랍이 발생했을 때 CPU 병목인지 GPU 병목인지 어떻게 판단할 것인가?

처음에는 CPU/GPU 전체 사용률이나 Draw Call 수부터 보게 되기 쉽지만, 이것만으로 병목을 판정하면 오해하기 쉽다. 먼저 stat unit 등으로 Frame / Game / Draw / GPU 시간을 비교하고, 프레임을 제한하는 영역을 특정한 뒤 세부 프로파일링으로 내려가는 편이 안전하다.

주의할 점

8코어 16스레드 CPU에서

Game Thread의 하나만 완전히 바빠서

Game Thread : 100%
나머지 스레드 : 대부분 놀고 있음

이라고 하면 작업 관리자에서 CPU 전체 사용률은 낮게 보일 수 있다.

그런데 한 프레임이 Game Thread 완료를 기다린다면 게임은 명백히 CPU 병목이다.

즉,

CPU 전체 사용률 30%
    ↓
CPU 여유 있음

이라고 판단하면 안 된다.

대부분 CPU 병목도 일반화하면 안 되는 이유는 게임과 장면에 따라 완전히 달라진다.

오브젝트/AI/물리가 많으면 CPU 쪽일 가능성이 있고, 높은 해상도/복잡한 셰이더/Lumen/그림자/후처리/오버드로우 등이 크면 GPU 쪽일 가능성이 있다.

FPS보다 먼저 Frame Time을 본다.

60FPS를 목표로 한다 했을 때

1초 = 1000ms 이므로 한 프레임을 16.67ms안에 끝내야 60FPS가 가능하다.

즉, 어떤 단계가 16.67ms를 넘기고 있지? 라고 생각하는게 프로파일링에 더 적합하다.

CPU Time + GPU Time을 더하면 Frame Time인가?

CPU와 GPU는 상당 부분 병렬로 작업한다.

시간 ────────────────────────────────>
CPU
Frame N+1 준비
████████████████          10ms
GPU
Frame N 렌더링
████████████████████████  15ms

요런 느낌이라서 대체로 느린쪽이 throughput을 제한한다.

CPU와 GPU가 파이프라인으로 겹쳐 실행되는 정상적인 steady-state 상황에서는 프레임 처리량이 대체로 가장 느린 단계에 의해 제한된다고 이해하면 좋다. 다만 동기화, Present/VSync, RHI 작업, 프레임 큐잉과 같은 요소가 있으므로 FrameTime = max(CPU, GPU)를 항상 성립하는 수학적 등식처럼 사용하면 안 된다.

예시

몬스터가 500마리가 있는 전투에서 언리얼의 stat unit을 실행했더니

Frame : 24 ms
Game  : 23 ms
Draw  : 7 ms
GPU   : 10 ms

라고 나와있다고 치면 게임 스레드 병목일 가능성이 크다.

따라서 이 상황에 그림자 옵션을 낮춘다 라고 하면 해결이 안 될 가능성이 크다.

이때는 Unreal Insights 등을 열어서 게임 스레드에서 무엇이 시간을 먹는지 내려가야 한다.

CPU 사용률이 낮다고 해서 무조건 CPU 병목이 없다고는 할 수 없다

전체 CPU 사용률이 낮아도 Game Thread나 Render Thread 하나가 프레임 예산을 초과하면 CPU 병목이 될 수 있다.

stat unit의 Draw는 CPU의 Render Thread 시간을 의미한다. GPU 시간과는 별개의 값이다.

GPU 병목 확인에 좋은 실험 - 해상도 낮추기

해상도를 낮춰서 GPU가 그릴 픽셀 수를 줄였을 때

2560 × 1440
Frame : 24ms
Game  : 8ms
Draw  : 7ms
GPU   : 23ms
-> 해상도 낮춘 후
Frame : 14ms
Game  : 8ms
Draw  : 7ms
GPU   : 13ms

GPU Time이 현저히 줄어서 FrameTime이 줄었다면 GPU 쪽 작업이 병목임을 확인할 수 있다.

차이가 거의 없다면 CPU 병목을 의심할 수 있다. 다만 GPU 병목이라도 지오메트리 처리, 레이 트레이싱, 고정 비용이 큰 패스처럼 해상도 변화에 덜 민감한 원인이 있을 수 있으므로, 해상도 실험만으로 CPU 병목이라고 확정하지는 않는다.

더 심화로 가면 GPU프로파일러로 어떤 pass가 비싼지 확인하고 원인에 따라 Shadow, Material, Overdraw, Resolution등을 조사한다.

멀티스레딩

질문

입력, 물리, 렌더링 등이 서로 다른 스레드에서 돌아가며 같은 게임 상태에 접근하면 어떤 문제가 생기는가?

여러 스레드가 같은 메모리 위치에 충돌하는 접근을 하고, 그중 하나 이상이 쓰기이며, 두 접근 사이에 적절한 happens-before 관계가 없고 원자적 접근도 아니라면 Data Race(데이터 레이스/데이터 경쟁)가 발생한다.

C++에서 Data Race는 Undefined Behavior(정의되지 않은 동작)이다.

게임에서는 이런 문제를 줄이기 위해 공유 게임 상태의 실제 변경은 Game Thread가 담당하고, Worker Thread는 무거운 계산만 수행하도록 역할을 분리하는 구조를 사용할 수 있다. 다만 이것은 한 가지 설계 방식이며, 데이터 소유권을 분리할 수 있다면 Worker가 자신이 소유한 파티션을 직접 갱신하는 구조도 가능하다.

기본 구조

예를 들어 몬스터 1000마리의 AI를 모두 Game Thread에서 계산하면

Game Thread
Enemy 1 AI 계산
Enemy 2 AI 계산
Enemy 3 AI 계산
...
Enemy 1000 AI 계산

모든 계산이 직렬로 실행되기 때문에 Game Thread 병목이 발생할 수 있다.

그래서 계산 작업을 Worker Thread에 분배할 수 있다.

Worker 1 → Enemy 1~250
Worker 2 → Enemy 251~500
Worker 3 → Enemy 501~750
Worker 4 → Enemy 751~1000

하지만 Worker Thread가 직접 World State를 수정하면 여러 스레드가 같은 상태를 건드리면서 동기화가 복잡해진다.

한 가지 흔한 설계는 Worker에서는 가능한 한 계산만 수행하고, 공유 World State의 최종 변경은 소유권이 명확한 스레드에서 처리하는 것이다.

Worker Thread
Enemy 27의 AI 계산
        ↓
결과 생성
EnemyId = 27
Target = B
DesiredVelocity = ...

계산 결과를 모아두고

Worker Threads
      ↓
Result Buffer
      ↓
Game Thread
      ↓
실제 게임 상태 변경

Game Thread가 실제 상태를 적용한다.

Result Buffer / Command Queue

둘 다 Worker가 만든 내용을 Game Thread에 전달하기 위한 방법이다.

Result Buffer

Worker가 계산 결과 데이터를 저장한다.

struct FAIResult
{
    int EnemyId;
    int TargetId;
    FVector DesiredVelocity;
};

예:

[Enemy 1의 AI 결과]
[Enemy 2의 AI 결과]
[Enemy 3의 AI 결과]
...

Game Thread가 나중에 이 결과를 읽어서 실제 상태를 변경한다.

Command Queue

결과 데이터 대신 실행해야 할 명령을 저장하는 방식이다.

Move Enemy 1
Change Target Enemy 2
Attack Enemy 3

즉:

Result Buffer
= "계산 결과가 이것이다."
Command Queue
= "이 작업을 실행해라."

그러면 왜 Game Thread가 다시 병목이 될 수 있는가?

Worker Thread를 사용했다고 해서 Game Thread의 일이 없어지는 것은 아니다.

예를 들어 Worker가 병렬로 AI를 계산해서:

AI 계산 전체 = 4ms

밖에 걸리지 않았다고 하자.

하지만 결과 100,000개를 Game Thread가 하나씩 적용한다면:

Game Thread
결과 1 적용
결과 2 적용
결과 3 적용
...
결과 100,000 적용

이 작업에 20ms가 걸릴 수도 있다.

그러면:

Worker 계산       4ms
Game Thread 적용 20ms

결국 Game Thread의 직렬 구간이 새로운 병목이 된다.

병렬 계산을 빠르게 만들더라도 최종 상태 변경을 하나의 스레드에서 대량으로 처리하면 그 Commit 단계가 병목이 될 수 있다.

Batch Commit

이때 고려할 수 있는 것이 Batch Commit이다.

결과를 받을 때마다 하나씩 바로 반영하는 대신:

Worker 결과
Worker 결과
Worker 결과
Worker 결과
      ↓
결과들을 모음
      ↓
Game Thread에서 묶어서 처리

하는 방식이다.

예를 들어 여러 변경을 개별 함수 호출, 이벤트 전달, 동기화와 함께 처리하는 대신 시스템이 지원한다면 여러 변경을 모아서 한 번에 처리하여 반복되는 부가 비용을 줄일 수 있다.

중요한 점은

Batch Commit이 100,000개의 실제 작업 자체를 없애주는 것은 아니다.

실제로 반드시 해야 하는 상태 변경 자체가 20ms 걸린다면 Batch 처리만으로 해결되지 않을 수도 있다.

그 경우에는 Game Thread에서 수행해야 하는 작업 자체를 줄이거나 다른 구조를 고려해야 한다.

흐름

전체 흐름은 이것만 먼저 기억하면 된다.

Game State
    ↓ 읽기
Worker Threads
    ↓
병렬 계산
    ↓
Result Buffer
    ↓
Game Thread
    ↓
Batch Commit
    ↓
실제 상태 변경

추가적인 개념

Snapshot

Worker가 AI를 계산하는 동안 Game Thread가 Worker가 읽는 데이터를 변경하면 어떻게 하는가?

예를 들어

Worker
Player Position 읽음
동시에
Game Thread
Player Position 변경

이런 공유 접근을 피하기 위해 Worker에게 계산 시점의 읽기 전용 상태 복사본을 제공할 수 있다.

Game State
    ↓
Snapshot
    ↓
Workers가 읽기만 함

Snapshot은 Worker에게 계산 동안 변경되지 않는 입력 뷰를 제공하기 위한 방법이다.

복사본의 수명과 불변성이 보장되어야 하며, Snapshot 생성 비용과 한 프레임 정도 오래된 데이터를 사용할 수 있다는 점도 고려해야 한다.

Batch Commit과 목적이 다르다.

Snapshot
= 계산 전에 사용할 입력 데이터 관리
Batch Commit
= 계산이 끝난 후 결과 적용 관리

Double Buffering

Snapshot을 운용하는 방법 중 하나다.

두 개의 버퍼를 두고

Buffer A → 현재 쓰기
Buffer B → Worker가 읽기

다음 시점에 역할을 바꾼다.

A ↔ B

그러면 읽는 데이터와 쓰는 데이터를 분리할 수 있다. 단, 버퍼 역할을 교체할 때는 이전 Reader가 모두 사용을 끝냈는지 확인하는 동기화가 필요하다.

Double Buffering = 읽기용/쓰기용 데이터를 두 벌 두고 안전한 시점에 역할을 교체하는 방식

Synchronization Point / Barrier

Game Thread는 Worker 계산이 끝났다는 것을 어떻게 알고 결과를 적용하는가?

예를 들어

Worker 1 ── 완료
Worker 2 ───── 완료
Worker 3 ───────── 완료
                  ↓
             모두 완료 확인
                  ↓
              Commit

Game Thread가 Worker들의 작업 완료를 기다리는 지점이 Synchronization Point다.

Barrier는 여러 작업이 특정 지점까지 모두 도착해야 다음 단계로 넘어가도록 만드는 동기화 방식이다.

단점도 있다.

Worker 1 = 2ms
Worker 2 = 2ms
Worker 3 = 8ms

이면 앞의 Worker들도 결국 가장 느린 Worker 3이 끝날 때까지 기다려야 한다.

State Partitioning

Game Thread에서 결과를 적용하는 구조 자체가 계속 병목이면 어떻게 할 것인가?

한 가지 더 근본적인 방법은 공유 상태 자체를 줄이는 것이다.

예

Worker A → Enemy 1~100 상태 담당
Worker B → Enemy 101~200 상태 담당

서로 같은 상태를 수정하지 않도록 데이터 소유권을 나누는 것이다.

엔진 구조가 허용한다면 각 Worker가 자신이 소유한 파티션을 직접 갱신하게 하여 하나의 중앙 Commit 단계에 몰리는 작업을 줄일 수 있다. 다만 Unreal Engine의 UObject/Actor 관련 작업처럼 Game Thread 제약이 있는 API는 단순히 파티션만 나눈다고 Worker에서 안전하게 수정할 수 있는 것은 아니다.

State Partitioning은 Game Thread 병목이나 Lock 경쟁을 줄이기 위해 상태의 소유권 자체를 나누는 구조적 해결책이다.

네트워크 위치 동기화

Server Authority / Client Prediction / Reconciliation

왜 이런 구조가 필요한지 -> 각 단계가 무슨 역할인지 -> 서로 어떻게 연결되는지

질문

서버와 클라이언트의 플레이어 위치가 자주 어긋난다면 어떻게 처리할 것인가?

-> 클라이언트는 자신의 입력을 로컬에서 즉시 시뮬레이션하고, 서버도 같은 이동 정보를 권위 있게 시뮬레이션한다. 서버 결과와 차이가 생기면 클라이언트는 서버 상태를 기준으로 보정하고 아직 확인되지 않은 이동을 다시 적용한다.

클라이언트 예측을 사용하면서도 서버 권한을 유지하고 플레이 감각을 해치지 않으려면?

-> 서버는 이동 입력과 결과를 검증해 권위를 유지하고, 클라이언트는 Prediction과 Reconciliation을 사용한다. 화면에서는 Smoothing을 적용해 작은 보정이 순간이동처럼 보이지 않도록 한다.

중요점

클라이언트가 서버에 무엇을 보내는지
서버가 무엇을 돌려주는지
클라이언트가 과거 입력을 어떻게 다시 적용하는지

개념

왜 서버 위치만 따라가면 안 되나?

네트워크 지연때문이다.

클라이언트 입력 → 서버에서 이동 계산 → 권위 상태가 다시 클라이언트에 도착 → 화면 반영

이 구조만 사용하면 입력 반응이 네트워크 왕복 지연과 서버/전송 주기의 영향을 받는다. 예를 들어 RTT가 약 100ms라면 체감 입력 지연이 매우 커질 수 있다.

그래서 자기 캐릭터는 서버 응답을 기다리지 않고 즉시 움직인다. 이게 Client-Side Prediction 클라이언트 예측이다.

Client-side Prediction

클라이언트에서

W 입력
↓
"앞으로 이동할 거라고 예상"
↓
화면에서 즉시 이동

동시에 서버에도 이동에 필요한 데이터를 보낸다. 개념적으로는 서버가 클라이언트의 최종 위치를 그대로 신뢰하는 것이 아니라 입력/가속도/타임스탬프 등의 이동 정보로 서버에서 다시 시뮬레이션하고 검증하는 구조라고 이해하는 것이 중요하다. Unreal의 CharacterMovementComponent는 이동 정보와 함께 클라이언트의 결과 위치도 전송해 서버 계산 결과와 비교한다.

Server Authority

클라이언트가 제 위치는 X=5000입니다 라고 보냈다고 해서 서버가 그냥 믿으면 치트를 막을 수가 없다.

일반적으로 서버가 최종 정답을 가진다.

이게 Server Authority의 핵심

클라이언트와 서버의 차이가 생기는 이유

클라이언트는 플레이어 위치를 100이라고 예상했는데 서버에서는 95라고 계산을 했다 왜그럴까?

패킷 지연/손실, 충돌 판정 차이, 서버에서만 알고있는 상태, 이동 속도 변경, 다른 플레이어와 충돌, 서버 검증 결과 등이 있다.

서버상태가 오면 클라이언트는 맞춰야 한다 이를 Reconciliation

이때 Rubber Banding 같은 튀는 현상이 발생한다.

Input Sequence Number

여기서 Sequence Number가 나온다.

클라이언트는 입력마다 번호를 붙인다.

101 : 앞으로
102 : 앞으로
103 : 오른쪽
104 : 앞으로

그리고 서버에 전송

서버는 타임스탬프나 시퀀스 정보로 이동의 순서와 유효성을 판단하고 처리한다. 패킷은 지연·중복·유실될 수 있으므로 단순히 "도착한 순서"를 신뢰한다는 뜻은 아니다.

101 처리
102 처리
103 처리
...

그리고 응답할때

현재 위치 = 95
현재 Input #102까지 처리했다.

라고 알려준다. 이를 Acknowledgement, 줄여서 ACK라고 한다.

ACK의 필요성

클라이언트에서는 104까지 전부 예측해서 화면에서 반영했는데 서버에서 ACK가 102로 왔다. 그러면 101, 102는 끝난 입력이라 버려도 되지만 103, 104는 아직 서버가 처리하지 않은 입력이다 이를 Unacknowledged Input이라고 한다.

Reconciliation의 핵심

클라이언트는 ACK을 받으면

1. 위치를 서버 위치 95로 되돌림
2. ACK된 입력 제거 (101, 102 제거)
3. 아직 ACK 안 된 입력 재적용 (103, 104)
즉,
Client Prediction
        ↓
Server Position으로 rewind
        ↓
미확인 입력 replay
        ↓
최신 Client Position 구성

즉 서버 결과를 받아도 그 순간 이후에 클라이언트가 입력한 것 까지 버리지는 않는다.

Smoothing

현재 위치 100 -> 서버 보정 결과 95로 한번에 이동하면 순간이동처럼 보인다.,

그래서 작은 차이는 보통 여러 프레임에 걸쳐 천천히 보정한다.

이를 Smoothing이라고 한다.

Reconciliation은 논리적인 상태를 서버와 맞추는 것

Smoothing은 그 보정을 화면에서 덜 거슬리게 보여주는 것

Interpolation

다른 플레이어를 보여줄 때 중요하다.

내 캐릭터는 입력을 내가 알고있으니까 Prediction이 가능하다.

하지만 다른 플레이어가 다음에 어떤 입력을 할지는 모른다.

그래서 보통 서버에서 위치 Snapshot이 주기적으로 오면

t1 : 위치 10
t2 : 위치 20
이렇게 오면 렌더링 시점을 약간 과거로 지연시켜 두 Snapshot 사이를
10 → 12 → 14 → 16 → 18 → 20
처럼 보간한다.
이런 식으로 중간을 보간한다.

이게 Interpolation이다. 실제 네트워크 게임에서는 다음 Snapshot을 미리 알 수 있어야 하므로, 보통 렌더링 시점을 약간 과거로 늦춘 interpolation buffer를 둔다.

내 캐릭터 vs 다른 캐릭터

내 캐릭터

Prediction
+
Reconciliation
+
Smoothing

다른 플레이어

Server Snapshot
+
Interpolation

필요에 따라 Extrapolation을 쓸 수도 있다.

Extrapolation

예를들어 서버 패킷이 잠깐 늦었다.

마지막으로 알고 있는 정보가

위치 = 100
속도 = +10

이라면

아마 계속 같은 방향으로 가고 있겠지

라고 잠깐 미래 위치를 예측할 수 있다.

이게 Extrapolation이다.

잘못 예측하면 나중에 보정이 더 커질 수 있다.

Rubber Banding

서버와 클라이언트 차이가 크면

클라이언트
앞으로 감
↓ 서버 보정
갑자기 뒤로 끌려감

처럼 보일 수 있다.

이걸 흔히 Rubber Banding이라고 한다.

주 원인은

높은 Ping
Packet Loss
큰 Prediction Error
서버에서 이동 거부
서버 부하

서버 이동 검증

서버 권한을 유지하려면 클라이언트 입력을 무조건 믿으면 안 된다.

예를들어

예를 들어 서버가 재시뮬레이션한 결과와 클라이언트가 보고한 결과가 크게 다르거나, 현재 이동 모드에서 허용될 수 없는 변화가 발생했다면 서버가 검증하고 보정할 수 있다.

이동 속도가 허용 범위인가?
충돌을 뚫었는가?
현재 상태에서 이동 가능한가?
텔레포트 권한이 있었는가?

이상하면 서버가 거부하고 서버 위치로 보정한다.

상속, 조합, 전략 패턴

Inheritance, Composition, Strategy Pattern

질문

여러 캐릭터가 서로 다른 공격 방식을 가지고 있고 공격 방식이 계속 추가된다면 어떻게 설계할 것인가?

-> 공통 인터페이스를 만들고 각 캐릭터가 공격 방식을 구현하도록 한다.

무기 교체나 버프에 따라 런타임 중 공격 방식이 변경되어야 한다.

-> 분기를 사용하거나, 공격 방식 자체를 별도의 상위 클래스/인터페이스로 만들어 캐릭터에게 붙인다.

답변하다보니 두번째쪽 방향이 더 맞는거 같았다.

캐릭터 자체의 상속을 계속 늘리지 말고, 공격 방식만 별도 객체로 분리해서 캐릭터가 그 객체를 사용하게 한다.

이게 Composition(조합)쪽 사고고, 그 중 대표적인 형태가 전략패턴(Strategy Pattern)이다.

개념

Inheritance

A는 B의 한 종류다

is-a관계라고 한다.

class Character
{
public:
    virtual ~Character() = default;
    virtual void Attack() = 0;
};
class Warrior : public Character
{
public:
    void Attack() override
    {
        // 검 공격
    }
};

장점

공통 인터페이스를 강제할 수 있음
다형성(Polymorphism, 다형성) 사용 가능
구조가 단순할 때 이해하기 쉬움

단점

행동 변화가 타입과 강하게 결합됨
런타임 교체가 불편함
조합 경우의 수가 많아지면 클래스가 급증함

Composition

조합은

객체가 다른 객체와의 관계를 이용해 기능을 구성하는 방식

실무에서는 넓은 의미로 has-a 관계를 조합이라고 표현하는 경우가 많다. 다만 UML의 엄밀한 용어에서는 Composition은 강한 소유권과 수명 결합을 의미하고, 단순 참조는 Association/Aggregation에 더 가깝다.

class Character
{
private:
    std::unique_ptr<IAttackBehavior> AttackBehavior;
};

캐릭터가 공격 기능을 직접 구현하지 않고, 공격 동작을 별도 객체에게 맡긴다.

Character
   ↓
AttackBehavior
   ↓
SwordAttack
BowAttack
MagicAttack

Interface는 Composition인가?

Interface자체는 조합이 아니다.

인터페이스는

어떤 기능을 제공해야 하는지 약속하는 추상 계약

class IAttackBehavior
{
public:
    virtual ~IAttackBehavior() = default;
    virtual void Attack() = 0;
};

이 기능을 쓰려면 Attack()을 구현해야 한다.

Character가 인터페이스 구현 객체를 소유하고 그 수명을 함께 관리한다면 엄밀한 의미의 Composition에 가깝다. 단순 포인터/레퍼런스로 외부 객체를 참조하기만 한다면 넓은 의미의 조합 설계라고 부를 수는 있지만 UML의 Composition과는 구분하는 편이 정확하다.

class Character
{
private:
    std::unique_ptr<IAttackBehavior> AttackBehavior;
};

Interface
= 기능의 계약
Composition
= 객체가 다른 객체를 포함/참조해서 기능을 구성
Strategy Pattern
= 교체 가능한 행동을 인터페이스 뒤에 분리한 조합 설계

Strategy Pattern

Strategy Pattern은

알고리즘이나 행동의 집합을 각각 캡슐화하고, 사용하는 쪽에서 구체 구현에 덜 의존하도록 만드는 패턴

런타임 교체가 Strategy Pattern의 대표적인 장점 중 하나다.

공격 시스템에 적용하면

class IAttackBehavior
{
public:
    virtual ~IAttackBehavior() = default;
    virtual void Attack() = 0;
};

공격 방식별 구현

class SwordAttack : public IAttackBehavior
{
public:
    void Attack() override
    {
        // 근접 공격
    }
};
class BowAttack : public IAttackBehavior
{
public:
    void Attack() override
    {
        // 화살 발사
    }
};

캐릭터는

class Character
{
private:
    std::unique_ptr<IAttackBehavior> AttackBehavior;
public:
    void Attack()
    {
        if (AttackBehavior)
        {
            AttackBehavior->Attack();
        }
    }
    void SetAttackBehavior(std::unique_ptr<IAttackBehavior> NewBehavior)
    {
        AttackBehavior = std::move(NewBehavior);
    }
};

왜 이 상황에서 상속보다 나은가?

상속 기반이면

SwordCharacter
BowCharacter
MagicCharacter

처럼 캐릭터 타입 자체가 공격 방식과 묶인다.

조합기반이면 AttackBehavior만 교체하면 된다.

Virtual Dispatch

Character.SetAttackBehavior(
    std::make_unique<BowAttack>()
);
AttackBehavior->Attack()

가상 함수 디스패치는 AttackBehavior->Attack()을 호출할 때

BowAttack Bow;
IAttackBehavior* Behavior = &Bow;
Behavior->Attack();

실제 실행되는 것은 BowAttack::Attack()이다.

이게 Virtual Dispatch(가상 함수 디스패치 / 동적 디스패치)다. 개념적으로 런타임의 동적 타입에 맞는 override 함수가 선택된다. 흔히 vtable/vptr로 구현되지만 C++ 표준이 특정 구현 방식을 강제하는 것은 아니다.

Ownership / Lifetime

Character가 AttackBehavior를 가지고 있다면

누가 이 객체를 소유하고 언제 파괴할 것인가?

Character만 그 공격 방식을 소유한다면

std::unique_ptr<IAttackBehavior>

가 자연스럽다

Composition의 단점

행동을 전부 분리하면 클래스가 너무 많이 생길 수 있다.

SwordAttack
BowAttack
FireAttack
IceAttack
ChargeAttack
SpreadAttack
PoisonAttack
...

또 너무 잘게 쪼개면 오히려 구조 파악이 어려워진다는 단점이 있다.

변경 가능성이 실제로 있는 행동만 분리하는 게 중요하다

Data Driven Design과 차이

Strategy는 교체 가능한 행동/알고리즘의 구현이 다를 때 유용하다.

SwordAttack
→ 근접 충돌 검사
BowAttack
→ Projectile 생성
MagicAttack
→ 범위 탐색 후 데미지

SwordDamage = 50
BowDamage = 30
AttackSpeed = 1.2
Range = 500

로직은 같고 데미지, 속도, 사거리, 사용할 에셋, 태그 같은 설정 데이터만 다르다면 굳이 클래스를 늘릴 필요가 없다. 이런 값들을 코드 밖의 데이터로 분리하면 Data-Driven Design으로 관리하기 좋다.

로직이 다름
-> Strategy / 다른 클래스
설정 데이터만 다름
-> Data-Driven

정리

Inheritance(상속)
= 올바른 subtype 관계를 표현할 때 사용
= is-a
Composition(조합)
= 기능 객체를 붙임
= has-a
Interface(인터페이스)
= 행동 계약
Strategy Pattern(전략 패턴)
= 교체 가능한 행동을 별도 객체로 분리
Data-Driven(데이터 주도)
= 로직은 같고 설정 데이터만 다를 때

vector

먼저 바로잡을 점

비활성 객체가 많이 남아 있다고 해서 그 자체를 메모리 내부 단편화라고 부르지는 않는다. 슬롯의 Alive/Dead 상태는 논리적인 사용 상태이고, allocator의 내부 단편화는 할당된 블록 내부에 실제로 쓰이지 않는 공간이 생기는 현상이다.

게임에서 어떻게 삭제하는가?

벡터는 erase하면 원소를 앞으로 당겨오는 비용 O(N)이 발생한다.

그렇기 때문에 삭제 순서가 중요하지 않다면 가장 대표적인 방법은

Swap-and-Pop(스왑 후 제거)이다.

Enemies[Index] = std::move(Enemies.back());
Enemies.pop_back();

단점은

A B C D E
Swap and Pop후
A B E D

마지막 원소를 삭제되는 자리에 이동 대입한 뒤 마지막 원소를 제거한다. 따라서 원소 순서가 중요하지 않을 때 유용하다.

주의할 점도 있다.

삭제된 위치를 가리키던 iterator/reference는 더 이상 유효한 대상으로 취급하면 안 된다.
마지막 원소가 Index 위치로 이동했으므로, 외부에서 "원소 → Index" 매핑을 들고 있다면 그 원소의 Index를 갱신해야 한다.
Index == Enemies.size() - 1이라면 굳이 self-move를 하지 않고 pop_back()만 하는 분기를 둘 수 있다.

Tombstone 방식

죽은 몬스터를 지우지 않고 비활성화 -> Tombstone(툼스톤 / 삭제 표시) 방식

삭제하지 않고 비활성화 상태로 남겨둔다. 객체가 큰 외부 자원을 소유하고 있다면 단순히 bAlive = false만 해서는 그 자원도 계속 유지될 수 있으므로, 필요한 경우 비활성화 시 자원을 별도로 정리해야 한다.

장점

삭제가 매우 싸다.

erase
→ 뒤 원소 이동 필요
tombstone
→ bool 하나 변경

Dead가 계속 쌓이면 실제 문제는 뭘까?

쓸데 없는 메모리 사용

1000개 중 100개만 살아 있어도 900개의 죽은 Enemy공간을 유지해야 한다
Working Set(작업 집합) 증가

운영체제 용어의 Working Set은 보통 현재 물리 메모리에 상주하는 프로세스의 페이지 집합을 뜻한다. 여기서 말하고 싶은 성능 문제는 엄밀히는 "순회해야 하는 데이터 footprint와 cache working set이 커진다"는 쪽에 가깝다.

100개의 Enemy만 실제 처리 대상인데 vector의 10,000개 슬롯을 매 프레임 검사한다면 CPU는 훨씬 큰 데이터 범위를 순회하게 된다.
Cache Locality(캐시 지역성)약화
```
[Alive][Dead][Dead][Dead][Alive][Dead][Dead][Alive]
```
CPU가 Cache Line하나를 가져왔는데 실제 필요한 데이터가 하나밖에 없을 수 있다.

즉, 캐시 안에 필요한 데이터1개, Dead 데이터 여러개가 들어간다

결국 메모리가 연속이라는 vector의 장점이 약해진다.
매 프레임 검사 비용
```
if (!E.bAlive)
    continue;
```
자체는 싸지만 객체가 수십만개 라면 쓸데없는 순회 자체가 비용이다.

Free List

Tombstone의 단점을 보완하는 방법

죽은 자리의 인덱스를 따로 저장해두고

Enemies
0 Alive
1 Dead
2 Alive
3 Dead
4 Alive
FreeList = [1, 3]

다음 몬스터가 생성되면 push_back() 대신 빈 슬롯을 재사용할 수 있다. 다만 이 방식은 슬롯 Index의 안정성을 위한 것이지 std::vector 요소의 메모리 주소 안정성을 자동으로 보장하는 것은 아니다. vector가 capacity를 넘어서 재할당되면 모든 요소의 주소가 바뀔 수 있다.

새 Enemy 생성
↓
FreeList에서 3 꺼냄
↓
Enemies[3]에 재사용

Tombstone과 Free List를 함께 쓸 때

Tombstone
→ 이 슬롯 살아있음?
→ lookup / iteration / validity check
Free List
→ 비어 있는 슬롯 어디 있음?
→ allocation / reuse
Generation Counter
→ 같은 Index가 다른 객체로 재사용되었는지 구분
→ stale handle 방지

Periodic Compaction(주기적 압축)

Free List로 빈 슬롯을 재사용해도 Alive/Dead가 섞여 순회 효율이 떨어질 수 있다.

그러면 특정 시점에 살아있는 객체만 앞으로 모은다.

[A][X][B][X][X][C][X][D]
압축 후
[A][B][C][D]

이게 Compaction(압축/밀집화)이다. 다만 압축하면 요소의 Index와 주소가 바뀔 수 있으므로 외부 핸들/참조를 갱신할 수 있는 구조에서만 사용해야 한다. 또한 vector의 논리적 크기를 줄여도 capacity가 자동으로 줄어드는 것은 아니다.

어떤 방식을 언제 쓸까?

순서가 중요하지 않음 + 삭제 빈번

Swap-and-Pop

Index 안정성이 중요하고 슬롯 재사용이 필요함

Tombstone + Free List + Generation Handle

실제 메모리 주소 안정성이 중요함

std::vector는 재할당 시 모든 요소의 주소가 바뀔 수 있으므로 Tombstone만으로는 부족하다. 최대 크기를 확실히 알고 reserve()로 재할당을 막거나, 주소 안정성을 제공하는 별도 저장소/청크 기반 풀을 고려해야 한다.

Tombstone이 너무 많이 쌓임

Periodic Compaction 으로 다시 밀집

정리

vector
= 순차 접근 좋음
= Cache Locality 좋음
erase
= 뒤 원소 이동
= O(n)
Swap-and-Pop
= vector 길이 N에 대해 O(1) 삭제 (단, 원소 타입의 이동 대입 비용은 별도)
= 순서 변경됨
Tombstone
= 삭제 대신 Dead 표시
= 삭제 빠름
= Dead가 쌓이면 순회/캐시 낭비
Free List
= Dead 슬롯 재사용
Compaction
= Dead가 많이 쌓였을 때 살아있는 것만 다시 밀집
Dead가 많은 문제
≠ 메모리 단편화
실제 문제
= 메모리 footprint 증가 + CPU cache working set 증가 + Cache Locality 저하 + 불필요한 순회

Object Pool / Allocator

Allocator

Allocator(할당자)는 메모리 저장소에서 공간을 요청하고 반환하며, 어떤 블록을 어떻게 배정할지 결정하는 정책/구조다. 반드시 운영체제의 일반 힙만 관리하는 것은 아니며, 별도의 Arena나 Pool 같은 메모리 영역을 대상으로 할 수도 있다.

예를들어 힙이 이렇게 있다고 했을 때

[사용][빈 공간][사용][빈 공간][사용]

새로운 32바이트 할당 요청이 들어오면 Allocator가 현재 관리 중인 빈 공간 중에 이 요청을 처리할 수 있는 블록을 찾아서 넘겨준다.

중요한 건 힙 전체를 매번 처음부터 끝까지 선형 탐색하는건 아니다.

일반적으로 Allocator는 빈 공간을 빠르게 찾기 위한 별도의 자료구조를 쓴다

대표적으로 Free List와 Size Class다

FreeList

프리리스트란 빈 블록 목록이다. vector에 있던것과 아이디어가 같다

빈곳을 매번 전체 탐색하지 않고, 어디가 비었는지 따로 관리한다

Size Class

크기 클래스

만약 메모리 요청이 제각각 들어올때

13 bytes
21 bytes
30 bytes
57 bytes
...

이걸 정확히 크기마다 따로 관리하면 복잡하다. 그래서 Allocator가 비슷한 크기를 묶는다

예시

16B Class
32B Class
64B Class
128B Class

21바이트가 필요하다? -> 32사이즈 클래스에서 할당

왜 이렇게 하는가?

비슷한 크기의 블록을 묶으면

빈 블록을 찾기 쉬움
할당/반환 관리가 단순해짐
같은 크기의 블록을 재사용하기 쉬움

대신 21바이트가 필요한데 32바이트를 받으면 11바이트가 남는다 이를 내부 단편화 라고 한다

메모리 단편화

외부/내부 단편화 두개로 나뉜다

외부 단편화

메모리가

[사용][빈 20][사용][빈 30][사용][빈 10]

이라고 했을 때 전체 빈 공간은 20 + 30 + 10 = 60

그런데 50짜리 연속 공간이 필요하다면??? -> 없다

빈 공간은 충분한데 조각조각 흩어져 있어서 큰 연속 공간을 만들 수 없는 것이 외부 단편화다.

내부 단편화

아까 예시에서 11바이트가 남는 그 상황

블록 내부에서 남는 공간이므로 내부 단편화라고 한다.

그래서 ObjectPool이 왜좋은가?

총알처럼 같은 타입의 객체를 계속 생성/삭제 한다고 하자

일반 할당을 반복하면 할당/해제/할당/해제 반복을 계속 Allocator가 관리해야 한다.

ObjectPool은 아예 한번에 총알 여러개를 준비한다.

사용할때
Free List에서 빈 Bullet 슬롯 꺼냄
사용끝나면?
Reset
-> Free List에 반환

일반 Heap Allocator를 반복적으로 거치는 횟수를 줄인다.

동일한 크기의 객체 공간을 반복해서 사용하기 때문에 메모리 상태도 비교적 예측 가능해진다.

Object Pool의 장점

할당/해제 비용 감소

매번 일반 Allocator에게 새로운 공간을 요청하지 않고 기존 슬롯을 재사용한다.

Fragmentation 감소

동일한 객체 공간을 반복해서 재사용하기 때문에 빈번한 다양한 할당/해제로 인한 메모리 조각화를 줄일 수 있다.

Cache Locality

Pool이 객체들을 가까운 메모리에 배치한다면 순회 시 캐시 효율도 좋아질 수 있다.

단, Object Pool을 썼다고 무조건 캐시 효율이 좋아지는 것은 아니다. -> 메모리 배치 방식에 따라 달라진다

예시

이런 Pool은 캐시 지역성이 좋을 수 있다.

std::vector<Bullet> Pool;

객체들이 연속해서 붙어 있으니까 매 프레임 순회할때

for (Bullet& B : Pool)
{
    B.Update();
}

CPU가 한 Bullet을 읽으면서 주변 Bullet 데이터도 같은 Cache Line(캐시 라인)에 같이 가져올 가능성이 높다.

이런 배치는 캐시 친화적임

반대로 이런 식이면 다르다

std::vector<Bullet*> Pool;

각 Bullet을 개별적으로 new해서 저장했다고 치자

Pool
[ptr][ptr][ptr][ptr]
  │    │    │    │
  ↓    ↓    ↓    ↓
0x1000   Bullet
0xA800   Bullet
0x3500   Bullet
0xF200   Bullet

포인터 배열 자체는 연속이지만, 실제 Bullet 객체들은 Heap 여기저기에 흩어져 있을 수 있다.

순회하면

Bullet A 읽음
↓
멀리 떨어진 Bullet B
↓
또 다른 주소의 Bullet C

이런 식이 되기 때문에 Cache Miss(캐시 미스)가 많이 날 수 있다.

또 중요한게 활성 객체 배치

[Active][Inactive][Inactive][Active][Inactive][Active]

Pool이 연속 메모리여도 위처럼 활성 객체가 듬성듬성 섞여있으면 매 프레임 Active만 처리하고 싶어도 불필요한 데이터까지 캐시에 들어올 수 있다.

반대로

[Active][Active][Active][Active][Inactive][Inactive]

위처럼 활성 객체를 앞쪽으로 밀집시키면 실제로 순회하는 데이터가 서로 붙어있어서 캐시 효율이 더 좋다.

결론

배치방식은 크게 두가지를 보면 된다.

객체 자체가 연속 메모리에 있느냐
자주 같이 접근하는 활성 객체들이 서로 가까이 있느냐

Object Pool의 단점

Pool 크기 문제

1000개를 미리 준비했는데 실제 최대 동시 사용량이 100개라면 많은 메모리를 미리 잡아둘 수 있다.

반대로 준비한 용량보다 더 많이 필요해지면 실패 처리, 추가 Chunk 할당, Pool 확장 같은 정책이 필요하다. Object Pool이 반드시 고정 크기일 필요는 없다.

최대 동시 사용량을 예측하고 실제 프로파일링 결과로 크기를 조정해야 한다

Reset(초기화) 문제

이게 실제 버그로 이어지기 쉽다

총알을 반환하기 전에

Damage = 100
Target = EnemyA
Homing = true

가 남아있다고 하자

다음에 같은 객체를 재사용했는데 초기화를 안하면 이전 총알 상태가 새 총알에 남는다.

그래서 Pool에는

Acquire
↓
초기화
사용
Release
↓
상태 정리

가 중요하다

Object Pool / Arena / Slab 차이

Object Pool -> 특정 종류의 슬롯/객체를 재사용해 반복적인 일반 할당·해제 비용을 줄이는 것이 핵심. 구현에 따라 객체의 생성자/소멸자를 매번 호출할 수도 있고, 상태를 Reset해 객체 자체를 재사용할 수도 있다.

Arena Allocator -> 큰 메모리 덩어리 하나를 잡아두고 앞에서부터 빠르게 할당한다, 개별 해제를 거의 안하고 전체 Reset한다. 예) 한 프레임 동안만 사용하는 임시 데이터

Slab Allocator -> 같은 크기의 메모리 블록을 대량으로 관리한다, Object Pool과 비슷하지만 Object Pool은 게임 객체 재사용 관점, Slab은 메모리 할당 시스템 관점

캐시 지역성

CPU 캐시는 일반적으로 데이터를 Cache Line(캐시 라인) 단위로 가져오고 관리한다. 요청한 데이터가 상위 캐시에 없다면 더 낮은 캐시나 메모리 계층에서 해당 캐시 라인을 가져온다.

일반적인 현대 CPU에서 캐시 라인은 보통 64바이트이다.

예를 들어 캐시 라인이 64바이트이고 Bullet 하나가 16바이트라면

[Bullet0][Bullet1][Bullet2][Bullet3]
|----------- 64B -----------|

예시처럼 Bullet 4개가 하나의 64바이트 캐시 라인 경계 안에 배치되어 있다면, Bullet0을 읽을 때 같은 라인의 Bullet1~3도 함께 캐시에 들어온다. 실제 배치는 정렬과 객체 크기에 따라 달라질 수 있다.

그 다음 바로 Bullet1을 읽으면

더 낮은 메모리 계층까지 내려갈 필요가 줄어듦
→ 이미 Cache에 있음
→ Cache Hit(캐시 히트)

이것이 공간 지역성(Spatial Locality)

지금 사용한 데이터 근처의 데이터를 곧 다시 사용할 가능성이 높다

시간 지역성 (Temporal Locality)는

한 데이터를 사용하면 가까운 시간 안에 같은 데이터를 다시 사용할 가능성이 높다.

한 번 가져온 캐시 라인은 당장 사라지는 것이 아니라 캐시에 머무를 수 있으므로, 가까운 시간 안에 같은 데이터를 다시 사용하면 Cache Hit가 날 가능성이 높다.

캐시 공간이 필요하면 기존 Cache Line 일부가 Eviction(축출)된다. 어떤 라인을 교체할지는 CPU 마이크로아키텍처의 Replacement Policy(교체 정책)에 따라 달라지며, 실제 하드웨어는 정확한 LRU보다는 pseudo-LRU나 적응형 정책 등 구현별 정책을 사용하는 경우가 많다.

Kyu_

이전 포스트