# HG changeset patch
# User Alexander Krotov <krotov@iitp.ru>
# Date 1473435103 -10800
#      Fri Sep 09 18:31:43 2016 +0300
# Node ID 4a582d516525862661b2a3a442f6758606e97e8d
# Parent  57c13c69110d0b914ba1b1e0cef3fc515fe82f98
core: Store events in a calendar scheduler bucket in reverse chronological order

This improvement was actually introduced in ns v2.33, but lost in ns-3:
http://www.isi.edu/nsnam/ns/doc/node35.html

When a new event is inserted into a bucket, which is implemented as a
sorted list, it is more likely that new event has timestamp greater than
timestamps of previously inserted events.

Therefore, it is better to sort list in *reverse* chronological order.

This change makes CalendarScheduler outperform MapScheduler in benchmark:
./waf --run 'bench-simulator --cal=true --map=false'

For this reason, note about CalendarScheduler being slow is removed.

diff -r 57c13c69110d -r 4a582d516525 src/core/model/calendar-scheduler.cc
--- a/src/core/model/calendar-scheduler.cc	Mon Sep 05 11:36:53 2016 -0700
+++ b/src/core/model/calendar-scheduler.cc	Fri Sep 09 18:31:43 2016 +0300
@@ -16,6 +16,7 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  *
  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ * Author: Alexander Krotov <krotov@iitp.ru>
  */
 
 #include "calendar-scheduler.h"
@@ -108,7 +109,7 @@
   Bucket::iterator end = m_buckets[bucket].end ();
   for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
     {
-      if (ev.key < i->key)
+      if (ev.key > i->key)
         {
           m_buckets[bucket].insert (i, ev);
           return;
@@ -147,7 +148,7 @@
     {
       if (!m_buckets[i].empty ())
         {
-          Scheduler::Event next = m_buckets[i].front ();
+          Scheduler::Event next = m_buckets[i].back ();
           if (next.key.m_ts < bucketTop)
             {
               return next;
@@ -183,13 +184,13 @@
     {
       if (!m_buckets[i].empty ())
         {
-          Scheduler::Event next = m_buckets[i].front ();
+          Scheduler::Event next = m_buckets[i].back ();
           if (next.key.m_ts < bucketTop)
             {
               m_lastBucket = i;
               m_lastPrio = next.key.m_ts;
               m_bucketTop = bucketTop;
-              m_buckets[i].pop_front ();
+              m_buckets[i].pop_back ();
               return next;
             }
           if (next.key < minKey)
@@ -207,8 +208,8 @@
   m_lastPrio = minKey.m_ts;
   m_lastBucket = Hash (minKey.m_ts);
   m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;
-  Scheduler::Event next = m_buckets[minBucket].front();
-  m_buckets[minBucket].pop_front ();
+  Scheduler::Event next = m_buckets[minBucket].back ();
+  m_buckets[minBucket].pop_back ();
 
   return next;
 }
diff -r 57c13c69110d -r 4a582d516525 src/core/model/calendar-scheduler.h
--- a/src/core/model/calendar-scheduler.h	Mon Sep 05 11:36:53 2016 -0700
+++ b/src/core/model/calendar-scheduler.h	Fri Sep 09 18:31:43 2016 +0300
@@ -16,6 +16,7 @@
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  *
  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ * Author: Alexander Krotov <krotov@iitp.ru>
  */
 
 #ifndef CALENDAR_SCHEDULER_H
@@ -47,11 +48,13 @@
  * the original algorithm (to the best of my knowledge).
  *
  * \note
- * This queue is much slower than I expected (much slower than the
- * std::map queue) and this seems to be because the original resizing policy
- * is horribly bad.  This is most likely the reason why there have been
- * so many variations published which all slightly tweak the resizing
- * heuristics to obtain a better distribution of events across buckets.
+ * While inserion sort is not discussed in the original article, its
+ * implementation appears to dramatically affect performance.
+ * CalendarScheduler sorts buckets in \em reverse chronological order.
+ * This heuristic, originating in NS-2 implementation of
+ * calendar scheduler, reduces enqueue time, as it is likely that
+ * timestamp of new event is greater than timestamp of already
+ * scheduled event.
  */
 class CalendarScheduler : public Scheduler
 {