faster / smaller
registers -> L1 -> L2 -> last-level cache -> RAM -> storage
slower / larger

지역성

시간 지역성은 최근 사용한 값을 다시 사용할 가능성이고, 공간 지역성은 가까운 주소를 곧 사용할 가능성입니다. CPU는 메모리에서 필요한 바이트 하나만 가져오기보다 cache line 단위로 주변 데이터를 가져옵니다.

// 연속 주소를 순서대로 읽어 공간 지역성을 활용합니다.
for (std::size_t i = 0; i < values.size(); ++i) {
    sum += values[i];
}

연결 리스트는 삽입·삭제에 장점이 있지만 노드가 메모리에 흩어지면 다음 노드를 읽을 때마다 cache miss가 날 수 있습니다. 자료구조 선택에서는 이론적 복잡도와 실제 배치를 함께 봅니다.

성능 읽기

cache hit이면 가까운 계층에서 데이터를 얻고, miss이면 더 느린 계층으로 내려갑니다. miss가 많아지면 CPU가 연산보다 데이터를 기다리는 시간이 커집니다. 구조체 배열과 배열 구조체, 반복 순서, working set 크기가 성능에 영향을 주는 이유입니다.

멀티스레드에서는 서로 다른 thread가 같은 cache line의 값을 자주 쓰는 false sharing도 문제가 됩니다. 서로 다른 변수라도 같은 line에 놓이면 core 사이의 cache coherence 갱신이 반복될 수 있습니다.

자주 틀리는 점

• cache 크기와 단계는 CPU 모델마다 다르므로 고정 숫자를 일반 규칙처럼 외우지 않습니다.
• O(1) 접근이 항상 같은 실제 시간을 뜻하지 않습니다.
• 연속 메모리가 무조건 최선은 아닙니다. 삽입 비용, 수명, 메모리 사용량도 함께 봅니다.
• 수동 prefetch나 padding은 profiler로 병목을 확인한 뒤 적용합니다.