Bug 2947 - Improve performance of InterferenceHelper::AppendEvent
Improve performance of InterferenceHelper::AppendEvent
Product: ns-3
Classification: Unclassified
Component: wifi
All All
: P3 enhancement
Assigned To: sebastien.deronne
Depends on:
  Show dependency treegraph
Reported: 2018-07-10 08:18 EDT by Matthew Bradbury
Modified: 2018-08-08 15:46 EDT (History)
1 user (show)

See Also:

Patch to reduce the number of upper_bound calls (1.94 KB, patch)
2018-07-10 08:18 EDT, Matthew Bradbury
Details | Diff
Profile result 1 (17.44 KB, application/pdf)
2018-07-10 08:19 EDT, Matthew Bradbury
Profile result 2 (17.41 KB, application/pdf)
2018-07-10 08:19 EDT, Matthew Bradbury
Incomplete patch using Boost.ICL (18.12 KB, patch)
2018-07-31 10:31 EDT, Matthew Bradbury
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Matthew Bradbury 2018-07-10 08:18:58 EDT
Created attachment 3129 [details]
Patch to reduce the number of upper_bound calls

In bug 2791 the implementation of InterferenceHelper was rewritten using a std::multimap. In my scenario of 500 mobile and 1000 stationary WAVE devices, where the mobile devices send a packet every 0.1 seconds, InterferenceHelper::AppendEvent can take between 35% to 50% of the time taken to perform the simulation.

The attached patch reduces the number of calls to m_niChanges.upper_bound. However, it seems that iterating over the std::multimap is where most of the performance cost lies.
Comment 1 Matthew Bradbury 2018-07-10 08:19:44 EDT
Created attachment 3130 [details]
Profile result 1
Comment 2 Matthew Bradbury 2018-07-10 08:19:59 EDT
Created attachment 3131 [details]
Profile result 2
Comment 3 sebastien.deronne 2018-07-15 08:14:03 EDT
It's ok for me to push these changes if it reduces simulation time.
Could you show how much it affects performance?
Comment 4 Matthew Bradbury 2018-07-31 10:31:31 EDT
I didn't observe a large performance improvement with the original patch.

I have attached an incomplete patch using Boost.ICL which naturally models how additive noise changes over time. It is essentially a map of an ns3::Time interval to the noise (include the devices Tx power) during that interval. When a new value needs to be recorded for an overlapping interval Boost.ICL automatically splits the old interval and adds the new noise to the old noise in the bit of the interval that overlaps.

With an earlier version of this patch I was observing nearly a 4x speedup in my code (2600s to about 700s).

However, there are some fairly invasive changes which could really do with a review by the author of the code. I have made changes to InterferenceHelper::CalculatePlcpPayloadPer that I believe are correct. However, InterferenceHelper::CalculatePlcpHeaderPer is much more complicated and I have not been able to complete the changes.
Comment 5 Matthew Bradbury 2018-07-31 10:31:59 EDT
Created attachment 3155 [details]
Incomplete patch using Boost.ICL
Comment 6 sebastien.deronne 2018-08-08 15:46:49 EDT
(In reply to Matthew Bradbury from comment #5)
> Created attachment 3155 [details]
> Incomplete patch using Boost.ICL

Could you please provide more details about your changes and how they improve performance?