Size SpinLock and Mutex spin limits to machine capacity. Fixed spin-loop iteration counts spend 2–4× more wall-clock time on slower CPUs than on faster ones. In fleet experiments, longer fixed-iteration spins improved performance on smaller and mid-size machines, but regressed performance on the highest-capacity machines, where packed work scales with machine compute capacity. Calibrate the spin duration once on first contention inversely proportional to machine compute capacity, estimating per-CPU speed via an integer-latency probe. PiperOrigin-RevId: 1009321328
diff --git a/absl/base/internal/spinlock.cc b/absl/base/internal/spinlock.cc index 57966d2..483cb7c 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,88 @@ ABSL_TSAN_MUTEX_POST_DIVERT(&lock, 0); } +// Target spin duration, where N is NumCPUs(): +// +// spin_time = latency_probe_time * kSpinProbeMultiplier / max(N, kMinCpus) +// +// Since `latency_probe_time` is inversely proportional to single-core speed, +// this scales spin time inversely with total machine compute capacity, with +// smaller hosts spinning as long as a `kMinCpus`-CPU host. +static constexpr int kMinCpus = 64; +static constexpr int64_t kSpinProbeMultiplier = 56; + +// Measures single-core integer latency via a serial chain of `steps` (> 0) +// xorshift-multiply steps. Each step is bijective (odd SplitMix64 multiplier), +// so `state` never reaches 0 and checking it keeps the loop from being elided. +// Noinline so readings can't be merged or moved outside the timed region. +ABSL_ATTRIBUTE_NOINLINE void RunLatencyProbe(int steps) { + uint64_t state = static_cast<uint64_t>(steps); + for (int i = 0; i < steps; ++i) { + state = (state ^ (state >> 29)) * 0xbf58476d1ce4e5b9ULL; + } + ABSL_RAW_CHECK(state != 0, "RunLatencyProbe state reached 0"); +} + +static int64_t MeasureMinProbeCycles(void (*probe_fn)(int steps)) { + // Load `kProbeSteps` through `volatile` so LTO/inlining cannot constant-fold + // or unroll `probe_fn` differently from the runtime spin loop. + volatile int volatile_steps = kProbeSteps; + const int steps = volatile_steps; + int64_t min_cycles = 0; + for (int reading = 0; reading < kProbeReadings; ++reading) { + const int64_t start = CycleClock::Now(); + probe_fn(steps); + const int64_t elapsed = CycleClock::Now() - start; + if (elapsed > 0 && (min_cycles == 0 || elapsed < min_cycles)) { + min_cycles = elapsed; + } + } + return min_cycles; +} + +int ComputeSpinIterations(int num_cpus, int64_t latency_probe_cycles, + int64_t spin_probe_cycles) { + const int64_t target_cycles = latency_probe_cycles * kSpinProbeMultiplier / + std::max(num_cpus, kMinCpus); + const int64_t iterations = target_cycles * kProbeSteps / spin_probe_cycles; + return static_cast<int>( + std::clamp<int64_t>(iterations, kMinSpinIterations, kMaxSpinIterations)); +} + +int CalibrateSpinIterations(void (*absl_nonnull spin_probe_fn)(int steps)) { + const int num_cpus = NumCPUs(); + if (num_cpus <= 1) { + // Uniprocessors don't spin: 1 means a single attempt and is non-zero. + return 1; + } + const int64_t latency_probe_cycles = MeasureMinProbeCycles(&RunLatencyProbe); + const int64_t spin_probe_cycles = MeasureMinProbeCycles(spin_probe_fn); + if (latency_probe_cycles <= 0 || spin_probe_cycles <= 0) { + // If CycleClock fails to advance across all probe readings, permanently + // fall back to the minimum spin count. + return kMinSpinIterations; + } + return ComputeSpinIterations(num_cpus, latency_probe_cycles, + spin_probe_cycles); +} + +// 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; +} + +void SpinLock::ProbeSpinLockLoop(int steps) { + std::atomic<uint32_t> lockword{kSpinLockHeld}; + ABSL_RAW_CHECK(SpinLockLoop(&lockword, steps) == kSpinLockHeld, + "SpinLockLoop cleared held lockword"); +} + // 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. @@ -117,22 +201,12 @@ uint32_t SpinLock::SpinLoop() { // We are already in the slow path of SpinLock, initialize the // 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; - // 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. - adaptive_spin_count_.compare_exchange_weak( - current_spin_count, new_spin_count, std::memory_order_relaxed, - 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; + if (c == 0) { + c = CalibrateSpinIterations(&ProbeSpinLockLoop); + adaptive_spin_count_.store(c, std::memory_order_relaxed); + } + return SpinLockLoop(&lockword_, c); } void SpinLock::SlowLock() {
diff --git a/absl/base/internal/spinlock.h b/absl/base/internal/spinlock.h index aff0c9f..d395266 100644 --- a/absl/base/internal/spinlock.h +++ b/absl/base/internal/spinlock.h
@@ -241,6 +241,9 @@ 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 steps); inline bool TryLockImpl() { uint32_t lock_value = lockword_.load(std::memory_order_relaxed); @@ -329,6 +332,27 @@ return lock_value; } +// Bounds on calibrated spin iterations on multi-CPU machines. +inline constexpr int kMinSpinIterations = 1000; +inline constexpr int kMaxSpinIterations = 12000; + +// Steps per calibration probe trial and number of trials taken per probe. +inline constexpr int kProbeSteps = 4096; +inline constexpr int kProbeReadings = 4; + +// Converts `num_cpus` (> 1) and positive `kProbeSteps`-step latency and +// spin-loop probe cycle counts into spin iterations. Exposed for testing. +int ComputeSpinIterations(int num_cpus, int64_t latency_probe_cycles, + int64_t spin_probe_cycles); + +// The latency probe CalibrateSpinIterations() times. Exposed for testing. +void RunLatencyProbe(int steps); + +// Returns this host's spin iterations in [kMinSpinIterations, +// kMaxSpinIterations], timing `spin_probe_fn(steps)` against a latency probe. +// Returns 1 on single-CPU hosts. +int CalibrateSpinIterations(void (*absl_nonnull spin_probe_fn)(int steps)); + } // namespace base_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/base/spinlock_test_common.cc b/absl/base/spinlock_test_common.cc index a29a7f5..8484943 100644 --- a/absl/base/spinlock_test_common.cc +++ b/absl/base/spinlock_test_common.cc
@@ -18,6 +18,7 @@ #include <cstddef> #include <cstdint> +#include <cstdlib> #include <limits> #include <mutex> // NOLINT(build/c++11) #include <random> @@ -296,6 +297,96 @@ std::scoped_lock l(s); } +TEST(SpinLockTest, ComputeSpinIterationsScalesWithCapacityAndLoopSpeed) { + constexpr int kNumCpus = 80; + constexpr int64_t kRefLatencyCycles = 4000; + constexpr int64_t kSlowCoreLatencyCycles = 6000; + constexpr int64_t kFastCoreLatencyCycles = 3000; + constexpr int64_t kOneCyclePerSpinIter = kProbeSteps; + + // In the unclamped regime, doubling NumCPUs() halves the target cycle budget. + const int base_iters = + ComputeSpinIterations(kNumCpus, kRefLatencyCycles, kOneCyclePerSpinIter); + const int double_cpu_iters = ComputeSpinIterations( + 2 * kNumCpus, kRefLatencyCycles, kOneCyclePerSpinIter); + EXPECT_GT(double_cpu_iters, kMinSpinIterations); + EXPECT_LT(base_iters, kMaxSpinIterations); + EXPECT_NEAR(base_iters, 2 * double_cpu_iters, 1); + + // Faster cores (fewer latency-probe cycles) get a smaller spin budget at the + // same CPU count and spin-loop speed. + const int slow_core = ComputeSpinIterations(kNumCpus, kSlowCoreLatencyCycles, + kOneCyclePerSpinIter); + const int fast_core = ComputeSpinIterations(kNumCpus, kFastCoreLatencyCycles, + kOneCyclePerSpinIter); + EXPECT_LT(slow_core, kMaxSpinIterations); + EXPECT_GT(slow_core, base_iters); + EXPECT_GT(base_iters, fast_core); + EXPECT_GT(fast_core, kMinSpinIterations); + + // Faster spin loops (fewer cycles per probe) run proportionally more + // iterations for the same target cycle budget. + const int half_cycle_per_iter = ComputeSpinIterations( + kNumCpus, kRefLatencyCycles, kOneCyclePerSpinIter / 2); + const int quarter_cycle_per_iter = ComputeSpinIterations( + kNumCpus, kRefLatencyCycles, kOneCyclePerSpinIter / 4); + EXPECT_LT(quarter_cycle_per_iter, kMaxSpinIterations); + EXPECT_NEAR(half_cycle_per_iter, 2 * base_iters, 1); + EXPECT_NEAR(quarter_cycle_per_iter, 2 * half_cycle_per_iter, 1); + + // Low-CPU-count machines spin as long as a minimum-size machine would, well + // below kMaxSpinIterations. + const int low_cpu_8 = + ComputeSpinIterations(8, kRefLatencyCycles, kOneCyclePerSpinIter); + const int low_cpu_16 = + ComputeSpinIterations(16, kRefLatencyCycles, kOneCyclePerSpinIter); + EXPECT_GT(low_cpu_8, base_iters); + EXPECT_LT(low_cpu_8, kMaxSpinIterations); + EXPECT_EQ(low_cpu_8, low_cpu_16); +} + +// Checks that CalibrateSpinIterations() measures real probe costs, so that a +// regression (e.g. an elided probe loop) can't silently pin the result to +// kMinSpinIterations or kMaxSpinIterations. +TEST(SpinLockTest, CalibrateSpinIterationsMeasuresProbeCost) { + if (NumCPUs() <= 1) GTEST_SKIP() << "Uniprocessors don't calibrate"; + + // The spin probe runs RunLatencyProbe() for 1/divisor of the steps. Both + // probes then run the same compiled loop, so their cycle ratio is `divisor` + // on any machine or build mode, which makes the expected result exact. + // Static so the captureless probe below can read it. + static int divisor; + int expected; + // Start at 2, since a probe whose cost doesn't scale with `steps` gives a + // ratio of 1. Grow it so the expected count is far above the lower clamp + // (which large machines hit in real calibration) and a result stuck there + // fails clearly. + constexpr int kMinExpected = 3 * kMinSpinIterations; + for (divisor = 2;; ++divisor) { + expected = ComputeSpinIterations(NumCPUs(), int64_t{kProbeSteps} * divisor, + kProbeSteps); + if (expected >= kMinExpected) break; + } + ASSERT_LT(expected, kMaxSpinIterations); // Also unclamped at the top. + + // Keep the closest of a few calibrations to tolerate preemption. + int best = 0; + for (int i = 0; i < 5; ++i) { + const int iterations = CalibrateSpinIterations( + [](int steps) { RunLatencyProbe(steps / divisor); }); + if (std::abs(iterations - expected) < std::abs(best - expected)) { + best = iterations; + } + } + // Bugs move the result far off: to a clamp, or to about expected / divisor. + // Noise is a few percent, but fixed per-timing overhead (clock reads, calls) + // biases the ratio low: negligible with hardware cycle counters, ~10% under + // emulation with a steady_clock-based CycleClock (e.g. Android ARM32). So + // allow 10% above and 1/3 below, which still excludes expected / 2. + EXPECT_LE(best, expected + expected / 10); + EXPECT_GE(best, expected - expected / 3); +} + } // namespace } // namespace base_internal ABSL_NAMESPACE_END
diff --git a/absl/synchronization/mutex.cc b/absl/synchronization/mutex.cc index d5c1a3c..a988658 100644 --- a/absl/synchronization/mutex.cc +++ b/absl/synchronization/mutex.cc
@@ -1572,9 +1572,10 @@ } // Attempt to acquire *mu, and return whether successful. The implementation -// may spin for a short while if the lock cannot be acquired immediately. -static bool TryAcquireWithSpinning(std::atomic<intptr_t>* mu) { - int c = globals.spinloop_iterations.load(std::memory_order_relaxed); +// may spin up to `iterations` times if the lock cannot be acquired immediately. +// Noinline so ProbeMutexSpinLoop() times the same compiled loop. +ABSL_ATTRIBUTE_NOINLINE static bool TryAcquireWithSpinning( + std::atomic<intptr_t>* mu, int iterations) { do { // do/while somewhat faster on AMD intptr_t v = mu->load(std::memory_order_relaxed); if ((v & (kMuReader | kMuEvent)) != 0) { @@ -1585,10 +1586,23 @@ std::memory_order_relaxed)) { return true; } - } while (--c > 0); + } while (--iterations > 0); return false; } +static void ProbeMutexSpinLoop(int steps) { + std::atomic<intptr_t> mu{kMuWriter}; + ABSL_RAW_CHECK(!TryAcquireWithSpinning(&mu, steps), + "TryAcquireWithSpinning acquired held mutex"); +} + +ABSL_ATTRIBUTE_NOINLINE void Mutex::LockSlowWithSpinning() { + if (!TryAcquireWithSpinning( + &mu_, globals.spinloop_iterations.load(std::memory_order_relaxed))) { + LockSlow(kExclusive, nullptr, 0); + } +} + void Mutex::lock() { ABSL_TSAN_MUTEX_PRE_LOCK(this, 0); DebugOnlyDeadlockCheck(this); @@ -1599,9 +1613,7 @@ v, kMuWriter | v, std::memory_order_acquire, std::memory_order_relaxed))) { // try spin acquire, then slow loop - if (ABSL_PREDICT_FALSE(!TryAcquireWithSpinning(&this->mu_))) { - this->LockSlow(kExclusive, nullptr, 0); - } + this->LockSlowWithSpinning(); } DebugOnlyLockEnter(this); ABSL_TSAN_MUTEX_POST_LOCK(this, 0, 0); @@ -1898,13 +1910,9 @@ // spinloop_iterations properly initialized. if (ABSL_PREDICT_FALSE( globals.spinloop_iterations.load(std::memory_order_relaxed) == 0)) { - if (absl::base_internal::NumCPUs() > 1) { - // If this is multiprocessor, allow spinning. - globals.spinloop_iterations.store(1500, std::memory_order_relaxed); - } else { - // If this a uniprocessor, only yield/sleep. - globals.spinloop_iterations.store(-1, std::memory_order_relaxed); - } + globals.spinloop_iterations.store( + base_internal::CalibrateSpinIterations(&ProbeMutexSpinLoop), + std::memory_order_relaxed); } ABSL_RAW_CHECK( this->LockSlowWithDeadline(how, cond, KernelTimeout::Never(), flags),
diff --git a/absl/synchronization/mutex.h b/absl/synchronization/mutex.h index 0fbc9a5..1972b1f 100644 --- a/absl/synchronization/mutex.h +++ b/absl/synchronization/mutex.h
@@ -562,6 +562,8 @@ ABSL_ATTRIBUTE_COLD void LockSlow(MuHow absl_nonnull how, const Condition* absl_nullable cond, int flags); + // Contended exclusive lock(): spins, then falls back to LockSlow(). + void LockSlowWithSpinning(); // slow path release ABSL_ATTRIBUTE_COLD void UnlockSlow(SynchWaitParams* absl_nullable waitp); // TryLock slow path.