Adaptive backoff in CAS retry and wait loops

[lxl66566]

I have been profiling concurrent-queue and noticed a potential performance issue in the retry and wait paths compared to designs like crossbeam-queue.

Background

All retry/wait paths either retry immediately or use an all-or-nothing busy_wait(): under std every wait is a yield_now syscall, under no_std a single pause. Crossbeam use Backoff on that.

Measurements (x86_64, 32 cores, codegen-units = 1)

Example implementation at https://github.com/lxl66566/concurrent-queue/tree/backoff. It mirrors from crossbeam-queue:

• Backoff::spin() on CAS failure and empty/full check branches.
• Backoff::snooze() in wait loops.
• Reused crossbeam_utils::Backoff with std = ["crossbeam-utils/std"].

Result:

• High contention (MPSC 4P+1C, capacity 1024, pinned):
  • Bounded: Throughput increases from ~22–27 Mops/s to ~45–89 Mops/s.
  • Unbounded: Throughput increases from ~42–51 Mops/s to ~124–172 Mops/s.
• Low contention (Criterion mpsc_u32, 7P+1C, unbounded capacity):
  • Bounded: 79.6 ms -> 69.5 ms (-12.8%).
  • Unbounded: 48.5 ms -> 41.8 ms (-13.9%).
• Uncontended / Single-threaded / SPSC:
  • Instruction traces and pinned-core benchmarks show parity (no backoff branches).

Questions

• Is moving to a short exponential spin-then-yield backoff acceptable, or is the strict immediate-yield behavior intentionally preserved for specific scheduler characteristics?

Related issues:

• Merge implementation with crossbeam-queue #50, this is essentially an implementation that ports crossbeam's backoff logic to concurrent-queue.