X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=folly%2Fio%2Fasync%2FHHWheelTimer.h;h=4c33239db012f0532d9d78affd88ec2b627e6249;hb=1bc610c2c678569cee1339db20fa97fc35ad6f92;hp=4d255b6472b68b214722c7a7a2504d0fc2bbcf5f;hpb=27945a697803eab3c471aa22780c8b32ced45fdf;p=folly.git

diff --git a/folly/io/async/HHWheelTimer.h b/folly/io/async/HHWheelTimer.h
index 4d255b64..4c33239d 100644
--- a/folly/io/async/HHWheelTimer.h
+++ b/folly/io/async/HHWheelTimer.h
@@ -33,14 +33,6 @@ namespace folly {
 /**
  * Hashed Hierarchical Wheel Timer
  *
- * Comparison:
- * AsyncTimeout - a single timeout.
- * HHWheelTimer - a set of efficient timeouts with different interval,
- *    but timeouts are not exact.
- *
- * All of the above are O(1) in insertion, tick update and cancel
-
- * This implementation ticks once every 10ms.
  * We model timers as the number of ticks until the next
  * due event.  We allow 32-bits of space to track this
  * due interval, and break that into 4 regions of 8 bits.
@@ -53,8 +45,11 @@ namespace folly {
  * into a different bucket.
  *
  * This technique results in a very cheap mechanism for
- * maintaining time and timers, provided that we can maintain
- * a consistent rate of ticks.
+ * maintaining time and timers.
+ *
+ * Unlike the original timer wheel paper, this implementation does
+ * *not* tick constantly, and instead calculates the exact next wakeup
+ * time.
  */
 class HHWheelTimer : private folly::AsyncTimeout,
                      public folly::DelayedDestruction {
@@ -71,7 +66,9 @@ class HHWheelTimer : private folly::AsyncTimeout,
   /**
    * A callback to be notified when a timeout has expired.
    */
-  class Callback {
+  class Callback
+      : public boost::intrusive::list_base_hook<
+            boost::intrusive::link_mode<boost::intrusive::auto_unlink>> {
    public:
     Callback()
       : wheel_(nullptr)
@@ -137,15 +134,10 @@ class HHWheelTimer : private folly::AsyncTimeout,
 
     HHWheelTimer* wheel_;
     std::chrono::milliseconds expiration_;
-
-    typedef boost::intrusive::list_member_hook<
-      boost::intrusive::link_mode<boost::intrusive::auto_unlink> > ListHook;
-
-    ListHook hook_;
+    int bucket_{-1};
 
     typedef boost::intrusive::list<
       Callback,
-      boost::intrusive::member_hook<Callback, ListHook, &Callback::hook_>,
       boost::intrusive::constant_time_size<false> > List;
 
     std::shared_ptr<RequestContext> context_;
@@ -250,20 +242,6 @@ class HHWheelTimer : private folly::AsyncTimeout,
     return count_;
   }
 
-  /**
-   * This turns on more exact timing.  By default the wheel timer
-   * increments its cached time only once everyN (default) ticks.
-   *
-   * With catchupEveryN at 1, timeouts will only be delayed until the
-   * next tick, at which point all overdue timeouts are called.  The
-   * wheel timer is approximately 2x slower with this set to 1.
-   *
-   * Load testing in opt mode showed skew was about 1% with no catchup.
-   */
-  void setCatchupEveryN(uint32_t everyN) {
-    catchupEveryN_ = everyN;
-  }
-
   bool isDetachable() const {
     return !folly::AsyncTimeout::isScheduled();
   }
@@ -300,21 +278,29 @@ class HHWheelTimer : private folly::AsyncTimeout,
 
   typedef Callback::List CallbackList;
   CallbackList buckets_[WHEEL_BUCKETS][WHEEL_SIZE];
+  std::vector<uint64_t> bitmap_;
 
   int64_t timeToWheelTicks(std::chrono::milliseconds t) {
     return t.count() / interval_.count();
   }
 
   bool cascadeTimers(int bucket, int tick);
-  int64_t nextTick_;
+  int64_t lastTick_;
+  int64_t expireTick_;
   uint64_t count_;
-  std::chrono::milliseconds now_;
+  std::chrono::milliseconds startTime_;
+
+  int64_t calcNextTick();
 
-  static constexpr uint32_t DEFAULT_CATCHUP_EVERY_N = 10;
+  void scheduleNextTimeout();
 
-  uint32_t catchupEveryN_;
-  uint32_t expirationsSinceCatchup_;
   bool* processingCallbacksGuard_;
+  CallbackList timeouts; // Timeouts queued to run
+
+  std::chrono::milliseconds getCurTime() {
+    return std::chrono::duration_cast<std::chrono::milliseconds>(
+        std::chrono::steady_clock::now().time_since_epoch());
+  }
 };
 
 } // folly