Move libcds 1.6.0 from SVN
[libcds.git] / cds / backoff_strategy.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_BACKOFF_STRATEGY_H
4 #define __CDS_BACKOFF_STRATEGY_H
5
6 /*
7     Filename: backoff_strategy.h
8     Created 2007.03.01 by Maxim Khiszinsky
9
10     Description:
11          Generic back-off strategies
12
13     Editions:
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
17 */
18
19 #include <cds/compiler/backoff.h>
20 #include <cds/details/std/thread.h>
21 #include <cds/details/std/chrono.h>
22
23 namespace cds {
24     /// Different backoff schemes
25     /**
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.
29
30         The interface of back-off strategy is following:
31         \code
32             struct backoff_strategy {
33                 void operator()();
34                 template <typename Predicate> bool operator()( Predicate pr );
35                 void reset();
36             };
37         \endcode
38
39         \p operator() operator calls back-off strategy's action. It is main part of back-off strategy.
40
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:
44         \code
45         struct predicate {
46             bool operator()();
47         };
48         \endcode
49
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.
52     */
53     namespace backoff {
54
55         /// Empty backoff strategy. Do nothing
56         struct empty {
57             //@cond
58             void operator ()()
59             {}
60
61             template <typename Predicate>
62             bool operator()( Predicate pr )
63             {
64                 return pr();
65             }
66
67             void reset()
68             {}
69             //@endcond
70         };
71
72         /// Switch to another thread (yield). Good for thread preemption architecture.
73         struct yield {
74             //@cond
75             void operator ()()
76             {
77                 cds_std::this_thread::yield();
78                 //OS::yield();
79             }
80
81             template <typename Predicate>
82             bool operator()( Predicate pr )
83             {
84                 if ( pr() )
85                     return true;
86                 operator()();
87                 return false;
88             }
89
90             void reset()
91             {}
92             //@endcond
93         };
94
95         /// Random pause
96         /**
97             This back-off strategy calls processor-specific pause hint instruction
98             if one is available for the processor architecture.
99         */
100         struct pause {
101             //@cond
102             void operator ()()
103             {
104 #            ifdef CDS_backoff_pause_defined
105                 platform::backoff_pause();
106 #            endif
107             }
108
109             template <typename Predicate>
110             bool operator()( Predicate pr )
111             {
112                 if ( pr() )
113                     return true;
114                 operator()();
115                 return false;
116             }
117
118             void reset()
119             {}
120             //@endcond
121         };
122
123         /// Processor hint back-off
124         /**
125             This back-off schema calls performance hint instruction if it is available for current processor.
126             Otherwise, it calls \p nop.
127         */
128         struct hint
129         {
130         //@cond
131             void operator ()()
132             {
133 #           if defined(CDS_backoff_hint_defined)
134                 platform::backoff_hint();
135 #           elif defined(CDS_backoff_nop_defined)
136                 platform::backoff_nop();
137 #           endif
138             }
139
140             template <typename Predicate>
141             bool operator()( Predicate pr )
142             {
143                 if ( pr() )
144                     return true;
145                 operator()();
146                 return false;
147             }
148
149             void reset()
150             {}
151         //@endcond
152         };
153
154         /// Exponential back-off
155         /**
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.
162
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:
168             \code
169
170             #include <cds/backoff_strategy.h>
171             namespace bkoff = cds::backoff;
172
173             struct tagA ;   // tag to select task A implementation
174             struct tagB ;   // tag to select task B implementation
175
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;
179
180             // // set up the best bounds for task A
181             expBackOffA::s_nExpMin = 32;
182             expBackOffA::s_nExpMax = 1024;
183
184             // // set up the best bounds for task B
185             expBackOffB::s_nExpMin = 2;
186             expBackOffB::s_nExpMax = 512;
187
188             \endcode
189
190             Another way of solving this problem is subclassing \p exponential back-off class:
191             \code
192             #include <cds/backoff_strategy.h>
193             namespace bkoff = cds::backoff;
194             typedef bkoff::exponential<bkoff::hint, bkoff::yield>   base_bkoff;
195
196             class expBackOffA: public base_bkoff
197             {
198             public:
199                 expBackOffA()
200                     : base_bkoff( 32, 1024 )
201                     {}
202             };
203
204             class expBackOffB: public base_bkoff
205             {
206             public:
207                 expBackOffB()
208                     : base_bkoff( 2, 512 )
209                     {}
210             };
211             \endcode
212         */
213         template <typename SpinBkoff, typename YieldBkoff, typename Tag=void>
214         class exponential
215         {
216         public:
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
220
221             static size_t s_nExpMin ;   ///< Default minimum spinning bound (16)
222             static size_t s_nExpMax ;   ///< Default maximum spinning bound (16384)
223
224         protected:
225             size_t  m_nExpCur   ;   ///< Current spinning
226             size_t  m_nExpMin   ;   ///< Minimum spinning bound
227             size_t  m_nExpMax   ;   ///< Maximum spinning bound
228
229             spin_backoff    m_bkSpin    ;   ///< Spinning (fast-path) phase back-off strategy
230             yield_backoff   m_bkYield   ;   ///< Yield phase back-off strategy
231
232         public:
233             /// Initializes m_nExpMin and m_nExpMax from default s_nExpMin and s_nExpMax respectively
234             exponential()
235                 : m_nExpMin( s_nExpMin )
236                 , m_nExpMax( s_nExpMax )
237             {
238                 m_nExpCur = m_nExpMin;
239             }
240
241             /// Explicitly defined bounds of spinning
242             /**
243                 The \p libcds library never calls this ctor.
244             */
245             exponential(
246                 size_t nExpMin,     ///< Minimum spinning
247                 size_t nExpMax      ///< Maximum spinning
248                 )
249                 : m_nExpMin( nExpMin )
250                 , m_nExpMax( nExpMax )
251             {
252                 m_nExpCur = m_nExpMin;
253             }
254
255             //@cond
256             void operator ()()
257             {
258                 if ( m_nExpCur <= m_nExpMax ) {
259                     for ( size_t n = 0; n < m_nExpCur; ++n )
260                         m_bkSpin();
261                     m_nExpCur *= 2;
262                 }
263                 else
264                     m_bkYield();
265             }
266
267             template <typename Predicate>
268             bool operator()( Predicate pr )
269             {
270                 if ( m_nExpCur <= m_nExpMax ) {
271                     for ( size_t n = 0; n < m_nExpCur; ++n ) {
272                         if ( m_bkSpin(pr) )
273                             return true;
274                     }
275                     m_nExpCur *= 2;
276                 }
277                 else
278                     return m_bkYield(pr);
279                 return false;
280             }
281
282             void reset()
283             {
284                 m_nExpCur = m_nExpMin;
285                 m_bkSpin.reset();
286                 m_bkYield.reset();
287             }
288             //@endcond
289         };
290
291         //@cond
292         template <typename SpinBkoff, typename YieldBkoff, typename Tag>
293         size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMin = 16;
294
295         template <typename SpinBkoff, typename YieldBkoff, typename Tag>
296         size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMax = 16 * 1024;
297         //@endcond
298
299         /// Delay back-off strategy
300         /**
301             Template arguments:
302             - \p Duration - duration type, default is \p std::chrono::milliseconds
303             - \p Tag - a selector tag
304
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:
310             \code
311
312             #include <cds/backoff_strategy.h>
313             namespace bkoff = cds::backoff;
314
315             struct ms5  ;   // tag to select 5ms
316             struct ms10 ;   // tag to select 10ms
317
318             // // define your back-off specialization
319             typedef bkoff::delay<std::chrono::milliseconds, ms5> delay5;
320             typedef bkoff::delay<std::chrono::milliseconds, ms10> delay10;
321
322             // // set up the timeouts
323             delay5::s_nTimeout = 5;
324             delay10::s_nTimeout = 10;
325             \endcode
326
327             Another way of solving this problem is subclassing \p delay back-off class:
328             \code
329             #include <cds/backoff_strategy.h>
330             namespace bkoff = cds::backoff;
331             typedef bkoff::delay<> delay_bkoff;
332
333             class delay5: public delay_bkoff {
334             public:
335                 delay5(): delay_bkoff( 5 ) {}
336             };
337
338             class delay10: public delay_bkoff {
339             public:
340                 delay10(): delay_bkoff( 10 ) {}
341             };
342             \endcode
343
344         */
345         template <class Duration = cds_std::chrono::milliseconds, typename Tag=void >
346         class delay
347         {
348         public:
349             typedef Duration duration_type; ///< Duration type (default \p std::chrono::milliseconds)
350             static unsigned int s_nTimeout; ///< default timeout, =5
351
352         protected:
353             ///@cond
354             unsigned int const m_nTimeout;
355             ///@endcond
356
357         public:
358             /// Default ctor takes the timeout from s_nTimeout
359             delay()
360                 : m_nTimeout( s_nTimeout )
361             {}
362
363             /// Initializes timeout from \p nTimeout
364             CDS_CONSTEXPR delay( unsigned int nTimeout )
365                 : m_nTimeout( nTimeout )
366             {}
367
368             //@cond
369             void operator()() const
370             {
371                 cds_std::this_thread::sleep_for( duration_type( m_nTimeout ));
372             }
373
374             template <typename Predicate>
375             bool operator()( Predicate pr ) const
376             {
377                 for ( unsigned int i = 0; i < m_nTimeout; i += 2 ) {
378                     if ( pr() )
379                         return true;
380                     cds_std::this_thread::sleep_for( duration_type( 2 ));
381                 }
382                 return false;
383             }
384
385             void reset() const
386             {}
387             //@endcond
388         };
389
390         //@cond
391         template <class Duration, typename Tag>
392         unsigned int delay<Duration, Tag>::s_nTimeout = 5;
393         //@endcond
394
395
396         /// Delay back-off strategy, template version
397         /**
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>.
402         */
403         template <unsigned int Timeout, class Duration = cds_std::chrono::milliseconds >
404         class delay_of: public delay<Duration>
405         {
406         //@cond
407             typedef delay<Duration> base_class;
408         public:
409             delay_of()
410                 : base_class( Timeout )
411             {}
412         //@endcond
413         };
414
415
416         /// Default backoff strategy
417         typedef exponential<hint, yield>    Default;
418
419         /// Default back-off strategy for lock primitives
420         typedef exponential<hint, yield>    LockDefault;
421
422     } // namespace backoff
423 } // namespace cds
424
425
426 #endif // #ifndef __CDS_BACKOFF_STRATEGY_H