메모리의 물리학 - dmurph.com

자주 접근하는 데이터의 메모리 지역성이 높을 때 많은 알고리즘, 예를 들어 정렬 같은 것들이 상당히 개선된다는 이야기를 들어왔습니다. 예를 들어 CPU가 처리에 필요한 관련 정보를 RAM을 치는 대신 자신의 L1/L2 캐시에 모두 올려둘 수 있는 경우입니다. 이를 다루는 일반적인 방법 중 하나가 Entity Component System (ECS) 소프트웨어 아키텍처를 사용하는 것입니다. 하지만 인터프리터 언어나 OOP 언어(Java, Python, Javscript)에서는 이런 메모리 배치를 달성하기가 어려울 수 있습니다. 이런 언어들은 대개 개발자에게 객체의 메모리 위치에 대한 제어권을 그만큼 많이 주지 않기 때문입니다. 제 질문은 이것입니다.

Javascript에서 ECS 스타일 아키텍처를 사용하는 것이 가능할까요? 그리고 해당되는 연산에서 실제로 객체 + V8의 가비지 컬렉션보다 더 나을까요?

이를 테스트하기 위해, 저는 충분히 복잡한 벤치마크를 만들었습니다. 바로… “상자 안에서 튀어다니는 공들”입니다! 이것은 표준적인 2차원 물리 엔진 기법을 따릅니다.

• “broad-phase” 충돌 단계 (즉, “바운딩 박스들이 교차하는가?”)
• “narrow-phase” 충돌 단계 (즉, “이 교차하는 박스들이 주어졌을 때, 충돌을 해결하라!”)

그리고 물론, 저는 너무 신이 나서 아래에 엄청나게 많은 벤치마크 종류를 만들고 말았습니다. 한번 해보세요!

배경 - ECS란 무엇인가?

게임 개발을 조금이라도 해봤다면, 아마 Entity Component System (ECS) 을 들어본 적이 있을 것입니다. OOP가 행 기반 데이터베이스(각 객체가 모든 속성을 하나의 메모리 덩어리에 저장하는 구조)라면, ECS는 열 기반 데이터베이스로, 각 속성(또는 속성들의 집합)을 별도의 열 배열에 저장합니다.

다르게 말하면(그리고 ECS에 대한 더 좋은 설명은 다른 곳에서 훨씬 잘 찾을 수 있겠지만)… MovingObject를 상속받고 그것이 다시 PhysicalObject를 상속받는 GameEntity 같은 복잡한 클래스 계층을 만드는 대신, ECS는 모든 것을 세 가지 구별된 개념으로 분해합니다.

1. 엔티티: 이것들은 그저 고유한 정수 ID일 뿐입니다. 데이터도, 동작도 담고 있지 않습니다.
2. 컴포넌트: 상태의 개별 측면을 나타내는 평범한 데이터 구조입니다(예: Position, Velocity, Color). 로직은 포함하지 않습니다. 각 엔티티는 0개부터 전부까지 동적인 컴포넌트 집합을 가질 수 있습니다.
3. 시스템: 게임 로직을 실행하는 함수 또는 루프입니다. 특정 컴포넌트 집합을 기준으로 엔티티를 조회한 다음 그 데이터에 대해 동작합니다.

벤치마크 선택

저는 너무 과하게 다섯 가지 차원으로 테스트했습니다.

• 언어: Javascript (V8 엔진 최적화와 TypedArrays 테스트) 대 WASM (극단적인 메모리 제어를 위한 AssemblyScript).
• 아키텍처: 전통적인 OOP (객체 참조 배열) 대 ECS (캐시 친화적인 Structure of Arrays).
• Broad-phase: 공간 AVL 트리 ( $O \left(\right. N log ⁡ N \left.\right)$ 균형 트리) 대 Sweep & Prune (X축 기준 정렬 후 겹침 검사).
• 정렬 전략 (S&P용): Insertion Sort (거의 정렬된 데이터에 대한 교과서적 선호 방식), Hybrid Quicksort, 복사 없는 Hybrid Mergesort, 그리고 JS NativeArray.sort()를 테스트했습니다.
• 운동 응집성: Wandering (부드러운 움직임, 배열이 거의 정렬된 상태 유지), Erratic (무작위 순간이동, 극단적인 캐시 스래싱), 그리고 Static (움직임은 없지만 영구적인 충돌 존재, 일부 충돌이 있는 순수 메모리 읽기 속도 분리).

