Lock-Free 는 과연 빠른가?

아래의 테스트 코드로 Lock을 사용한 알고리즘과 LockFree 알고리즘의 성능을 간단히 비교해보았다.
아래 코드는 n개의 변수를 atomic하게 변경할 때, 두 방식의 퍼포먼스를 비교하기 위한 것이다. Lock-free 구현 시 2개 이상의 변수를 atomic 하게 변경하는 범용적인 알고리즘은 존재하지 않으므로, 각각 독립된 n개 변수를 변경하는 것으로 비교하였다.

아래 코드는 쓰레드 간 충돌이 발생하지 않는 상황에서 테스트되었다. 일반적인 멀티쓰레드 프로그램 내에서 동일변수(또는 집합)을 동시에 참조하는 경우는 극히 드물게 발생하므로 그로 인한 실질적인 성능 감소는 무시할 수 있기 때문이다.


// Test code

CRITICAL_SECTION cs;

void compare_lock_free(int cntTest) {
const int TEST_LOOP = 1000 * 10000;
 volatile LONG v[20] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

ULONGLONG t0 = ::GetTickCount64();
for (int i = 0; i < TEST_LOOP; i ++) {
::EnterCriticalSection(&cs);
volatile LONG* p = v;
for (int j = 0; j < cntTest; j ++) {
_asm mov eax, p;
_asm inc [eax];
p ++;
}
::LeaveCriticalSection(&cs);
}
ULONGLONG t1 = ::GetTickCount64();
for (int i = 0; i < TEST_LOOP; i ++) {
volatile LONG* p = v;
for (int j = 0; j < cntTest; j ++) {
_asm mov eax, p;
_asm lock inc [eax];
p ++;
}
}
ULONGLONG t2 = ::GetTickCount64();
for (int i = 0; i < TEST_LOOP; i ++) {
volatile LONG* p = v;
for (int j = 0; j < cntTest; j ++) {
::InterlockedIncrement(p);
p++;
}
}
ULONGLONG t3 = ::GetTickCount64();
printf("test = %d : lock = %d, lock_free 1 = %d, lock_free 2 = %d\n", 
cntTest, (int)(t1-t0), (int)(t2-t1), (int)(t3-t2));
}

// 실행 결과.
test =  1 : lock = 202, lock_free 1 = 110, lock_free 2 = 78
test =  2 : lock = 234, lock_free 1 = 171, lock_free 2 = 172
test =  3 : lock = 218, lock_free 1 = 250, lock_free 2 = 234
test =  4 : lock = 234, lock_free 1 = 343, lock_free 2 = 281
test =  5 : lock = 234, lock_free 1 = 437, lock_free 2 = 358
test =  6 : lock = 234, lock_free 1 = 515, lock_free 2 = 421
test =  7 : lock = 250, lock_free 1 = 593, lock_free 2 = 499
test =  8 : lock = 250, lock_free 1 = 686, lock_free 2 = 562
test =  9 : lock = 265, lock_free 1 = 733, lock_free 2 = 624
test = 10 : lock = 281, lock_free 1 = 811, lock_free 2 = 702

보다시피 3번 이상 atomic 연산이 필요한 경우, CriticalSection을 사용한 알고리즘이 더욱 빨리 실행된다. 일부러 함께 비교한 InterlockedIncreement() 함수가 assembly 코드보다 더 효율적인 것으로 나오는 것도 참고할 필요가 있을 것이다. 일부러 assembly 쓸 필요가 없다는. ^^

BeginCriticalSection() 과 EnterCriticalSection() 내부에서 _asm lock 이 각각 1회 이상 사용되므로, 결국 _asm lock 호출 회수에 의해 성능차이가 발생하는 것이라 하겠다. 위 코드를 pthread mutex 를 사용하는 것으로 바꾸어도 결과는 마찬가지일 것이다. x86의 _asm lock 오퍼레이션은 수백 사이클 이상 소모되는 매우 고비용 명령어임을 위 결과로 확인할 수 있다.

단 하나의 변수만을 치환할 때 CriticalSection 과 lock-free 알고리즘의 차이는 100ms / 천만, 즉 10ns 정도 차이가 발생한다. 서버 성능에 따라 좀 더 차이가 있을 수는 있겠으나, 일반적인 상황에서 이 정도 차이는 무시해도 무방할 정도이다.

다음 글에서는 쓰레드간 충돌이 매우 빈번하게 발생하는 경우에 대해 다뤄보도록 하겠다.