[Ns-developers] calendar queue
mathieu.lacage at sophia.inria.fr
Thu Jan 8 23:22:45 PST 2009
I just pushed in ns-3-dev an implementation of the original 1988
calendar queue as well as a new command-line option
--SchedulerType=MyTypeId to switch event schedulers. The default is
still the std::map-based event scheduler.
For those interested, here is a copy of the relevant header
* \ingroup scheduler
* \brief a calendar queue event scheduler
* This event scheduler is a direct implementation of the algorithm known as a calendar queue.
* first published in 1988 in "Calendar Queues: A Fast O(1) Priority Queue Implementation for
* the Simulation Event Set Problem" by Randy Brown. There are many refinements published
* later but this class implements 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.
To summarize, it's slow as hell. I might have screwed up small heuristic
details so, if someone wants to look at it or to use it as a basis to
implement a dynamic calendar queue or a snoopy calendar queue, be my
More information about the Ns-developers