아무튼, 어떻게 동작하는지 봅시다! 직접 이것저것 만져보고 싶다면 GitHub 에 호스팅되어 있습니다.

Macbook M4 결과

이 모든 구성을 제 Apple M4 Pro chip 에서 로컬로 실행하면(전원 연결 상태, 200 프레임) 숫자가 엄청 많이 나옵니다. 전체 6회 실행의 전체 데이터셋이 보고 싶다면 아래의 Appendix: Full Benchmark Dataset 를 확인해보세요.

정보 과부하를 줄이기 위해, 세 가지 주요 가설에 집중해봅시다.

H1: 공간 트리 대 Sweep & Prune

연속적인 1차원 메모리 스윕은, 둘 다 평면 배열에 저장되어 있더라도, 계층적인 2차원 공간 트리보다 일관되게 더 빠릅니다.

15,000개의 wandering 엔티티에서, 평면 배열 기반 Sweep & Prune (WASM ECS S&P Quick) 는 1.81 ms 로 실행되며(기준선 대비 9.02배 향상), 평면 배열 기반 공간 트리(ECS Tree) 는 9.97 ms 로 실행됩니다(단지 1.64배 향상).

평면 배열을 사용하고 JavaScript 힙 객체도 피하는데도, 왜 트리는 이렇게 더 느릴까요?

• 중첩된 간접 참조: Sweep & Prune는 인덱스 간접 참조가 한 단계뿐입니다(posX[indices[i]]). 하지만 AABB 트리는 중첩된 간접 참조를 요구합니다. 순회 중 CPU는 자식 인덱스를 조회해야 하고(treeLeft[idx]), 그다음 그 자식을 사용해 노드의 경계를 다시 조회해야 합니다(treeMinX[leftChild]). 배열들 사이를 이런 비선형 방식으로 점프하면 CPU의 하드웨어 프리페처가 다음 메모리 주소를 예측할 수 없습니다.
• 분기 예측 실패: 트리 순회 루프는 조건 분기로 가득합니다(예: 겹침 여부에 따라 왼쪽, 오른쪽 또는 둘 다 내려갈지 결정). 15,000개의 움직이는 엔티티에서는 이런 분기들이 매우 예측 불가능해서 CPU 명령 파이프라인이 자주 비워집니다. 반면 Sweep & Prune는 단순하고, 매우 예측 가능한 선형 스윕입니다.
• 시간적 응집성: 엔티티들은 프레임 간 아주 조금만 움직이기 때문에(높은 공간 응집성), Sweep & Prune의 정렬된 indices 는 거의 연속된 상태를 유지합니다. 덕분에 인덱스 조회가 캐시 안에서 매우 국소적으로 이뤄집니다. 반면 트리 순회는 언제나 멀리 떨어진 노드들 사이를 점프합니다.

---

H2: JavaScript 대 WebAssembly

데이터 지향 설계의 캐시 지역성 이점을 얻기 위해 WebAssembly가 필수는 아니지만, 검사 없는 메모리 접근을 가능하게 하면서 큰 2차적인 향상을 제공합니다.

순수 JavaScript에서 OOP(객체 배열)에서 ECS(평면 TypedArrays)로 단순히 옮기는 것만으로도 공간 응집성에 따라 1.58배에서 24.9배까지의 속도 향상이 나옵니다.

AssemblyScript WASM으로 옮기면 추가로 약 2.5배의 속도 향상이 제공됩니다(2.11 ms까지 감소). 이 향상의 주된 원인은 unchecked() 연산자를 사용할 수 있다는 점입니다. 이것은 컴파일러에게 배열 경계 검사를 건너뛰라고 알려주며, 컴파일러가 고도로 최적화된 벡터 명령을 생성하고 CPU 명령 처리량을 최대화할 수 있게 해줍니다.

