[부연] CAS Lock Lock-Free 알고리즘은 과연 빠른가?
아래와 같은 글이 있군요. ^^
Lock-Free 알고리즘은 과연 빠른가?
; http://little-thread.blogspot.kr/2014/08/lock-free.html
결론은 CAS Lock
lock-free보다 CriticalSection을 쓴 것이 더 빠르다는 것입니다.
그런데, 약간 테스트 상에 공정성이 위배되는 것이 있습니다. CriticalSection은 블록으로 썼으면서,
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);
}
CAS Lock
lock-free 쪽은 매순간 lock을 거는 방식을 썼습니다.
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++;
}
}
CAS Lock
lock-free를 블록으로 사용하는 방법은 조금 미루고 바로 위에 소개한 2개의 테스트를 좀 볼까요? 우선 _asm으로 인라인 시킨 경우 실행시 기계어가 이렇고,
mov eax,dword ptr [ebp-0C0h]
lock inc byte ptr [eax]
InterlockedIncrement의 경우 결국 다음과 같은 기계어로 인라인 되므로,
mov eax,dword ptr [ebp-0F4h]
mov ecx,1
lock xadd dword ptr [eax],ecx
별반 큰 차이가 없습니다. 재미있는 것은 기계어가 오히려 1개 더 늘었는데도 "
Lock-Free 알고리즘은 과연 빠른가?" 글에 공개된 수치를 보면 InterlockedIncrement의 성능이 근소하게 빠르다는 점입니다.
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
그나저나, CAS Lock
lock-free를 블록으로 사용하는 방법이 뭘까요? 예전에 이에 대해 한번 소개해 드렸었지요. ^^
CAS Lock lock-free 방식이 과연 성능에 얼마나 도움이 될까요?
; https://www.sysnet.pe.kr/2/0/1458
저 역시 위의 글에서 C#의 경우 lock 코드가 CAS Lock
lock-free보다 더 빠르다고 결론을 내렸었습니다. 따라서 저 글의 코드를 유사하게 가져다가 테스트를 할 수 있습니다.
volatile unsigned int _lockVariable = 0;
ULONGLONG t3 = ::GetTickCount64();
for (int i = 0; i < TEST_LOOP; i++) {
volatile LONG* p = v;
while (::InterlockedCompareExchange(&_lockVariable, 1, 0) != 0)
{
}
for (int j = 0; j < cntTest; j++)
{
_asm mov eax, p;
_asm inc[eax];
p++;
}
_lockVariable = 0;
}
테스트 결과가 궁금하지 않으세요? ^^ 다음은 제 컴퓨터에서 수행한 것입니다.
test = 1 : lock = 203, lock_free 1 = 78, lock_free 2 = 78, lock_free 3 = 250
test = 2 : lock = 188, lock_free 1 = 125, lock_free 2 = 125, lock_free 3 = 265
test = 3 : lock = 203, lock_free 1 = 204, lock_free 2 = 187, lock_free 3 = 266
test = 4 : lock = 218, lock_free 1 = 250, lock_free 2 = 235, lock_free 3 = 281
test = 5 : lock = 219, lock_free 1 = 312, lock_free 2 = 297, lock_free 3 = 297
test = 6 : lock = 234, lock_free 1 = 360, lock_free 2 = 359, lock_free 3 = 313
test = 7 : lock = 234, lock_free 1 = 422, lock_free 2 = 422, lock_free 3 = 328
test = 8 : lock = 266, lock_free 1 = 500, lock_free 2 = 484, lock_free 3 = 359
test = 9 : lock = 266, lock_free 1 = 547, lock_free 2 = 547, lock_free 3 = 375
test = 10 : lock = 281, lock_free 1 = 609, lock_free 2 = 594, lock_free 3 = 391
오호~~~ 그래도 CriticalSection보다 성능이 낮군요. 그러나 이것은 DEBUG 빌드의 결과물입니다. Release 빌드로 하면 상황이 역전됩니다.
test = 1 : lock = 187, lock_free 1 = 78, lock_free 2 = 47, lock_free 3 = 109
test = 2 : lock = 204, lock_free 1 = 125, lock_free 2 = 109, lock_free 3 = 94
test = 3 : lock = 203, lock_free 1 = 187, lock_free 2 = 157, lock_free 3 = 78
test = 4 : lock = 203, lock_free 1 = 250, lock_free 2 = 203, lock_free 3 = 109
test = 5 : lock = 219, lock_free 1 = 313, lock_free 2 = 265, lock_free 3 = 94
test = 6 : lock = 203, lock_free 1 = 391, lock_free 2 = 312, lock_free 3 = 94
test = 7 : lock = 219, lock_free 1 = 453, lock_free 2 = 359, lock_free 3 = 110
test = 8 : lock = 218, lock_free 1 = 516, lock_free 2 = 406, lock_free 3 = 125
test = 9 : lock = 219, lock_free 1 = 594, lock_free 2 = 453, lock_free 3 = 125
test = 10 : lock = 219, lock_free 1 = 671, lock_free 2 = 500, lock_free 3 = 141
보시는 바와 같이 새롭게 추가한 "lock_free 3" 번의 결과는 CriticalSection 보다 성능이 더 좋습니다.
(
첨부한 코드는 "
Lock-Free 알고리즘은 과연 빠른가?" 글에 공개된 것에 블록 방식의 lock-free 코드를 추가한 것입니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]