3 #ifndef CDSLIB_BACKOFF_STRATEGY_H
4 #define CDSLIB_BACKOFF_STRATEGY_H
7 Filename: backoff_strategy.h
8 Created 2007.03.01 by Maxim Khiszinsky
11 Generic back-off strategies
14 2007.03.01 Maxim Khiszinsky Created
15 2008.10.02 Maxim Khiszinsky Backoff action transfers from contructor to operator() for all backoff schemas
16 2009.09.10 Maxim Khiszinsky reset() function added
19 #include <utility> // declval
22 #include <cds/compiler/backoff.h>
25 /// Different backoff schemes
27 Back-off schema may be used in lock-free algorithms when the algorithm cannot perform some action because a conflict
28 with the other concurrent operation is encountered. In this case current thread can do another work or can call
29 processor's performance hint.
31 The interface of back-off strategy is following:
33 struct backoff_strategy {
35 template <typename Predicate> bool operator()( Predicate pr );
40 \p operator() operator calls back-off strategy's action. It is main part of back-off strategy.
42 Interruptible back-off <tt>template < typename Predicate > bool operator()( Predicate pr )</tt>
43 allows to interrupt back-off spinning if \p pr predicate returns \p true.
44 \p Predicate is a functor with the following interface:
51 \p reset() function resets internal state of back-off strategy to initial state. It is required for some
52 back-off strategies, for example, exponential back-off.
56 /// Empty backoff strategy. Do nothing
59 void operator ()() const CDS_NOEXCEPT
62 template <typename Predicate>
63 bool operator()(Predicate pr) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
68 void reset() const CDS_NOEXCEPT
73 /// Switch to another thread (yield). Good for thread preemption architecture.
76 void operator ()() CDS_NOEXCEPT
78 std::this_thread::yield();
81 template <typename Predicate>
82 bool operator()(Predicate pr) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
90 void reset() const CDS_NOEXCEPT
97 This back-off strategy calls processor-specific pause hint instruction
98 if one is available for the processor architecture.
102 void operator ()() CDS_NOEXCEPT
104 # ifdef CDS_backoff_pause_defined
105 platform::backoff_pause();
109 template <typename Predicate>
110 bool operator()(Predicate pr) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
118 void reset() const CDS_NOEXCEPT
123 /// Processor hint back-off
125 This back-off schema calls performance hint instruction if it is available for current processor.
126 Otherwise, it calls \p nop.
131 void operator ()() CDS_NOEXCEPT
133 # if defined(CDS_backoff_hint_defined)
134 platform::backoff_hint();
135 # elif defined(CDS_backoff_nop_defined)
136 platform::backoff_nop();
140 template <typename Predicate>
141 bool operator()(Predicate pr) CDS_NOEXCEPT_(noexcept(std::declval<Predicate>()() ))
149 void reset() const CDS_NOEXCEPT
154 /// Exponential back-off
156 This back-off strategy is composite. It consists of \p SpinBkoff and \p YieldBkoff
157 back-off strategy. In first, the strategy tries to apply repeatedly \p SpinBkoff
158 (spinning phase) until internal counter of failed attempts reaches its maximum
159 spinning value. Then, the strategy transits to high-contention phase
160 where it applies \p YieldBkoff until \p reset() is called.
161 On each spinning iteration the internal spinning counter is doubled.
163 Choosing the best value for maximum spinning bound is platform and task specific.
164 In this implementation, the default values for maximum and minimum spinning is statically
165 declared so you can set its value globally for your platform.
166 The third template argument, \p Tag, is used to separate implementation. For
167 example, you may define two \p exponential back-offs that is the best for your task A and B:
170 #include <cds/algo/backoff_strategy.h>
171 namespace bkoff = cds::backoff;
173 struct tagA ; // tag to select task A implementation
174 struct tagB ; // tag to select task B implementation
176 // // define your back-off specialization
177 typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagA> expBackOffA;
178 typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagB> expBackOffB;
180 // // set up the best bounds for task A
181 expBackOffA::s_nExpMin = 32;
182 expBackOffA::s_nExpMax = 1024;
184 // // set up the best bounds for task B
185 expBackOffB::s_nExpMin = 2;
186 expBackOffB::s_nExpMax = 512;
190 Another way of solving this problem is subclassing \p exponential back-off class:
192 #include <cds/algo/backoff_strategy.h>
193 namespace bkoff = cds::backoff;
194 typedef bkoff::exponential<bkoff::hint, bkoff::yield> base_bkoff;
196 class expBackOffA: public base_bkoff
200 : base_bkoff( 32, 1024 )
204 class expBackOffB: public base_bkoff
208 : base_bkoff( 2, 512 )
213 template <typename SpinBkoff, typename YieldBkoff, typename Tag=void>
217 typedef SpinBkoff spin_backoff ; ///< spin back-off strategy
218 typedef YieldBkoff yield_backoff ; ///< yield back-off strategy
219 typedef Tag impl_tag ; ///< implementation separation tag
221 static size_t s_nExpMin ; ///< Default minimum spinning bound (16)
222 static size_t s_nExpMax ; ///< Default maximum spinning bound (16384)
225 size_t m_nExpCur ; ///< Current spinning
226 size_t m_nExpMin ; ///< Minimum spinning bound
227 size_t m_nExpMax ; ///< Maximum spinning bound
229 spin_backoff m_bkSpin ; ///< Spinning (fast-path) phase back-off strategy
230 yield_backoff m_bkYield ; ///< Yield phase back-off strategy
233 /// Initializes m_nExpMin and m_nExpMax from default s_nExpMin and s_nExpMax respectively
234 exponential() CDS_NOEXCEPT
235 : m_nExpMin( s_nExpMin )
236 , m_nExpMax( s_nExpMax )
238 m_nExpCur = m_nExpMin;
241 /// Explicitly defined bounds of spinning
243 The \p libcds library never calls this ctor.
246 size_t nExpMin, ///< Minimum spinning
247 size_t nExpMax ///< Maximum spinning
249 : m_nExpMin( nExpMin )
250 , m_nExpMax( nExpMax )
252 m_nExpCur = m_nExpMin;
256 void operator ()() CDS_NOEXCEPT_(noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
258 if ( m_nExpCur <= m_nExpMax ) {
259 for ( size_t n = 0; n < m_nExpCur; ++n )
267 template <typename Predicate>
268 bool operator()( Predicate pr ) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()) && noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()() ))
270 if ( m_nExpCur <= m_nExpMax ) {
271 for ( size_t n = 0; n < m_nExpCur; ++n ) {
278 return m_bkYield(pr);
282 void reset() CDS_NOEXCEPT_( noexcept( std::declval<spin_backoff>().reset() ) && noexcept( std::declval<yield_backoff>().reset() ))
284 m_nExpCur = m_nExpMin;
292 template <typename SpinBkoff, typename YieldBkoff, typename Tag>
293 size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMin = 16;
295 template <typename SpinBkoff, typename YieldBkoff, typename Tag>
296 size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMax = 16 * 1024;
299 /// Delay back-off strategy
302 - \p Duration - duration type, default is \p std::chrono::milliseconds
303 - \p Tag - a selector tag
305 Choosing the best value for th timeout is platform and task specific.
306 In this implementation, the default values for timeout is statically
307 declared so you can set its value globally for your platform.
308 The second template argument, \p Tag, is used to separate implementation. For
309 example, you may define two \p delay back-offs for 5 and 10 ms timeout:
312 #include <cds/algo/backoff_strategy.h>
313 namespace bkoff = cds::backoff;
315 struct ms5 ; // tag to select 5ms
316 struct ms10 ; // tag to select 10ms
318 // // define your back-off specialization
319 typedef bkoff::delay<std::chrono::milliseconds, ms5> delay5;
320 typedef bkoff::delay<std::chrono::milliseconds, ms10> delay10;
322 // // set up the timeouts
323 delay5::s_nTimeout = 5;
324 delay10::s_nTimeout = 10;
327 Another way of solving this problem is subclassing \p delay back-off class:
329 #include <cds/algo/backoff_strategy.h>
330 namespace bkoff = cds::backoff;
331 typedef bkoff::delay<> delay_bkoff;
333 class delay5: public delay_bkoff {
335 delay5(): delay_bkoff( 5 ) {}
338 class delay10: public delay_bkoff {
340 delay10(): delay_bkoff( 10 ) {}
345 template <class Duration = std::chrono::milliseconds, typename Tag=void >
349 typedef Duration duration_type; ///< Duration type (default \p std::chrono::milliseconds)
350 static unsigned int s_nTimeout; ///< default timeout, =5
354 unsigned int const m_nTimeout;
358 /// Default ctor takes the timeout from s_nTimeout
360 : m_nTimeout( s_nTimeout )
363 /// Initializes timeout from \p nTimeout
364 CDS_CONSTEXPR delay( unsigned int nTimeout ) CDS_NOEXCEPT
365 : m_nTimeout( nTimeout )
369 void operator()() const
371 std::this_thread::sleep_for( duration_type( m_nTimeout ));
374 template <typename Predicate>
375 bool operator()(Predicate pr) const
377 for ( unsigned int i = 0; i < m_nTimeout; i += 2 ) {
380 std::this_thread::sleep_for( duration_type( 2 ));
385 void reset() const CDS_NOEXCEPT
391 template <class Duration, typename Tag>
392 unsigned int delay<Duration, Tag>::s_nTimeout = 5;
396 /// Delay back-off strategy, template version
398 This is a template version of backoff::delay class.
399 Template parameter \p Timeout sets a delay timeout.
400 The declaration <tt>cds::backoff::delay_of< 5 > bkoff</tt> is equal for
401 <tt>cds::backoff::delay<> bkoff(5)</tt>.
403 template <unsigned int Timeout, class Duration = std::chrono::milliseconds >
404 class delay_of: public delay<Duration>
407 typedef delay<Duration> base_class;
409 delay_of() CDS_NOEXCEPT
410 : base_class( Timeout )
416 /// Default backoff strategy
417 typedef exponential<hint, yield> Default;
419 /// Default back-off strategy for lock primitives
420 typedef exponential<hint, yield> LockDefault;
422 } // namespace backoff
426 #endif // #ifndef CDSLIB_BACKOFF_STRATEGY_H