---

흥미로운 배움들

이걸 만들면서 꽤 흥미로운 것들을 많이 발견했습니다!

1. 공간 응집성 정렬 함정 (왜 Hybrid Sort가 필요한가)

교과서적인 Insertion Sort는 실시간 물리에서 성능 함정이며, 최악의 프레임 끊김을 막으려면 하이브리드 정렬이 필요합니다.

Wandering (높은 응집성)에서는 배열이 거의 정렬된 상태를 유지하므로 Insertion Sort가 매우 빠릅니다(4.21 ms). 하지만 Erratic (낮은 응집성) 작업 부하(예: 폭발이나 순간이동)에서는 배열이 완전히 정렬되지 않은 상태가 됩니다. 그러면 Insertion Sort는 이차 시간 최악 사례($O \left(\right. N^{2} \left.\right)$)로 무너지고, 프레임 시간이 36.39 ms 까지 불어나며 심각한 끊김을 유발합니다.

이를 해결하기 위해, 우리는 Hybrid Sort 를 구현했습니다(Quicksort 또는 Mergesort가 하위 배열이 12개 요소 미만이 되면 Insertion Sort로 전환). 이렇게 하면 작은 분할에서 재귀 스택 오버헤드를 없애면서도, 혼란스러운 움직임 아래에서 $O \left(\right. N log ⁡ N \left.\right)$ 성능을 보장합니다(5.60 ms).

왜 하위 배열이 12개 요소 미만이 되면 insertion sort로 전환할까요? 아주 작은 배열에서는 분할 정복 재귀의 상대적으로 큰 호출 스택 및 버퍼 오버헤드를 제거할 수 있기 때문입니다. 이런 경우 insertion sort는 준비 비용이 거의 0에 가까워 매우 빠릅니다. 실제로 이렇게 바꾸니 성능이 좋아졌습니다! (다만 얼마나였는지는 잊었습니다)

2. 라이브러리 절충안 (bitECS 대 Custom SoA)

ECS 라이브러리를 사용하는 것은 손수 튜닝한 SoA보다 약간 느리지만, 여전히 매우 경쟁력이 있으며 실제 엔지니어링에서는 최적의 선택입니다.

15,000개의 erratic 엔티티에서 bitECS S&P (Quick) 는 9.56 ms 로 실행되며, 우리의 커스텀 ECS는 5.60 ms 입니다. 약 2배 느리지만, 여전히 OOP 기준선(131.6 ms) 대비 엄청난 14배 속도 향상을 제공합니다.

왜 bitECS가 더 느릴까요?

• 속성 패킹 부재: 우리 ECS (Custom SoA)에서는 y, w, h 를 하나의 posYwh 배열에 패킹합니다(posYwh[i * 3 + 0]). 즉 세 값 모두 하나의 CPU 캐시 라인에 로드됩니다. 기본적으로 bitECS 는 컴포넌트의 각 속성마다 별도의 TypedArray 를 할당합니다(y, w, h 가 각각 별도 배열). 그래서 CPU는 세 개의 분리된 메모리 스트림에서 가져와야 합니다.
• 쿼리 및 ID 매핑 오버헤드: bitECS는 아키타입을 조회하고 희소한 Entity ID를 내부 배열 슬롯에 매핑해야 하므로, 작은 간접 참조가 추가됩니다.

하지만 실제 게임에서는 bitECS 같은 라이브러리의 사용성, API 안전성, 동적 엔티티 관리가 몇 밀리초의 미세 최적화보다 훨씬 더 가치 있습니다.

게다가 아래의 성능 최적화 팁 중 하나를 적용하고, 물리 데이터를 연산 전에 커스텀 구조로 추출하면 이런 차이는 전부 사라질 수도 있습니다.

3. JavaScript Float32 함정

순수 JavaScript에서 32비트 부동소수점(Float32Array)으로 바꾸면 V8의 배정밀도 승격 오버헤드 때문에 성능이 떨어집니다.

