WORD에 대한 cmpxchg가 BYTE보다 빠릅니다.

Question

어제 저는 빠른 스핀 록 작성 방법에 대해 this question을 게시했습니다. Cory Nelson 덕택에 제 질문에서 논의 된 다른 방법들보다 성능이 우수한 방법을 찾은 것 같습니다. CMPXCHG 명령을 사용하여 잠금이 0인지 무료인지 확인합니다. CMPXCHG은 'BYTE', WORD 및 DWORD에서 작동합니다. 나는 지시가 BYTE에 더 빨리 작동한다고 가정 할 것이다. 하지만 데이터 유형의 각을 구현하는 잠금을 썼다 :

inline void spin_lock_8(char* lck) 
{ 
    __asm 
    { 
     mov ebx, lck      ;move lck pointer into ebx 
     xor cl, cl       ;set CL to 0 
     inc cl        ;increment CL to 1 
     pause        ; 
     spin_loop: 
     xor al, al       ;set AL to 0 
     lock cmpxchg byte ptr [ebx], cl  ;compare AL to CL. If equal ZF is set and CL is loaded into address pointed to by ebx 
     jnz spin_loop      ;jump to spin_loop if ZF 
    } 
} 
inline void spin_lock_16(short* lck) 
{ 
    __asm 
    { 
     mov ebx, lck 
     xor cx, cx 
     inc cx 
     pause 
     spin_loop: 
     xor ax, ax 
     lock cmpxchg word ptr [ebx], cx 
     jnz spin_loop 
    } 
} 
inline void spin_lock_32(int* lck) 
{ 
    __asm 
    { 
     mov ebx, lck 
     xor ecx, ecx 
     inc ecx 
     pause 
     spin_loop: 
     xor eax, eax 
     lock cmpxchg dword ptr [ebx], ecx 
     jnz spin_loop 
    } 
} 
inline spin_unlock(<anyType>* lck) 
{ 
    __asm 
    { 
     mov ebx, lck 
     mov <byte/word/dword> ptr [ebx], 0 
    } 
} 

다음 의사 코드를 사용하여 테스트 된 잠금합니다 (LCM-포인터가 항상 4 주소 분할 가능한 가리 점에 유의하시기 바랍니다) :

<int/short/char>* lck; 
threadFunc() 
{ 
    loop 10,000,000 times 
    { 
     spin_lock_8/16/32 (lck); 
     spin_unlock(lck); 
    } 
} 
main() 
{ 
    lck = (char/short/int*)_aligned_malloc(4, 4);//Ensures memory alignment 
    start 1 thread running threadFunc and measure time; 
    start 2 threads running threadFunc and measure time; 
    start 4 threads running threadFunc and measure time; 
    _aligned_free(lck); 
} 

4 스레드 (아이비 브리지)를 실행할 수있는 2 개의 물리적 코어가있는 프로세서에서 다음 결과를 msec 단위로 측정했습니다.

  1 thread 2 threads  4 threads 
8-bit  200   700   3200 
16-bit  200   500   1400 
32-bit  200   900   3400 

데이터가 모든 기능을 실행하는 동일한 시간이 걸릴 것을 시사한다. 그러나 여러 스레드가 확인해야 할 때 012 비트를 사용하여 lck == 0은 상당히 빠를 수 있습니다. 왜 그런가요? 나는 그것이 lck의 정렬과 관련이 있다고 가정하지 않습니까? 사전에

감사합니다.

Answer 1

자물쇠는 단어 (2 바이트)에서 작동합니다. 그것은 처음 486에서 처음 도입되었을 때 쓰여졌습니다.

다른 크기의 자물쇠를 가지고 있으면 실제로는 2 자물쇠를 생성합니다 (더블 워드의 경우 단어 A와 B를 잠급니다). 바이트 2 잠금과 다소 유사한 두 번째 바이트의 잠금을 막아야합니다. ...

결과가 CPU 최적화와 일치합니다.

Answer 2

