캐시 지역성(Cache Locality)

Об этом предложении

1. 게임 개발자들은 완전히 멘탈이 나가버렸습니다 지난 편에서 빅오를 배웠습니다. 반복문 하나면 O(N), 다 비슷하다고 생각했죠. 그런데 이상한 일이 벌어졌습니다. 적 100만 마리의 체력을 한 번씩 더하는 코드를 두 가지로 짰는데요. 배열 에 담아서 한 번씩 훑기 → 원소 하나당 1.6ns 연결 리스트 에 담아서 한 번씩 훑기 → 원소 하나당 202ns 둘 다 "N개를 한 번씩 본다"는 똑같은 O(N) 인데, 120배 넘게 차이가 났거든요. 빅오로는 도저히 설명이 안 됐습니다. 이 글의 측정값은 모두 직접 돌려본 결과입니다. (클라우드 VM · Intel Xeon 2.1GHz · g++ -O2 · 단일 스레드 · 여러 번 실행한 중 최솟값) 숫자 자체는 PC마다 다르지만, 차이의 크기와 방향 은 거의 모든 PC에서 비슷하게 나옵니다. 2. CPU는 빠른데, 메모리가 너무 느렸거든요 CPU는 1초에 수십억 번 계산할 수 있습니다. 그런데 막상 계산할 데이터를 메모리(RAM)에서 가져오려니 , 그 한 번에 CPU가 수백 번 계산할 시간을 기다려야 했거든요. ▲ CPU와 메모리 사이의 캐시 계층 오른쪽으로 갈수록 크지만 느리고, 왼쪽으로 갈수록 작지만 빠릅니다. CPU는 필요한 데이터를 L1부터 찾고, 없으면 L2, L3, 마지막으로 RAM까지 갑니다. 대략적인 거리 감각은 이렇습니다. (CPU마다 다르니 "몇 배 차이"만 기억하세요.) 위치 대략적인 크기 대략적인 접근 시간 비유 L1 캐시 수십 KB 약 1ns 책상 위 L2 캐시 수백 KB ~ 수 MB 수 ns 책상 서랍 L3 캐시 수 MB ~ 수백 MB 십수 ~ 수십 ns 방 안 책장 RAM 수 GB 이상 수십 ~ 100ns 이상 동네 도서관 계산은 책상 위에서 1초 만에 끝나는데, 재료를 가지러 매번 도서관까지 다녀와야 했던 거죠. CPU는 대부분의 시간을 기다리면서 놀았습니다. 3. 그래서 똑똑한 개발자들이 기발한 생각을 했는데요 "어차피 도서관까지 간 김에, 옆에 꽂힌 책도 한 아름 같이 가져오자." CPU는 메모리에서 데이터 하나만 가져오지 않습니다. 그 주변까지 한 덩어리를 통째로 가져옵니다. 이 덩어리를 캐시 라인(Cache Line) 이라고 하고, 대부분의 x86 CPU에서 64바이트 입니다. ▲ 캐시 라인: 하나를 읽으면 64바이트가 통째로 온다 아래는 메모리, 굵은 세로선 사이가 캐시 라인 하나(float 16개 = 64바이트)입니다. 빨간 점 하나만 필요했지만, CPU는 그 캐시 라인 전체(주황)를 캐시(위 초록 상자)로 가져옵니다. 그래서 바로 다음 칸을 읽을 땐 도서관에 갈 필요가 없습니다. 이미 책상 위에 있거든요. 여기서 두 가지 규칙이 나옵니다. 이걸 지역성(Locality) 이라고 부릅니다. 공간 지역성(Spatial Locality): 방금 읽은 데이터의 바로 옆 을 곧 읽을 가능성이 높다 → 메모리에 나란히 붙여두면 빠르다 시간 지역성(Temporal Locality): 방금 읽은 데이터를 곧 다시 읽을 가능성이 높다 → 같은 데이터를 쓰는 작업은 몰아서 하면 빠르다 게다가 CPU는 "순서대로 읽고 있네?"를 눈치채면, 다음 캐시 라인을 미리 가져오기(Prefetch) 까지 합니다. 데이터가 나란히만 있으면 CPU는 거의 기다리지 않게 되죠. 4. 그런데 진짜 문제는 여기서부터였습니다 이 규칙을 몰랐던 코드는 캐시를 정면으로 배신 하고 있었거든요. 처음의 연결 리스트가 바로 그랬습니다. 1편에서 봤던 그림을 다시 떠올려 보세요. 배열은 원소가 나란히 붙어 있지만, 연결 리스트는 원소들이 메모리 여기저기 흩어져 있고 "다음 원소의 주소"를 따라 점프해야 합니다. 점프할 때마다 새 캐시 라인 을 가져와야 하고 다음 주소는 지금 원소를 읽어야만 알 수 있으니 미리 가져오기도 불가능 하죠 정말 그런지 데이터 크기를 바꿔가며 재봤습니다. ▲ 배열 vs 연결 리스트: 원소 하나당 걸린 시간 (로그 스케일, 실측) 가로축은 전체 데이터 크기, 세로축은 원소 하나를 처리하는 데 걸린 시간(ns)입니다. 세 방식 모두 원소를 한 번씩만 보는 O(N)입니다. 초록(배열) 은 데이터가 커져도 거의 평평합니다. 파랑(리스트지만 메모리에 순서대로 할당) 은 배열의 약 2배. 빨강(리스트, 메모리에 흩어져 할당) 은 데이터가 캐시를 넘어서는 순간 폭발해서, 384MB에서는 배열보다 120배 이상 느립니다. 데이터 크기 배열 리스트 (순서대로) 리스트 (흩어짐) 흩어짐 ÷ 배열 0.1MB 0.6ns 1.5ns 3.8ns 약 6배 1.5MB 0.6ns 1.5ns 7.7ns 약 13배 24MB 1.1ns 2.1ns 77.9ns 약 70배 384MB 1.6ns 3.5ns 202.1ns 약 120배 데이터가 작아서 캐시 안에 다 들어갈 때는 차이가 크지 않았는데요. 데이터가 커지자 흩어진 리스트는 원소마다 도서관을 다녀오기 시작했죠. 그리고 이건 연결 리스트만의 이야기가 아니었습니다. 게임 코드에서 아주 흔한 이 모양도 똑같거든요. TArray<AEnemy*> Enemies; // 배열이긴 하지만, 안에 든 건 "포인터" for (AEnemy* Enemy : Enemies) { Enemy->UpdateMovement(DeltaTime); // 포인터를 따라 액터마다 메모리 여기저기로 점프 } 배열에 담긴 건 주소 뿐이고, 액터 본체는 각자 따로 할당되어 메모리에 흩어져 있습니다. 결국 흩어진 리스트를 도는 것과 비슷한 일이 벌어지죠. 5. 바로 그 순간 또 다른 개발자가 천재적인 아이디어를 냈습니다 "객체 단위로 묶지 말고, 같이 쓰는 데이터끼리 나란히 묶자." 적을 이동시킬 때 필요한 건 위치와 속도 뿐입니다. 그런데 적 구조체에는 이름, 스탯, 인벤토리까지 잔뜩 들어 있었죠. // AoS (Array of Structures): 적 하나에 모든 걸 담고, 그걸 배열로 struct FFatEnemy { FVector3f Position; // 이동에 필요 (12바이트) FVector3f Velocity; // 이동에 필요 (12바이트) char Name[32]; // 이동엔 필요 없음 float Stats[16]; // 이동엔 필요 없음 int32 Inventory[8]; // 이동엔 필요 없음 }; // 총 152바이트 중 이동에 쓰는 건 24바이트 TArray<FFatEnemy> Enemies; ▲ AoS vs SoA: 캐시 라인 하나에 실려 오는 데이터 위 (AoS): 적 한 마리(152바이트)를 그린 것입니다. 주황이 이동에 쓰는 위치·속도, 회색이 이동엔 안 쓰는 나머지입니다. 초록 상자(캐시 라인 64바이트)를 가져와도 대부분이 쓸모없는 회색입니다. 아래 (SoA): 위치 X, Y, Z와 속도 X, Y, Z를 각각 따로 배열로 모았습니다. 초록 상자를 가져오면 16마리 분량의 쓸모 있는 데이터 가 꽉 차서 옵니다. 그래서 이렇게 바꿨습니다. 이게 SoA(Structure of Arrays) 입니다. // SoA (Structure of Arrays): 필드별로 배열을 따로 struct FEnemyMovementData { TArray<float> PosX, PosY, PosZ; TArray<float> VelX, VelY, VelZ; }; for (int32 i = 0; i < Num; ++i) { Data.PosX[i] += Data.VelX[i] * DeltaTime; Data.PosY[i] += Data.VelY[i] * DeltaTime; Data.PosZ[i] += Data.VelZ[i] * DeltaTime; } 결과는 이랬습니다. ▲ 왼쪽: 적 100만 마리 위치 갱신 (AoS vs SoA) / 오른쪽: 4096×4096 격자 전체 순회 (행 우선 vs 열 우선), 실측 왼쪽: 하는 계산은 똑같은데 SoA가 약 3.4배 빨랐습니다(7.9ms → 2.3ms). 오른쪽은 아래 6절에서 이어집니다. 계산은 한 줄도 줄지 않았습니다. CPU가 기다리는 시간 만 줄었을 뿐이죠. 이런 식으로 "객체가 아니라 데이터가 어떻게 흐르는지"를 기준으로 설계하는 걸 데이터 지향 설계(DOD, Data-Oriented Design) 라고 부릅니다. 실무에서는 전부 SoA로 쪼개기보다 자주 쓰는 데이터(Hot)와 가끔 쓰는 데이터(Cold)를 나누는 것 부터 시작합니다. 매 프레임 쓰는 위치·속도·체력은 작은 구조체 배열로, 이름·인벤토리는 다른 곳에 두는 것만으로도 효과가 큽니다. 6. 하지만 또 골칫거리가 생겼습니다 데이터를 나란히 붙여놨는데도 느린 코드가 또 나타났거든요. 공간 탐색 시리즈에서 많이 썼던 2D 격자 였습니다. // 4096 × 4096 격자: Grid[Y * Width + X] for (int32 X = 0; X < Width; ++X) // 바깥이 X { for (int32 Y = 0; Y < Height; ++Y) // 안쪽이 Y { Sum += Grid[Y * Width + X]; // 한 번에 Width칸(16KB)씩 점프! } } 격자는 메모리에 한 줄(행)씩 이어져 있습니다. 그런데 안쪽 반복문이 Y를 돌면, 매번 다음 줄로 점프 하게 되죠. 캐시 라인을 통째로 가져와 놓고 그중 4바이트만 쓰고 버리는 셈입니다. ▲ 행 우선 순회 vs 열 우선 순회 왼쪽 (행 우선): 한 줄씩 옆으로 훑습니다. 아래 메모리 띠에서도 한 방향으로 쭉 읽어서, 가져온 캐시 라인을 남김없이 씁니다. 오른쪽 (열 우선): 세로로 내려갑니다. 메모리에서는 한 줄 길이만큼 계속 점프해서, 캐시 라인마다 한 칸(주황)만 쓰고 버립니다. 앞의 실측 그래프 오른쪽이 바로 이 결과입니다. 64MB 격자를 한 번 훑는 데 행 우선은 3.5ms, 열 우선은 140ms . 반복문 두 줄의 순서만 바꿨을 뿐인데 40배 였습니다. 7. 바로 그 순간, 누군가 이렇게 말했습니다 "코드를 짜기 전에, 데이터가 메모리에 어떻게 놓여 있는지부터 그려보자." 캐시 지역성을 지키는 규칙은 결국 몇 줄로 정리됩니다. 나란히 놓는다: 포인터 배열보다 값 배열( TArray<FMyData> ) 같이 쓰는 것끼리 묶는다: 자주 쓰는 데이터(Hot)와 가끔 쓰는 데이터(Cold)를 분리, 필요하면 SoA 메모리 순서대로 돈다: 2D 배열은 바깥 Y, 안쪽 X 같은 데이터는 몰아서 처리한다: 적마다 "이동 → 공격 → 애니메이션"을 번갈아 하기보다, 모든 적 이동 → 모든 적 공격 순으로 (시간 지역성) // 메모리 순서대로: 안쪽 반복문이 연속된 주소를 돈다 for (int32 Y = 0; Y < Height; ++Y) { for (int32 X = 0; X < Width; ++X) { Sum += Grid[Y * Width + X]; } } 8. 그리고 지금, 언리얼 엔진에는 개발자들이 고생하며 깨달은 데이터 지향 설계는, 오늘날 언리얼의 Mass Entity 프레임워크로 들어가 있습니다. ▲ Mass의 아키타입 청크: 같은 종류의 데이터끼리 나란히 같은 프래그먼트 조합(여기서는 Transform, Velocity, Health)을 가진 엔티티들이 청크(큰 사각형) 단위로 모입니다. 청크 안에서는 Transform은 Transform끼리, Velocity는 Velocity끼리 나란히 붙어 있습니다. 위에서 본 SoA 구조를 엔진이 알아서 만들어 주는 셈입니다. 이동 처리는 이렇게 청크 단위로 돕니다. void UMyMovementProcessor::Execute(FMassEntityManager& EntityManager, FMassExecutionContext& Context) { EntityQuery.ForEachEntityChunk(Context, [](FMassExecutionContext& Context) { // 청크 안에 나란히 붙어 있는 프래그먼트 배열을 그대로 받는다 const TArrayView<FTransformFragment> Transforms = Context.GetMutableFragmentView<FTransformFragment>(); const TConstArrayView<FMassVelocityFragment> Velocities = Context.GetFragmentView<FMassVelocityFragment>(); const float DeltaTime = Context.GetDeltaTimeSeconds(); for (int32 i = 0; i < Context.GetNumEntities(); ++i) // 메모리 순서대로 쭉 { Transforms[i].GetMutableTransform().AddToTranslation(Velocities[i].Value * DeltaTime); } }); } ForEachEntityChunk 의 인자는 엔진 버전에 따라 다릅니다(구버전은 EntityManager 를 첫 인자로 받습니다). 사용 중인 버전의 Mass 샘플이나 엔진 소스를 꼭 확인하세요. 알아두면 좋은 포인트 TArray<UObject*> 를 매 프레임 도는 코드는 의심해 보세요. 액터 수가 수천 단위로 늘어날 로직이라면, 매 프레임 쓰는 데이터만 TArray<FMyHotData> 로 따로 모아 관리하는 매니저를 두는 것만으로 크게 빨라집니다. TInlineAllocator : TArray<int32, TInlineAllocator<8>> 처럼 쓰면 원소 8개까지는 힙 할당 없이 구조체 안에 바로 들어갑니다. 작은 배열이 여기저기 흩어지는 걸 막아줍니다. 구조체 필드 순서: 큰 타입부터 작은 타입 순으로 배치하면 정렬 패딩이 줄어서, 캐시 라인 하나에 더 많은 원소가 들어갑니다. 멀티스레드의 함정, False Sharing: ParallelFor 로 여러 스레드가 같은 캐시 라인 안의 서로 다른 변수 를 쓰면, 서로의 캐시를 계속 무효화해서 느려집니다. 스레드별 결과는 alignas(PLATFORM_CACHE_LINE_SIZE) 로 캐시 라인을 분리해 두세요. 최종 확인은 역시 측정: 캐시 문제는 코드만 봐서는 잘 안 보입니다. Unreal Insights로 구간 시간을 비교하고, 필요하면 VTune 같은 CPU 프로파일러로 캐시 미스를 직접 확인하세요. 정리 구분 내용 핵심 원리 CPU는 빠르고 메모리는 느리다. CPU는 64바이트 캐시 라인 단위로 가져온다 공간 지역성 옆에 있는 데이터를 곧 쓴다 → 나란히 붙여둔다 시간 지역성 방금 쓴 데이터를 곧 또 쓴다 → 같은 작업은 몰아서 한다 배열 vs 흩어진 리스트 같은 O(N)인데 384MB에서 약 120배 차이 (실측) AoS vs SoA 같은 계산인데 약 3.4배 차이 (실측) 행 우선 vs 열 우선 반복문 순서만 바꿨는데 약 40배 차이 (실측) 언리얼 실무 값 배열, Hot/Cold 분리, TInlineAllocator , Mass Entity, False Sharing 주의 빅오는 "일을 몇 번 하느냐" 를 알려주고, 캐시 지역성은 "한 번 할 때 얼마나 기다리느냐" 를 알려줍니다. 둘 다 봐야 진짜 빠른 코드가 나옵니다.