eventq: new eventq data structure. The new data structure is singly

linked list sorted by time and priority.  For things of the same time
and priority, a second, circularly linked list maintains the data
structure.  Events of the same time and priority are now inserted in
FIFO order instead of LIFO order.  This dramatically improves the
performance of systems that schedule multiple events at the same time.

The FIFO order version is not preferred to LIFO (because it may cause
people to rely on it), but I'm going to commit it anyway and
immediately commit the preferred LIFO version on top.

1 files changed, 97 insertions, 35 deletions

diff --git a/src/sim/eventq.hh b/src/sim/eventq.hh
index ea950e625..10c0048a8 100644
--- a/src/sim/eventq.hh
+++ b/src/sim/eventq.hh
@@ -74,7 +74,20 @@ class Event : public Serializable, public FastAlloc
     friend class EventQueue;
 
   private:
-    Event *next;
+    // The event queue is now a linked list of linked lists.  The
+    // 'nextBin' pointer is to find the bin, where a bin is defined as
+    // when+priority.  All events in the same bin will be stored in a
+    // second circularly linked list maintained by the 'nextInBin'
+    // pointer.  The list will be accessed in FIFO order.  The end
+    // result is that the insert/removal in 'nextBin' is
+    // linear/constant, and the lookup/removal in 'nextInBin' is
+    // constant/constant.  Hopefully this is a significant improvement
+    // over the current fully linear insertion.
+    Event *nextBin;
+    Event *nextInBin;
+
+    friend void insertBefore(Event *event, Event *curr);
+    friend Event *removeItem(Event *event, Event *last);
 
     /// queue to which this event belongs (though it may or may not be
     /// scheduled on this queue yet)
@@ -99,6 +112,17 @@ class Event : public Serializable, public FastAlloc
     Tick whenCreated;   //!< time created
     Tick whenScheduled; //!< time scheduled
 #endif
+
+  protected:
+    void
+    setWhen(Tick when)
+    {
+        _when = when;
+#ifdef DEBUG_EVENTQ
+        whenScheduled = curTick;
+#endif
+    }
+
   protected:
     enum Flags {
         None = 0x0,
@@ -181,7 +205,7 @@ class Event : public Serializable, public FastAlloc
      * @param queue that the event gets scheduled on
      */
     Event(EventQueue *q, Priority p = Default_Pri)
-        : next(NULL), _queue(q), _priority(p), _flags(None)
+        : nextBin(NULL), nextInBin(NULL), _queue(q), _priority(p), _flags(None)
     {
 #ifndef NDEBUG
         instance = ++instanceCounter;
@@ -343,9 +367,9 @@ class EventQueue : public Serializable
     virtual const std::string name() const { return objName; }
 
     // schedule the given event on this queue
-    void schedule(Event *ev);
+    void schedule(Event *ev, Tick when);
     void deschedule(Event *ev);
-    void reschedule(Event *ev);
+    void reschedule(Event *ev, Tick when);
 
     Tick nextTick() const { return head->when(); }
     Event *serviceOne();
@@ -379,6 +403,8 @@ class EventQueue : public Serializable
 
     Tick nextEventTime() { return empty() ? curTick : head->when(); }
 
+    bool debugVerify() const;
+
     virtual void serialize(std::ostream &os);
     virtual void unserialize(Checkpoint *cp, const std::string &section);
 };
@@ -396,53 +422,77 @@ class EventQueue : public Serializable
 // schedule at specified time (place on event queue specified via
 // constructor)
 inline void
-Event::schedule(Tick t)
+Event::schedule(Tick when)
 {
-    assert(!scheduled());
-    assert(t >= curTick);
-
-    setFlags(Scheduled);
-#ifdef DEBUG_EVENTQ
-    whenScheduled = curTick;
-#endif
-    _when = t;
-    _queue->schedule(this);
+    _queue->schedule(this, when);
 }
 
 inline void
 Event::deschedule()
 {
-    assert(scheduled());
-
-    clearFlags(Squashed);
-    clearFlags(Scheduled);
     _queue->deschedule(this);
 }
 
 inline void
-Event::reschedule(Tick t, bool always)
+Event::reschedule(Tick when, bool always)
 {
-    assert(scheduled() || always);
-    assert(t >= curTick);
-
-#ifdef DEBUG_EVENTQ
-    whenScheduled = curTick;
-#endif
-    _when = t;
-
     if (scheduled()) {
-        clearFlags(Squashed);
-        _queue->reschedule(this);
+        _queue->reschedule(this, when);
     } else {
-        setFlags(Scheduled);
-        _queue->schedule(this);
+        assert(always);
+        _queue->schedule(this, when);
     }
 }
 
+inline bool
+operator<(const Event &l, const Event &r)
+{
+    return l.when() < r.when() ||
+        (l.when() == r.when() && l.priority() < r.priority());
+}
+
+inline bool
+operator>(const Event &l, const Event &r)
+{
+    return l.when() > r.when() ||
+        (l.when() == r.when() && l.priority() > r.priority());
+}
+
+inline bool
+operator<=(const Event &l, const Event &r)
+{
+    return l.when() < r.when() ||
+        (l.when() == r.when() && l.priority() <= r.priority());
+}
+inline bool
+operator>=(const Event &l, const Event &r)
+{
+    return l.when() > r.when() ||
+        (l.when() == r.when() && l.priority() >= r.priority());
+}
+
+inline bool
+operator==(const Event &l, const Event &r)
+{
+    return l.when() == r.when() && l.priority() == r.priority();
+}
+
+inline bool
+operator!=(const Event &l, const Event &r)
+{
+    return l.when() != r.when() || l.priority() != r.priority();
+}
+
 inline void
-EventQueue::schedule(Event *event)
+EventQueue::schedule(Event *event, Tick when)
 {
+    assert(when >= curTick);
+    assert(!event->scheduled());
+
+    event->setWhen(when);
     insert(event);
+    event->setFlags(Event::Scheduled);
+
     if (DTRACE(Event))
         event->trace("scheduled");
 }
@@ -450,19 +500,31 @@ EventQueue::schedule(Event *event)
 inline void
 EventQueue::deschedule(Event *event)
 {
+    assert(event->scheduled());
+
     remove(event);
-    if (DTRACE(Event))
-        event->trace("descheduled");
+
+    event->clearFlags(Event::Squashed);
+    event->clearFlags(Event::Scheduled);
 
     if (event->getFlags(Event::AutoDelete))
         delete event;
+
+    if (DTRACE(Event))
+        event->trace("descheduled");
 }
 
 inline void
-EventQueue::reschedule(Event *event)
+EventQueue::reschedule(Event *event, Tick when)
 {
+    assert(when >= curTick);
+    assert(event->scheduled());
+
     remove(event);
+    event->setWhen(when);
     insert(event);
+    event->clearFlags(Event::Squashed);
+
     if (DTRACE(Event))
         event->trace("rescheduled");
 }