Bug 1276

Summary: optimize NistErrorRateModel
Product: ns-3 Reporter: Tom Henderson <tomh>
Component: generalAssignee: ns-bugs <ns-bugs>
Status: RESOLVED FIXED    
Severity: normal CC: guangyu.pei, nicola, ns-bugs, pdbarnes, ruben, tommaso.pecorella
Priority: P5    
Version: pre-release   
Hardware: All   
OS: All   
Attachments: suggested patch
test performance program
Changes to core module
All the other modules patched
new patch...
Patch - minimal

Description Tom Henderson 2011-10-10 01:10:36 EDT
Created attachment 1251 [details]
suggested patch

posted here:
http://mailman.isi.edu/pipermail/ns-developers/2011-October/009498.html
Comment 1 Tom Henderson 2011-10-10 01:11:02 EDT
Created attachment 1252 [details]
test performance program
Comment 2 Tom Henderson 2011-10-19 10:41:08 EDT
Additional comment from Fabian:

I do the new tests and I find that there is a precision issue doing D*D
than pow(D,2) and the results there are no goods. Of courses, this is
when there are number very very littles. But Nist use always number very
littles. So the patch is incorrect.
Comment 3 Tommaso Pecorella 2012-03-18 09:42:05 EDT
So, the patch is correct but the method does increase the rounding errors and should be rejected, right ?

If this is the case, can we close this ?

On the other hand... never leave something unanswered.

"I do the new tests and I find that there is a precision issue doing D*D
than pow(D,2)"
Of course. The latter is more precise as it can leverage a shift in the mantissa, while the firs is a full multiplication. If the compiler is smart, tho, it can do the same. I'd expect similar timings *and* results when optimized. Unoptimized... maybe different results and timing.

That as a logical argument. Of course logic and programming often are different.

Ok, let's look at the code.

pow in that function (and in many other places) is used as pow(double, double) *even when it's pow(double, int)* !

Digging in the net: http://stackoverflow.com/questions/4541130/definitions-of-sqrt-sin-cos-pow-etc-in-cmath-c-c 
"pow(x, y) = exp(y * log(x)), so pow is not to be used when y is an integer"

WOAH !

More digging needed, but in our own code. What are we using ?
Answer: #include <math.h>, as is the old C one.
But C++ should use #include <math.h>.... it is just a naming thing or is there a REAL difference ?

On my Mac:
math.h points to "architecture/i386/math.h", where only 2 "pow" are defined:
extern double pow ( double, double );
extern float powf ( float, float );

and cmath ? C++ do have 5 "pow" functions:
1) double pow ( double base, double exponent );
2) long double pow ( long double base, long double exponent );
3) float pow ( float base, float exponent );
4) double pow ( double base, int exponent );
5) long double pow ( long double base, int exponent );

So I was expecting just some castings and a call to the old math.h.

Now, this is funny, as *I didn't expect this*.
  using ::pow;

  inline float
  pow(float __x, float __y)
  { return __builtin_powf(__x, __y); }

  inline long double
  pow(long double __x, long double __y)
  { return __builtin_powl(__x, __y); }

  inline double
  pow(double __x, int __i)
  { return __builtin_powi(__x, __i); }

  inline float
  pow(float __x, int __n)
  { return __builtin_powif(__x, __n); }

  inline long double
  pow(long double __x, int __n)
  { return __builtin_powil(__x, __n); }

... no comment, let's search for __builtin_powi.

— Built-in Function: double __builtin_powi (double, int)
Returns the first argument raised to the power of the second. Unlike the pow function no guarantees about precision and rounding are made.

This is getting interesting, but the times grow short and the answer is already here, so no need for further digging.

The answer is: *we are using the wrong pow function* and as a sub-answer *the precision is not guaranteed*.

The action is thus:
1) kill all the references to math.h and use cmath instead, as they are different. Performance might increase dramatically.
2) use pow (double, int) where appropriate, do NOT use pow(double, double) as the precision might be quite lower than expected.

