Cache Locality와 False Sharing 이해하기

성능 이슈를 볼 때 algorithm complexity만 확인하면 충분하다고 생각하기 쉽습니다.

하지만 같은 O(n) 코드라도 data layout과 memory access pattern에 따라 실제 실행 시간은 크게 달라질 수 있습니다.

CPU는 main memory에서 값을 매번 직접 읽지 않고, cache line 단위로 데이터를 가져와 L1, L2, L3 cache를 통해 접근 비용을 줄입니다.

이 구조를 이해하면 왜 연속된 배열 접근이 빠르고, 왜 멀티스레드 코드에서 서로 다른 변수만 수정해도 느려질 수 있는지 설명할 수 있습니다.

 

Cache locality는 CPU가 이미 가져온 cache line을 얼마나 잘 재사용하는가의 문제이고, false sharing은 서로 다른 data가 같은 cache line을 공유해서 thread 간 불필요한 cache invalidation을 만드는 문제입니다.

 

이번 글에서는 CPU cache, cache line, spatial locality, temporal locality, false sharing을 실무 개발자 관점에서 정리하고, C++ 코드에서 어떤 설계 기준으로 연결되는지 살펴보겠습니다.

 

CPU cache는 memory access 비용을 줄이지만, data layout이 나쁘면 cache miss와 false sharing으로 성능이 크게 흔들릴 수 있습니다.

 

---

1. CPU cache는 왜 필요한가?

CPU register와 main memory 사이에는 큰 속도 차이가 있습니다.

CPU가 모든 값을 main memory에서 직접 읽는다면 연산 장치가 memory access를 기다리는 시간이 길어집니다.

그래서 CPU는 자주 쓰거나 곧 다시 쓸 가능성이 높은 데이터를 cache에 저장합니다.

일반적으로 cache는 L1, L2, L3처럼 여러 계층으로 구성되고, CPU core에 가까울수록 작고 빠릅니다.

 

계층	특징	개발자가 체감하는 지점
L1 cache	core에 가장 가깝고 매우 빠름	tight loop의 data locality에 민감
L2 cache	L1보다 크지만 느림	작은 working set이 반복될 때 유리
L3 cache	여러 core가 공유하는 경우가 많음	thread 간 data 공유와 contention에 영향
Main memory	용량은 크지만 cache보다 훨씬 느림	cache miss가 많으면 latency가 커짐

중요한 점은 CPU가 값을 byte 단위로 하나씩 가져오는 것이 아니라 보통 cache line 단위로 가져온다는 것입니다.

많은 시스템에서 cache line은 64 bytes이지만, 실제 크기는 hardware에 따라 다를 수 있습니다.

따라서 인접한 data를 순서대로 접근하면 이미 가져온 cache line 안의 값을 계속 활용할 가능성이 커집니다.

 

---

2. 왜 중요한가?

현대 애플리케이션에서 성능 병목은 순수한 계산보다 memory access에서 자주 나타납니다.

특히 대량 데이터를 순회하는 code, game loop, log processing, database engine, analytics pipeline, network packet processing에서는 data layout이 성능에 직접 연결됩니다.

Cache locality를 이해하면 다음 질문에 더 정확히 답할 수 있습니다.

1. 왜 std::vector 순회가 linked list 순회보다 빠른 경우가 많은가?
2. 왜 2차원 배열을 row-major 순서로 접근하는 것이 유리한가?
3. 왜 object가 너무 크면 cache 효율이 떨어질 수 있는가?
4. 왜 멀티스레드 counter를 나란히 두면 느려질 수 있는가?
5. 왜 benchmark에서는 CPU 사용률보다 cache miss를 같이 봐야 하는가?

즉, cache locality는 낮은 수준의 hardware 지식으로만 끝나지 않습니다.

container 선택, struct field 배치, batch 처리, thread별 data 분리 같은 실무 설계 기준으로 이어집니다.

 

---

3. 핵심 개념은 cache line이다

Cache line은 CPU cache와 main memory 사이에서 data가 이동하는 기본 단위입니다.

프로그램이 어떤 int 하나를 읽더라도 CPU는 그 주변 bytes를 함께 cache line으로 가져올 수 있습니다.

이때 주변 data를 곧바로 다시 사용하면 cache locality가 좋아지고, 가져온 data를 거의 쓰지 않으면 memory bandwidth와 cache 공간을 낭비하게 됩니다.

 

