Bug 826

Created attachment 772 [details]
Profile before optimization

Created attachment 773 [details]
profile after optimization

I have tried ./wa

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

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?

(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.

(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.

(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.

(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 ?

(In reply to comment #9)
.
> and to know on which platform you ran your test. 32 or 64bit ?

32bit

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.

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."

(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).

(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.

(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.

(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

the regresssion tests do not pass for me but this is really a separate issue. I am going to file another bug about it.