캐시 친화적 코드란? (번역)

게임과 같은 극한의 성능이 요구되는 환경에서는 캐시 hitting률을 높이는 것이 중요하다. 그래서 data - oriented design같이 data들을 configous하게 배치해서 캐시 히트를 높이고자 한다.
그런데 이론적으로는 캐시에 대해 빠삭한 데 어떻게 이걸 코드에 접목시킬 수 있을까??
그래서 스택오버플로우를 검색하던 중 좋은 글을 발견해서 번역해보자한다.

Cache - Friendly 코드란 무엇일까?
https://stackoverflow.com/questions/16699247/what-is-a-cache-friendly-code ( Marc Claesen )

기초 지식 :

현대 컴퓨팅 환경에서 가장 낮은 Level의 메모리 즉 레지스터는 한 클록 사이클만에 데이터를 옮길 수 있다. 그러나 레지스터는 매우 비싸고(가격적인 면에서) 대다수의 CPU 코어들이 적은 수의 레지스터를 가지고 있다. 반면 흔히 메인메모리라 부르는 DRAM은 값이 매우 매우 싸다. 그렇지만 요청된 데이터를 처리하기 위해서는 몇백 클록 사이클이 필요하다. 이렇게 속도와 가격이라는 두 간극을 절충하기 위해 L1, L2, L3 캐시 같이 캐시를 여러 레벨로 나누어져있다.(L3로 갈 수록 속도는 느리지만 가격이 더 싸다). 프로그램에서 대개 소수의 변수들이 메모리 접근의 대다수를 차지하고 나머지 대다수의 변수들은 가끔 접근한다. 만약 CPU 프로세서가 L1캐쉬에서 원하는 데이터를 찾지 못하면 L2를 뒤져보고, 그래도 찾지 못하면 L3 마지막으로 메인 메모리를 뒤져서 원하는 데이터를 찾는다. 이렇게 각 메모리 Level에서 원하는 데이터를 찾지 못하는 “miss”들은 성능면에서 매우 느리다.(오버헤드가 크다)

캐싱이라는 기법은 데이터 전송의 지연 속도를 낮추는 주요 전략입니다. Herb Sutter을 의역하면 ( 아래의 링크를 참조하시오. ) “대역폭(bandwidth)을 높이는건 쉽지만 그것이 지연속도(latency)를 낮추지는 않습니다.”

데이터는 항상 메모리 계층 ( 가장 작은 것 == 가장 빠르다 )을 통해 접근된다. 캐시 히트/미스는 대개 가장 높은 단계의 캐시에서의 히드/미스를 말한다. 여기서 말하는 가장 높은 단계란 가장 사이즈가 큰, 즉 가장 느린 메모리 계층을 말한다. 캐시 미스가 발생하여서 데이터를 DRAM에서 가져오는 것은 매우 느리기 때문에 캐시 히트율을 높이는 것이 성능 향상을 위해 매우 중요하다.

현대 컴퓨터 아키텍쳐에서 병목(bottleneck) 현상은 CPU를 죽이고 있다. 이러한 현상은 날이 갈수록 심해질 것이다. 이제 더 이상 프로세서 클록 속도의 향상이 성능 향상을 불러오지 않는다. 이제는 메모리 접근 속도 향상을 통해 성능 향상을 꾀해야한다. 그러므로 현재 CPU 아키텍쳐 디자이너들은 성능 향상을 위해 캐시를 최적화, Prefetching, pipeline, concurrency 같은 부분에 집중하고 있다. 예를 들어보면 현대 cpu들은 CPU Die의 85% 정도를 캐시로 사용하고 CPU Die의 대다수를 데이터 전송과 저장에 사용하고 있다. ( 99% 까지 )

이 주제에 대해서는 말할 것들이 많은 데 여기 캐시와 메모리 계층, 적절한 프로그래밍에 대한 자료를 제공해주겠다.

Agner Fog의 글. 그의 excellent한 문서에서 당신은 어셈블리에서 C++에 이르는 매우 디테일한 예제들을 볼 수 있을 것이다.
영상 자료를 찾는 다면 이 영상을 추천하고 싶다. Herb Sutter의 컴퓨터 아키텍쳐에 대한 Talk (특히 12분을 집중해서 봐라!!).
Christer Ericson의 메모리 최적화에 대한 슬라이드 (director of technology @ Sony)
LWN.net’s article “What every programmer should know about memory”

캐쉬 친화적 코드의 주요 전략

캐시 친화적 코드의 가장 중요한 점은 지역성의 원리(the principle of locality)이다. 이는 연관된 데이터(서로 인접하게 사용되는)들을 메모리상에서 가까운 위치에 할당해 캐싱 효율성을 높이는 것이다. CPU 캐시의 측면에서 봤을 때 이것이 어떻게 동작하는지를 이해하기 위해서는 캐시 라인(Cache Line)을 이해하는 것이 매우 중요한데 이 캐시 라인이 어떻게 동작하는지를 알아보자.

