Bug 2498 - Make calendar scheduler fast
Make calendar scheduler fast
Status: RESOLVED FIXED
Product: ns-3
Classification: Unclassified
Component: core
ns-3-dev
All All
: P5 enhancement
Assigned To: Peter Barnes
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2016-09-09 11:53 EDT by Alexander Krotov
Modified: 2020-08-10 19:08 EDT (History)
2 users (show)

See Also:


Attachments
Proposed patch (1.07 KB, patch)
2016-09-09 11:53 EDT, Alexander Krotov
Details | Diff
Proposed patch (4.07 KB, patch)
2016-09-09 11:56 EDT, Alexander Krotov
Details | Diff
Fix a typo (865 bytes, patch)
2016-09-09 12:03 EDT, Alexander Krotov
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Alexander Krotov 2016-09-09 11:53:50 EDT
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.
---
Comment 1 Alexander Krotov 2016-09-09 11:56:20 EDT
Created attachment 2570 [details]
Proposed patch

Exported wrong revision, this one is correct
Comment 2 Alexander Krotov 2016-09-09 12:03:44 EDT
Created attachment 2571 [details]
Fix a typo

Also fix a typo in benchmark
Comment 3 Peter Barnes 2020-08-10 19:08:41 EDT
Merged in c9769dc4
https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/217