퀴즈: 다음 코드의 문제점은?

두 스레드에서 각기 다른 변수를 업데이트를 하는 코드였다. 코드에는 전혀 문제가 없으나 성능이라는 관점에서 보면 문제가 있는 코드였다. 문제점은 바로: false sharing. 멀티코어 시스템에서 일어날 수 있는 대표적인 성능하락 주범 중 하나이다. 나도 그냥 얼마나 이게 영향을 미치는가 보기 위해 테스트해봤는데 꽤 큰 수치가 나옴을 알 수 있었다. False sharing을 그림으로 대략 나타내면 아래와 같다.

위 그림은 엑셀로 1분만에 그린 대략적인 캐쉬의 모습. 4-way set-associativity 캐쉬를 그렸고, 주황색 한 블럭은 4바이트를 가리킨다. 그래서 캐쉬 라인의 크기는 64바이트이다. Core 2 Duo 같은 경우는 L2 캐쉬는 공유되어있고 L1 캐쉬가 각자 private 캐쉬니까 false sharing은 L1 레벨에서 일어날 것이다.

False sharing의 자세한 설명은 예전에 쓴 글을 참조하면 되고, 매우 간단히 설명하면: 빨간 색 두 블럭으로 표현된 두 4바이트 데이터가 두 스레드로부터 접근된다고 하자. 이 캐쉬는 한 코어의 모습이고, 듀얼 코어라면 이런 상태가 두 코어에게 존재한다. 그런데 이 두 빨간 데이터는 서로 공유되지 않고 있다. 그런데 같은 캐쉬 라인에 올라와있기 때문에 어느 한쪽이 여기에 데이터를 쓰면 다른 쪽 캐쉬에게 이 라인을 무효화 시키게 된다. 그래서 각 스레드가 데이터를 쓰려고 할 때 마다 캐쉬 라인을 무효화 시키기 때문에 성능 하락이 일어난다.

반면, 녹색 블럭으로 표현된 데이터는 다른 캐쉬 라인에 있기 때문에 어느 한 쓰레드가 이 데이터를 고쳐도 무효화 신호를 보낼 필요가 없기 때문에 빠르게 자기 사본만 업데이트를 할 수 있다.

당연히 private cache가 없는 싱글코어 CPU나 하이퍼스레딩 CPU는 이런 일이 벌어지지 않는다. 만약, L2 캐쉬도 각각 독립적인 예전 Pentium-D라면 성능 하락은 더욱 클 것 같다.

사실 원 문제에 있던 코드는 조금 억지이다. 그런데 이런 경우는 malloc을 이용할 경우에도 얼마든지 일어날 수 있다. 두 스레드가 malloc으로부터 각각 4바이트를 할당 받고 접근한다고 생각해보자.

DWORD CALLBACK TestThread1(void* arg)
{
    volatile int& data1 = *((int*)malloc(4));
    _tprintf(_T("%d\n"), &data1);
    for (int i = 0; i < 500000000; ++i)
        data1 = data1 + 1;
    return data1;
}
  
DWORD CALLBACK TestThread2(void* arg)
{
    volatile int& data1 = *((int*)malloc(4));
    _tprintf(_T("%d\n"), &data1);
    for (int i = 0; i < 500000000; ++i)
        data1 = data1 + 1;
    return data1;
}

만약, 위 코드에서 각 스레드가 할당 받은 데이터의 주소가 8421184, 8421200와 같이 16바이트 정도만 떨어져있다면, 위 그림의 빨간 블럭처럼 같은 캐쉬라인에 배치될 확률이 높다. 그렇게 되면 위의 설명한 일이 고스란히 벌어지고 성능 하락이 된다. 이런 false sharing이 일어날 경우, 위 코드는 약 1.5초가 걸렸으며, false sharing이 일어나지 않도록 좀 떨어져서 메모리가 할당되게 해보니 1.15초 정도가 나왔다. 물론 이런 코드는 극단적이지만 30%라는 결코 무시할 수 없는 성능 차이가 있다. 고성능 서버나 속도가 단 1초라도 중요한 코드에서는 이런 점을 고려해야할 것이다.

사실 이런 문제는 운에 달려있다. malloc이 어떤 방식으로 메모리를 줄지 예측하기는 불가능하다. 그래도 익히 알려진 malloc 알고리즘을 가지고 유추해볼 때, 보통은 근접한 메모리가 할당된다. 그래서 이런 경우 문제 해결이 쉽지 않다. 대안으론 각 스레드마다 별도의 힙 할당 관리자를 둘 수도 있다. 마찬가지로 원래 퀴즈에 있었던 코드도 그 데이터가 어떤 주소에 할당될지 예측하기가 쉽지 않다.

