Optimalisatie van een Spin-Lock

Elke pico uit de eenvoudigste lock persen.

Een spin-lock is een lock die nooit in slaap gaat. In plaats van de controle over te dragen aan de scheduler, blijft de thread op de CPU en "spint". Geen syscalls, geen context-switches. In dit artikel bouwen we stap voor stap een versie die 5,7x sneller is en 5,4x minder energie verbruikt.

Benchmark

Threads verhogen een gedeelde teller onder de lock. De benchmark is uitgevoerd op een systeem dat is geoptimaliseerd voor benchmarking, gebouwd met Clang en met alle optimalisaties ingeschakeld.

template <typename Lockable>
auto BM_SpinLock(benchmark::State& state) -> void {
    alignas(std::hardware_destructive_interference_size) static auto lockable = Lockable{};
    alignas(std::hardware_destructive_interference_size) static auto counter = std::uint64_t{};
    pinThread(state.thread_index());
    for (auto _ : state) {
        lockable.lock();
        ++counter;
        lockable.unlock();
    }
    benchmark::DoNotOptimize(counter);
}

De lock en de teller krijgen elk een eigen cache-line. De threads zijn "pinned" (vastgezet op specifieke cores).

Een naïeve spin-lock (V1)

De eerste versie maakt gebruik van een atomic bool en een exchange-loop. De functie exchange schrijft atomair true en geeft de vorige waarde terug. false betekent dat de lock vrij was en nu van ons is; true betekent dat iemand anders de lock vasthoudt, waarna we het opnieuw proberen.

class SpinLockV1 {
    std::atomic_bool locked_{false};
public:
    auto lock() noexcept -> void { while (locked_.exchange(true)); }
    auto unlock() noexcept -> void { locked_.store(false); }
};

Bij één thread (uncontended) duurt dit 3,14 ns. Bij twee threads stijgt dit naar 61,5 ns (twintig keer zo lang), en bij vier threads naar 246 ns.

$ ./benchmark --benchmark_filter='V1>'
BM_SpinLock<SpinLockV1>/real_time/threads:1      3.14 ns
BM_SpinLock<SpinLockV1>/real_time/threads:2      61.5 ns
BM_SpinLock<SpinLockV1>/real_time/threads:4       246 ns

Een core moet de cache-line exclusief bezitten om erin te kunnen schrijven, waardoor wachtende threads de line voortdurend van elkaar afnemen. De L1-d misses stijgen van 1,27% bij één thread naar 61,73% bij vier threads, en één op de acht branches wordt foutief voorspeld. Omdat het succes van de exchange wordt bepaald door de andere cores, heeft de branch-predictor niets om van te leren.

$ perf stat -d ./benchmark --benchmark_filter='V1>.*threads:1'
1,638,619,370      instructions           # 0.51  insn per cycle
244,253      branch-misses          # 0.11% of all branches
75,519      L1-dcache-load-misses  # 1.27% of all L1-dcache accesses

$ perf stat -d ./benchmark --benchmark_filter='V1>.*threads:4'
1,231,495,723      instructions           # 0.02  insn per cycle
33,824,516      branch-misses          # 12.52% of all branches
208,756,315      L1-dcache-load-misses  # 61.73% of all L1-dcache accesses

Energieverbruik

Spinnen kost energie. High-frequency trading bedrijven hechten hier veel waarde aan; colocatie-services voor exchange-servers rekenen kosten voor stroom, en de NYSE hanteert een limiet van 32 kW. Bij vier threads verbruikt deze versie 64,92 J.

(Opmerking: het uitlezen van RAPL-counters vereist systeem-brede modus (-a) en root-rechten, dus dit cijfer beslaat het gehele pakket, inclusief idle cores).

$ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V1>.*threads:4'
64.92 Joules power/energy-pkg/

Geheugenvolgorde (Memory Ordering, V2)

De standaardinstelling is seq_cst (sequentially consistent), wat sterker is dan een lock nodig heeft. Een lock hoeft alleen acquire te zijn bij binnenkomst en release bij vertrek.

class SpinLockV2 {
    std::atomic_bool locked_{false};
public:
    auto lock() noexcept -> void {
        while (locked_.exchange(true, std::memory_order_acquire));
    }
    auto unlock() noexcept -> void {
        locked_.store(false, std::memory_order_release);
    }
};

Op x86 blijft de lock-functie ongewijzigd:

SpinLockV2::lock():
mov     al, 1
xchg    byte ptr [rdi], al  // Locked exchange, both orderings
test    al, 1
jne     .LBB0_1
ret

Het verschil zit in unlock. De standaardvolgorde voegt een tweede "locked read-modify-write" toe bovenop die in de lock-functie.

SpinLockV1::unlock():

xor     eax, eax
xchg    byte ptr [rdi], al  // Locked read-modify-write
ret

Met memoryorderrelease is de unlock een eenvoudige store:

SpinLockV2::unlock():

mov     byte ptr [rdi], 0   // Plain store
ret

Door één atomaire operatie te vervangen door twee, daalt de tijd van 3,14 ns naar 1,57 ns (uncontended) en van 246 ns naar 131 ns bij vier threads.

$ ./benchmark --benchmark_filter='V2>'
BM_SpinLock<SpinLockV2>/real_time/threads:1      1.57 ns
BM_SpinLock<SpinLockV2>/real_time/threads:2      32.5 ns
BM_SpinLock<SpinLockV2>/real_time/threads:4       131 ns

