cmpxchg für WORD schneller als für BYTE

Question

Gestern habe ich this question auf, wie man einen schnellen Spinlock geschrieben. Dank Cory Nelson habe ich anscheinend eine Methode gefunden, die die anderen in meiner Frage besprochenen Methoden übertrifft. Ich benutze die CMPXCHG Anweisung, um zu überprüfen, ob die Sperre 0 und damit frei ist. CMPXCHG arbeitet auf "BYTE", WORD und DWORD. Ich würde annehmen, dass der Befehl schneller auf BYTE funktionieren würde. Aber ich schrieb eine Sperre jeden des Datentypen Implementierung:

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

Das Schloss wurde dann den folgenden Pseudo-Code getestet mit (bitte beachten Sie, dass die LCM-Zeiger immer auf eine Adresse teilbaren von 4 Punkt):

Ich habe die folgenden Ergebnisse in msecs auf einem Prozessor mit 2 physischen Kernen in der Lage, 4 Threads (Ivy Bridge) laufen gemessen.

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

Die Daten legen nahe, dass alle Funktionen die gleiche Zeit benötigen, um ausgeführt zu werden. Aber wenn mehrere Threads prüfen müssen, ob lck == 0 mit einem 16-Bit deutlich schneller sein kann. Warum das? Ich nehme an, es hat etwas mit der Ausrichtung der lck zu tun?

Vielen Dank im Voraus.

Answer 1

Von was ich erinnere, funktioniert die Sperre auf ein Wort (2 Bytes). Es wurde so geschrieben, als es zuerst in der 486.

eingeführt wurde Wenn Sie ein Schloss auf einer anderen Größe tragen, erzeugt es tatsächlich das Äquivalent von 2 Schlössern (Schloss Wort A und Wort B für ein Doppelwort.) Für ein Byte es muss wahrscheinlich das Sperren des zweiten Bytes verhindern, das ist ähnlich wie 2 Sperren ...

So sind Ihre Ergebnisse im Einklang mit den CPU-Optimierungen.

Answer 2

Stellen Sie sich vor, es gibt 1234 Threads und 16 CPUs. Ein Thread erwirbt den Spinlock, dann führt das OS einen Taskwechsel durch. Jetzt haben Sie 16 CPUs, von denen jede einen der verbleibenden 1233-Threads ausführt, die alle bemerkenswert sinnlos rotieren, egal wie lange es dem Betriebssystem dauert, dem einzigen Thread, der den Spinlock freigeben kann, CPU-Zeit zurückzugeben. Dies bedeutet, dass das gesamte Betriebssystem im Prinzip für einige Sekunden gesperrt werden kann (wobei alle CPUs leer sind). Dies ist ernsthaft zurückgeblieben; Wie reparierst du es?

Sie beheben es, indem Sie keine Spinlocks im User-Space verwenden. Spinlocks sollten immer nur dann verwendet werden, wenn Task Switches deaktiviert werden können. und nur der Kernel sollte Task-Switches deaktivieren können.

Genauer gesagt, müssen Sie einen Mutex verwenden. Nun kann sich der Mutex anfänglich drehen, bevor er aufgibt und der Thread auf die Sperre wartet, und (für typische/niedrige Konkurrenzfälle) hilft das zwar, aber es wäre immer noch ein Mutex und kein Spinlock.

Nächste; Für eine vernünftige Software ist es wichtig, Sperrkonflikte zu vermeiden und dann sicherzustellen, dass der unkonsolidierte Fall schnell ist (und ein guter Mutex wird keinen Taskwechsel verursachen, wenn es keine Konflikte gibt). Sie messen den strittigen/irrelevanten Fall.

Schließlich; Dein Schloss ist schlecht. Um eine übermäßige Nutzung des Präfix lock zu vermeiden, sollten Sie testen, ob Sie ohne Präfix lock erwerben können, und nur, wenn Sie in der Lage sein sollten, sollten Sie das Präfix lock verwenden. Intel (und wahrscheinlich viele andere Leute) nennen diese Strategie "test; then (test and set)".Außerdem haben Sie den Zweck von pause (oder "rep nop" für Assembler, die so schlecht sind, dass sie keine 10 Jahre alten Anweisungen unterstützen) nicht verstanden.

Ein halbwegs ordentliche spinlock könnte etwa so aussehen:

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 

Beachten Sie auch, dass, wenn Sie ausreichend versagt haben die Chance auf Sperrenkonflikte zu minimieren, dann über „Fairness“ kümmern Sie brauchen und sollten nicht Verwenden Sie einen Spinlock. Das Problem mit "unfairen" Spinlocks ist, dass einige Aufgaben Glück haben und immer das Schloss bekommen, und einige Aufgaben können unglücklich sein und niemals das Schloss bekommen, weil die glücklichen Aufgaben es immer bekommen haben. Dies war immer ein Problem für stark umkämpfte Sperren, aber für moderne NUMA-Systeme ist es ein viel wahrscheinlicheres Problem geworden. In diesem Fall sollten Sie mindestens eine Ticketsperre verwenden.

Die Grundidee einer Ticketsperre besteht darin, sicherzustellen, dass Aufgaben das Schloss in der Reihenfolge ihres Eintreffens erhalten (und nicht irgendeine "möglicherweise extrem schlechte" zufällige Reihenfolge). Der Vollständigkeit halber kann ein Ticket-Sperre wie folgt aussehen:

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; Sie sollten nicht mit dem falschen Werkzeug für den Job (Spinlocks) beginnen; aber wenn du darauf bestehst, das falsche Werkzeug zu benutzen, dann lass wenigstens das falsche Werkzeug richtig implementiert werden ... :-)