아래에 나오는 여러 요소들은 캐싱을 최적하 하기 위해 매우 중요한 것들이다.

시간적 지역성 : 한 메모리 위치에 접근 했을 때 단시간 내에 다시 같은 메모리 위치에 접근하는 경우를 말한다. 이상적으로는 이 경우 해당 메모리 위치의 데이터가 캐시에 존재한다.(즉 매우 빠르게 접근할 수 있다)
공간적 지역성 : 이것 관련된 데이터들을 메모리 위치상 인접하게 배치하는 것을 말한다. 예를 들면 너가 RAM에서 데이터를 읽어 올 때 딱 그 데이터 하나만 전송되는 게 아니라 데이터 뭉치(Chunk)(Cache Line을 말하는 것 같다)가 전송된다. 왜냐면 대개 프로그램은 요청된 데이터를 읽어 온 후 곧이어 그 주위에 있는 데이터를 요청하는 경우가 많이 때문이다.(어차피 좀 있다 요청할 꺼 미리 그 주위의 데이터들까지 가져오는 것이다.) HDD 캐시 또한 그러한 아이디어를 채용하여 작동한다. CPU 캐시에서 캐시 라인의 개념은 매우 중요하다.

적절한 C++ Containers를 사용하라

캐시 친화적 대 반친화적의 대표적인 예는 std::vector와 std::list이다. std::vector은 연속된 메모리에 데이터들을 저장한다. 그래서 std::vector에 저장된 데이터에 접근하는 것은 std::list의 데이터에 접근하는 것에 비해 더 캐쉬 친화적이다. (std::list의 데이터들은 여러 장소에 퍼져있다, 연속되어 있지 않다. 멀리 떨어져 있다)

C++의 창시자 Bjarne Stroustrup 선생께서 이에 대한 좋은 영상을 올려주셨습니다. youtube clip

데이터 구조나 알고리즘을 디자인 할 때 캐시에 집중하다

가능하면 데이터 구조나 연산의 순서를 캐시의 활용을 극대화 하는 방법으로 만들기 위해 노력하라. 이에 대한 흔한 기술로는 캐시 블로킹(cache blocking)이 있다.( Archive.org version ) 이 캐시 블로킹은 ATLAS같은 곳에서 성능향상을 위해 매우 매우 중요하게 쓰인다.

데이터 내부 구조에 대해 알고 활용하라

현역에서 활동중인 많은 프로그래머들이 자주 잊고 있는 것이 2차원 배열을 저장하기 위해 사용되는 “열 우선 저장” 대 “행 우선 저장”의 두 상반된 Ordering 방법에 대한 것이다.
아래와 같은 예를 생각해보자.

행렬 :
1 2
3 4
행 우선 개념에서는 위의 데이터는 1, 2, 3, 4 순으로 저장된다. 반면 열 우선 개념에서는 1, 3, 2, 4 순으로 저장된다. 이러한 저장 순서를 활용하지 않는 프로그램 구현은 캐시 이슈(miss)를 맞닥뜨릴 것이다. 불행히도 나는 이러한 것들을 현재 내가 종사하는 분야( 머신 러닝 )에서 자주 보았다.

메모리에서 행렬의 특정한 값을를 가져올 때 그 데이터 주위에 있는 값들도 함께 가져와서 캐시 라인에 같이 저장된다. 만약 위에 나온 ordering 방법을 활용하면 DRAM으로의 접근(Cache miss)을 최소화 할 수 있다. ( 왜냐면 행렬의 한 값을 가져 올 때 다음 연산에도 사용할 주위 값을 함께 가져오게 ordering 방법을 체택할 수 있기 때문이다. )

간단한 예를 들어보면 행렬의 값 중 2개만 캐시 라인에 저장될 수 있다고 가정할 때 아래의 경우를 보자.

Ordering을 활용한 경우
M[0][0] (DRAM)) + M[0][1] (캐시) + M[1][0] (DRAM) + M[1][1] (캐시)
= 1 + 2 + 3 + 4
–> 2 캐시 히트, 2 DRAM 접근

Ordering을 활용안한 경우
M[0][0] (DRAM) + M[1][0] (DRAM) + M[0][1] (DRAM) + M[1][1] (DRAM)
= 1 + 3 + 2 + 4
–> 0 캐시 히트, 4 DRAM 접근

위의 간단한 예에서 ordering을 활용한 경우는 대략 아닌 경우에 비해 2배의 성능 향상을 보였다.

예측 불가능 한 분기(if)는 피하라