15,000개 엔티티에서, 우리 ECS (Custom SoA)의 Float32Array 구현은 Float64Array 버전보다 약 5% 느렸습니다 (5.60 ms 대 5.32 ms).

왜 그럴까요? JavaScript 숫자는 항상 64비트 배정밀도입니다. V8이 Float32Array 에서 값을 읽을 때는, 수학 연산을 수행하기 전에 런타임에서 32비트 부동소수점을 64비트 배정밀도로 변환해야 합니다. 다시 쓸 때는 반대로 다시 변환해야 합니다. 이런 런타임 변환 오버헤드가 L1/L2 캐시 밀도 향상 이득을 상쇄해버립니다.

네이티브 환경(WASM, C++, Rust 등)에서는 f32 가 변환 없이 FPU 레지스터에서 직접 처리되므로, 순수한 성능 향상이 됩니다.

4. 결정론의 물리학

접촉 해결 순서가 달라지는 순간, 알고리즘 간 궤적 결정론을 맞추려는 것은 허황된 절약입니다.

트리와 정렬 기반 스윕은 서로 다른 순서로 접촉을 순회하고 해결하므로, 반올림 오차가 다르게 누적됩니다. 이 때문에 시뮬레이션 경로는 거의 즉시(2프레임쯤부터) 갈라집니다. 서로 다른 패러다임 간 궤적을 정확히 일치시키는 것보다, 통계적 정확성과 국소적 안정성에 집중하는 편이 낫습니다.

5. DOD와 프레임 타임 안정성 (99번째 백분위수)

Data-Oriented Design은 가비지 컬렉션과 캐시 미스 급증을 제거함으로써 매우 안정적인 프레임 속도를 제공합니다.

벤치마크의 99번째 백분위수 숫자를 보면, 눈에 띄는 패턴이 나타납니다. OOP 구현에서는 99번째 백분위수가 평균 프레임 시간보다 종종 2배에서 3배 더 높습니다. 반면 ECS (Custom SoA)와 WASM 구현에서는 99번째 백분위수가 평균과 거의 동일합니다.

OOP에서는 엔티티들이 힙 전체에 흩어져 있습니다. 이들이 움직이고 상호작용하면서 JavaScript 엔진의 가비지 컬렉터가 계속 작동하고, CPU는 포인터 조회를 기다리며 자주 멈춥니다. 이로 인해 간헐적인 프레임 드롭(미세한 끊김)이 발생합니다. ECS는 미리 할당된 평면 TypedArrays를 사용하므로 메모리 접근이 100% 예측 가능하고 GC 오버헤드가 0이어서, 완벽하게 매끄러운 프레임 전달을 보장합니다.

---

🏆 그랜드 피날레

질문: 우리가 생각해낼 수 있는, 합리적으로 설계된 코드 중 가장 빠른 것은 무엇일까요?

판정: 최상위 공간 트리들(WASM Tree, JS ECS Tree)과 Sweep & Prune 챔피언들(WASM Quick S&P, JS Quick S&P)을 15,000개의 혼란스럽게 충돌하는 물체에 대해 맞붙여보면:

제 결론:

1. 캐시 지역성 > 알고리즘 복잡도: 15,000개 엔티티 규모에서는, 포인터 추적과 예측 불가능한 트리 분기가, 이론적인 Big-O 복잡도는 더 좋더라도, 평면 1차원 배열 정렬의 연속적인 L1/L2 캐시 지역성과 경쟁할 수 없습니다.
2. ECS의 승리를 위해 WASM이 꼭 필요한 것은 아니다: JavaScript 코드베이스를 단순히 평면 Structure of Arrays (SoA) 레이아웃으로 바꾸는 것만으로도 OOP 대비 최대 24배 속도 향상을 얻을 수 있습니다. WASM은 필수 입장권이 아니라, 그 위에 얹는 보너스(추가 2.5배)입니다.
3. 실용주의가 이긴다: 손수 튜닝한 SoA가 절대적으로 가장 빠르긴 하지만, bitECS 같은 실전용 ECS 라이브러리를 사용해도 OOP 대비 엄청난 14배 속도 향상을 얻으면서 깔끔하고 확장 가능한 API를 제공받을 수 있습니다. 제 생각에는, 애플리케이션의 99%에서는 라이브러리를 사용하는 것이 올바른 엔지니어링 선택입니다.