그래도 원래 코드의 문제점을 해결한 코드를 대략 써보면 아래와 같다. 단순히 data1, data2 선언 사이에 넉넉하게 배열을 선언한다고 해서 쉽게 해결되지는 않았다. 왜냐면 전역 공간에 할당된 변수들의 주소가 선언대로 할당되는 것이 아니었다. 직접 data1, data2 메모리 주소를 찍어보면 여전히 인접하게 할당되었다 (VC++ 컴파일러는 그랬음). 그래서 구조체로 감싸는 방법으로 회피하였다.

volatile struct {
    int data1;
    int data[32];
    int data2;
} DATA;    
 
DWORD CALLBACK TestThread1(void* /*arg*/)
{
    _tprintf(_T("Thread1: %d\n"), &DATA.data1);
    for (int i = 0; i < 500000000; ++i)
        DATA.data1 = DATA.data1 + 1;
    return DATA.data1;
}
 
DWORD CALLBACK TestThread2(void* /*arg*/)
{
    _tprintf(_T("Thread2: %d\n"), &DATA.data2);
    for (int i = 0; i < 500000000; ++i)
        DATA.data2 = DATA.data2 + 1;
    return DATA.data2;
}

이런식으로 할 경우 확실하게 두 데이터가 다른 캐쉬 라인에 올라가는 것을 보장할 수 있으므로 성능 저하를 막을 수 있다. 그리고 테스트를 좀 세밀히 해보니 정확하게 Core 2 Duo의 캐쉬 라인 사이즈인 64바이트만큼 간격이 확보될 때, 성능이 개선됨을 찾을 수 있었다. 아주 심심한 분들께선 한번 직접 테스트해보고 성능 차이를 올려주시면 고맙겠습니다. 해당 CPU도 같이 써주시면 고맙겠습니다.

// 코멘트들에 대한 답변:

kc님: 정확하게 말씀하셨습니다. 오래전에 쓴 글인데 아직까지 기억하시는군요 :)

까막님: 용어는 다소 틀렸지만 cache invalidation은 맞습니다. 그리고 보다시피 이건 힙에서도 얼마든지 일어날 수 있습니다.

uriel님: 이 경우에는 두 스레드 사이에 명시적인 데이터 공유가 없는 상황입니다. 그래서 락 혹은 atomic operation을 쓸 필요는 없습니다. 혹시 Interlocekd*를 써서 코드를 돌려보시면 알겠지만 코드가 엄청나게 느려집니다. 테스트해보니 1초 걸리는 코드가 20초가 되네요.. 락이나 atomic increment는 상당한 오버헤드를 유발합니다.

rein님: 인텔 TBB (Thread Building Block)에서 제공되는 malloc은 false sharing을 피하기 위해 malloc을 캐쉬 라인 단위로 뛰어가며 하는 것 같네요. 멀티코어에서 사용되는 malloc은 당연히 이런 점을 고려해야 합니다.

자연푼선생: 이 경우는 스레드 각각이 각기 다른 물리코어에 할당되어 돌아갑니다. 물론 이건 운영체제 스레드 스케쥴링 정책에 따라 다르지만 거의 이런 경우 독립적인 코어에 스레드가 할당이 되기 때문에 이 둘 사이의 컨텍스트 스위칭으로 인한 비용은 없습니다. 만약 싱글 코어에서 이렇게 만들면 컨텍스트 스위칭 비용이 상당합니다. 테스트해보니 당연히 두배로 증가합니다 :) 테스트를 하기 위해서는 아래 함수를 불러주세요.

SetProcessAffinityMask(GetCurrentProcess(), 1);

즉, CPU 1번에만 이 프로세스의 스레드들이 올라가게 합니다. 3을 주면 CPU 1, 2번에게 할당 됩니다. 그래서 여담이지만 CPU 개수만큼 빡세게 돌아가는 스레드를 만드는 것이 좋습니다.

이홍석님: 위에 답변도 있었지만 x++과 x = x + 1은 x86으로서는 완전히 동일한 코드가 나옵니다.

orge님: 싱글코어에서는 캐쉬 사본이 존재하지 않으므로 서로의 사본을 무효화시키라는 메세지도 발생할 일이 없습니다. Core 2 Duo는 오히려 Shared L2 캐쉬이므로 이런 경우 이득을 볼 수 있을 것 같습니다. Pentium D 같은 private L2 캐쉬 구조에서는 더 성능이 하락될 것 같습니다. 요건 추측이고 직접 테스트를 해봐야겠네요. 참고로 Core 2 Duo에서는 약 20% 정도의 성능 차이가 있었습니다.