현대 아키텍쳐 특징인 파이프라인과 컴파일로는 메모리 접근으로 인한 지연을 최소하 하기 위한 코드 재배치에 매우 능숙하다. 너의 핵심 코드가 예측 불가능한 분기를 가지고 있을 때 데이터를 미리 가져오는 것 Cache Prefetch을 거의 불가능하다. 이것은 더 많은 캐시 미스로 이끌 것이다.

아래의 링크가 이에 대해 잘 설명하고 있다 : Why is processing a sorted array faster than processing an unsorted array?

가상 함수 사용을 자제하라

C++에서 가상함수는 캐시 미스와 관련해 논란이 될만한 문제를 일으킨다. ( 성능향상을 위해서는 가능하면 가상함수를 자제해야 한다는 것에는 대다수의 사람들이 동의한다.) 자주 호출되지 않는 가상 함수를 호출하기 위해 가상 함수 테이블에서 가상 함수를 찾는 과정에서 캐시 미스가 발생하다. 그래서 만약 가상 함수가 자주 호출되는 경우에는 이는 별 문제가 되는 않는다. 이와 관련해서는 C++ 클래스에서 가상함수를 가지는 것의 비용은 어느 정도되는가?를 참조하라. ( 글쓴이는 가상 함수 호출시 명령어의 캐시 미스를 큰 성능 저하 요소로 꼽았지만 위의 링크에서도 나오듯이 가상 함수를 호출 전 Branch Predict하여서 예측한 가상 함수를 기반으로 이후 명령어들을 CPU 파이프라인 올려둔 상태에서 예측이 틀린 경우 미리 올려둔 명령어들을 모두 없애고 실제 호출할 가상 함수에 대한 명령어를 CPU 파이프라인에 올려야한다. 이 과정에서 큰 성능 저하가 발생한다. )

흔한 문제들

멀티 코어 캐시들을 가지는 현대 CPU 아키텍쳐에서 가장 흔한 문제는 가짜 공유(False sharing)이다. 이것은 각각의 cpu 코어가 서로 다른 위치의 메모리의 데이터를 사용하고 그것을 같은 캐시 라인에 저장할 때 발생한다. 이것은 캐시 라인이 계속해서 덮어 씌어지게 해 성능 하락을 유발한다. 여러 스레드들이 이 상황에서 캐시 미스를 발생시켜 서로를 기다리게 만든다. 이 링크 또한 참고하라 어떻게 그리고 언제 캐시 라인 사이즈에 align하는가.
( 역주 : 각 코어가 서로 다른 주소에 데이터를 쓰더라도, 두 주소가 physical memory 상의 동일한 캐시 라인에 속해 있다면 두 코어간의 캐시 동기화가 필요하다. 이를 False Sharing이라고 한다. 추가로 이 글을 읽어보세요. )

DRAM 메모리에서 최악의 캐싱을 지칭하는 thrashing이라는 개념도 잇다. 이것은 프로그램이 계속해서 page faults(찾고자 하는 데이터가 캐시에도 없고 DRAM에도 없는 경우, 이 경우 virtual memory 즉 HDD에 저장되어 있다)를 발생시켜서 디스크에 접근해야하는 경우를 말한다.

위의 Marc Claesen의 답변에 더하여 나는 반 캐시 친화적 코드의 유익한 예로 행 우성이 아닌 열 우선으로 2차원 배열을 탐색하는 코드를 들고 싶다.

행에서 인접한 값들은 메모리에 인접해 있다. 그래서 그러한 데이터에 연속적으로 접근하는 것은 오름 차순의 메모리 순서로 데이터에 접근하는 것을 의미한다. 이는 캐시가 그 주위 데이터들도 함께 가져오기 때문에 매우 캐시 친화적인다.

반면 열 우선으로 탐색하는 것은 반 캐시 친화적이다. 왜냐하면 같은 열에 있는 데이터들은 메모리 위치 상으로는 떨어져 있기 때문이다. ( 한 열에 있는 데이터들 사이의 메모리 상의 거리는 열의 길이와 같다. ) 그래서 너각 이러한 패턴(열 우선)으로 메모리 상의 데이터에 접근할 때는 인접한 데이터를 가져오는 캐시의 노력을 헛수고로 만든다.

캐시 친화적 버전 - 인접한 데이터에 접근한다.

for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

반 캐시 친화적 버전 - 별 다른 이유 없이 메모리들을 널뛰듯 접근하고 있다.

for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

캐시 사이즈가 작거나 매우 큰 배열을 작업할 때 이러한 두 방법의 성능 차이는 매우 매우 크다.
이러한 이유로 만약 너가 세로 탐색을 해야한다면, 이미지 픽셀 탐색을 시작하기 전 이미지를 90도 돌려 놓고 탐색을 하는 것이 차라리 더 빠를 것이다.

SungJin Kang

캐시 친화적 코드란? (번역)