2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_BACKOFF_STRATEGY_H
32 #define CDSLIB_BACKOFF_STRATEGY_H
35 Filename: backoff_strategy.h
36 Created 2007.03.01 by Maxim Khiszinsky
39 Generic back-off strategies
42 2007.03.01 Maxim Khiszinsky Created
43 2008.10.02 Maxim Khiszinsky Backoff action transfers from contructor to operator() for all backoff schemas
44 2009.09.10 Maxim Khiszinsky reset() function added
47 #include <utility> // declval
50 #include <cds/compiler/backoff.h>
53 /// Different backoff schemes
55 Back-off schema may be used in lock-free algorithms when the algorithm cannot perform some action because a conflict
56 with the other concurrent operation is encountered. In this case current thread can do another work or can call
57 processor's performance hint.
59 The interface of back-off strategy is following:
61 struct backoff_strategy {
63 template <typename Predicate> bool operator()( Predicate pr );
68 \p operator() operator calls back-off strategy's action. It is main part of back-off strategy.
70 Interruptible back-off <tt>template < typename Predicate > bool operator()( Predicate pr )</tt>
71 allows to interrupt back-off spinning if \p pr predicate returns \p true.
72 \p Predicate is a functor with the following interface:
79 \p reset() function resets internal state of back-off strategy to initial state. It is required for some
80 back-off strategies, for example, exponential back-off.
84 /// Empty backoff strategy. Do nothing
87 void operator ()() const CDS_NOEXCEPT
90 template <typename Predicate>
91 bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()))
96 static void reset() CDS_NOEXCEPT
101 /// Switch to another thread (yield). Good for thread preemption architecture.
104 void operator ()() const CDS_NOEXCEPT
106 std::this_thread::yield();
109 template <typename Predicate>
110 bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()))
118 static void reset() CDS_NOEXCEPT
125 This back-off strategy calls processor-specific pause hint instruction
126 if one is available for the processor architecture.
130 void operator ()() const CDS_NOEXCEPT
132 # ifdef CDS_backoff_hint_defined
133 platform::backoff_hint();
137 template <typename Predicate>
138 bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()))
146 static void reset() CDS_NOEXCEPT
151 /// Processor hint back-off
153 This back-off schema calls performance hint instruction if it is available for current processor.
154 Otherwise, it calls \p nop.
159 void operator ()() const CDS_NOEXCEPT
161 # if defined(CDS_backoff_hint_defined)
162 platform::backoff_hint();
163 # elif defined(CDS_backoff_nop_defined)
164 platform::backoff_nop();
168 template <typename Predicate>
169 bool operator()(Predicate pr) const CDS_NOEXCEPT_(noexcept(std::declval<Predicate>()()))
177 static void reset() CDS_NOEXCEPT
182 /// \p backoff::exponential const traits
183 struct exponential_const_traits
185 typedef hint fast_path_backoff; ///< Fast-path back-off strategy
186 typedef yield slow_path_backoff; ///< Slow-path back-off strategy
189 lower_bound = 16, ///< Minimum spinning limit
190 upper_bound = 16 * 1024 ///< Maximum spinning limit
194 /// \p nackoff::exponential runtime traits
195 struct exponential_runtime_traits
197 typedef hint fast_path_backoff; ///< Fast-path back-off strategy
198 typedef yield slow_path_backoff; ///< Slow-path back-off strategy
200 static size_t lower_bound; ///< Minimum spinning limit, default is 16
201 static size_t upper_bound; ///< Maximum spinning limit, default is 16*1024
204 /// Exponential back-off
206 This back-off strategy is composite. It consists of \p SpinBkoff and \p YieldBkoff
207 back-off strategy. In first, the strategy tries to apply repeatedly \p SpinBkoff
208 (spinning phase) until internal counter of failed attempts reaches its maximum
209 spinning value. Then, the strategy transits to high-contention phase
210 where it applies \p YieldBkoff until \p reset() is called.
211 On each spinning iteration the internal spinning counter is doubled.
213 Selecting the best value for maximum spinning limit is platform and application specific task.
214 The limits are described by \p Traits template parameter.
215 There are two types of \p Traits:
216 - constant traits \p exponential_const_traits - specifies the lower and upper limits
217 as a compile-time constants; to change the limits you should recompile your application
218 - runtime traits \p exponential_runtime_traits - specifies the limits as \p s_nExpMin
219 and \p s_nExpMax variables which can be changed at runtime to tune back-off strategy.
221 The traits class must declare two data member:
222 - \p lower_bound - the lower bound of spinning loop
223 - \p upper_bound - the upper boudn of spinning loop
225 You may use \p Traits template parameter to separate back-off implementations.
226 For example, you may define two \p exponential back-offs that is the best for your task A and B:
229 #include <cds/algo/backoff_strategy.h>
230 namespace bkoff = cds::backoff;
232 // the best bounds for task A
233 struct traits_A: public bkoff::exponential_const_traits
235 static size_t lower_bound;
236 static size_t upper_bound;
238 size_t traits_A::lower_bound = 1024;
239 size_t traits_A::upper_bound = 8 * 1024;
241 // the best bounds for task B
242 struct traits_B: public bkoff::exponential_const_traits
244 static size_t lower_bound;
245 static size_t upper_bound;
247 size_t traits_A::lower_bound = 16;
248 size_t traits_A::upper_bound = 1024;
250 // // define your back-off specialization
251 typedef bkoff::exponential<traits_A> expBackOffA;
252 typedef bkoff::exponential<traits_B> expBackOffB;
255 template <typename Traits = exponential_const_traits >
259 typedef Traits traits; ///< Traits
261 typedef typename traits::fast_path_backoff spin_backoff ; ///< spin (fast-path) back-off strategy
262 typedef typename traits::slow_path_backoff yield_backoff ; ///< yield (slow-path) back-off strategy
265 size_t m_nExpCur ; ///< Current spin counter in range [traits::s_nExpMin, traits::s_nExpMax]
267 spin_backoff m_bkSpin ; ///< Spinning (fast-path) phase back-off strategy
268 yield_backoff m_bkYield ; ///< Yield phase back-off strategy
272 exponential() CDS_NOEXCEPT
273 : m_nExpCur( traits::lower_bound )
277 void operator ()() CDS_NOEXCEPT_(noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
279 if ( m_nExpCur <= traits::upper_bound ) {
280 for ( size_t n = 0; n < m_nExpCur; ++n )
288 template <typename Predicate>
289 bool operator()( Predicate pr ) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()) && noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
291 if ( m_nExpCur <= traits::upper_bound ) {
292 for ( size_t n = 0; n < m_nExpCur; ++n ) {
299 return m_bkYield(pr);
303 void reset() CDS_NOEXCEPT_( noexcept( std::declval<spin_backoff>().reset()) && noexcept( std::declval<yield_backoff>().reset()))
305 m_nExpCur = traits::lower_bound;
313 template <typename FastPathBkOff, typename SlowPathBkOff>
314 struct make_exponential
316 struct traits: public exponential_const_traits
318 typedef FastPathBkOff fast_path_backoff;
319 typedef SlowPathBkOff slow_path_backoff;
322 typedef exponential<traits> type;
325 template <typename FastPathBkOff, typename SlowPathBkOff>
326 using make_exponential_t = typename make_exponential<FastPathBkOff, SlowPathBkOff>::type;
329 /// Constant traits for \ref delay back-off strategy
330 struct delay_const_traits
332 typedef std::chrono::milliseconds duration_type; ///< Timeout type
334 timeout = 5 ///< Delay timeout
338 /// Runtime traits for \ref delay back-off strategy
339 struct delay_runtime_traits
341 typedef std::chrono::milliseconds duration_type; ///< Timeout type
342 static unsigned timeout; ///< Delay timeout, default 5
345 /// Delay back-off strategy
348 - \p Duration - duration type, default is \p std::chrono::milliseconds
349 - \p Traits - a class that defines default timeout.
351 Choosing the best value for th timeout is platform and application specific task.
352 The default values for timeout is provided by \p Traits class that should
353 \p timeout data member. There are two predefined \p Traits implementation:
354 - \p delay_const_traits - defines \p timeout as a constant (enum).
355 To change timeout you should recompile your application.
356 - \p delay_runtime_traits - specifies timeout as static data member that can be changed
357 at runtime to tune the back-off strategy.
359 You may use \p Traits template parameter to separate back-off implementations.
360 For example, you may define two \p delay back-offs for 5 and 10 ms timeout:
363 #include <cds/algo/backoff_strategy.h>
364 namespace bkoff = cds::backoff;
369 typedef std::chrono::milliseconds duration_type;
370 enum: unsigned { timeout = 5 };
373 // 10ms delay, runtime support
376 typedef std::chrono::milliseconds duration_type;
377 static unsigned timeout;
379 unsigned ms10::timeout = 10;
381 // define your back-off specialization
382 typedef bkoff::delay<std::chrono::milliseconds, ms5> delay5;
383 typedef bkoff::delay<std::chrono::milliseconds, ms10> delay10;
387 template <typename Traits = delay_const_traits>
391 typedef Traits traits; ///< Traits
392 typedef typename Traits::duration_type duration_type; ///< Duration type (default \p std::chrono::milliseconds)
396 duration_type const timeout;
400 /// Default ctor takes the timeout from \p traits::timeout
402 : timeout( traits::timeout )
405 /// Initializes timeout from \p nTimeout
406 CDS_CONSTEXPR explicit delay( unsigned int nTimeout ) CDS_NOEXCEPT
407 : timeout( nTimeout )
411 void operator()() const
413 std::this_thread::sleep_for( timeout );
416 template <typename Predicate>
417 bool operator()(Predicate pr) const
419 for ( unsigned int i = 0; i < traits::timeout; i += 2 ) {
422 std::this_thread::sleep_for( duration_type( 2 ));
427 static void reset() CDS_NOEXCEPT
433 template <unsigned int Timeout, class Duration = std::chrono::milliseconds >
437 typedef Duration duration_type;
438 enum: unsigned { timeout = Timeout };
441 typedef delay<traits> type;
445 /// Delay back-off strategy, template version
447 This is a simplified version of \p backoff::delay class.
448 Template parameter \p Timeout sets a delay timeout of \p Duration unit.
450 template <unsigned int Timeout, class Duration = std::chrono::milliseconds >
451 using delay_of = typename make_delay_of< Timeout, Duration >::type;
454 /// Default backoff strategy
455 typedef exponential<exponential_const_traits> Default;
457 /// Default back-off strategy for lock primitives
458 typedef exponential<exponential_const_traits> LockDefault;
460 } // namespace backoff
464 #endif // #ifndef CDSLIB_BACKOFF_STRATEGY_H