3 #ifndef __CDS_BACKOFF_STRATEGY_H
4 #define __CDS_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
20 #include <cds/compiler/backoff.h>
21 #include <cds/details/std/chrono.h>
24 /// Different backoff schemes
26 Back-off schema may be used in lock-free algorithms when the algorithm cannot perform some action because a conflict
27 with the other concurrent operation is encountered. In this case current thread can do another work or can call
28 processor's performance hint.
30 The interface of back-off strategy is following:
32 struct backoff_strategy {
34 template <typename Predicate> bool operator()( Predicate pr );
39 \p operator() operator calls back-off strategy's action. It is main part of back-off strategy.
41 Interruptible back-off <tt>template < typename Predicate > bool operator()( Predicate pr )</tt>
42 allows to interrupt back-off spinning if \p pr predicate returns \p true.
43 \p Predicate is a functor with the following interface:
50 \p reset() function resets internal state of back-off strategy to initial state. It is required for some
51 back-off strategies, for example, exponential back-off.
55 /// Empty backoff strategy. Do nothing
61 template <typename Predicate>
62 bool operator()( Predicate pr )
72 /// Switch to another thread (yield). Good for thread preemption architecture.
77 std::this_thread::yield();
80 template <typename Predicate>
81 bool operator()( Predicate pr )
96 This back-off strategy calls processor-specific pause hint instruction
97 if one is available for the processor architecture.
103 # ifdef CDS_backoff_pause_defined
104 platform::backoff_pause();
108 template <typename Predicate>
109 bool operator()( Predicate pr )
122 /// Processor hint back-off
124 This back-off schema calls performance hint instruction if it is available for current processor.
125 Otherwise, it calls \p nop.
132 # if defined(CDS_backoff_hint_defined)
133 platform::backoff_hint();
134 # elif defined(CDS_backoff_nop_defined)
135 platform::backoff_nop();
139 template <typename Predicate>
140 bool operator()( Predicate pr )
153 /// Exponential back-off
155 This back-off strategy is composite. It consists of \p SpinBkoff and \p YieldBkoff
156 back-off strategy. In first, the strategy tries to apply repeatedly \p SpinBkoff
157 (spinning phase) until internal counter of failed attempts reaches its maximum
158 spinning value. Then, the strategy transits to high-contention phase
159 where it applies \p YieldBkoff until \p reset() is called.
160 On each spinning iteration the internal spinning counter is doubled.
162 Choosing the best value for maximum spinning bound is platform and task specific.
163 In this implementation, the default values for maximum and minimum spinning is statically
164 declared so you can set its value globally for your platform.
165 The third template argument, \p Tag, is used to separate implementation. For
166 example, you may define two \p exponential back-offs that is the best for your task A and B:
169 #include <cds/algo/backoff_strategy.h>
170 namespace bkoff = cds::backoff;
172 struct tagA ; // tag to select task A implementation
173 struct tagB ; // tag to select task B implementation
175 // // define your back-off specialization
176 typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagA> expBackOffA;
177 typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagB> expBackOffB;
179 // // set up the best bounds for task A
180 expBackOffA::s_nExpMin = 32;
181 expBackOffA::s_nExpMax = 1024;
183 // // set up the best bounds for task B
184 expBackOffB::s_nExpMin = 2;
185 expBackOffB::s_nExpMax = 512;
189 Another way of solving this problem is subclassing \p exponential back-off class:
191 #include <cds/algo/backoff_strategy.h>
192 namespace bkoff = cds::backoff;
193 typedef bkoff::exponential<bkoff::hint, bkoff::yield> base_bkoff;
195 class expBackOffA: public base_bkoff
199 : base_bkoff( 32, 1024 )
203 class expBackOffB: public base_bkoff
207 : base_bkoff( 2, 512 )
212 template <typename SpinBkoff, typename YieldBkoff, typename Tag=void>
216 typedef SpinBkoff spin_backoff ; ///< spin back-off strategy
217 typedef YieldBkoff yield_backoff ; ///< yield back-off strategy
218 typedef Tag impl_tag ; ///< implementation separation tag
220 static size_t s_nExpMin ; ///< Default minimum spinning bound (16)
221 static size_t s_nExpMax ; ///< Default maximum spinning bound (16384)
224 size_t m_nExpCur ; ///< Current spinning
225 size_t m_nExpMin ; ///< Minimum spinning bound
226 size_t m_nExpMax ; ///< Maximum spinning bound
228 spin_backoff m_bkSpin ; ///< Spinning (fast-path) phase back-off strategy
229 yield_backoff m_bkYield ; ///< Yield phase back-off strategy
232 /// Initializes m_nExpMin and m_nExpMax from default s_nExpMin and s_nExpMax respectively
234 : m_nExpMin( s_nExpMin )
235 , m_nExpMax( s_nExpMax )
237 m_nExpCur = m_nExpMin;
240 /// Explicitly defined bounds of spinning
242 The \p libcds library never calls this ctor.
245 size_t nExpMin, ///< Minimum spinning
246 size_t nExpMax ///< Maximum spinning
248 : m_nExpMin( nExpMin )
249 , m_nExpMax( nExpMax )
251 m_nExpCur = m_nExpMin;
257 if ( m_nExpCur <= m_nExpMax ) {
258 for ( size_t n = 0; n < m_nExpCur; ++n )
266 template <typename Predicate>
267 bool operator()( Predicate pr )
269 if ( m_nExpCur <= m_nExpMax ) {
270 for ( size_t n = 0; n < m_nExpCur; ++n ) {
277 return m_bkYield(pr);
283 m_nExpCur = m_nExpMin;
291 template <typename SpinBkoff, typename YieldBkoff, typename Tag>
292 size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMin = 16;
294 template <typename SpinBkoff, typename YieldBkoff, typename Tag>
295 size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMax = 16 * 1024;
298 /// Delay back-off strategy
301 - \p Duration - duration type, default is \p std::chrono::milliseconds
302 - \p Tag - a selector tag
304 Choosing the best value for th timeout is platform and task specific.
305 In this implementation, the default values for timeout is statically
306 declared so you can set its value globally for your platform.
307 The second template argument, \p Tag, is used to separate implementation. For
308 example, you may define two \p delay back-offs for 5 and 10 ms timeout:
311 #include <cds/algo/backoff_strategy.h>
312 namespace bkoff = cds::backoff;
314 struct ms5 ; // tag to select 5ms
315 struct ms10 ; // tag to select 10ms
317 // // define your back-off specialization
318 typedef bkoff::delay<std::chrono::milliseconds, ms5> delay5;
319 typedef bkoff::delay<std::chrono::milliseconds, ms10> delay10;
321 // // set up the timeouts
322 delay5::s_nTimeout = 5;
323 delay10::s_nTimeout = 10;
326 Another way of solving this problem is subclassing \p delay back-off class:
328 #include <cds/algo/backoff_strategy.h>
329 namespace bkoff = cds::backoff;
330 typedef bkoff::delay<> delay_bkoff;
332 class delay5: public delay_bkoff {
334 delay5(): delay_bkoff( 5 ) {}
337 class delay10: public delay_bkoff {
339 delay10(): delay_bkoff( 10 ) {}
344 template <class Duration = cds_std::chrono::milliseconds, typename Tag=void >
348 typedef Duration duration_type; ///< Duration type (default \p std::chrono::milliseconds)
349 static unsigned int s_nTimeout; ///< default timeout, =5
353 unsigned int const m_nTimeout;
357 /// Default ctor takes the timeout from s_nTimeout
359 : m_nTimeout( s_nTimeout )
362 /// Initializes timeout from \p nTimeout
363 CDS_CONSTEXPR delay( unsigned int nTimeout )
364 : m_nTimeout( nTimeout )
368 void operator()() const
370 std::this_thread::sleep_for( duration_type( m_nTimeout ));
373 template <typename Predicate>
374 bool operator()( Predicate pr ) const
376 for ( unsigned int i = 0; i < m_nTimeout; i += 2 ) {
379 std::this_thread::sleep_for( duration_type( 2 ));
390 template <class Duration, typename Tag>
391 unsigned int delay<Duration, Tag>::s_nTimeout = 5;
395 /// Delay back-off strategy, template version
397 This is a template version of backoff::delay class.
398 Template parameter \p Timeout sets a delay timeout.
399 The declaration <tt>cds::backoff::delay_of< 5 > bkoff</tt> is equal for
400 <tt>cds::backoff::delay<> bkoff(5)</tt>.
402 template <unsigned int Timeout, class Duration = cds_std::chrono::milliseconds >
403 class delay_of: public delay<Duration>
406 typedef delay<Duration> base_class;
409 : base_class( Timeout )
415 /// Default backoff strategy
416 typedef exponential<hint, yield> Default;
418 /// Default back-off strategy for lock primitives
419 typedef exponential<hint, yield> LockDefault;
421 } // namespace backoff
425 #endif // #ifndef __CDS_BACKOFF_STRATEGY_H