cds/algo/backoff_strategy.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_BACKOFF_STRATEGY_H
  32 #define CDSLIB_BACKOFF_STRATEGY_H
  33
  34 /*
  35     Filename: backoff_strategy.h
  36     Created 2007.03.01 by Maxim Khiszinsky
  37
  38     Description:
  39          Generic back-off strategies
  40
  41     Editions:
  42     2007.03.01  Maxim Khiszinsky    Created
  43     2008.10.02  Maxim Khiszinsky    Backoff action transfers from contructor to operator() for all backoff schemas
  44     2009.09.10  Maxim Khiszinsky    reset() function added
  45 */
  46
  47 #include <utility>      // declval
  48 #include <thread>
  49 #include <chrono>
  50 #include <cds/compiler/backoff.h>
  51
  52 namespace cds {
  53     /// Different backoff schemes
  54     /**
  55         Back-off schema may be used in lock-free algorithms when the algorithm cannot perform some action because a conflict
  56         with the other concurrent operation is encountered. In this case current thread can do another work or can call
  57         processor's performance hint.
  58
  59         The interface of back-off strategy is following:
  60         \code
  61             struct backoff_strategy {
  62                 void operator()();
  63                 template <typename Predicate> bool operator()( Predicate pr );
  64                 void reset();
  65             };
  66         \endcode
  67
  68         \p operator() operator calls back-off strategy's action. It is main part of back-off strategy.
  69
  70         Interruptible back-off <tt>template < typename Predicate > bool operator()( Predicate pr )</tt>
  71         allows to interrupt back-off spinning if \p pr predicate returns \p true.
  72         \p Predicate is a functor with the following interface:
  73         \code
  74         struct predicate {
  75             bool operator()();
  76         };
  77         \endcode
  78
  79         \p reset() function resets internal state of back-off strategy to initial state. It is required for some
  80         back-off strategies, for example, exponential back-off.
  81     */
  82     namespace backoff {
  83
  84         /// Empty backoff strategy. Do nothing
  85         struct empty {
  86             //@cond
  87             void operator ()() const CDS_NOEXCEPT
  88             {}
  89
  90             template <typename Predicate>
  91             bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
  92             {
  93                 return pr();
  94             }
  95
  96             static void reset() CDS_NOEXCEPT
  97             {}
  98             //@endcond
  99         };
 100
 101         /// Switch to another thread (yield). Good for thread preemption architecture.
 102         struct yield {
 103             //@cond
 104             void operator ()() const CDS_NOEXCEPT
 105             {
 106                 std::this_thread::yield();
 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         /// Random pause
 124         /**
 125             This back-off strategy calls processor-specific pause hint instruction
 126             if one is available for the processor architecture.
 127         */
 128         struct pause {
 129             //@cond
 130             void operator ()() const CDS_NOEXCEPT
 131             {
 132 #            ifdef CDS_backoff_pause_defined
 133                 platform::backoff_pause();
 134 #            endif
 135             }
 136
 137             template <typename Predicate>
 138             bool operator()(Predicate pr) const CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()() ))
 139             {
 140                 if ( pr() )
 141                     return true;
 142                 operator()();
 143                 return false;
 144             }
 145
 146             static void reset() CDS_NOEXCEPT
 147             {}
 148             //@endcond
 149         };
 150
 151         /// Processor hint back-off
 152         /**
 153             This back-off schema calls performance hint instruction if it is available for current processor.
 154             Otherwise, it calls \p nop.
 155         */
 156         struct hint
 157         {
 158         //@cond
 159             void operator ()() const CDS_NOEXCEPT
 160             {
 161 #           if defined(CDS_backoff_hint_defined)
 162                 platform::backoff_hint();
 163 #           elif defined(CDS_backoff_nop_defined)
 164                 platform::backoff_nop();
 165 #           endif
 166             }
 167
 168             template <typename Predicate>
 169             bool operator()(Predicate pr) const CDS_NOEXCEPT_(noexcept(std::declval<Predicate>()() ))
 170             {
 171                 if ( pr() )
 172                     return true;
 173                 operator()();
 174                 return false;
 175             }
 176
 177             static void reset() CDS_NOEXCEPT
 178             {}
 179         //@endcond
 180         };
 181
 182         /// Exponential back-off
 183         /**
 184             This back-off strategy is composite. It consists of \p SpinBkoff and \p YieldBkoff
 185             back-off strategy. In first, the strategy tries to apply repeatedly \p SpinBkoff
 186             (spinning phase) until internal counter of failed attempts reaches its maximum
 187             spinning value. Then, the strategy transits to high-contention phase
 188             where it applies \p YieldBkoff until \p reset() is called.
 189             On each spinning iteration the internal spinning counter is doubled.
 190
 191             Choosing the best value for maximum spinning bound is platform and task specific.
 192             In this implementation, the default values for maximum and minimum spinning is statically
 193             declared so you can set its value globally for your platform.
 194             The third template argument, \p Tag, is used to separate implementation. For
 195             example, you may define two \p exponential back-offs that is the best for your task A and B:
 196             \code
 197
 198             #include <cds/algo/backoff_strategy.h>
 199             namespace bkoff = cds::backoff;
 200
 201             struct tagA ;   // tag to select task A implementation
 202             struct tagB ;   // tag to select task B implementation
 203
 204             // // define your back-off specialization
 205             typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagA> expBackOffA;
 206             typedef bkoff::exponential<bkoff::hint, bkoff::yield, tagB> expBackOffB;
 207
 208             // // set up the best bounds for task A
 209             expBackOffA::s_nExpMin = 32;
 210             expBackOffA::s_nExpMax = 1024;
 211
 212             // // set up the best bounds for task B
 213             expBackOffB::s_nExpMin = 2;
 214             expBackOffB::s_nExpMax = 512;
 215
 216             \endcode
 217
 218             Another way of solving this problem is subclassing \p exponential back-off class:
 219             \code
 220             #include <cds/algo/backoff_strategy.h>
 221             namespace bkoff = cds::backoff;
 222             typedef bkoff::exponential<bkoff::hint, bkoff::yield>   base_bkoff;
 223
 224             class expBackOffA: public base_bkoff
 225             {
 226             public:
 227                 expBackOffA()
 228                     : base_bkoff( 32, 1024 )
 229                     {}
 230             };
 231
 232             class expBackOffB: public base_bkoff
 233             {
 234             public:
 235                 expBackOffB()
 236                     : base_bkoff( 2, 512 )
 237                     {}
 238             };
 239             \endcode
 240         */
 241         template <typename SpinBkoff, typename YieldBkoff, typename Tag=void>
 242         class exponential
 243         {
 244         public:
 245             typedef SpinBkoff  spin_backoff    ;   ///< spin back-off strategy
 246             typedef YieldBkoff yield_backoff   ;   ///< yield back-off strategy
 247             typedef Tag        impl_tag        ;   ///< implementation separation tag
 248
 249             static size_t s_nExpMin ;   ///< Default minimum spinning bound (16)
 250             static size_t s_nExpMax ;   ///< Default maximum spinning bound (16384)
 251
 252         protected:
 253             size_t  m_nExpCur   ;   ///< Current spinning
 254             size_t  m_nExpMin   ;   ///< Minimum spinning bound
 255             size_t  m_nExpMax   ;   ///< Maximum spinning bound
 256
 257             spin_backoff    m_bkSpin    ;   ///< Spinning (fast-path) phase back-off strategy
 258             yield_backoff   m_bkYield   ;   ///< Yield phase back-off strategy
 259
 260         public:
 261             /// Initializes m_nExpMin and m_nExpMax from default s_nExpMin and s_nExpMax respectively
 262             exponential() CDS_NOEXCEPT
 263                 : m_nExpMin( s_nExpMin )
 264                 , m_nExpMax( s_nExpMax )
 265             {
 266                 m_nExpCur = m_nExpMin;
 267             }
 268
 269             /// Explicitly defined bounds of spinning
 270             /**
 271                 The \p libcds library never calls this ctor.
 272             */
 273             exponential(
 274                 size_t nExpMin,     ///< Minimum spinning
 275                 size_t nExpMax      ///< Maximum spinning
 276                 ) CDS_NOEXCEPT
 277                 : m_nExpMin( nExpMin )
 278                 , m_nExpMax( nExpMax )
 279             {
 280                 m_nExpCur = m_nExpMin;
 281             }
 282
 283             //@cond
 284             void operator ()() CDS_NOEXCEPT_(noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
 285             {
 286                 if ( m_nExpCur <= m_nExpMax ) {
 287                     for ( size_t n = 0; n < m_nExpCur; ++n )
 288                         m_bkSpin();
 289                     m_nExpCur *= 2;
 290                 }
 291                 else
 292                     m_bkYield();
 293             }
 294
 295             template <typename Predicate>
 296             bool operator()( Predicate pr ) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()) && noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()() ))
 297             {
 298                 if ( m_nExpCur <= m_nExpMax ) {
 299                     for ( size_t n = 0; n < m_nExpCur; ++n ) {
 300                         if ( m_bkSpin(pr) )
 301                             return true;
 302                     }
 303                     m_nExpCur *= 2;
 304                 }
 305                 else
 306                     return m_bkYield(pr);
 307                 return false;
 308             }
 309
 310             void reset() CDS_NOEXCEPT_( noexcept( std::declval<spin_backoff>().reset() ) && noexcept( std::declval<yield_backoff>().reset() ))
 311             {
 312                 m_nExpCur = m_nExpMin;
 313                 m_bkSpin.reset();
 314                 m_bkYield.reset();
 315             }
 316             //@endcond
 317         };
 318
 319         //@cond
 320         template <typename SpinBkoff, typename YieldBkoff, typename Tag>
 321         size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMin = 16;
 322
 323         template <typename SpinBkoff, typename YieldBkoff, typename Tag>
 324         size_t exponential<SpinBkoff, YieldBkoff, Tag>::s_nExpMax = 16 * 1024;
 325         //@endcond
 326
 327         /// Delay back-off strategy
 328         /**
 329             Template arguments:
 330             - \p Duration - duration type, default is \p std::chrono::milliseconds
 331             - \p Tag - a selector tag
 332
 333             Choosing the best value for th timeout is platform and task specific.
 334             In this implementation, the default values for timeout is statically
 335             declared so you can set its value globally for your platform.
 336             The second template argument, \p Tag, is used to separate implementation. For
 337             example, you may define two \p delay back-offs for 5 and 10 ms timeout:
 338             \code
 339
 340             #include <cds/algo/backoff_strategy.h>
 341             namespace bkoff = cds::backoff;
 342
 343             struct ms5  ;   // tag to select 5ms
 344             struct ms10 ;   // tag to select 10ms
 345
 346             // // define your back-off specialization
 347             typedef bkoff::delay<std::chrono::milliseconds, ms5> delay5;
 348             typedef bkoff::delay<std::chrono::milliseconds, ms10> delay10;
 349
 350             // // set up the timeouts
 351             delay5::s_nTimeout = 5;
 352             delay10::s_nTimeout = 10;
 353             \endcode
 354
 355             Another way of solving this problem is subclassing \p delay back-off class:
 356             \code
 357             #include <cds/algo/backoff_strategy.h>
 358             namespace bkoff = cds::backoff;
 359             typedef bkoff::delay<> delay_bkoff;
 360
 361             class delay5: public delay_bkoff {
 362             public:
 363                 delay5(): delay_bkoff( 5 ) {}
 364             };
 365
 366             class delay10: public delay_bkoff {
 367             public:
 368                 delay10(): delay_bkoff( 10 ) {}
 369             };
 370             \endcode
 371
 372         */
 373         template <class Duration = std::chrono::milliseconds, typename Tag=void >
 374         class delay
 375         {
 376         public:
 377             typedef Duration duration_type; ///< Duration type (default \p std::chrono::milliseconds)
 378             static unsigned int s_nTimeout; ///< default timeout, =5
 379
 380         protected:
 381             ///@cond
 382             unsigned int const m_nTimeout;
 383             ///@endcond
 384
 385         public:
 386             /// Default ctor takes the timeout from s_nTimeout
 387             delay() CDS_NOEXCEPT
 388                 : m_nTimeout( s_nTimeout )
 389             {}
 390
 391             /// Initializes timeout from \p nTimeout
 392             CDS_CONSTEXPR explicit delay( unsigned int nTimeout ) CDS_NOEXCEPT
 393                 : m_nTimeout( nTimeout )
 394             {}
 395
 396             //@cond
 397             void operator()() const
 398             {
 399                 std::this_thread::sleep_for( duration_type( m_nTimeout ));
 400             }
 401
 402             template <typename Predicate>
 403             bool operator()(Predicate pr) const
 404             {
 405                 for ( unsigned int i = 0; i < m_nTimeout; i += 2 ) {
 406                     if ( pr() )
 407                         return true;
 408                     std::this_thread::sleep_for( duration_type( 2 ));
 409                 }
 410                 return false;
 411             }
 412
 413             static void reset() CDS_NOEXCEPT
 414             {}
 415             //@endcond
 416         };
 417
 418         //@cond
 419         template <class Duration, typename Tag>
 420         unsigned int delay<Duration, Tag>::s_nTimeout = 5;
 421         //@endcond
 422
 423
 424         /// Delay back-off strategy, template version
 425         /**
 426             This is a template version of backoff::delay class.
 427             Template parameter \p Timeout sets a delay timeout.
 428             The declaration <tt>cds::backoff::delay_of< 5 > bkoff</tt> is equal for
 429             <tt>cds::backoff::delay<> bkoff(5)</tt>.
 430         */
 431         template <unsigned int Timeout, class Duration = std::chrono::milliseconds >
 432         class delay_of: public delay<Duration>
 433         {
 434         //@cond
 435             typedef delay<Duration> base_class;
 436         public:
 437             delay_of() CDS_NOEXCEPT
 438                 : base_class( Timeout )
 439             {}
 440         //@endcond
 441         };
 442
 443
 444         /// Default backoff strategy
 445         typedef exponential<hint, yield>    Default;
 446
 447         /// Default back-off strategy for lock primitives
 448         typedef exponential<hint, yield>    LockDefault;
 449
 450     } // namespace backoff
 451 } // namespace cds
 452
 453
 454 #endif // #ifndef CDSLIB_BACKOFF_STRATEGY_H