캐시를 고려한 코드

캐시의 매핑 방식과 쓰기 정책 같은 하드웨어 구조는 캐시 메모리와 MMU에 있다. 이 노트는 코드를 쓰는 쪽에서 캐시를 어떻게 다뤄야 하는지를 다룬다.

프로그래머는 캐시를 직접 제어하지 않는다

일반 명령어로는 데이터를 어느 캐시 레벨에 둘지 정할 수 없고, 지금 어느 레벨에 있는지도 알 수 없다. x86은 몇 가지 힌트 명령만 준다. CPU는 힌트를 무시할 수 있다.

수동 프리페치가 드물어진 이유는 하드웨어 프리페처가 충분히 똑똑하기 때문이다. 순차 접근이나 일정한 간격(stride)의 접근을 감지해 다음 라인을 미리 가져온다. 그래서 프로그래머의 일은 캐시를 조종하는 것이 아니라 프리페처가 알아볼 수 있는 접근 패턴을 만드는 것이다.

캐시 라인과 접근 패턴

캐시는 바이트가 아니라 캐시 라인(x86·대부분 ARM은 64바이트, Apple M 시리즈는 128바이트) 단위로 가져온다. int 배열의 arr[0]을 읽으면 arr[0]~arr[15]가 함께 온다.

// 행 우선: 연속 주소를 따라감 → 라인 하나로 16개 처리
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) sum += a[i][j];
 
// 열 우선: 매번 N*4바이트씩 건너뜀 → 원소마다 다른 라인
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++) sum += a[i][j];

측정하면 보통 행 우선 < 열 우선 ≪ 무작위 순이다. 열 우선도 간격이 일정해 프리페처가 따라오므로 생각보다 덜 느리다. 진짜로 느린 것은 예측할 수 없는 무작위 접근이다. C는 행 우선 저장이고, Fortran·MATLAB은 열 우선이다.

행렬 곱: 같은 연산, 열 배 차이

res[i][j] += mul1[i][k] * mul2[k][j]는 mul2를 열 방향으로 훑어 매번 다른 캐시 라인을 건드린다. 계산량(O(n³))은 그대로 두고 접근 순서만 바꿔도 결과가 크게 달라진다. 1000×1000 double 행렬 곱을 Core 2에서 잰 결과다.

캐시 라인 크기는 하드코딩하지 말고 sysconf(_SC_LEVEL1_DCACHE_LINESIZE)(Linux)나 std::hardware_destructive_interference_size(C++17)로 얻는다. 실제로는 BLAS·Eigen 같은 라이브러리가 이 최적화를 이미 해 두었으니 직접 짜기 전에 라이브러리를 쓴다.

배열 vs 연결 리스트

시간 복잡도로는 중간 삽입이 배열 O(n), 연결 리스트 O(1)이다. 그런데 실제로는 원소가 수십 개 정도면 배열이 더 빠르고, 순회가 많은 작업에서는 훨씬 큰 크기에서도 배열이 이긴다.

연결 리스트가 필요하면 노드를 미리 큰 덩어리로 할당해 두고 나눠 쓰는 메모리 풀을 쓰면 할당 비용과 단편화를 함께 줄인다. 자료구조를 고를 때는 복잡도와 함께 데이터가 메모리에 어떻게 놓이는지를 본다. 같은 이유로 구조체 배열(AoS) 대신 필드별 배열(SoA)로 바꾸면 한 필드만 순회할 때 캐시를 덜 낭비한다.

데이터베이스도 같은 원리로 빨라진다. 분석용 DB는 행이 아니라 열 단위로 저장해(컬럼 저장) 필요한 열만 연속으로 훑고, 한 행씩이 아니라 값 수천 개 묶음(벡터)으로 연산자를 실행해(벡터화 실행) 호출 비용을 줄이고 SIMD를 쓴다(DuckDB, ClickHouse). B+트리 노드를 캐시 라인·페이지 크기에 맞추고, 해시 조인에서 해시 테이블이 캐시보다 크면 파티션으로 나눠 캐시에 들어가게 하는 것도 캐시 미스를 줄이려는 설계다.

작은 타입이 유리한 이유

현대 x86에서 8·16·32·64비트 정수 덧셈의 지연 시간은 같다. 차이는 메모리에서 난다. 작은 타입은 한 라인에 더 많이 들어가 캐시 적중률이 높다. 그래서 C·C++ 컴파일러는 bool을 1바이트로 둔다. 비트 하나로 줄이면 공간은 아끼지만 꺼낼 때 시프트·마스크 연산이 더 든다. 반대로 임베디드나 특정 연산에서는 결과가 달라질 수 있으므로 성능표를 보고 판단한다.

넌템포럴 저장과 쓰기 결합 버퍼

일반적인 쓰기는 쓰기 할당(write-allocate)이다. 라인 일부만 써도 나머지 바이트를 알아야 나중에 메모리에 되쓸 수 있으므로, 먼저 그 라인을 메모리에서 L1까지 읽어 온다(RFO, Read For Ownership). 큰 버퍼를 한 번만 쓰고 다시 읽지 않는다면 두 가지 손해다.

• 쓰려고 쓸데없이 읽는다.
• 그 데이터가 캐시를 채우며 정말 필요한 데이터를 쫓아낸다(캐시 오염).

