[Ns-developers] calendar queue

[Mathieu Lacage]

it's slow:

[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::HeapScheduler
real 1.61
user 1.57
sys 0.03
[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::CalendarScheduler
real 6.13
user 6.08
sys 0.02
[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::ListScheduler
real 1.66
user 1.61
sys 0.03
[mathieu at localhost ns-3-dev]$ time -p ./build/optimized/examples/csma-star --SchedulerType=ns3::MapScheduler
real 1.58
user 1.55
sys 0.02
[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.

Mathieu

On Fri, 2009-01-09 at 08:22 +0100, Mathieu Lacage wrote:
> hi,
> 
> 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
> (src/simulator/calendar-scheduler.h):
> 
> /**                                                                                                                                                                   
>  * \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
> guest.
> 
> regards,
> Mathieu