Bug 826 - Using uint64_t instead of Time in DcfManager
Using uint64_t instead of Time in DcfManager
Status: RESOLVED FIXED
Product: ns-3
Classification: Unclassified
Component: core
ns-3-dev
All All
: P5 enhancement
Assigned To: Mathieu Lacage
:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2010-02-27 09:18 EST by Kirill Andreev
Modified: 2010-08-07 14:43 EDT (History)
4 users (show)

See Also:


Attachments
Proposed fix (11.57 KB, patch)
2010-02-27 09:18 EST, Kirill Andreev
Details | Diff
Profile before optimization (66.04 KB, application/octet-stream)
2010-02-27 09:19 EST, Kirill Andreev
Details
profile after optimization (132.06 KB, application/octet-stream)
2010-02-27 09:19 EST, Kirill Andreev
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Kirill Andreev 2010-02-27 09:18:53 EST
Created attachment 771 [details]
Proposed fix

Replacing all timings in DcfManager with uint64_t (and keeping nanoseconds) makes 25% runtime decrease. All tests and regressions are passed.
Comment 1 Kirill Andreev 2010-02-27 09:19:23 EST
Created attachment 772 [details]
Profile before optimization
Comment 2 Kirill Andreev 2010-02-27 09:19:42 EST
Created attachment 773 [details]
profile after optimization
Comment 3 Kirill Andreev 2010-02-27 09:28:17 EST
I have tried ./wa
Comment 4 Kirill Andreev 2010-02-27 09:29:42 EST
I have tried ./waf --run "mesh --x-size=6 --y-size=6 --step=20"


Old:
real    20m17.648s
user    18m15.836s
sys     0m0.776s


