omango_util/
backoff.rs

1// Copyright (c) 2024 Trung Tran <tqtrungse@gmail.com>
2//
3// Permission is hereby granted, free of charge, to any person obtaining a copy
4// of this software and associated documentation files (the "Software"), to deal
5// in the Software without restriction, including without limitation the rights
6// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7// copies of the Software, and to permit persons to whom the Software is
8// furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in all
11// copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
19// SOFTWARE.
20
21//! This file was modified based on the following program in Crossbeam-Utils.
22//!
23//! Source: `<https://github.com/crossbeam-rs/crossbeam/blob/master/crossbeam-utils/src/backoff.rs>`
24//!
25//! Copyright & License:
26//!   - The Crossbeam Project Developers
27//!   - The MIT License (MIT) or Apache License 2.0
28//!         `<https://opensource.org/licenses/MIT>`
29//!         '<https://www.apache.org/licenses/LICENSE-2.0>'
30
31use core::cell::Cell;
32
33use crate::hint::likely;
34
35const SPIN_LIMIT: u32 = 6;
36const YIELD_LIMIT: u32 = 10;
37
38/// Makes the current thread to wait in the short time.
39///
40/// It should be used to implement wait-retry in high contention multithreading environment
41/// because of improving performance significantly.
42///
43/// It should not be used to replace other blocking mechanism.
44pub struct Backoff {
45    step: Cell<u32>,
46}
47
48impl Backoff {
49    #[inline(always)]
50    pub fn reset(&self) {
51        self.step.set(0);
52    }
53
54    /// Backs off in a lock-free loop.
55    ///
56    /// This method should be used when we need to retry an operation because another thread made
57    /// progress.
58    ///
59    /// The processor may yield using the *YIELD* or *PAUSE* instruction.
60    #[inline]
61    pub fn spin(&self) {
62        for _ in 0..1 << self.step.get().min(SPIN_LIMIT) {
63            core::hint::spin_loop();
64        }
65        if self.step.get() <= SPIN_LIMIT {
66            self.step.set(self.step.get() + 1);
67        }
68    }
69
70    /// Backs off in a blocking loop.
71    ///
72    /// This method should be used when we need to wait for another thread to make progress.
73    ///
74    /// The processor may yield using the *YIELD* or *PAUSE* instruction and the current thread
75    /// may yield by giving up a time slice to the OS scheduler.
76    #[inline]
77    pub fn snooze(&self) {
78        if self.step.get() <= SPIN_LIMIT {
79            for _ in 0..1 << self.step.get() {
80                core::hint::spin_loop();
81            }
82            self.step.set(self.step.get() + 1);
83        } else {
84            std::thread::yield_now();
85        }
86    }
87
88    /// Backs off in a blocking loop.
89    ///
90    /// This method should be used when we need to wait for another thread to make progress.
91    ///
92    /// The processor may yield using the *YIELD* or *PAUSE* instruction and the current thread
93    /// may yield by giving up a time slice to the OS scheduler.
94    ///
95    /// Return `true` to advise to stop using backoff and
96    /// block the current thread using a different synchronization mechanism instead.
97    #[inline]
98    pub fn snooze_completed(&self) -> bool {
99        if likely(self.step.get() <= SPIN_LIMIT) {
100            for _ in 0..1 << self.step.get() {
101                core::hint::spin_loop();
102            }
103        } else {
104            std::thread::yield_now();
105        }
106
107        if likely(self.step.get() <= YIELD_LIMIT) {
108            self.step.set(self.step.get() + 1);
109            return false;
110        }
111        true
112    }
113}
114
115impl Default for Backoff {
116    #[inline(always)]
117    fn default() -> Backoff {
118        Self {
119            step: Cell::new(0)
120        }
121    }
122}
omango_util/backoff.rs

omango_util/
backoff.rs
