[Cache] 시간 지역성, 공간 지역성

CPU는 빠르지만 메인 메모리라고 하는 RAM은 느립니다. 둘의 속도 차이는 병목 현상을 만들고 이는 성능 저하의 원인 중 하나입니다. 물론 데이터에 접근할 때 일어나는 컨텍스트 스위칭 역시도 성능에 영향을 주겠지만요. 캐시는 CPU와 램(DRAM) 사이에서 중간자 역할을 합니다. 자주 사용되는 데이터를 캐시에 저장하면 CPU가 빠르게 꺼내어 사용할 수 있습니다. CPU에서 요청한 데이터가 캐시 안에 있을 때 캐시 히트라고 합니다(cache hit). 캐시에 존재하지 않으면 캐스 미스(miss)라고 합니다.

 

캐시가 효율적으로 동작하기 위해서는 캐시에 저장할 데이터가 지역성(locality)을 가져야 합니다. 지역성은 시간 지역성과 공간 지역성으로 나뉩니다. 시간 지역성은 데이터의 읽기/쓰기를 위해 특정 메모리가 사용됐을 때 가까운 시일 내에 해당 메모리가 다시 사용될 가능성이 높은 걸 말합니다. 공간 지역성은 특정 데이터와 가까운 주소가 순서대로 접근되는 경우를 말합니다. 한 메모리 주소에 접근할 때 그 주소뿐만 아니라 해당 블록을 전부 캐시에 가져옴으로써 공간 지역성의 효율을 높입니다.

 

#include <chrono>
#include <iostream>
using namespace std;
int matrix[20240][20240] = {};
int main()
{
	auto start = chrono::high_resolution_clock::now();
	for (int i = 0; i < 20240; ++i)
	{
		for (int j = 0; j < 20240; ++j)
		{
			matrix[i][j] = 1;
		}
	}
	auto end = chrono::high_resolution_clock::now();
	auto elapsed = end - start;
	auto elapsedTime = chrono::duration_cast<chrono::milliseconds>(elapsed);
	cout << elapsedTime.count() << endl;

위와 같이 어마어마하게 큰 배열의 각 요소에 값을 할당해야 한다고 해봅시다. m[i][j]에 접근하는 방법에서는 1초가 조금 안 걸렸습니다(ms 기준).

 

m[j][i]로 바꿔서 해보면 메모리에 연속적으로 접근하지 못하게 되면서 시간이 오래 걸립니다. 코드 한 줄 잘못 썼다가 4.5배 차이나는 성능 차이가 발생했습니다.