개념	의미	예시
Spatial locality	가까운 주소의 data를 연속해서 사용할 가능성	배열을 앞에서 뒤로 순회
Temporal locality	최근 사용한 data를 다시 사용할 가능성	작은 lookup table을 반복 사용
Cache miss	필요한 data가 cache에 없어 더 느린 계층에서 가져오는 상황	큰 data를 random access
Cache invalidation	다른 core의 write 때문에 cache line을 다시 받아야 하는 상황	여러 thread가 같은 cache line에 write

Spatial locality와 temporal locality가 좋으면 CPU가 이미 가져온 cache line을 여러 번 활용할 수 있습니다.

반대로 pointer chasing처럼 다음 data 위치가 메모리 곳곳으로 흩어져 있으면 cache miss가 늘기 쉽습니다.

 

---

4. 그림으로 이해하기

Cache locality와 false sharing을 단순화하면 다음처럼 볼 수 있습니다.

 

연속 data 접근은 cache line 재사용을 높이고, false sharing은 서로 다른 thread가 다른 값을 수정하더라도 같은 cache line 때문에 invalidation을 유발할 수 있습니다.

 

왼쪽처럼 연속된 data를 순서대로 읽으면 CPU는 한 번 가져온 cache line 안의 여러 값을 사용할 수 있습니다.

오른쪽처럼 thread별 counter가 논리적으로는 분리되어 있어도 같은 cache line에 놓이면, 각 thread의 write가 서로의 cache line을 계속 무효화할 수 있습니다.

이 현상이 false sharing입니다.

 

---

5. False sharing은 무엇인가?

False sharing은 여러 thread가 서로 다른 data를 수정하지만, 그 data가 같은 cache line에 들어 있어서 발생하는 성능 문제입니다.

논리적으로는 공유하지 않는 값인데 hardware 관점에서는 같은 cache line을 공유하므로, 한 core의 write가 다른 core의 cache line을 invalidation할 수 있습니다.

이 문제는 data race와 다릅니다.

Data race는 correctness bug이고, false sharing은 correctness가 맞아도 성능을 크게 떨어뜨릴 수 있는 cache coherence 문제입니다.

 

구분	Data race	False sharing
문제 성격	정확성 문제	성능 문제
발생 조건	같은 memory location을 동기화 없이 접근하고 write 포함	다른 memory location이 같은 cache line을 공유
결과	undefined behavior 가능	cache invalidation 증가
대응	mutex, atomic, ownership 분리	padding, alignment, thread-local aggregation

False sharing은 profiling 없이 발견하기 어려울 수 있습니다.

코드만 보면 thread들이 서로 다른 index를 쓰기 때문에 안전해 보이지만, 실제 cache line 배치에서는 서로 간섭하고 있을 수 있습니다.

 

---

6. C++ 코드로 연결해보기

다음 코드는 false sharing 자체를 benchmark하는 예제는 아닙니다.

대신 작은 counter 두 개가 같은 cache line에 들어갈 수 있고, alignas로 padding한 counter는 cache line을 분리할 수 있다는 점을 출력으로 확인합니다.

#include <cstddef>
#include <iostream>

struct Counter {
    long long value;
};

struct PaddedCounter {
    alignas(64) long long value;
};

int main()
{
    constexpr std::size_t assumed_cache_line = 64;

    std::cout << std::boolalpha;
    std::cout << "assumed cache line: "
              << assumed_cache_line << " bytes\n";
    std::cout << "Counter size: "
              << sizeof(Counter) << " bytes\n";
    std::cout << "PaddedCounter size: "
              << sizeof(PaddedCounter) << " bytes\n";

    std::cout << "two Counter objects may share one cache line: "
              << (sizeof(Counter) * 2 <= assumed_cache_line) << '\n';
    std::cout << "two PaddedCounter objects may share one cache line: "
              << (sizeof(PaddedCounter) * 2 <= assumed_cache_line) << '\n';
}

 

실행 결과

assumed cache line: 64 bytes
Counter size: 8 bytes
PaddedCounter size: 64 bytes
two Counter objects may share one cache line: true
two PaddedCounter objects may share one cache line: false

 

Counter는 8 bytes라서 여러 개가 같은 cache line에 들어갈 수 있습니다.

반면 PaddedCounter는 alignas(64) 때문에 객체 하나가 64 bytes alignment를 요구하고, 이 예제에서는 size도 64 bytes가 됩니다.

실무에서는 C++17의 std::hardware_destructive_interference_size를 사용할 수 있는 환경도 있지만, compiler와 standard library 지원 여부를 확인해야 합니다.

또한 무조건 padding을 넣으면 memory 사용량이 늘어나므로 hot write path에서만 근거를 가지고 적용해야 합니다.

 

