Microsoft MVP성태의 닷넷 이야기
VC++: 79. [부연] Lock-Free 알고리즘은 과연 빠른가? [링크 복사], [링크+제목 복사]
조회: 12361
글쓴 사람
정성태 (techsharer at outlook.com)
홈페이지
첨부 파일

[부연] Lock-Free 알고리즘은 과연 빠른가?

아래와 같은 글이 있군요. ^^

Lock-Free 알고리즘은 과연 빠른가? 
; http://little-thread.blogspot.kr/2014/08/lock-free.html

결론은 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);
}

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++;
    }
}

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




그나저나, lock-free를 블록으로 사용하는 방법이 뭘까요? 예전에 이에 대해 한번 소개해 드렸었지요. ^^

lock-free 방식이 과연 성능에 얼마나 도움이 될까요?
; https://www.sysnet.pe.kr/2/0/1458

저 역시 위의 글에서 C#의 경우 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 코드를 추가한 것입니다.)




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]

[연관 글]


donaricano-btn



[최초 등록일: ]
[최종 수정일: 8/20/2014

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer at outlook.com

비밀번호

댓글 쓴 사람
 



2014-08-26 12시13분
위에서 제가 제시한 방법은 엄밀히 lock-free라고 볼 수 없고, 그냥 CAS를 이용한 lock을 한 것에 불과합니다. lock-free에 대한 자세한 사항은 다음의 글을 참조하세요. ^^

Chapter 17. Boost.Lockfree
; http://www.boost.org/doc/libs/1_53_0/doc/html/lockfree.html

Ndc2014 시즌 2 : 멀티쓰레드 프로그래밍이 왜 이리 힘드나요? (Lock-free에서 Transactional Memory까지)
; http://www.slideshare.net/zzapuno/ndc2014-2
정성태
2021-05-15 11시48분
정성태

1  2  3  4  [5]  6  7  8  9  10  11  12  13  14  15  ...
NoWriterDateCnt.TitleFile(s)
12638정성태5/12/2021301사물인터넷: 63. NodeMCU v1 ESP8266 - 펌웨어 내 파일 시스템(SPIFFS, LittleFS) 및 EEPROM 활용
12637정성태5/10/2021320사물인터넷: 62. NodeMCU v1 ESP8266 보드의 A0 핀에 다중 아날로그 센서 연결 [1]
12636정성태5/10/2021350사물인터넷: 61. NodeMCU v1 ESP8266 보드의 A0 핀 사용법 - FSR-402 아날로그 압력 센서 연동파일 다운로드1
12635정성태5/9/2021282기타: 81. OpenTabletDriver를 (관리자 권한으로 실행하지 않고도) 관리자 권한의 프로그램에서 동작하게 만드는 방법
12634정성태5/9/2021306개발 환경 구성: 572. .NET에서의 신뢰도 등급 조정 - 외부 Manifest 파일을 두는 방법파일 다운로드1
12633정성태5/7/2021362개발 환경 구성: 571. UAC - 관리자 권한 없이 UIPI 제약을 없애는 방법
12632정성태5/7/2021339기타: 80. (WACOM도 지원하는) Tablet 공통 디바이스 드라이버 - OpenTabletDriver
12631정성태5/5/2021312사물인터넷: 60. ThingSpeak 사물인터넷 플랫폼에 ESP8266 NodeMCU v1 + 조도 센서 장비 연동파일 다운로드1
12630정성태5/5/2021325사물인터넷: 59. NodeMCU v1 ESP8266 보드의 A0 핀 사용법 - CdS Cell(GL3526) 조도 센서 연동파일 다운로드1
12629정성태5/5/2021403.NET Framework: 1057. C# - CoAP 서버 및 클라이언트 제작 (UDP 소켓 통신)파일 다운로드1
12628정성태5/4/2021253Linux: 39. Eclipse 원격 디버깅 - Cannot run program "gdb": Launching failed
12627정성태5/4/2021300Linux: 38. 라즈베리 파이 제로 용 프로그램 개발을 위한 Eclipse C/C++ 윈도우 환경 설정
12626정성태5/3/2021343.NET Framework: 1056. C# - Thread.Suspend 호출 시 응용 프로그램 hang 현상 (2)파일 다운로드1
12625정성태5/3/2021402오류 유형: 714. error CS5001: Program does not contain a static 'Main' method suitable for an entry point
12624정성태5/2/2021539.NET Framework: 1055. C# - struct/class가 스택/힙에 할당되는 사례 정리 [6]파일 다운로드1
12623정성태5/2/2021339.NET Framework: 1054. C# 9 최상위 문에 STAThread 사용파일 다운로드1
12622정성태5/2/2021221오류 유형: 713. XSD 파일을 포함한 프로젝트 - The type or namespace name 'TypedTableBase<>' does not exist in the namespace 'System.Data'
12621정성태5/1/2021527.NET Framework: 1053. C# - 특정 레지스트리 변경 시 알림을 받는 방법파일 다운로드1
12620정성태4/29/2021779.NET Framework: 1052. C# - 왜 구조체는 16 바이트의 크기가 적합한가? [1]파일 다운로드1
12619정성태4/28/2021648.NET Framework: 1051. C# - 구조체의 크기가 16바이트가 넘어가면 힙에 할당된다? [1]파일 다운로드1
12618정성태4/27/2021390사물인터넷: 58. NodeMCU v1 ESP8266 CP2102 Module을 이용한 WiFi UDP 통신파일 다운로드1
12617정성태4/26/2021296.NET Framework: 1050. C# - ETW EventListener의 Keywords별 EventId에 따른 필터링 방법파일 다운로드1
12616정성태4/26/2021273.NET Framework: 1049. C# - ETW EventListener를 상속받았을 때 초기화 순서파일 다운로드1
12615정성태4/26/2021192오류 유형: 712. Microsoft Live 로그인 - 계정을 선택하는(Pick an account) 화면에서 진행이 안 되는 문제
12614정성태4/24/2021372개발 환경 구성: 570. C# - Azure AD 인증을 지원하는 ASP.NET Core/5+ 웹 애플리케이션 예제 구성 [2]파일 다운로드1
12613정성태4/23/2021282.NET Framework: 1048. C# - ETW 이벤트의 Keywords에 속한 EventId 구하는 방법 (2) 관리 코드파일 다운로드1
1  2  3  4  [5]  6  7  8  9  10  11  12  13  14  15  ...