Spin SpinLock for a fixed duration rather than a fixed iteration count. A fixed spin-loop iteration count spends about 2× more wall-clock time on slower CPUs than on faster ones. On first contention, time the spin loop and convert a 500 ns target into an iteration count using CycleClock::Frequency(), spinning at least 500 iterations. PiperOrigin-RevId: 1015592590
diff --git a/absl/base/internal/spinlock.cc b/absl/base/internal/spinlock.cc index 57966d2..34297db 100644 --- a/absl/base/internal/spinlock.cc +++ b/absl/base/internal/spinlock.cc
@@ -14,6 +14,7 @@ #include "absl/base/internal/spinlock.h" +#include <algorithm> #include <atomic> #include <cstdint> @@ -22,6 +23,7 @@ #include "absl/base/config.h" #include "absl/base/internal/atomic_hook.h" #include "absl/base/internal/cycleclock.h" +#include "absl/base/internal/raw_logging.h" #include "absl/base/internal/scheduling_mode.h" #include "absl/base/internal/spinlock_wait.h" #include "absl/base/internal/sysinfo.h" /* For NumCPUs() */ @@ -110,6 +112,58 @@ ABSL_TSAN_MUTEX_POST_DIVERT(&lock, 0); } +// Calibration times `kProbeReadings` runs of `kProbeIterations` iterations. +static constexpr int kProbeIterations = 4096; +static constexpr int kProbeReadings = 4; + +static constexpr double kNanosecondsPerSecond = 1e9; + +// Spins up to `iterations` times until `kSpinLockHeld` clears, returning the +// last value read. Noinline so ProbeSpinLockLoop() times the same loop. +ABSL_ATTRIBUTE_NOINLINE uint32_t SpinLock::SpinLockLoop( + const std::atomic<uint32_t>* absl_nonnull lockword, int iterations) { + uint32_t lock_value; + do { + lock_value = lockword->load(std::memory_order_relaxed); + } while ((lock_value & kSpinLockHeld) != 0 && --iterations > 0); + return lock_value; +} + +// Runs SpinLockLoop() for `iterations` on a lock word that stays held. The +// check gives this a side effect and noinline keeps it opaque, so readings +// can't be elided, merged, or moved outside the timed region. +ABSL_ATTRIBUTE_NOINLINE void SpinLock::ProbeSpinLockLoop(int iterations) { + std::atomic<uint32_t> lockword{kSpinLockHeld}; + ABSL_RAW_CHECK(SpinLockLoop(&lockword, iterations) == kSpinLockHeld, + "SpinLockLoop cleared held lockword"); +} + +int SpinLock::CalibrateSpinCount() { + // Load `kProbeIterations` through `volatile` so LTO can't specialize + // SpinLockLoop() for a constant iteration count when timing it. + volatile int volatile_iterations = kProbeIterations; + const int probe_iterations = volatile_iterations; + // Keep the fastest of a few readings to filter out preemption. + int64_t min_cycles = 0; + for (int reading = 0; reading < kProbeReadings; ++reading) { + const int64_t start = CycleClock::Now(); + ProbeSpinLockLoop(probe_iterations); + const int64_t elapsed = CycleClock::Now() - start; + if (elapsed > 0 && (min_cycles == 0 || elapsed < min_cycles)) { + min_cycles = elapsed; + } + } + if (min_cycles <= 0) { + // CycleClock failed to advance across all readings. + return kMinSpinIterations; + } + const double iterations = kSpinNanoseconds / kNanosecondsPerSecond * + CycleClock::Frequency() * kProbeIterations / + static_cast<double>(min_cycles); + return static_cast<int>( + std::clamp<double>(iterations, kMinSpinIterations, kMaxSpinIterations)); +} + // Monitor the lock to see if its value changes within some time period // (adaptive_spin_count_ loop iterations). The last value read from the lock // is returned from the method. @@ -119,7 +173,7 @@ // adaptive_spin_count here. if (adaptive_spin_count_.load(std::memory_order_relaxed) == 0) { int current_spin_count = 0; - int new_spin_count = NumCPUs() > 1 ? 1000 : 1; + int new_spin_count = NumCPUs() > 1 ? CalibrateSpinCount() : 1; // If this fails, the value will remain unchanged. We may not spin for the // intended duration, but that is still safe. We will try again on the next // call to SpinLoop. @@ -128,11 +182,7 @@ std::memory_order_relaxed); } int c = adaptive_spin_count_.load(std::memory_order_relaxed); - uint32_t lock_value; - do { - lock_value = lockword_.load(std::memory_order_relaxed); - } while ((lock_value & kSpinLockHeld) != 0 && --c > 0); - return lock_value; + return SpinLockLoop(&lockword_, c); } void SpinLock::SlowLock() {
diff --git a/absl/base/internal/spinlock.h b/absl/base/internal/spinlock.h index aff0c9f..7269d7e 100644 --- a/absl/base/internal/spinlock.h +++ b/absl/base/internal/spinlock.h
@@ -241,6 +241,20 @@ ABSL_ATTRIBUTE_COLD void SlowLock(); ABSL_ATTRIBUTE_COLD void SlowUnlock(uint32_t lock_value); uint32_t SpinLoop(); + static uint32_t SpinLockLoop( + const std::atomic<uint32_t>* absl_nonnull lockword, int iterations); + static void ProbeSpinLockLoop(int iterations); + + // Target duration of SpinLoop() on multi-CPU hosts. + static constexpr int64_t kSpinNanoseconds = 500; + // Minimum spin count on multi-CPU hosts, also used if calibration fails. + static constexpr int kMinSpinIterations = 500; + // Maximum spin count, which bounds the spin if CycleClock::Frequency() is + // wrong. + static constexpr int kMaxSpinIterations = 12000; + // Returns the number of SpinLockLoop() iterations that take about + // kSpinNanoseconds, within [kMinSpinIterations, kMaxSpinIterations]. + static int CalibrateSpinCount(); inline bool TryLockImpl() { uint32_t lock_value = lockword_.load(std::memory_order_relaxed);
diff --git a/absl/base/spinlock_test_common.cc b/absl/base/spinlock_test_common.cc index a29a7f5..4f1bc1b 100644 --- a/absl/base/spinlock_test_common.cc +++ b/absl/base/spinlock_test_common.cc
@@ -16,6 +16,8 @@ // spinlock. If the spinlock is working properly, all elements of the // array should be equal at the end of the test. +#include <algorithm> +#include <chrono> // NOLINT(build/c++11) #include <cstddef> #include <cstdint> #include <limits> @@ -54,6 +56,12 @@ } static bool IsCooperative(const SpinLock& l) { return l.IsCooperative(); } + + static constexpr int64_t kSpinNanoseconds = SpinLock::kSpinNanoseconds; + static uint32_t SpinLoop(SpinLock& l) { return l.SpinLoop(); } + static void SetAdaptiveSpinCount(int count) { + SpinLock::SetAdaptiveSpinCount(count); + } }; namespace {