Bug 2498

Created attachment 2569 [details]
Proposed patch

This patch ports calendar scheduler improvement from NS-2. It reverses the order of insertion sort in buckets.

Default MapScheduler:
Run #       Inititialization:                   Simulation:
            Time (s)    Rate (ev/s) Per (s/ev)  Time (s)    Rate (ev/s) Per (s/ev)
----------- ----------- ----------- ----------- ----------- ----------- -----------
(prime)     0.12        833333      1.2e-06     0.94        1.06383e+06 9.4e-07
0           0.07        1.42857e+06 7e-07       0.93        1.07527e+06 9.3e-07

Calendar scheduler before patch:
Run #       Inititialization:                   Simulation:
            Time (s)    Rate (ev/s) Per (s/ev)  Time (s)    Rate (ev/s) Per (s/ev)
----------- ----------- ----------- ----------- ----------- ----------- -----------
(prime)     0.61        163934      6.1e-06     20.26       49358.3     2.026e-05
0           0.43        232558      4.3e-06     23.98       41701.4     2.398e-05

Calendar scheduler with patch:
Run #       Inititialization:                   Simulation:
            Time (s)    Rate (ev/s) Per (s/ev)  Time (s)    Rate (ev/s) Per (s/ev)
----------- ----------- ----------- ----------- ----------- ----------- -----------
(prime)     0.11        909091      1.1e-06     0.53        1.88679e+06 5.3e-07
0           0.05        2e+06       5e-07       0.59        1.69492e+06 5.9e-07

This simple change makes calendar scheduler the fastest scheduler in NS-3 according to the benchmark. Maybe it is not ready to be used as default scheduler yet, as calendar scheduler has known drawbacks in some scenarios, but at least it is not actually as bad as doxygen documentation says and can be used for scenarios where it improves performance.

I also tried to use std::map inside buckets, but it has higher overhead compared to std::list, so it actually performs worse in benchmark.

Copy of commit message for convenience
---
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.
---