cds/algo/backoff_strategy.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_BACKOFF_STRATEGY_H
   4 #define CDSLIB_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 <utility>      // declval
  20 #include <thread>
  21 #include <chrono>
  22 #include <cds/compiler/backoff.h>
  23
  24 namespace cds {
  25     /// Different backoff schemes
  26     /**
  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.
  30
  31         The interface of back-off strategy is following:
  32         \code
  33             struct backoff_strategy {
  34                 void operator()();
  35                 template <typename Predicate> bool operator()( Predicate pr );
  36                 void reset();
  37             };
  38         \endcode
  39
  40         \p operator() operator calls back-off strategy's action. It is main part of back-off strategy.
  41
  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:
  45         \code
  46         struct predicate {
  47             bool operator()();
  48         };
  49         \endcode
  50
  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.
  53     */
  54     namespace backoff {
  55
  56         /// Empty backoff strategy. Do nothing
  57         struct empty {
  58             //@cond
  59             void operator ()() const CDS_NOEXCEPT
  60             {}
  61
  62             template <typename Predicate>
  63             bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
  64             {
  65                 return pr();
  66             }
  67
  68             static void reset() CDS_NOEXCEPT
  69             {}
  70             //@endcond
  71         };
  72
  73         /// Switch to another thread (yield). Good for thread preemption architecture.
  74         struct yield {
  75             //@cond
  76             void operator ()() const CDS_NOEXCEPT
  77             {
  78                 std::this_thread::yield();
  79             }
  80
  81             template <typename Predicate>
  82             bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
  83             {
  84                 if ( pr() )
  85                     return true;
  86                 operator()();
  87                 return false;
  88             }
  89
  90             static void reset() CDS_NOEXCEPT
  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 ()() const CDS_NOEXCEPT
 103             {
 104 #            ifdef CDS_backoff_pause_defined
 105                 platform::backoff_pause();
 106 #            endif
 107             }
 108
 109             template <typename Predicate>
 110             bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
 111             {
 112                 if ( pr() )
 113                     return true;
 114                 operator()();
 115                 return false;
 116             }
 117
 118             static void reset() CDS_NOEXCEPT
 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 ()() const CDS_NOEXCEPT
 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) const CDS_NOEXCEPT_(noexcept(std::declval<Predicate>()() ))
 142             {
 143                 if ( pr() )
 144                     return true;
 145                 operator()();
 146                 return false;
 147             }
 148
 149             static void reset() CDS_NOEXCEPT
 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/algo/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/algo/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() CDS_NOEXCEPT
 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                 ) CDS_NOEXCEPT
 249                 : m_nExpMin( nExpMin )
 250                 , m_nExpMax( nExpMax )
 251             {
 252                 m_nExpCur = m_nExpMin;
 253             }
 254
 255             //@cond
 256             void operator ()() CDS_NOEXCEPT_(noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
 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 ) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()) && noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()() ))
 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() CDS_NOEXCEPT_( noexcept( std::declval<spin_backoff>().reset() ) && noexcept( std::declval<yield_backoff>().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/algo/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/algo/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 = 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() CDS_NOEXCEPT
 360                 : m_nTimeout( s_nTimeout )
 361             {}
 362
 363             /// Initializes timeout from \p nTimeout
 364             CDS_CONSTEXPR explicit delay( unsigned int nTimeout ) CDS_NOEXCEPT
 365                 : m_nTimeout( nTimeout )
 366             {}
 367
 368             //@cond
 369             void operator()() const
 370             {
 371                 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                     std::this_thread::sleep_for( duration_type( 2 ));
 381                 }
 382                 return false;
 383             }
 384
 385             static void reset() CDS_NOEXCEPT
 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 = std::chrono::milliseconds >
 404         class delay_of: public delay<Duration>
 405         {
 406         //@cond
 407             typedef delay<Duration> base_class;
 408         public:
 409             delay_of() CDS_NOEXCEPT
 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 CDSLIB_BACKOFF_STRATEGY_H