However, before going straight into that direction, it would be interesting to see some real performance and precision tests.


Funny results from a simple performance bug, isn't it ?

T.
Comment 4 Tom Henderson 2012-03-20 04:33:34 EDT
I will have Gary (original author) look at this and reply back.
Comment 5 Gary Pei 2012-03-20 13:53:03 EDT
(In reply to comment #4)
> I will have Gary (original author) look at this and reply back.

(In reply to comment #4)
> I will have Gary (original author) look at this and reply back.

Yes, I think we should use cmath.h and use pow (double,int) signature.
Comment 6 Tommaso Pecorella 2012-03-20 17:59:27 EDT
(In reply to comment #5)
> (In reply to comment #4)
> > I will have Gary (original author) look at this and reply back.
> 
> (In reply to comment #4)
> > I will have Gary (original author) look at this and reply back.
> 
> Yes, I think we should use cmath.h and use pow (double,int) signature.

I did a little test...


#include <iostream>
#include <math.h>

using namespace std;

int main() {

	double foo = 2.0;
	double bar;

	for( int i=0; i<1000000000; i++ )
	{
		bar = pow(foo, 20.0);
	}

	return 0;
}

On a MacOS the result is:

22:53:33:~/Development/workspace/TestMath pecos$ time ./Debug/TestMath 
real	0m36.887s
user	0m36.879s
sys	0m0.006s

Changing math.h to cmath and pow(foo, 20.0); to pow(foo, 20); it's a bit faster:
22:52:59:~/Development/workspace/TestMath pecos$ time ./Debug/TestMath 
real	0m15.546s
user	0m15.541s
sys	0m0.004s

Seems we should find all the remaining math.h and change them, we should see an overall improvement.

What about a global patch to fix all the occurrences ?

Cheers,

T.
Comment 7 Gary Pei 2012-03-20 18:03:02 EDT
(In reply to comment #6)

> 
> Seems we should find all the remaining math.h and change them, we should see an
> overall improvement.
> 
> What about a global patch to fix all the occurrences ?
> 
> Cheers,
> 
> T.

Sounds good.
Comment 8 Tommaso Pecorella 2012-03-20 18:23:54 EDT
Hem... maybe a global patch is not wise. However we should really do it.

Tom, suggestions on how to proceed ?

21:44:55:~/Development/workspace/ns-3-dev pecos$ grep -r math.h src/
src/core/model/default-simulator-impl.cc:#include <math.h>
src/core/model/int64x64-128.h:#include <math.h>
src/core/model/int64x64-cairo.cc:#include <math.h>
src/core/model/int64x64-cairo.h:#include <math.h>
src/core/model/int64x64-double.h:#include <math.h>
src/core/model/ns2-calendar-scheduler.cc:#include <math.h>
src/core/model/nstime.h:#include <math.h>
src/core/model/random-variable.cc:#include <math.h>
src/core/model/realtime-simulator-impl.cc:#include <math.h>
src/core/model/simulator.cc:#include <math.h>
src/core/model/test.cc:#include <math.h>
src/core/model/time.cc:#include <math.h>
src/core/test/random-variable-test-suite.cc:#include <math.h>
src/core/test/rng-test-suite.cc:#include <math.h>
src/energy/model/rv-battery-model.cc:#include <math.h>
src/energy/test/basic-energy-model-test.cc:#include <math.h>
src/energy/test/rv-battery-model-test.cc:#include <math.h>
src/flow-monitor/model/histogram.cc:#include <math.h>
src/lte/model/amc-module.cc:#include <math.h>
src/lte/model/enb-lte-spectrum-phy.cc:#include <math.h>
src/lte/model/enb-phy.cc:#include <math.h>
src/lte/model/lte-phy.cc:#include <math.h>
src/lte/model/lte-spectrum-phy.cc:#include <math.h>
src/lte/model/ue-lte-spectrum-phy.cc:#include <math.h>
src/lte/model/ue-phy.cc:#include <math.h>
src/mobility/model/mobility-model.cc:#include <math.h>
src/mpi/model/distributed-simulator-impl.cc:#include <math.h>
src/network/utils/error-model.cc:#include <math.h>
src/network/utils/radiotap-header.cc:#include <math.h>
src/propagation/model/cost231-propagation-loss-model.cc:#include <math.h>
src/propagation/model/jakes-propagation-loss-model.cc:#include <math.h>
src/propagation/model/propagation-loss-model.cc:#include <math.h>
src/spectrum/model/constant-spectrum-propagation-loss.cc:#include <math.h>
src/spectrum/model/friis-spectrum-propagation-loss.cc:#include <math.h>
src/spectrum/model/half-duplex-ideal-phy.cc:#include <math.h>
src/spectrum/model/spectrum-value.cc:#include <math.h>
src/spectrum/test/spectrum-value-test.cc:#include <math.h>
src/stats/test/basic-data-calculators-test-suite.cc:#include <math.h>
src/tools/test/average-test-suite.cc:#include <math.h>
src/wifi/model/dcf-manager.cc:#include <math.h>
src/wifi/model/dsss-error-rate-model.cc:#include <math.h>
src/wifi/model/dsss-error-rate-model.h:#include <gsl/gsl_math.h>
src/wifi/model/ideal-wifi-manager.cc:#include <math.h>
src/wifi/model/wifi-phy.cc:#include <math.h>
src/wifi/model/yans-wifi-phy.cc:#include <math.h>
src/wimax/model/simple-ofdm-wimax-phy.cc:#include <math.h>
Comment 9 Tommaso Pecorella 2012-03-20 18:47:21 EDT
Created attachment 1364 [details]
Changes to core module

Remove math.h and add cmath (only where needed)
Comment 10 Tommaso Pecorella 2012-03-20 18:54:35 EDT
The changes to code are easy, in other places we shall check where inappropriate casting is done, so to avoid pow(double, double) where it's not needed.

The good news is that it seems that the only relevant function to be checked is pow(). Other math functions have the same signature in math.h and cmath.

T.
Comment 11 Tommaso Pecorella 2012-03-20 19:27:07 EDT
Created attachment 1365 [details]
All the other modules patched

Patch for all the other modules (except core).

Changed math.h to cmath
Changed some pow functions to be pow(double, int), only where appropriate.

BEWARE: triple check all the changes, as I could have done a mistake somewhere. It's compiling but it's untested.
Comment 12 Nicola Baldo 2012-03-30 13:03:55 EDT
I had a look at the patch, and it seems ok for me (also builds ok and passes test.py, for what it means). 

The only minor thing is that one instance of math.h is still left over:
src/core/model/int64x64-cairo.cc:#include <math.h>

I guess that if we plan to forever ban math.h in favor of cmath, we should mention it somewhere in our guidelines.
Comment 13 Peter Barnes 2014-03-02 04:13:45 EST
Last <math.c> converted to <cmath> in:
Bug 1856 Patch r10637 67601c471c22
http://code.nsnam.org/ns-3-dev/rev/67601c471c22

(In reply to Nicola Baldo from comment #12)
> I had a look at the patch, and it seems ok for me (also builds ok and passes
> The only minor thing is that one instance of math.h is still left over:
> src/core/model/int64x64-cairo.cc:#include <math.h>
Comment 14 Tommaso Pecorella 2014-03-02 18:21:06 EST
Created attachment 1792 [details]
new patch...

Interesting enough, this patch was never applied.
The new patch is against 3.19 / ns-3-dev.
Comment 15 Tommaso Pecorella 2014-04-19 04:14:33 EDT
Created attachment 1819 [details]
Patch - minimal

This one really limit the number of changes to the bare minimum.
All tests as today are passing, and valgrind doesn't raise warning.

Patch contains python bindings rescan.
Comment 16 Tommaso Pecorella 2014-04-29 04:03:33 EDT
changeset:   10706:ac80fd74d8cd