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-2017
   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_hint_defined
 133                 platform::backoff_hint();
 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         /// \p backoff::exponential const traits
 183         struct exponential_const_traits
 184         {
 185             typedef hint    fast_path_backoff;  ///< Fast-path back-off strategy
 186             typedef yield   slow_path_backoff;  ///< Slow-path back-off strategy
 187
 188             enum: size_t {
 189                 lower_bound = 16,         ///< Minimum spinning limit
 190                 upper_bound = 16 * 1024   ///< Maximum spinning limit
 191             };
 192         };
 193
 194         /// \p nackoff::exponential runtime traits
 195         struct exponential_runtime_traits
 196         {
 197             typedef hint    fast_path_backoff;  ///< Fast-path back-off strategy
 198             typedef yield   slow_path_backoff;  ///< Slow-path back-off strategy
 199
 200             static size_t lower_bound;    ///< Minimum spinning limit, default is 16
 201             static size_t upper_bound;    ///< Maximum spinning limit, default is 16*1024
 202         };
 203
 204         /// Exponential back-off
 205         /**
 206             This back-off strategy is composite. It consists of \p SpinBkoff and \p YieldBkoff
 207             back-off strategy. In first, the strategy tries to apply repeatedly \p SpinBkoff
 208             (spinning phase) until internal counter of failed attempts reaches its maximum
 209             spinning value. Then, the strategy transits to high-contention phase
 210             where it applies \p YieldBkoff until \p reset() is called.
 211             On each spinning iteration the internal spinning counter is doubled.
 212
 213             Selecting the best value for maximum spinning limit is platform and application specific task.
 214             The limits are described by \p Traits template parameter.
 215             There are two types of \p Traits:
 216             - constant traits \p exponential_const_traits - specifies the lower and upper limits
 217               as a compile-time constants; to change the limits you should recompile your application
 218             - runtime traits \p exponential_runtime_traits - specifies the limits as \p s_nExpMin
 219               and \p s_nExpMax variables which can be changed at runtime to tune back-off strategy.
 220
 221             The traits class must declare two data member:
 222             - \p lower_bound - the lower bound of spinning loop
 223             - \p upper_bound - the upper boudn of spinning loop
 224
 225             You may use \p Traits template parameter to separate back-off implementations.
 226             For example, you may define two \p exponential back-offs that is the best for your task A and B:
 227             \code
 228
 229             #include <cds/algo/backoff_strategy.h>
 230             namespace bkoff = cds::backoff;
 231
 232             // the best bounds for task A
 233             struct traits_A: public bkoff::exponential_const_traits
 234             {
 235                 static size_t lower_bound;
 236                 static size_t upper_bound;
 237             };
 238             size_t traits_A::lower_bound = 1024;
 239             size_t traits_A::upper_bound = 8 * 1024;
 240
 241             // the best bounds for task B
 242             struct traits_B: public bkoff::exponential_const_traits
 243             {
 244                 static size_t lower_bound;
 245                 static size_t upper_bound;
 246             };
 247             size_t traits_A::lower_bound = 16;
 248             size_t traits_A::upper_bound = 1024;
 249
 250             // // define your back-off specialization
 251             typedef bkoff::exponential<traits_A> expBackOffA;
 252             typedef bkoff::exponential<traits_B> expBackOffB;
 253             \endcode
 254         */
 255         template <typename Traits = exponential_const_traits >
 256         class exponential
 257         {
 258         public:
 259             typedef Traits     traits;   ///< Traits
 260
 261             typedef typename traits::fast_path_backoff  spin_backoff    ;   ///< spin (fast-path) back-off strategy
 262             typedef typename traits::slow_path_backoff  yield_backoff   ;   ///< yield (slow-path) back-off strategy
 263
 264         protected:
 265             size_t  m_nExpCur   ;           ///< Current spin counter in range [traits::s_nExpMin, traits::s_nExpMax]
 266
 267             spin_backoff    m_bkSpin    ;   ///< Spinning (fast-path) phase back-off strategy
 268             yield_backoff   m_bkYield   ;   ///< Yield phase back-off strategy
 269
 270         public:
 271             /// Default ctor
 272             exponential() CDS_NOEXCEPT
 273                 : m_nExpCur( traits::lower_bound )
 274             {}
 275
 276             //@cond
 277             void operator ()() CDS_NOEXCEPT_(noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
 278             {
 279                 if ( m_nExpCur <= traits::upper_bound ) {
 280                     for ( size_t n = 0; n < m_nExpCur; ++n )
 281                         m_bkSpin();
 282                     m_nExpCur *= 2;
 283                 }
 284                 else
 285                     m_bkYield();
 286             }
 287
 288             template <typename Predicate>
 289             bool operator()( Predicate pr ) CDS_NOEXCEPT_( noexcept(std::declval<Predicate>()()) && noexcept(std::declval<spin_backoff>()()) && noexcept(std::declval<yield_backoff>()()))
 290             {
 291                 if ( m_nExpCur <= traits::upper_bound ) {
 292                     for ( size_t n = 0; n < m_nExpCur; ++n ) {
 293                         if ( m_bkSpin(pr))
 294                             return true;
 295                     }
 296                     m_nExpCur *= 2;
 297                 }
 298                 else
 299                     return m_bkYield(pr);
 300                 return false;
 301             }
 302
 303             void reset() CDS_NOEXCEPT_( noexcept( std::declval<spin_backoff>().reset()) && noexcept( std::declval<yield_backoff>().reset()))
 304             {
 305                 m_nExpCur = traits::lower_bound;
 306                 m_bkSpin.reset();
 307                 m_bkYield.reset();
 308             }
 309             //@endcond
 310         };
 311
 312         //@cond
 313         template <typename FastPathBkOff, typename SlowPathBkOff>
 314         struct make_exponential
 315         {
 316             struct traits: public exponential_const_traits
 317             {
 318                 typedef FastPathBkOff   fast_path_backoff;
 319                 typedef SlowPathBkOff   slow_path_backoff;
 320             };
 321
 322             typedef exponential<traits> type;
 323         };
 324
 325         template <typename FastPathBkOff, typename SlowPathBkOff>
 326         using make_exponential_t = typename make_exponential<FastPathBkOff, SlowPathBkOff>::type;
 327         //@endcond
 328
 329         /// Constant traits for \ref delay back-off strategy
 330         struct delay_const_traits
 331         {
 332             typedef std::chrono::milliseconds duration_type;    ///< Timeout type
 333             enum: unsigned {
 334                 timeout = 5                                     ///< Delay timeout
 335             };
 336         };
 337
 338         /// Runtime traits for \ref delay back-off strategy
 339         struct delay_runtime_traits
 340         {
 341             typedef std::chrono::milliseconds duration_type;    ///< Timeout type
 342             static unsigned timeout;                            ///< Delay timeout, default 5
 343         };
 344
 345         /// Delay back-off strategy
 346         /**
 347             Template arguments:
 348             - \p Duration - duration type, default is \p std::chrono::milliseconds
 349             - \p Traits - a class that defines default timeout.
 350
 351             Choosing the best value for th timeout is platform and application specific task.
 352             The default values for timeout is provided by \p Traits class that should
 353             \p timeout data member. There are two predefined \p Traits implementation:
 354             - \p delay_const_traits - defines \p timeout as a constant (enum).
 355               To change timeout you should recompile your application.
 356             - \p delay_runtime_traits - specifies timeout as static data member that can be changed
 357               at runtime to tune the back-off strategy.
 358
 359             You may use \p Traits template parameter to separate back-off implementations.
 360             For example, you may define two \p delay back-offs for 5 and 10 ms timeout:
 361             \code
 362
 363             #include <cds/algo/backoff_strategy.h>
 364             namespace bkoff = cds::backoff;
 365
 366             // 5ms delay
 367             struct ms5
 368             {
 369                 typedef std::chrono::milliseconds duration_type;
 370                 enum: unsigned { timeout = 5 };
 371             };
 372
 373             // 10ms delay, runtime support
 374             struct ms10
 375             {
 376                 typedef std::chrono::milliseconds duration_type;
 377                 static unsigned timeout;
 378             };
 379             unsigned ms10::timeout = 10;
 380
 381             // define your back-off specialization
 382             typedef bkoff::delay<std::chrono::milliseconds, ms5>  delay5;
 383             typedef bkoff::delay<std::chrono::milliseconds, ms10> delay10;
 384
 385             \endcode
 386         */
 387         template <typename Traits = delay_const_traits>
 388         class delay
 389         {
 390         public:
 391             typedef Traits   traits;        ///< Traits
 392             typedef typename Traits::duration_type duration_type; ///< Duration type (default \p std::chrono::milliseconds)
 393
 394         protected:
 395             ///@cond
 396             duration_type const timeout;
 397             ///@endcond
 398
 399         public:
 400             /// Default ctor takes the timeout from \p traits::timeout
 401             delay() CDS_NOEXCEPT
 402                 : timeout( traits::timeout )
 403             {}
 404
 405             /// Initializes timeout from \p nTimeout
 406             CDS_CONSTEXPR explicit delay( unsigned int nTimeout ) CDS_NOEXCEPT
 407                 : timeout( nTimeout )
 408             {}
 409
 410             //@cond
 411             void operator()() const
 412             {
 413                 std::this_thread::sleep_for( timeout );
 414             }
 415
 416             template <typename Predicate>
 417             bool operator()(Predicate pr) const
 418             {
 419                 for ( unsigned int i = 0; i < traits::timeout; i += 2 ) {
 420                     if ( pr())
 421                         return true;
 422                     std::this_thread::sleep_for( duration_type( 2 ));
 423                 }
 424                 return false;
 425             }
 426
 427             static void reset() CDS_NOEXCEPT
 428             {}
 429             //@endcond
 430         };
 431
 432         //@cond
 433         template <unsigned int Timeout, class Duration = std::chrono::milliseconds >
 434         struct make_delay_of
 435         {
 436             struct traits {
 437                 typedef Duration duration_type;
 438                 enum: unsigned { timeout = Timeout };
 439             };
 440
 441             typedef delay<traits> type;
 442         };
 443         //@endcond
 444
 445         /// Delay back-off strategy, template version
 446         /**
 447             This is a simplified version of \p backoff::delay class.
 448             Template parameter \p Timeout sets a delay timeout of \p Duration unit.
 449         */
 450         template <unsigned int Timeout, class Duration = std::chrono::milliseconds >
 451         using delay_of = typename make_delay_of< Timeout, Duration >::type;
 452
 453
 454         /// Default backoff strategy
 455         typedef exponential<exponential_const_traits>    Default;
 456
 457         /// Default back-off strategy for lock primitives
 458         typedef exponential<exponential_const_traits>    LockDefault;
 459
 460     } // namespace backoff
 461 } // namespace cds
 462
 463
 464 #endif // #ifndef CDSLIB_BACKOFF_STRATEGY_H