2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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_pause_defined
133 platform::backoff_pause();
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 /// Exponential back-off
184 This back-off strategy is composite. It consists of \p SpinBkoff and \p YieldBkoff
185 back-off strategy. In first, the strategy tries to apply repeatedly \p SpinBkoff
186 (spinning phase) until internal counter of failed attempts reaches its maximum
187 spinning value. Then, the strategy transits to high-contention phase
188 where it applies \p YieldBkoff until \p reset() is called.
189 On each spinning iteration the internal spinning counter is doubled.
191 Choosing the best value for maximum spinning bound is platform and task specific.
192 In this implementation, the default values for maximum and minimum spinning is statically
193 declared so you can set its value globally for your platform.
194 The third template argument, \p Tag, is used to separate implementation. For
195 example, you may define two \p exponential back-offs that is the best for your task A and B:
198 #include <cds/algo/backoff_strategy.h>
199 namespace bkoff = cds::backoff;
201 struct tagA ; // tag to select task A implementation
202 struct tagB ; // tag to select task B implementation
204 // // define your back-off specialization
205 typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagA> expBackOffA;
206 typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagB> expBackOffB;
208 // // set up the best bounds for task A
209 expBackOffA::s_nExpMin = 32;
210 expBackOffA::s_nExpMax = 1024;
212 // // set up the best bounds for task B
213 expBackOffB::s_nExpMin = 2;
214 expBackOffB::s_nExpMax = 512;
218 Another way of solving this problem is subclassing \p exponential back-off class:
220 #include <cds/algo/backoff_strategy.h>
221 namespace bkoff = cds::backoff;
222 typedef bkoff::exponential<bkoff::hint, bkoff::yield> base_bkoff;
224 class expBackOffA: public base_bkoff
228 : base_bkoff( 32, 1024 )
232 class expBackOffB: public base_bkoff
236 : base_bkoff( 2, 512 )
241 template <typename SpinBkoff, typename YieldBkoff, typename Tag=void>
245 typedef SpinBkoff spin_backoff ; ///< spin back-off strategy
246 typedef YieldBkoff yield_backoff ; ///< yield back-off strategy
247 typedef Tag impl_tag ; ///< implementation separation tag
249 static size_t s_nExpMin ; ///< Default minimum spinning bound (16)
250 static size_t s_nExpMax ; ///< Default maximum spinning bound (16384)
253 size_t m_nExpCur ; ///< Current spinning
254 size_t m_nExpMin ; ///< Minimum spinning bound
255 size_t m_nExpMax ; ///< Maximum spinning bound
257 spin_backoff m_bkSpin ; ///< Spinning (fast-path) phase back-off strategy
258 yield_backoff m_bkYield ; ///< Yield phase back-off strategy
261 /// Initializes m_nExpMin and m_nExpMax from default s_nExpMin and s_nExpMax respectively
262 exponential() CDS_NOEXCEPT
263 : m_nExpMin( s_nExpMin )
264 , m_nExpMax( s_nExpMax )
266 m_nExpCur = m_nExpMin;
269 /// Explicitly defined bounds of spinning
271 The \p libcds library never calls this ctor.
274 size_t nExpMin, ///< Minimum spinning
275 size_t nExpMax ///< Maximum spinning
277 : m_nExpMin( nExpMin )
278 , m_nExpMax( nExpMax )
280 m_nExpCur = m_nExpMin;
284 void operator ()() CDS_NOEXCEPT_(noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
286 if ( m_nExpCur <= m_nExpMax ) {
287 for ( size_t n = 0; n < m_nExpCur; ++n )
295 template <typename Predicate>
296 bool operator()( Predicate pr ) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()) && noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()() ))
298 if ( m_nExpCur <= m_nExpMax ) {
299 for ( size_t n = 0; n < m_nExpCur; ++n ) {
306 return m_bkYield(pr);
310 void reset() CDS_NOEXCEPT_( noexcept( std::declval<spin_backoff>().reset() ) && noexcept( std::declval<yield_backoff>().reset() ))
312 m_nExpCur = m_nExpMin;
320 template <typename SpinBkoff, typename YieldBkoff, typename Tag>
321 size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMin = 16;
323 template <typename SpinBkoff, typename YieldBkoff, typename Tag>
324 size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMax = 16 * 1024;
327 /// Delay back-off strategy
330 - \p Duration - duration type, default is \p std::chrono::milliseconds
331 - \p Tag - a selector tag
333 Choosing the best value for th timeout is platform and task specific.
334 In this implementation, the default values for timeout is statically
335 declared so you can set its value globally for your platform.
336 The second template argument, \p Tag, is used to separate implementation. For
337 example, you may define two \p delay back-offs for 5 and 10 ms timeout:
340 #include <cds/algo/backoff_strategy.h>
341 namespace bkoff = cds::backoff;
343 struct ms5 ; // tag to select 5ms
344 struct ms10 ; // tag to select 10ms
346 // // define your back-off specialization
347 typedef bkoff::delay<std::chrono::milliseconds, ms5> delay5;
348 typedef bkoff::delay<std::chrono::milliseconds, ms10> delay10;
350 // // set up the timeouts
351 delay5::s_nTimeout = 5;
352 delay10::s_nTimeout = 10;
355 Another way of solving this problem is subclassing \p delay back-off class:
357 #include <cds/algo/backoff_strategy.h>
358 namespace bkoff = cds::backoff;
359 typedef bkoff::delay<> delay_bkoff;
361 class delay5: public delay_bkoff {
363 delay5(): delay_bkoff( 5 ) {}
366 class delay10: public delay_bkoff {
368 delay10(): delay_bkoff( 10 ) {}
373 template <class Duration = std::chrono::milliseconds, typename Tag=void >
377 typedef Duration duration_type; ///< Duration type (default \p std::chrono::milliseconds)
378 static unsigned int s_nTimeout; ///< default timeout, =5
382 unsigned int const m_nTimeout;
386 /// Default ctor takes the timeout from s_nTimeout
388 : m_nTimeout( s_nTimeout )
391 /// Initializes timeout from \p nTimeout
392 CDS_CONSTEXPR explicit delay( unsigned int nTimeout ) CDS_NOEXCEPT
393 : m_nTimeout( nTimeout )
397 void operator()() const
399 std::this_thread::sleep_for( duration_type( m_nTimeout ));
402 template <typename Predicate>
403 bool operator()(Predicate pr) const
405 for ( unsigned int i = 0; i < m_nTimeout; i += 2 ) {
408 std::this_thread::sleep_for( duration_type( 2 ));
413 static void reset() CDS_NOEXCEPT
419 template <class Duration, typename Tag>
420 unsigned int delay<Duration, Tag>::s_nTimeout = 5;
424 /// Delay back-off strategy, template version
426 This is a template version of backoff::delay class.
427 Template parameter \p Timeout sets a delay timeout.
428 The declaration <tt>cds::backoff::delay_of< 5 > bkoff</tt> is equal for
429 <tt>cds::backoff::delay<> bkoff(5)</tt>.
431 template <unsigned int Timeout, class Duration = std::chrono::milliseconds >
432 class delay_of: public delay<Duration>
435 typedef delay<Duration> base_class;
437 delay_of() CDS_NOEXCEPT
438 : base_class( Timeout )
444 /// Default backoff strategy
445 typedef exponential<hint, yield> Default;
447 /// Default back-off strategy for lock primitives
448 typedef exponential<hint, yield> LockDefault;
450 } // namespace backoff
454 #endif // #ifndef CDSLIB_BACKOFF_STRATEGY_H