---

7. 실무에서는 어떻게 볼까?

Cache locality는 C++ container 선택과 data layout에서 자주 드러납니다.

std::vector는 element가 연속적으로 배치되기 때문에 순차 접근에서 cache locality가 좋습니다.

반면 linked list는 각 node가 memory 여기저기에 흩어질 수 있어 pointer chasing과 cache miss가 늘기 쉽습니다.

물론 모든 상황에서 std::vector가 정답은 아니지만, 단순 순회가 많고 element 이동 비용이 관리 가능하다면 연속 memory layout의 이점이 큽니다.

 

상황	확인할 것	가능한 개선
큰 배열 순회가 느림	접근 순서, stride, cache miss	연속 접근, blocking, data layout 재검토
객체 배열 순회가 느림	실제로 사용하는 field가 일부인지 확인	AoS와 SoA 비교
멀티스레드 counter가 느림	thread별 data가 같은 cache line에 있는지 확인	padding, alignas, thread-local aggregation
lock은 적은데 scaling이 안 됨	cache coherence traffic 확인	공유 write 줄이기, batch update

실제 성능 분석에서는 perf, Instruments, VTune 같은 profiler로 cache miss, branch miss, memory bandwidth, CPU pipeline stall을 함께 봐야 합니다.

추측으로 padding을 넣거나 container를 바꾸면 memory 사용량만 늘고 효과가 없을 수 있습니다.

좋은 접근은 먼저 hot path를 찾고, 그 다음 data access pattern을 확인한 뒤, 작은 변경으로 측정하는 것입니다.

 

---

8. 면접 질문 예시

이 주제는 컴퓨터 구조와 실무 성능 감각을 함께 묻기 좋습니다.

1. Cache locality가 무엇인지 설명해보세요.
   CPU가 이미 cache에 가져온 data를 얼마나 잘 재사용하는가의 문제이며, spatial locality와 temporal locality로 나누어 설명할 수 있습니다.
2. std::vector가 linked list보다 순회에서 빠른 경우가 많은 이유는 무엇인가요?
   std::vector는 element가 연속된 memory에 있어 cache line 재사용이 쉽고 prefetch에 유리합니다. linked list는 node가 흩어져 pointer chasing과 cache miss가 늘 수 있습니다.
3. False sharing은 data race와 어떻게 다른가요?
   Data race는 correctness 문제이고 false sharing은 서로 다른 data가 같은 cache line에 있어 cache invalidation이 늘어나는 성능 문제입니다.

좋은 답변은 cache를 단순히 빠른 memory라고 설명하는 데서 끝나지 않습니다.

Cache line, locality, memory layout, multi-core cache coherence까지 연결하면 실무적인 답변이 됩니다.

 

---

9. 자주 하는 오해

1. Big-O가 같으면 성능도 비슷하다.
   같은 O(n)이라도 cache locality, branch prediction, memory bandwidth에 따라 실제 시간은 크게 달라질 수 있습니다.
2. False sharing은 같은 변수를 공유할 때만 생긴다.
   서로 다른 변수라도 같은 cache line에 있으면 false sharing이 생길 수 있습니다.
3. Padding을 넣으면 항상 빨라진다.
   Padding은 memory 사용량을 늘립니다. Hot write path에서 false sharing이 확인된 경우에만 제한적으로 적용해야 합니다.
4. Cache 문제는 시스템 프로그래머만 신경 쓰면 된다.
   대량 data 처리, 게임, 서버, DB, analytics code에서는 일반 application 개발자도 cache locality의 영향을 받습니다.

핵심은 cache를 추상적인 hardware 계층으로만 보지 않고, data layout과 access pattern의 결과로 보는 것입니다.

 

---

10. 정리

CPU cache는 main memory 접근 비용을 줄이기 위해 cache line 단위로 data를 가져옵니다.

Spatial locality와 temporal locality가 좋으면 이미 가져온 cache line을 더 잘 재사용할 수 있습니다.

std::vector 같은 연속 memory layout은 순차 접근에서 cache locality에 유리한 경우가 많습니다.

False sharing은 서로 다른 data가 같은 cache line을 공유해 thread 간 불필요한 cache invalidation을 만드는 성능 문제입니다.

성능 개선은 추측보다 profiler와 benchmark로 hot path, cache miss, memory access pattern을 확인한 뒤 적용해야 합니다.

 

Cache locality를 이해하면 container 선택과 data layout이 단순한 취향이 아니라 성능 설계의 일부라는 점이 보입니다.

 

---