orengine_utils/
backoff.rs

1//! This module provides a [`Backoff`] that can be used to busy-wait with
2//! preemptive yield when it is necessary.
3//!
4//! It has the same API as `crossbeam::Backoff`.
5use crate::hints::likely;
6use core::cell::Cell;
7use core::fmt;
8
9const SPIN_LIMIT: u32 = 6;
10
11/// Performs exponential backoff in spin loops.
12///
13/// Backing off in spin loops reduces contention and improves overall performance.
14///
15/// This primitive can execute *YIELD* and *PAUSE* instructions, yield the current thread to the OS
16/// scheduler, and tell when it is a good time to block the thread using a different synchronization
17/// mechanism. Each step of the back off procedure takes roughly twice as long as the previous
18/// step.
19pub struct Backoff {
20    step: Cell<u32>,
21}
22
23impl Backoff {
24    /// Creates a new `Backoff` instance.
25    #[inline]
26    pub fn new() -> Self {
27        Self { step: Cell::new(0) }
28    }
29
30    /// Returns the current backoff step
31    /// (how many times it has been called since the last [`reset`](Self::reset)).
32    #[inline]
33    pub fn step(&self) -> u32 {
34        self.step.get()
35    }
36
37    /// Resets the backoff state.
38    #[inline]
39    pub fn reset(&self) {
40        self.step.set(0);
41    }
42
43    /// Backs off in a lock-free loop.
44    ///
45    /// This method should be used when we need to retry an operation because another thread made
46    /// progress.
47    ///
48    /// The processor may yield using the *YIELD* or *PAUSE* instruction.
49    #[inline]
50    pub fn spin(&self) {
51        for _ in 0..1 << self.step.get().min(SPIN_LIMIT) {
52            std::hint::spin_loop();
53        }
54
55        self.step.set(self.step.get() + 1);
56    }
57
58    /// It [`spins`](Self::spin) or calls the provided function if
59    /// it [`should be used`](Self::is_completed).
60    ///
61    /// If the provided function is [`std::thread::yield_now`],
62    /// then this function has the same behaviour as [`snooze`](Self::snooze).
63    #[inline]
64    pub fn spin_or<F>(&self, f: F)
65    where
66        F: FnOnce(),
67    {
68        if likely(self.step.get() < SPIN_LIMIT) {
69            for _ in 0..1 << self.step.get().min(SPIN_LIMIT) {
70                std::hint::spin_loop();
71            }
72        } else {
73            f();
74        }
75
76        self.step.set(self.step.get() + 1);
77    }
78
79    /// Backs off in a blocking loop.
80    ///
81    /// This method should be used when we need to wait for another thread to make progress.
82    ///
83    /// The processor may yield using the *YIELD* or *PAUSE* instruction, and the current thread
84    /// may yield by giving up a timeslice to the OS scheduler.
85    ///
86    /// In `#[no_std]` environments, this method is equivalent to [`spin`].
87    ///
88    /// If possible, use [`is_completed`] to check when it is advised to stop using backoff and
89    /// block the current thread using a different synchronization mechanism instead.
90    ///
91    /// [`spin`]: Backoff::spin
92    /// [`is_completed`]: Backoff::is_completed
93    #[inline]
94    pub fn snooze(&self) {
95        self.spin_or(std::thread::yield_now);
96    }
97
98    /// Returns `true` if exponential backoff has completed and blocking the thread is advised.
99    #[inline]
100    pub fn is_completed(&self) -> bool {
101        self.step.get() >= SPIN_LIMIT
102    }
103}
104
105impl fmt::Debug for Backoff {
106    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
107        f.debug_struct("Backoff")
108            .field("step", &self.step)
109            .field("is_completed", &self.is_completed())
110            .finish()
111    }
112}
113
114impl Default for Backoff {
115    fn default() -> Self {
116        Self::new()
117    }
118}
orengine_utils/backoff.rs

orengine_utils/
backoff.rs