---

잠재적 개선점

이 섹션은 상용급 게임 엔진을 위해 S&P broadphase를 더 최적화하는 방법을 설명합니다.

1. ETL Physics Buffer 패턴을 통한 인덱스 간접 참조 제거

가벼운 물리 버퍼를 추출하고 실제로 재배열함으로써, Sweep 단계에서 인덱스 간접 참조를 제거할 수 있습니다.

우리의 단순한 ECS S&P에서는 스윕 단계가 좌표를 간접적으로 읽어야 합니다: posX[indices[i]]. 이를 연속적으로 만들기 위해 모든 컴포넌트 배열을 실제로 정렬할 수도 있겠지만, 실제 게임에서는 아키타입 단편화와 물리와 무관한 컴포넌트(예: 인벤토리나 AI 상태)까지 재배열해야 하는 낭비 때문에 매우 비실용적입니다.

대신 Extract-Transform-Load (ETL) Physics Buffer 패턴을 사용할 수 있습니다.

1. 추출: broadphase 시작 시, 메인 ECS 배열에서 필요한 공간 필드(x, y, w, h, id)만 전용의 평면 PhysicsBuffer 로 복사합니다.
2. 변환 (정렬 및 재배열): 이 버퍼의 indices 를 정렬한 다음, 이 가벼운 PhysicsBuffer 만 실제로 재배열합니다.
3. 연속 스윕: 이제 Sweep 단계는 정렬된 PhysicsBuffer 를 순차적으로 읽을 수 있습니다(posX[indices[i]] 대신 posX[i]).
4. 적재 (출력): broadphase는 결과 접촉 쌍(Entity IDs)을 narrowphase로 출력하고, 메인 ECS 데이터베이스는 전혀 건드리지 않습니다.

왜 이것이 매우 실용적인가:

• 범용 호환성: 데이터가 분리된 버퍼로 추출되기 때문에, 이 패턴은 어떤 ECS 라이브러리와도 (예: bitECS) 100% 호환됩니다. 라이브러리를 쿼리하고, 버퍼를 채우고, 해결하고, 다시 기록하면 됩니다.
• 엄청나게 빠른 복사: JavaScript에서의 순차적인 $O \left(\right. N \left.\right)$ 데이터 복사(.set() 또는 단순 루프 사용)는 매우 빠릅니다. 현대 CPU는 순차 메모리 복사에 매우 최적화되어 있어서, 프리페처가 잘 작동하는 가운데 메모리 대역폭을 쉽게 가득 채웁니다.
• 측정 가능한 이득: 이를 벤치마크에 구현했을 때, 15,000개 엔티티에서 추가로 약 6% 속도 향상을 얻었습니다(erratic 부하에서 프레임 시간이 5.32 ms 에서 5.01 ms 로 감소).

2. Spatial Hash Grid (대안적 공간 분할)

크기가 균일한 엔티티의 경우, 평면 배열 기반 Spatial Hash Grid는 정렬이나 트리 균형 조정 오버헤드 없이 평균적으로 $O \left(\right. 1 \left.\right)$ 성능을 제공할 수 있습니다.

우리는 Sweep & Prune를 Dynamic AABB Tree와 비교했지만, 또 다른 매우 캐시 친화적인 대안은 Spatial Hash Grid 입니다.

• AABB Tree와 달리(재귀적이고 비선형적인 트리 순회가 필요), Spatial Hash Grid는 2차원 좌표를 1차원 그리드 배열로 매핑합니다.
• 엔티티는 단일 $O \left(\right. N \left.\right)$ 패스로 그리드 셀에 삽입되고, 질의는 인접 셀을 확인함으로써 $O \left(\right. 1 \left.\right)$ 시간에 수행됩니다.
• 이 접근법은 평면 배열로 구현할 때 매우 캐시 친화적이며, Sweep & Prune의 정렬 단계도 완전히 피하므로 매우 큰 규모에서 특히 최적입니다.

