Bugzilla – Bug 1276
optimize NistErrorRateModel
Last modified: 2014-04-29 04:03:33 EDT
Created attachment 1251 [details] suggested patch posted here: http://mailman.isi.edu/pipermail/ns-developers/2011-October/009498.html
Created attachment 1252 [details] test performance program
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.
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.
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. (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.
(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.
(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.
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>
Created attachment 1364 [details] Changes to core module Remove math.h and add cmath (only where needed)
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.
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.
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.
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>
Created attachment 1792 [details] new patch... Interesting enough, this patch was never applied. The new patch is against 3.19 / ns-3-dev.
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.
changeset: 10706:ac80fd74d8cd