넌템포럴(non-temporal) 저장(movntdq, _mm_stream_si128 같은 SIMD 명령)은 "다시 안 쓸 데이터"라고 알려 캐시를 건너뛴다. 데이터는 쓰기 결합 버퍼(WC buffer, Intel은 Line Fill Buffer)에 모였다가 라인 전체가 차면 한 번의 버스트 전송으로 메모리에 간다.

큰 memcpy·memset의 라이브러리 구현이 크기가 충분히 크면 내부적으로 넌템포럴 저장으로 바꾼다. 그래픽 드라이버가 주는 GPU 업로드 버퍼처럼 CPU가 쓰기만 하는 메모리는 페이지 속성 자체를 WC(write-combining) 로 둔다. 이런 버퍼를 CPU에서 읽으면 매우 느리다.

캐시 일관성과 거짓 공유

코어마다 L1·L2를 따로 가지므로 같은 주소의 사본이 여러 코어에 생긴다. 하드웨어는 캐시 일관성 프로토콜로 이를 맞춘다. 대표가 MESI다.

한 코어가 쓰려면 다른 코어의 사본을 무효화해야 한다. 무효화된 코어가 그 라인을 다시 읽으면 최신 값을 가진 코어로부터 받아 온다. 알리는 방식은 둘이다.

MESI에 상태를 하나 더한 변형도 있다. AMD의 MOESI는 O(Owned)를 더해, 수정된 라인을 메모리에 되쓰지 않은 채 다른 코어와 공유하고 O 상태인 코어가 요청에 답한다. 메모리 쓰기가 줄어든다. Intel의 MESIF는 F(Forward)를 더해 S 상태 사본 여럿 중 하나만 요청에 답하게 해 응답이 겹치지 않게 한다. 캐시 일관성은 한 주소에 대한 읽기·쓰기 순서를 맞출 뿐이다. counter++ 같은 읽기-수정-쓰기의 원자성은 보장하지 않으므로 경쟁 상태는 여전히 동기화로 막아야 한다(POSIX 스레드와 동기화 API).

거짓 공유(false sharing) 는 서로 다른 변수인데 같은 캐시 라인에 있어서 생기는 문제다. 두 스레드가 각자 자기 변수만 써도 라인 단위로 무효화가 오가며 라인이 코어 사이를 왕복한다.

같은 라인에 두 스레드가 각자 쓰기      376ms   ← 단일 스레드보다 느림
다른 라인에 두 스레드가 각자 쓰기      120ms
단일 스레드가 전부 쓰기              233ms
(i7-8700K, 10억 회 쓰기 실험)

해결은 스레드별 데이터를 라인 크기만큼 떨어뜨리는 것이다. C11·C++의 alignas(64), C++17의 std::hardware_destructive_interference_size, Java의 @Contended가 이 용도다. 스레드별 카운터를 따로 모았다가 마지막에 합치는 것도 방법이다.

TLB shootdown

TLB는 페이지 테이블 항목의 캐시다(메모리 관리). 페이지 매핑이 바뀌면 다른 코어 TLB의 옛 항목도 지워야 한다. 운영체제는 다른 코어에 프로세서 간 인터럽트(IPI) 를 보내 무효화를 요청하고, 모든 코어의 확인을 받을 때까지 기다린다. 이것이 TLB shootdown이다.

코어가 많고 매핑 변경이 잦으면 이 대기가 큰 비용이 된다. 대용량 데이터를 mmap으로 다루는 멀티스레드 DB가 페이지를 계속 들이고 내보내면 shootdown이 쏟아져 확장성이 떨어진다. DBMS가 mmap 대신 직접 버퍼 풀을 쓰는 이유 중 하나다(UNIX 파일 입출력).

마이크로벤치마크와 캐시

두 구현의 실행 시간을 같은 프로그램에서 차례로 재면 먼저 실행한 쪽이 불리하게 나오는 경우가 많다. 앞의 측정이 입력 데이터, 코드, TLB, 분기 예측기를 데워 두기 때문이다. 순서를 바꿨더니 결과도 뒤집히고, 입력이 작을수록 차이가 크다면 캐시 효과를 의심한다.

측정값이 흔들리는 다른 원인(CPU 주파수 변동, 다른 프로세스, 첫 페이지 폴트)도 있으므로, 같은 조건을 여러 번 재현해 분산까지 본다.

정리

• 캐시는 조종하는 대상이 아니라 접근 패턴으로 협조하는 대상이다.
• 연속 메모리를 순서대로 읽는 코드가 빠르다. 배열 > 포인터 추적, 행 우선 > 무작위.
• 한 번만 쓰는 큰 데이터는 넌템포럴 저장으로 캐시를 지킨다.
• 스레드별로 자주 쓰는 데이터는 캐시 라인 단위로 떨어뜨려 거짓 공유를 막는다.
• 복잡도가 같거나 더 나빠 보여도 캐시를 잘 쓰는 쪽이 이기는 경우가 많다. 판단은 측정으로 한다.

관련 노트: 캐시 메모리와 MMU, 메모리 계층 구조, 현대 CPU의 마이크로아키텍처, POSIX 스레드와 동기화 API