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