연속 배치: std::vector
순차 순회가 캐시 라인을 따라 진행됩니다.
01234567
공간 지역성이 좋아 반복문이 예측 가능하게 움직입니다.
캐시는 다음에 읽을 값이 가까울수록 유리하다
같은 원소 수라도 연속 배치는 한 번 가져온 캐시 라인을 더 많이 재사용하고, 포인터 추적은 매번 다른 위치로 뛸 수 있습니다.
포인터 추적: list/tree
논리적으로는 다음 원소지만 물리 주소는 흩어질 수 있습니다.
node A → 다른 주소
node B → 또 다른 주소
node C → 새 캐시 라인
캐시 미스가 많으면 알고리즘보다 메모리 대기가 병목이 됩니다.
캐시 최적화의 첫 질문은 “자료구조 이름”이 아니라 “읽는 순서와 메모리 배치가 가까운가”입니다.