[Ns-developers] calendar queue
mathieu.lacage at sophia.inria.fr
Thu Jan 8 23:25:01 PST 2009
[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::HeapScheduler
[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::CalendarScheduler
[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::ListScheduler
[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::MapScheduler
[mathieu at localhost ns-3-dev]$
I should point out that csma-star is a bit of an extreme case because
the event expiration time distribution is extremely skewed: most events
all have the _exact_ same expiration time. Anyway, food for thought.
On Fri, 2009-01-09 at 08:22 +0100, Mathieu Lacage wrote:
> 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