cache line 크기는 현대 CPU에서 보통 64바이트입니다. 4바이트 int 하나를 읽어도 그 주소를 포함한 64바이트가 통째로 올라오므로, 이웃한 int 15개는 공짜로 딸려 옵니다. 배열을 순차 접근하면 16번 접근 중 miss는 첫 번째 한 번뿐인 셈입니다. cache line이 공간 지역성을 하드웨어로 구현한 장치인 이유입니다.

이 효과를 체감할 수 있는 고전적 예가 2차원 배열 순회 방향입니다. 행 우선으로 저장된 배열을 행 방향으로 돌면 cache line을 꽉 채워 쓰지만, 열 방향으로 돌면 접근마다 다른 line을 건드려 매번 miss에 가까워집니다. 같은 O(n²) 이중 루프인데 순회 방향만 바꿔도 몇 배씩 느려질 수 있습니다.

평범한 루프 하나에 두 지역성이 모두 들어 있습니다. 루프 counter와 누적 변수는 매 반복마다 다시 쓰이니 시간 지역성이고, 배열 원소를 앞에서부터 차례로 읽는 것은 공간 지역성입니다. 지역성이 특별한 최적화 기법이라기보다, 대부분의 코드가 자연스럽게 갖는 성질이고 캐시는 그 성질에 베팅하는 장치입니다.

데이터만이 아니라 명령어에도 같은 원리가 적용됩니다. CPU에는 명령어 전용 캐시(L1i)가 따로 있는데, 루프는 같은 명령어를 반복 실행하므로 시간 지역성이 좋고, 분기 없이 이어지는 코드는 공간 지역성이 좋습니다. 함수를 잘게 쪼개 여기저기로 점프하는 코드보다 순차적으로 흐르는 코드가 명령어 캐시에도 유리합니다.

linked list가 불리한 이유는 miss가 잦다는 것 이상입니다. 다음 노드의 주소가 현재 노드를 읽어야만 알 수 있으므로, 메모리 접근이 직렬화됩니다. 배열이라면 CPU가 다음 접근 주소를 미리 알아 병렬로 가져올 수 있지만, pointer chasing은 매 단계가 이전 단계의 RAM 응답을 기다려야 하는 사슬이 됩니다.

현대 CPU에는 접근 패턴을 감시하다가 규칙적인 패턴(순차, 일정 간격)을 감지하면 다음 데이터를 미리 가져오는 하드웨어 prefetcher가 있습니다. 배열 순회는 prefetcher가 가장 잘 돕는 패턴이라 miss 자체가 사라지지만, 노드가 힙 여기저기에 흩어진 linked list는 다음 주소를 예측할 수 없어 prefetcher가 무력합니다. Big-O가 같은 순회라도 실측에서 배열이 몇 배씩 빠른 이유입니다.

miss의 원인은 세 종류로 구분합니다. 처음 접근이라 캐시에 있을 수 없는 cold miss, 작업 데이터가 캐시 용량보다 커서 밀려난 capacity miss, 용량은 남는데 여러 주소가 캐시의 같은 자리를 두고 경합해 생기는 conflict miss입니다. 원인에 따라 처방이 다릅니다. capacity miss는 한 번에 다루는 데이터 블록을 줄이는 것(blocking, tiling)이 해법이고, conflict miss는 데이터 배치를 바꾸는 것이 해법입니다.

CPU도 기다림을 숨기려 노력합니다. 비순차 실행(out-of-order execution)으로 memory 대기 중에 의존성 없는 다른 명령을 먼저 실행하고, hyper-threading은 한 thread가 stall된 동안 다른 thread의 명령을 실행합니다. 그러나 수백 cycle의 RAM 접근을 전부 숨기기에는 부족해서, 결국 접근 패턴을 캐시 친화적으로 만드는 것이 근본 해법입니다.

LFU(Least Frequently Used)는 사용 횟수가 가장 적은 데이터를 내보냅니다. 단점은 오래 전에 폭발적으로 쓰이고 이후 전혀 쓰이지 않는 데이터가 높은 빈도 수 덕분에 캐시에 오래 남는 문제가 있습니다.

LRU는 CPU 캐시(하드웨어 근사 구현)와 OS 페이지 교체, 웹 캐시 등 다양한 곳에서 쓰입니다.

원인은 캐시 일관성(cache coherence) 프로토콜이 line 단위로 동작한다는 데 있습니다. 각 코어는 자기 캐시를 따로 가지므로, 한 코어가 어떤 line에 쓰면 다른 코어가 가진 같은 line의 복사본은 무효화되어야 합니다(MESI 계열 프로토콜). 문제는 이 무효화가 변수 단위가 아니라 64바이트 line 단위라는 점입니다. 두 thread가 서로 다른 변수를 써도 그 둘이 한 line에 있으면, 쓸 때마다 상대 코어의 line을 무효화해 line이 코어 사이를 계속 오가는 ping-pong이 생깁니다.

이름이 false sharing인 이유는 논리적으로는 아무것도 공유하지 않는데 물리적으로만 공유가 일어나기 때문입니다. 해법은 자주 쓰는 변수들을 서로 다른 line에 두는 것으로, thread별 counter 같은 구조에 64바이트 padding을 넣거나 정렬(alignment)을 지정합니다. 멀티스레드 코드가 코어를 늘렸는데 오히려 느려질 때 의심할 대표 원인 중 하나입니다.