New:
real    17m36.144s
user    15m28.766s
sys     0m0.920s
Comment 5 Kirill Andreev 2010-03-02 06:51:39 EST
After this optimization a first time-consuming method is WifiMacQueue::Cleanup.
I suppose, that _all_ packets coming to a WifiMacQueue are _strictly ordered_ by the time. (if a packet has come later, it will be dequeued later too), but there is a method PushFront, that brakes this rule. This method is used by block acknowledgment mechanism only. If the packets are arranged by a time, cleaning up a queue may be performed much faster, because we do not need to go through all the queue(13% of total time is too time-consuming). I have serious doubts about adding a frame to the front of the queue rather than making another special queue for BA frames (in real hardware you can not perform PushFront). Is it worth changing qap, qsta, qadhoc-wifi-mac?
Comment 6 Nicola Baldo 2010-05-18 10:03:03 EDT
(In reply to comment #0)
> Replacing all timings in DcfManager with uint64_t (and keeping nanoseconds)
> makes 25% runtime decrease. All tests and regressions are passed.

so if I understand correctly the real question is: do we consider acceptable that some ns-3 module uses a fixed time resolution (nanoseconds in this case) instead using ns3::Time, for the purpose of making simulations faster?

I think we need an answer by the maintainer of the src/simulator module (that's where ns3::Time belongs), so I am CCing Mathieu.


(In reply to comment #5)
> After this optimization a first time-consuming method is WifiMacQueue::Cleanup.

I think this is an independent issue. I've filed bug 915 to keep track of it.
Comment 7 Mathieu Lacage 2010-05-18 10:13:36 EDT
(In reply to comment #6)
> (In reply to comment #0)
> > Replacing all timings in DcfManager with uint64_t (and keeping nanoseconds)
> > makes 25% runtime decrease. All tests and regressions are passed.
> 
> so if I understand correctly the real question is: do we consider acceptable
> that some ns-3 module uses a fixed time resolution (nanoseconds in this case)
> instead using ns3::Time, for the purpose of making simulations faster?
> 
> I think we need an answer by the maintainer of the src/simulator module (that's
> where ns3::Time belongs), so I am CCing Mathieu.

I think that individual modules are free to do what they want. In this case, though, it would be nice if we could find a way to fix this in in the time code instead. I would appreciate being given a couple of days to look at this testcase specifically.
Comment 8 Mathieu Lacage 2010-05-18 10:27:34 EDT
(In reply to comment #7)

> I think that individual modules are free to do what they want. In this case,
> though, it would be nice if we could find a way to fix this in in the time code
> instead. I would appreciate being given a couple of days to look at this
> testcase specifically.

it would help to get the actual testcase code.
Comment 9 Mathieu Lacage 2010-05-19 12:35:34 EDT
(In reply to comment #8)
> (In reply to comment #7)
> 
> > I think that individual modules are free to do what they want. In this case,
> > though, it would be nice if we could find a way to fix this in in the time code
> > instead. I would appreciate being given a couple of days to look at this
> > testcase specifically.
> 
> it would help to get the actual testcase code.

and to know on which platform you ran your test. 32 or 64bit ?
Comment 10 Kirill Andreev 2010-05-19 14:09:58 EDT
(In reply to comment #9)
.
> and to know on which platform you ran your test. 32 or 64bit ?

32bit
Comment 11 Mathieu Lacage 2010-07-04 11:09:28 EDT
I pushed something that should deal with this issue (I appear to be getting the same order of magnitude of improvement) at the integer arithmetic implementation for 64bit systems and gcc > 4.1. I will work on another fix for 32bit boxes later.
Comment 12 Tom Henderson 2010-08-01 23:06:07 EDT
Current status is that wifi-wired-bridging test fails on darwin-ppc:

The below note is from Lalith on 8 July:

"I've verified the changed result for the wifi-wired-bridging regression test. The older one is incorrect due to a floating point rounding error, that crept in via the HighPrecision code being used earlier. This lead to the 1ns difference in the mobility trace for Node 2. I've already discussed this with Mathieu."
Comment 13 Nicola Baldo 2010-08-02 07:13:28 EDT
(In reply to comment #12)
> Current status is that wifi-wired-bridging test fails on darwin-ppc:
> 
> The below note is from Lalith on 8 July:
> 
> "I've verified the changed result for the wifi-wired-bridging regression test.
> The older one is incorrect due to a floating point rounding error, that crept
> in via the HighPrecision code being used earlier. This lead to the 1ns
> difference in the mobility trace for Node 2. I've already discussed this with
> Mathieu."

I checked the traces and I confirm that the different in the traces is due to different rounding only. Therefore, I updated ns-3-dev-ref-traces (changeset:   119:0ea6d4e1272b).
Comment 14 Tom Henderson 2010-08-06 09:50:32 EDT
(In reply to comment #13)
> (In reply to comment #12)
> > Current status is that wifi-wired-bridging test fails on darwin-ppc:
> > 
> > The below note is from Lalith on 8 July:
> > 
> > "I've verified the changed result for the wifi-wired-bridging regression test.
> > The older one is incorrect due to a floating point rounding error, that crept
> > in via the HighPrecision code being used earlier. This lead to the 1ns
> > difference in the mobility trace for Node 2. I've already discussed this with
> > Mathieu."
> 
> I checked the traces and I confirm that the different in the traces is due to
> different rounding only. Therefore, I updated ns-3-dev-ref-traces (changeset:  
> 119:0ea6d4e1272b).

This checkin fixed the darwin-ppc platform but unfortunately broke the ns-regression results (x86_64 Linux).  We still have divergent traces.
Comment 15 Mathieu Lacage 2010-08-07 08:25:33 EDT
(In reply to comment #13)
> (In reply to comment #12)
> > Current status is that wifi-wired-bridging test fails on darwin-ppc:
> > 
> > The below note is from Lalith on 8 July:
> > 
> > "I've verified the changed result for the wifi-wired-bridging regression test.
> > The older one is incorrect due to a floating point rounding error, that crept
> > in via the HighPrecision code being used earlier. This lead to the 1ns
> > difference in the mobility trace for Node 2. I've already discussed this with
> > Mathieu."
> 
> I checked the traces and I confirm that the different in the traces is due to
> different rounding only. Therefore, I updated ns-3-dev-ref-traces (changeset:  
> 119:0ea6d4e1272b).

Which version of ns-3-dev did you use to generate those traces ?? 

Because the new traces don't pass on _any_ system I have tried them on.
Comment 16 Tom Henderson 2010-08-07 09:40:46 EDT
(In reply to comment #15)
> (In reply to comment #13)
> > (In reply to comment #12)
> > > Current status is that wifi-wired-bridging test fails on darwin-ppc:
> > > 
> > > The below note is from Lalith on 8 July:
> > > 
> > > "I've verified the changed result for the wifi-wired-bridging regression test.
> > > The older one is incorrect due to a floating point rounding error, that crept
> > > in via the HighPrecision code being used earlier. This lead to the 1ns
> > > difference in the mobility trace for Node 2. I've already discussed this with
> > > Mathieu."
> > 
> > I checked the traces and I confirm that the different in the traces is due to
> > different rounding only. Therefore, I updated ns-3-dev-ref-traces (changeset:  
> > 119:0ea6d4e1272b).
> 
> Which version of ns-3-dev did you use to generate those traces ?? 
> 
> Because the new traces don't pass on _any_ system I have tried them on.

They passed for me yesterday, using ns-3-dev-ref-traces:
changeset:   119:0ea6d4e1272b
date:        Mon Aug 02 13:07:57 2010 +0200
summary:     float rounding error was fixed as part of Bug 826

on ns-3-dev as of:
changeset:   6481:f6072e786db1
date:        Wed Aug 04 12:52:53 2010 +0100
summary:     merge

on OS X ppc system
Comment 17 Mathieu Lacage 2010-08-07 14:43:58 EDT
the regresssion tests do not pass for me but this is really a separate issue. I am going to file another bug about it.