Ook de miss-rates dalen: L1-d van 61,73% naar 21,16%, en branches van 12,52% naar 7,43%. Het energieverbruik daalt naar 34,45 J.

$ perf stat -d ./benchmark --benchmark_filter='V2>.*threads:4'
773,887,322      instructions           # 0.03  insn per cycle
12,348,239      branch-misses          # 7.43% of all branches
99,804,390      L1-dcache-load-misses  # 21.16% of all L1-dcache accesses

De exchange schrijft echter naar de cache-line, zelfs als de operatie mislukt. Wachtende threads moeten dus stoppen met schrijven.

Test and Test-and-Set (V3)

In deze versie voeren we één keer een exchange uit en wachten we daarna op een read-only load. De instructie mmpause markeert de loop als een spin-wait, waardoor de core in een idle-status gaat. De load kan relaxed zijn; de kritieke sectie wordt namelijk geordend door de exchange die slaagt, niet door de reads die mislukken.

class SpinLockV3 {
    std::atomic_bool locked_{false};
public:
    auto lock() noexcept -> void {
        while (locked_.exchange(true, std::memory_order_acquire)) {
            while (locked_.load(std::memory_order_relaxed)) {  // Read-only spin
                _mm_pause();                                     // Backoff
            }
        }
    }
    auto unlock() noexcept -> void {
        locked_.store(false, std::memory_order_release);
    }
};

Bij twee threads daalt de tijd met een derde (van 32,5 ns naar 21,3 ns). Bij vier threads is er een winst van 8% (van 131 ns naar 120 ns).

$ ./benchmark --benchmark_filter='V3>'
BM_SpinLock<SpinLockV3>/real_time/threads:1      1.58 ns
BM_SpinLock<SpinLockV3>/real_time/threads:2      21.3 ns
BM_SpinLock<SpinLockV3>/real_time/threads:4       120 ns

L1-d misses dalen van 21,16% naar 17,31% en branches van 7,43% naar 3,72%, omdat een read-only spin voorspelbaar is. Het energieverbruik daalt met 10%, van 34,45 J naar 30,97 J.

$ perf stat -d ./benchmark --benchmark_filter='V3>.*threads:4'
1,290,214,448      instructions           # 0.05  insn per cycle
12,089,906      branch-misses          # 3.72% of all branches
83,836,255      L1-dcache-load-misses  # 17.31% of all L1-dcache accesses

$ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V3>.*threads:4'
30.97 Joules power/energy-pkg/

Een probleem blijft dat elke wachtende thread precies even lang pauzeert, waardoor ze allemaal tegelijkertijd weer "wakker" worden.

Exponentiële Back-off (V4)

Intel documenteert een oplossing hiervoor: wacht elke ronde langer, waarbij de wachttijd verdubbelt tot aan een maximum. Dit is beschreven in Example 2-10, Contended Locks with Increasing Back-off, in de Intel Optimization Reference Manual (PDF, 248966-050US).

class SpinLockV4 {
    std::atomic_bool locked_{false};
public:
    auto lock() noexcept -> void {
        auto backoff = 1;
        while (locked_.exchange(true, std::memory_order_acquire)) {
            do {
                for (auto i = 0; i < backoff; ++i) _mm_pause();   // Backoff
                backoff = backoff < 64 ? backoff << 1 : 64;       // Exp. growth
            } while (locked_.load(std::memory_order_relaxed));  // Read-only spin
        }
    }
    auto unlock() noexcept -> void {
        locked_.store(false, std::memory_order_release);
    }
};

Door verschillende back-off tijden waken de threads niet meer gelijktijdig. Bij vier threads daalt de tijd van 120 ns naar 43,0 ns.

$ ./benchmark --benchmark_filter='V4>'
BM_SpinLock<SpinLockV4>/real_time/threads:1      1.58 ns
BM_SpinLock<SpinLockV4>/real_time/threads:2      18.3 ns
BM_SpinLock<SpinLockV4>/real_time/threads:4      43.0 ns

L1-d misses dalen van 17,31% naar 12,88%. Het energieverbruik daalt naar 11,92 J, wat 5,4x minder is dan de naïeve versie.

$ perf stat -d ./benchmark --benchmark_filter='V4>.*threads:4'
600,071,010      instructions           # 0.07  insn per cycle
8,296,063      branch-misses          # 6.17% of all branches
33,717,087      L1-dcache-load-misses  # 12.88% of all L1-dcache accesses

$ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V4>.*threads:4'
11.92 Joules power/energy-pkg/

Samenvatting

Versie1 thread2 threads4 threadsNotities
V13,14 ns61,5 ns246 ns / 64,92 JNaïef
V21,57 ns32,5 ns131 ns / 34,45 JGeheugenvolgorde
V31,58 ns21,3 ns120 ns / 30,97 JTest and test-and-set
V41,58 ns18,3 ns43,0 ns / 11,92 JExponentiële back-off

In de meeste code is std::mutex nog steeds de juiste standaardkeuze. Overweeg een spin-lock alleen wanneer threads zijn vastgezet op toegewezen cores en doe dit pas na nauwkeurige metingen. Bij scenario's met één schrijver en veel lezers is een seqlock een beter alternatief.