Bugzilla – Bug 2498
Make calendar scheduler fast
Last modified: 2020-08-10 19:08:41 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. ---
Created attachment 2570 [details] Proposed patch Exported wrong revision, this one is correct
Created attachment 2571 [details] Fix a typo Also fix a typo in benchmark
Merged in c9769dc4 https://gitlab.com/nsnam/ns-3-dev/-/merge_requests/217