앞서 이글은 igoros 라는 분의 Gallery of Processor Cache Effects 글을 번역한 것을 토대로 작성되있음을 알립니다. 링크는 마지막 레퍼런스에 있습니다.
캐시는 cpu의 입장에서는 너무나도 느린 메모리(RAM)에서 데이터를 가져오는 시간을 줄이기 위해서 나온 개념이다. 미리 캐시에 데이터를 한꺼번에 저장한 뒤, 데이터를 찾는 식이다. 보통은 최근 접근한 메모리의 주변 값들을 캐시에 적재한다.
개발자들은 캐시에 대해서 한번씩 들어보곤 했을 것이다. 캐시는 매우 작고 비싼 메모리이다. 그러나 많은 사람들이 캐시가 어떻게 동작하는지, 그리고 실제 프로그램에 영향이 얼마나 있는지 잘 알지 못한다. 따라서 이 글에서는 몇가지 재미있는 예제를 통해서 캐시의 동작을 알아보도록 할 것이다.
예제 1) 캐시라인 측면에서 메모리 접근
아래 코드는 1~1024까지 2씩 곱해가며 총 10번 내부 loop를 실행하면 배열에 접근하는 코드이다. 예상대로라면 k가 2배씩 늘어나기 때문에, 성능도 2배에 가깝게 줄어들어야 할 것이다.
int* arr = new int[1024 * 1024 * 256];
//아래 두줄은 시간측정용 변수
auto start = chrono::high_resolution_clock::now();
auto end = chrono::high_resolution_clock::now();
//k*2 씩하며 증가
for (int k = 1; k <= 1024; k *= 2)
{
start = chrono::high_resolution_clock::now();
for (int i = 0; i < 1024 * 1024 * 256; i += k)
{
arr[i] *= 2; //인덱싱
}
end = chrono::high_resolution_clock::now();
cout << "time(ms) : " << (end - start).count() / 1000000 << endl;
}결과
그러나 위 그래프를 보면 그렇지 않다. 오히려 k가 2~16일때는 차이가 미미했다. 그러나 16 이후부터는 약 1.7배씩 속도가 빨라지는 것을 볼 수 있다. 이유는 캐시라인 때문이다. cpu는 메모리에서 데이터를 1byte씩 꺼내는 것이 아니라 (일반적인)캐시라인의 크기인 64byte씩 캐시로 적재한 후에 캐시에서 데이터를 검색한다. int 형은 4바이트이기 때문에 16개가 캐시라인의 크기와 딱 들어맞기 때문에 위와 같은 결과가 나오게 된 것이다. 결과를 다르게 해석해보면, cpu에서 명령어를 실행하는데는 매우 적은 시간이 소요되지만, 물리적인 메모리에서 데이터를 인출하는데 크게 시간이 소요된다고 해석할 수도 있다.
예제 2) L1,L2,L3 캐시
cpu-z 라는 프로그램 또는 cpuid라는 함수를 사용하면 cpu에 대한 다양한 정보를 알 수 있는데, 아래 사진에서 필자의 cpu인 i7-9750h(6c/12t) 는 코어당 32kb 의 L1캐시(명령어/데이터)가 각각 6개, 256kb 의 L2 캐시가 6개, 12mb의 L3캐시가 한개 있는 것을 볼 수 있다. 나의 경우 L1, L2 캐시는 코어당 하나씩 있고 , L3캐시는 모든 코어가 공유한다고 볼 수 있겠다.
캐시는 Level 1 -> Level 3 으로 갈 수록 커지지만 느려진다. 캐시 메모리가 커질 수록 당연히 검사하는 시간도 오래 걸리기 때문에 L1 부터 데이터를 검색하여 L3 까지 내려간다. 여기서 찾지 못하는 것을 캐시 미스라고 하며, 이 경우 메모리에서 데이터를 검색한다.
아래 예제는 배열의 크기를 늘려가며 인덱싱한다. (x & (l-1) = x%l)
double prev = 0;
for (size_t size = 256; size <= 268435456; size *= 2) //1kb ~1GB
{
alignas(64) int* arr = new int[size]{ };
auto start = chrono::high_resolution_clock::now();
for (int i = 0; i < size; i++)
arr[(i*16)&(size-1)]++;
auto end = chrono::high_resolution_clock::now();
delete []arr;
//cout<< (end - start).count() << endl;
if (prev != 0)
cout << (end - start).count() / prev << endl;
prev = (end - start).count();
}결과
오차는 있지만 그래프의 시간 증가율을 보면 L1 캐시 크기인 32kb에서 L2 캐시로 넘어가는 32->64 구간에서 값이 급등하고 L2 캐시 크기인 256k에서 L3 캐시로 넘어가는 256->512 구간에서 값이 튀는 것을 볼 수 있다. L3 캐시 구간도 미미하지만 튀는 것을 볼 수 있다.
외에도 캐시 알고리즘에 관한 것도 있는데, 이 부분은 개발자가 신경쓸 수 있는 부분이 아닌 것 같아서 뺐다. 아래 레퍼런스의 Cache associativity 단락에 자세한 내용이 나와있다.
Reference
http://igoro.com/archive/gallery-of-processor-cache-effects/
