얼마 전에 좋은 질문이 있길래 조금 더 깊이있게 풀이해보고 싶어서 정리좀 해봤어. 일단 예제 코드를 먼저 볼게.
int a[20][20] = {1,};
for (int i=0; i<20; i++) {
for (int j=0; j<20; j++) {
sum += a[i][j];
}
}
원본 질문은 저 2차원 배열에서 어떤 차원을 먼저 반복하는게 빠른 지가 질문이었어. 이 질문은 단순하지만 사실 쉽게 대답하긴 힘든 내용이야. 왜냐하면 메모리 캐시가 어떻게 이루어지는지 제대로 알고 있어야 대답할 수 있거든.
간단한 답부터 먼저 말해보면 저 코드에 한해서는 최하단 차원부터 반복하는게 가장 빨라. 저러면 거의 대부분 캐시힛이 발생하거든. 그런데 자료구조에 따라 더 빠르지는 않고 동일할 수 있기도 해. 이런 반례들은 천천히 아래에서 설명할게.
일단 cpu 얘기를 안할 수 없으니 조금 길게 살펴볼게. 현대의 cpu는 L1, L2, L3 캐시 메모리가 cpu on chip으로 달려있고, 실제 메모리는 외부 RAM(16, 32GB 등)을 사용하게 돼. 예전에 펜티엄 이전 싱글코어 시절에는 메인보드에 cpu 캐시가 추가되어 나오는 경우도 있었다고 하던데 요즘에는 예외없이 cpu에 포함되어 있어.
아래는 실제 cpu인 amd 5600x의 캐시 메모리 사양표야.
Cores 6
L1 Cache 64K (per core)
L2 Cache 512K (per core)
L3 Cache 32MB (shared)
위에 나온대로 L1, L2 캐시는 6개의 코어(!)마다 저 용량만큼 하나씩 가지고 있고, L3는 모든 코어가 같이 공유하는 캐시 메모리야. 그리고 cpu 캐시 메모리는 SRAM, 외부 RAM은 DRAM으로 만들어져있어. 그래서 cpu 캐시 메모리는 일반 RAM보다 더 빠르지만 그만큼 비싼 녀석이야.
사양표에 안나온 얘기 조금만 더 해보면, L1 캐시는 다시 데이터와 명령어 캐시로 나눠져서 각각 32KB씩 할당되어 각 타입에 맞게 캐싱하게 되는데 보통 L1d/L1i라고 약어처럼 사용하고, TLB(Translation Lookaside Buffer)란 녀석도 있는데 가상 메모리 주소와 물리 주소의 변환 테이블 역할이고, 만약 TLB miss 발생 시 받은 주소를 변환해서 TLB에 적어두고 다음에 요청이 오면 이를 사용하게 돼.
그럼 캐시는 항상 클수록 좋을까? L1이 아예 L3처럼 크면 안되는건가? 라는 의문을 가질 수 있는데 이건 참 미묘한 문제야. 캐시 접근 측면에서는 어차피 반복문으로 찾지 않고 O(1) 복잡도로 바로 접근이 가능하니 용량이 클수록 캐시힛 비율이 높아져서 좋긴 한데 커질수록 다른 cpu의 캐시와 경합을 벌이거나 캐시의 쓰기 동작의 발생 시에 갱신해야하는 캐시 비용들로 인한 캐시 레이턴시가 길어지는 단점이 있거든. 그리고 캐시 관리 측면에서도 용량이 클수록 알고리즘(LRU, LFU..)에 따라 효율이 떨어지긴 하니까. 뭐 보통 캐시는 적당히 클수록 좋긴 한데 얼마나 큰게 효율적인지 intel, amd 아키텍쳐 분들이 잘 해주실테니 우린 상관없긴 해. (사실 가격 상승만 아니면 크게크게 만들것 같기도 하고..)
잠깐 또 생각난건데 amd를 망하기 직전까지 만들었던 비운의 프로세서 '불도저'가 캐시 정책 부분을 잘못 만들어서 그렇게나 속도가 느렸다고 해. L2, L3용량을 동일하게 8MB로 늘였는데 그러다보니 L2, L3 접근할 때의 캐시 레이턴시가 그 때 나온 인텔과 비교해 두배나 느려서 모든 벤치 하위권에다가 cpu 클럭은 높아서 전성비 나쁘기로 유명했어. 이걸 보면 멀티 프로세서 시대에서는 cpu 클럭만큼 아키텍쳐가 중요한 이유이기도 하고.
최근에 amd에서 3D V-Cache라고 cpu위에 메모리를 적층하는 모델이 나왔더라고. 5800X3D라는 cpu인데 L3 캐시 용량이 전작보다 세배 증가했다고 해. (5800X:32MB, 5800X3D:96MB) 전작 cpu랑 비교한 벤치보니까 일반적인 부분에서는 조금 더 높긴 한데 차이가 크진 않다가 cpu 몰빵한 게임에서는 정말 유의미하게 높게 나오긴 하더라. (로아나 배그에서 20~30% 프레임 향상)
너무 잡설이 길었네. 어쨌든 cpu랑 캐시에 대해 잠깐 살펴봤는데 다시 돌아와서 이제 기억이 희미해진 예제 코드를 한 번 더 보자구.
int a[20][20] = {1,};
for (int i=0; i<20; i++) {
for (int j=0; j<20; j++) {
sum += a[i][j];
}
}
여기서 a[0][0]을 최초 접근할 때 어떤 동작이 발생하는지 볼게.
a[0][0]에 접근하면 먼저 L1 캐시에 해당 주소가 캐시되어 있는지 살펴보고, 없으면 L2 -> L3 -> RAM으로 점점 내려가면서 읽게 돼. 따라서 캐시 미스는 여러 번 발생할 수 있지만 우리는 통상적으로 L3 캐시에 없을 때에야 비로소 캐시 미스라고 부르고 있어.
이렇게 순차적으로 접근하다보니 데이터가 어느 캐시까지 있는지에 따라 조금씩 차이가 있어. 인텔 cpu 문서에 cache and memory subsystem 항목에서 access latency 보면 아래처럼 나와있어. (i7 기준)
L1: 4 (clocks)
L2: 10
L3: 35~40
자. 이걸 기준으로 잠깐 계산해보면 cpu가 2GHz라고 할 때에 L1 캐시 레이턴시가 4 clocks니까 4 / 2GHz = 2ns 로 L1 캐시 레이턴시가 2나노세컨드인걸 알 수 있어. 근데 우리가 L2에 접근할 때는 L1에 검색했다가 없어서 L2로 간거니 10 / 2GHz + L1 = 5ns + 2ns = 7ns.. 이걸 쭉 정리해볼게.
L1: 4 / 2Ghz = 2ns
L2: 10 / 2GHz + L1 = 5 + 2 = 7ns
L3: 36 / 2GHz + L2 = 18 + 7 = 25ns
RAM: DRAM latency + L3 = 60 + 25 = 85ns
DRAM latency는 인터넷 검색해보니 대충 50~150 사이라고 하는데 그냥 60으로 써봤어. 어쨌든 캐시 미스가 발생해서 단계가 내려갈 때마다 2,3배씩 느려지는걸 확인할 수 있어.
다시 예제로 돌아와서 캐시가 비어있다고 가정하면, a배열에 최초 접근 시에는 캐시 미스가 발생할테니 메모리까지 가서 값을 가져오게 돼. 그럼 그 값을 L3, L2, L1 캐시에 순차적으로 등록해서 사용할 수 있어. (이 부분은 cpu에 따라 정책이 다를 수 있어)
근데 가져올 때 딱 4바이트만 가져오면 너무 작고 효율이 안나잖아? 지금 탐색으로 들어간 비용이 얼만데.. 그래서 접근하는 메모리 주소부터 시작해서 일정 구역을 가져오도록 되어 있어. 최근 cpu는 보통 64byte로 설정되어 있는데 이 값을 cache line size, 가져온 구역 하나를 cache line이라고 불러.
그럼 L1d 캐시가 32KB인 cpu의 cache line size가 64byte라고 한다면 캐시 라인 수는 몇 개일까? 답은 32 * 1024 / 64 = 512개야. 그래서 캐시 라인을 512개만큼 유지하다가 캐시 정책에 의해 만료되는 라인에 다시 쓰고 그러면서 캐시가 동작해.
우리 예제에서는 어디까지 캐시힛이 발생할건지 예측해볼게. 아래는 a배열을 16진수로 출력해 본 실제 주소값이야.
a[0][0]:7fff8981c830
a[0][1]:7fff8981c834
a[0][2]:7fff8981c838
a[1][0]:7fff8981c880
a[1][1]:7fff8981c884
a[1][2]:7fff8981c888
최하단 배열은 해당 배열의 자료형(int)만큼 증가되는걸 볼 수 있고, 상위 배열은 0x50만큼 그러니까 10진수로 80만큼 증가했어. cache line size가 64byte니까 최초에 a[0][0]를 읽으면서 캐시 라인에 등록되면 a[0][15]까지 캐시힛이 발생해. 그러다가 a[0][16]에 접근하면 캐시 미스가 되었다가 캐시를 새로 쓰고, a[0][17]을 읽을 때에는 방금 전에 추가된 캐시로 인해 캐시힛이 발생하게 돼. 결국 16번마다 1번씩 캐시 미스가 발생하니 이대로면 캐시 미스가 6.25%가 나오는 로직이 되겠지.
그럼 반대로 상위 차원으로 반복하는 a[j][i]는 어떻게 될까? 먼저 a[0][0]부터 시작해서 a[j][0]까지 최초 반복 시에는 모두 캐시 미스가 발생할거야. 그리고 그 다음 반복 시에는 a[0][1]을 읽을텐데 a[0][0]이 캐시에 들어있을까? 모르지. 아까 L1 캐시 라인이 512개라고 했잖아? 예제에서는 배열이 20개 뿐이라서 캐시힛이 될 확률이 높긴 한데 배열이 1000개였으면 당연히 L1 캐시에는 없을거야. a[488][0] ~ a[999][0]까지 512개만 L1 캐시에 존재하겠지.
L2 캐시에는 있을까? 그것도 L2 캐시 라인 개수에 따라 다르지만 L3에는 아무래도 있을 확률이 높아. L3 캐시가 워낙 크기도 하고 배열 개수에 비해 데이터가 매우 작으니까. 만약 L3에 존재한다고 하면 캐시 미스까진 아니더라도 L1, L2 캐시를 지나 L3 캐시 접근 비용인 25ns 이후에 데이터를 받을 수 있을거야.
여기서 캐시 미스가 얼마나 성능 하락을 발생시키는지 간단히 계산해볼게. 2GHz cpu는 0.5ns마다 한번씩 cycle을 돌고 있어. 명령어마다 필요한 cycle이 다르지만 평균 2cycle이라고 하면 1ns당 1개의 명령을 실행할 수 있겠지. 근데 캐시 미스가 발생하면 아까 RAM에서부터 가져오는 비용이 85ns라 그랬잖아? 그럼 이론적으로 캐시 미스 한번마다 85개 명령을 실행하지 못하는 손해볼 수 있다는거야.
그래서 큰 데이터를 처리하는 극도로 최적화된 코드를 보면 캐시 미스를 최대한 줄이기 위해 그 다음에 사용할 데이터를 미리 prefetch하는 코드도 있고 그래. inline asm을 사용하거나 volatile 지정자로 컴파일러 최적화 시에도 사라지지 않도록 하는데 실제로 내가 c++로 엔진 코드를 짤 때에 다음에 계산할 3d 모델을 prefetch하는 방식으로 속도를 개선해 본 적이 있어.
여기까진 사실 이론적인 얘기고, 실제로 적용되면 어떤 문제가 발생할 지 한 번 예상해볼까?
일단 cpu는 시분할 시스템을 사용하잖아? 그러니 지금 하는 동작이 인터럽트로 인해 잠깐 멈추고 다른 프로그램을 실행한다면 어떻게 될까? L1~L3 캐시가 그 프로그램에 의해 일부 덮어씌워지겠지. 그렇게 작업하다가 다시 돌아오면 캐시는 제대로 남아있지 않을거야. 그럼 캐시 미스가 발생할테고 이로 인해 예상보단 큰 시간이 걸리겠지.
그러면 이번엔 멀티 프로세서를 생각해보자. 지금 실행되던 동작이 인터럽트로 인해 멈췄다가 내가 원래 실행하던 cpu1번이 아닌 cpu2번으로 할당된다면 어떻게 될까? cpu가 바뀌는 컨텍스트 스위칭이 되면 register 정보는 PCB(Process Control Block)에서 가져오겠지만 해당 cpu2번에는 L1, L2 캐시에 이전 내용이 없어서 캐시 미스까진 아니더라도 L3에서 가져오는 비용을 치러야 할거야. 물론 거기도 없으면 RAM까지 가겠지.
이런 상황이 안생기게 하려고 각 운영체제에서는 프로그램이 최초 실행될 때 할당된 cpu에서 어지간한 상황에서는 바뀌지 않기도 해. 다만 다중 스레드라던가 여러가지 상황으로 인해 제어권이 뺏길 수 있어서 지정된 번호의 cpu를 우선적으로 할당하는 명령도 있어. 대표적으로 윈도우에서는 작업관리자에서 set affinity 메뉴가 있지. 근데 사실 이걸로 성능 테스트를 해본 적은 없어서 잘 작동하는지 확신은 못하겠네.
이 외에 더 생각해보면 좋을 시나리오는 데이터 하나가 cache line size를 넘어가는 자료를 가진 배열의 캐시 동작을 예상해보고 최적화 방향을 고민해 본다던가, 반복문에서 비동기 함수를 호출하게 되면 어떻게 될 지 생각도 해보고 뭐 여러가지가 있을 것 같아. 이런건 답은 없으니 상상으로 남겨둘게.
난 과거에 이런 최적화에 대해 한참 파보다가 나중에 좀 시들해졌는데 내가 굳이 이걸 고민하지 않아도 컴파일러가 알아서 파이프라이닝 잘 되게 instruction 위치랑 데이터 로드하는 위치도 잘 바꿔 주고, 알아서 L1i에 캐시힛 가능하도록 인라인 함수도 만들어주고 그러더라고. cpu는 또 얼마나 똑똑해졌는지 대충 만들어도 자주 실행하는 함수는 하드웨어에서 명령 예측 분기로 예측 실패도 막아주고.. 거기서 더 발전했으니 이제는 진짜 로직에만 집중할 수 있는 좋은 시대구나 싶기도 하고 그러네.
결론)
1) 다차원 배열은 최하위 차원부터 반복하면 캐시힛 확률이 높다
2) 캐시 미스는 상당히 큰 비용이 든다
3) 다만 이론과 실제 동작에는 많은 차이가 있으니 실제 벤치마킹 전에는 확신하지 말자
여기 내용들은 내가 공부했던 지식이 몇년 전에서 멈춰있는 관계로 지금 작동 방식이나 수치가 좀 다를 수 있어. 예를 들면 M1은 아예 system on chip이라고 표방하며 ram, gpu까지 cpu 하나에 다 넣었잖아? 그에 따라 캐시 정책이 많이 달라졌겠지. (근데 애플 얘네들은 왜 cpu 아키텍쳐 관련된 공식 세부 문서가 하나도 없지? 내가 못 찾는건가..)
어쨌든 이 글에서는 큰 맥락만 이해해주면 좋겠고, 혹시 틀린 내용이 있거나 요즘 트렌드에 대한 새로운 소식을 알고 있다면 덧글로 같이 얘기해보면 좋겠어.
긴글 읽느라 고생했어. 연휴 잘 보내.
#frogred8 #cache #cpu
내용 추가)
예제 코드에서 배열 크기만 1000*1000으로 바꿔서 캐시 미스 테스트한 결과.
i,j = 0.8%
j,i = 12.5%
<< i,j >>
D refs: 10,297,745 (8,032,396 rd + 2,265,349 wr)
D1 misses: 127,434 ( 64,197 rd + 63,237 wr)
LLd misses: 127,011 ( 63,850 rd + 63,161 wr)
D1 miss rate: 1.2% ( 0.8% + 2.8% )
LLd miss rate: 1.2% ( 0.8% + 2.8% )
<< j,i >>
D refs: 10,297,745 (8,032,396 rd + 2,265,349 wr)
D1 misses: 1,064,939 (1,001,696 rd + 63,243 wr)
LLd misses: 127,877 ( 64,700 rd + 63,177 wr)
D1 miss rate: 10.3% ( 12.5% + 2.8% )
LLd miss rate: 1.2% ( 0.8% + 2.8% )
