cmpxchg dla WORD szybciej niż dla BYTE

Question

Wczoraj opublikowałem this question o tym, jak napisać szybki spinlock. Dzięki Cory Nelson wydaje mi się, że znalazłem metodę, która przewyższa inne metody omówione w moim pytaniu. Korzystam z instrukcji CMPXCHG, aby sprawdzić, czy blokada wynosi 0, a co za tym idzie, jest wolna. CMPXCHG działa na "OTE", WORD i DWORD. Zakładam, że instrukcja działałaby szybciej na BYTE. Ale napisałem blokadę wykonawczego każdego z typów danych:

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

Zamek został następnie przetestowany za pomocą następującego pseudo-kodu (należy pamiętać, że LCM-wskaźnik zawsze będzie wskazywać na podzielna adresowej przez 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); 
} 

Otrzymałem następujące wyniki zmierzone w msecs na procesorze z 2 rdzeniami fizycznymi zdolnymi do uruchomienia 4 wątków (Ivy Bridge).

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

Dane sugerują, że wszystkie funkcje ma taką samą ilość czasu na wykonanie. Ale gdy wiele wątków musi sprawdzić, czy lck == 0 przy użyciu 16-bitów może być znacznie szybsze. Dlaczego? Nie sądzę, że ma to coś wspólnego z wyrównaniem lck?

Z góry dziękuję.

Answer 1

Z tego co pamiętam, zamek działa na słowo (2 bajty). Napisano to w ten sposób, gdy po raz pierwszy wprowadzono w 486.

Jeśli nosisz zamek w innym rozmiarze, to faktycznie generuje ekwiwalent 2 zamków (słowo blokujące A i słowo B dla podwójnego słowa). Dla bajtu prawdopodobnie musi zapobiec blokowaniu drugiego bajtu, który jest nieco podobny do 2 blokad ...

Twoje wyniki są zgodne z optymalizacją procesora.

Answer 2

Wyobraź sobie, że jest 1234 wątków i 16 procesorów. Jeden wątek nabywa blokadę, następnie system operacyjny przełącza zadania. Teraz masz 16 procesorów, z których każdy uruchamia jeden z pozostałych 1233 wątków, wszystkie obracają się w zaskakująco bezsensowny sposób, jednak przez długi czas system operacyjny daje czas procesora z powrotem do jedynego wątku, który może zwolnić spinlock. Oznacza to, że cały system operacyjny może zasadniczo zablokować się (wszystkie procesory wygaszają się) na kilka sekund. Jest to poważnie opóźnione; więc jak to naprawić?

Naprawiasz to, nie używając spinlocków w przestrzeni użytkownika. Spinlocks powinny być używane tylko wtedy, gdy/kiedy przełączniki zadań mogą być wyłączone; i tylko jądro powinno być w stanie wyłączyć przełączniki zadań.

Dokładniej, musisz użyć muteksa. Teraz muteks może początkowo się obrócić przed poddaniem się i sprawić, że wątek będzie czekał na blokadę i (dla typowych/małych przypadków rywalizacji), to pomoże, ale nadal będzie muteksem i nie będzie spinlockiem.

Następny; w przypadku rozsądnego oprogramowania ważne jest, aby (dla wydajności) uniknąć rywalizacji o blokadę, a następnie upewnić się, że niezamierzony przypadek jest szybki (a dobry muteks nie spowoduje przełączenia zadania, jeśli nie będzie żadnego sporu). Mierzysz toczący się/nieistotny przypadek.

Wreszcie; twój zamek jest zły. Aby uniknąć nadmiernego używania prefiksu lock, powinieneś przetestować, czy możesz uzyskać dostęp bez prefiksu lock i tylko wtedy, gdy możesz być w stanie je uzyskać, jeśli używasz prefiksu lock. Intel (i prawdopodobnie wiele innych osób) nazywa tę strategię "testem, a następnie (test i zestaw)".Ponadto nie udało ci się zrozumieć celu pause (lub "rep nop" dla asemblerów, które są tak złe, że nie obsługują 10-letnich instrukcji).

Pół przyzwoity Spinlock może wyglądać:

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 

Należy również pamiętać, że jeśli nie udało się odpowiednio zminimalizować ryzyko blokady niezgody, to trzeba dbać o „sprawiedliwości” i nie powinien używać spinlock. Problem z "nieuczciwymi" spinblokami polega na tym, że niektóre zadania mogą być szczęśliwe i zawsze mieć blokadę, a niektóre zadania mogą być pechowe i nigdy nie dostać blokady, ponieważ szczęśliwe zadania zawsze ją mają. To zawsze stanowiło problem dla silnie strzeżonych zamków, ale dla nowoczesnych systemów NUMA stało się znacznie bardziej prawdopodobnym problemem. W takim przypadku minimum powinno się używać blokady biletu.

Podstawową ideą zamka biletowego jest zapewnienie, aby zadania zdobywały zamek w kolejności, w jakiej przybyły (a nie jakiejś "potencjalnie wyjątkowo złej" kolejności losowej). Dla kompletności, blokada bilet może wyglądać następująco:

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; dr; Nie powinieneś używać niewłaściwego narzędzia do pracy (spinlocks); ale jeśli nalegasz na użycie niewłaściwego narzędzia, to przynajmniej poprawnie zaimplementuj niewłaściwe narzędzie ... :-)