3. 다중 축 Sweep & Prune

공간 분산이 가장 큰 축을 기준으로 정렬하면, 정렬 정렬 병목 사례에서 Sweep & Prune가 성능 저하되는 것을 막을 수 있습니다.

우리의 단순한 Sweep & Prune는 X축만 기준으로 정렬합니다. 많은 엔티티가 수직으로 정렬되면(예: 좁은 통로를 따라 아래로 떨어지는 경우), 이들은 모두 X 투영에서 겹치게 되어 스윕 단계가 $O \left(\right. N^{2} \left.\right)$ 에 가까워집니다.

• 상용급 Sweep & Prune는 X축과 Y축 모두에 대해 엔티티 위치의 분산 을 계산합니다.
• 그런 다음 겹치는 구간 수를 최소화하기 위해 분산이 가장 큰 축을 동적으로 선택해 정렬 및 스윕합니다.

4. WebAssembly SIMD 벡터화

WASM SIMD (Single Instruction Multiple Data)를 사용하면 네 개의 바운딩 박스 교차를 동시에 검사할 수 있습니다.

PhysicsBuffer 가 좌표를 연속적으로 저장하고 있으므로, 한 번에 네 개 엔티티의 경계를 128비트 SIMD 레지스터에 로드할 수 있습니다. 그러면 CPU는 단일 명령으로 AABB 겹침 검사를 병렬 수행할 수 있어, 스윕 단계 처리량을 잠재적으로 네 배까지 늘릴 수 있습니다.

---

제가 뭔가 놓치고 있을까요?

제가 무엇을 놓치고 있을까요? 어떤 다른 구성을 추가해야 할까요? 제가 뭔가 잘못한 걸까요?

FAQ

• 왜 Web Workers를 사용하지 않았나요? 마이크로벤치마크에서는 Web Workers에 넣는 것이 오히려 실제 병목을 흐릴 수 있기 때문입니다. 여러 스레드를 띄우면 브라우저가 메인 스레드를 진공 상태처럼 최적화해 “마이크로벤치마크 증후군”을 일으킬 수 있습니다. 단일 스레드로 유지하면, 활성 시뮬레이션 부하 아래에서 브라우저 엔진이 메모리 접근을 어떻게 관리하는지를 직접 비교할 수 있습니다.
• 왜 AssemblyScript 대신 C나 C++를 사용하지 않았나요? 여기서 C++를 사용해보려 했지만, AssemblyScript보다 느리게 만든 두 가지 주요 장애물이 있었습니다.
  • 포인터 별칭화: AssemblyScript에서는 unchecked() 를 사용해 포인터 별칭화 보호를 쉽게 비활성화할 수 있었는데, C++와 clang에서는 이게 조금 더 어려웠습니다. 물론 불가능한 것은 아니었습니다.
  • 최적화된 수학 연산: C++에서 WASM으로 갈 때 수학 라이브러리 호출을 더 빠르게 만드는 방법을 알아내지 못했습니다. 이상하게도 AssemblyScript는 sin/cos/pow 같은 것에 매우 빠른 수학 호출을 연결해주는데, 저는 그것을 C++로는 제대로 작동시키지 못했습니다.

부록

전체 벤치마크 데이터셋

통계 매니아와 성능 순수주의자를 위해, 여기 200 프레임 동안 등록된 18개 시뮬레이터 구성 전체에 걸친, 가감 없는 전체 데이터셋을 제공합니다.

1. Static 동작 (절대적 응집성 - 5,000 Entities)

2. Wandering 동작 (높은 응집성 - 5,000 Entities)

3. Erratic 동작 (낮은 응집성 - 5,000 Entities)

4. Static 동작 (절대적 응집성 - 15,000 Entities)

5. Wandering 동작 (높은 응집성 - 15,000 Entities)

6. Erratic 동작 (낮은 응집성 - 15,000 Entities)