1234 개의 스레드와 16 개의 CPU가 있다고 상상해보십시오. 하나의 스레드가 스핀 록을 획득하면 OS는 작업 스위치를 수행합니다. 이제 각각 16 개의 CPU가 있고 각 스레드는 나머지 1233 개의 스레드 중 하나를 실행합니다. OS가 스핀 록을 해제 할 수있는 유일한 스레드로 CPU 시간을 되돌려주기 위해 오랜 시간 동안 놀랄만 한 방법으로 회전하고 있습니다. 이것은 전체 운영체제가 기본적으로 (몇 초 동안 모든 CPU가 평평하게) 잠길 수 있음을 의미합니다. 이것은 심각하게 지연됩니다; 그래서 어떻게 고치 죠?

사용자 공간에서 스핀 록을 사용하지 않아서 문제를 해결할 수 있습니다. 스핀 록은 작업 스위치를 비활성화 할 수있는 경우에만 사용해야합니다. 커널 만 작업 스위치를 비활성화 할 수 있어야합니다.

더 구체적으로 뮤텍스를 사용해야합니다. 이제 뮤텍스는 포기하고 스레드가 잠금을 기다리게하기 전에 처음에 회전 할 수 있습니다 (일반적인/낮은 경합의 경우) 이것은 도움이되지만 여전히 뮤텍스이며 스핀 록이 아닙니다.

다음으로; 정상적인 소프트웨어의 경우, 성능면에서 중요한 것은 잠금 경합을 피한 다음 비경쟁 사례가 빠르다는 것입니다 (그리고 좋은 뮤텍스는 경쟁이 없다면 작업 전환을 일으키지 않습니다). 경합/부적절한 경우를 측정하고 있습니다.

마지막으로; 자물쇠가 나쁘다. lock 접두어를 과도하게 사용하지 않으려면 lock 접두사없이 획득 할 수 있는지, 그리고 lock 접두사 만 사용해야 하는지를 테스트해야합니다. Intel (그리고 아마도 다른 많은 사람들)은이 전략을 "test; then (test and set)"이라고 부릅니다.또한 pause (또는 10 년 된 지침을 지원하지 않는 매우 나쁜 어셈블러에 대해서는 "rep nop")의 목적을 이해하지 못했습니다.

acquire: 
    lock bts dword [myLock],0 ;Optimistically attempt to acquire 
    jnc .acquired    ;It was acquired! 
.retry: 
    pause 
    cmp dword [myLock],0  ;Should we attempt to acquire again? 
    jne .retry     ; no, don't use `lock` 
    lock bts dword [myLock],0 ;Attempt to acquire 
    jc .retry     ;It wasn't acquired, so go back to waiting 
.acquired: 
    ret 

release: 
    mov dword [myLock],0  ;No lock prefix needed here as "myLock" is aligned 
    ret 

는 또한 적절 잠금 경합의 가능성을 최소화하는 데 실패했다면, 당신은 "공정성"에 대해 신경 쓸 필요하고해야하지 않음을 노트 :

반 괜찮은 스핀 록 같은 것을 보일 수 있습니다 스핀 록을 사용하고 있어야합니다. "불공정 한"스핀 락 문제는 운이 좋을 때 항상 잠금을받을 수 있으며, 운이 좋지 않은 작업은 항상 가지고 있기 때문에 일부 작업은 불행하고 결코 잠금을 얻을 수 없다는 것입니다. 이것은 항상 많이 얽힌 자물쇠에 대한 문제 였지만, 현대의 NUMA 시스템에서는 훨씬 더 많은 문제가 될 수 있습니다. 이 경우 적어도 티켓 잠금 장치를 사용해야합니다.

티켓 잠금의 기본 개념은 작업이 도착한 순서대로 잠금을 획득하고 (일부 "매우 나쁜"무작위 순서가 아님) 확보하도록하는 것입니다. 완성도를 들어, 티켓 잠금은 다음과 같습니다

acquire: 
    mov eax,1 
    lock xadd [myLock],eax   ;myTicket = currentTicket, currentTicket++ 

    cmp [myLock+4],eax    ;Is it my turn? 
    je .acquired      ; yes 
.retry: 
    pause 
    cmp [myLock+4],eax    ;Is it my turn? 
    jne .retry      ; no, wait 
.acquired: 
    ret 

release: 
    lock inc dword [myLock+4] 
    ret 

TL을, 닥터; 먼저 작업 (스핀 록)에 잘못된 도구를 사용해서는 안됩니다. 하지만 잘못된 도구를 사용하려고하면 잘못된 도구를 올바르게 구현해야합니다. :-)