Re: NaN-toolbox much faster now

[Alois Schlögl]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Jaroslav Hajek wrote:
> On Thu, Mar 12, 2009 at 5:13 PM, Alois Schlögl <address@hidden> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> The following improvements have been included in the NaN-toolbox.
>>
>> - - sumskipnan_mex.mex has been optimized for speed (minimizing cache
>> missing, reducing loop overhead)
>>
>> - - a flag is set if some NaN occures in the data. The flag can be checked
>> (and reset) with function FLAG_NANS_OCCURED(). This enables a flexible
>> control on checks for NaN. (You can check after every call, or only at
>> the end of your script).
>>
>> - - the performance of var, std, and meansq has been improved.
>>
>> A performance between the NaN-toolbox and corresponding standard octave
>> functions (see script below) show the following results (time in [s]):
>>
>>
>> with NaN-tb     w/o NaN-tb      ratio
>>    0.25884    3.56726   13.78183       mean(x,1)/nanmean(x,1)
>>    0.36784    3.32899    9.05020       mean(x,2)/nanmean(x,2)
>>    0.30019    6.62467   22.06789       std(x,0,1)
>>    0.40114    2.23262    5.56561       std(x,0,2)
>>    0.28681    6.40276   22.32407       var(x,0,1)
>>    0.40269    2.18056    5.41505       var(x,0,2)
>>    0.28175    4.05612   14.39598       meansq(x,1)
>>    0.40703    4.19346   10.30248       meansq(x,2)
>>    0.25930    0.19884    0.76683       sumskipnan(x,1)/sum(x,1)
>>    0.30624    0.24179    0.78955       sumskipnan(x,2)/sum(x,2)
>>
>>
>> A performance improvement by factors as high as 22 can be seen, and
>> sumskipnan() is only about 25% slower than sum().
>>
>> Of course, sumskipnan could also improve the speed of functions like
>> nanmean, nanstd, etc. Maybe you want to consider including sumskipnan in
>> standard octave.
>>
> 
> I repeated your experiment using current Octave tip (-O3
> -march=native, Core 2 Duo @ 2.83GHz):
> 
>    mean(x,1)  mean(x,2)  std(x,0,1)  std(x,0,2)  var(x,0,1)
> var(x,0,2) meansq(x,1)  meansq(x,2)  sum(skipnan)(x,1)
> sum(skipnan)(x,2)
> 
> tic-toc time
> 
>    0.108911   0.132629   0.114568   0.163950   0.112384   0.163973
> 0.112379   0.163682   0.096581   0.101545
>    0.090389   0.091657   0.915853   0.955799   0.883821   0.921007
> 0.110276   0.114233   0.082247   0.089742
> 
> tic-toc ratio
> 
>    0.82993   0.69108   7.99397   5.82982   7.86431   5.61683   0.98129
>   0.69790   0.85159   0.88376
> 
> cputime
> 
>    0.108007   0.136008   0.112007   0.164011   0.112007   0.164010
> 0.116007   0.160010   0.100006   0.100007
>    0.088005   0.088005   0.900056   0.956060   0.884055   0.924058
> 0.092006   0.116007   0.080005   0.092006
> 
> cputime ratio
> 
>    0.81481   0.64706   8.03571   5.82924   7.89285   5.63416   0.79311
>   0.72500   0.80000   0.92000
> 
> It can be seen that the penalty for skipping NaNs is mostly within
> 20-30%, smaller for column-oriented reductions.
> The speed-up factors 5 and 7 for std and var are caused by the
> single-sweep computation done in sumskipnan.
> This becomes apparent when a less random data are supplied, and the
> NaN toolbox reverts to a backup algorithm (which is what Octave always
> does) - relative error at the order of 10^-4:
> 
> tic-toc time
> 
>    0.108613   0.132721   1.362765   1.500724   1.366353   1.499243
> 0.115758   0.163625   0.097873   0.102086
>    0.089788   0.089979   0.876386   0.914380   0.880742   0.913636
> 0.094084   0.091950   0.082200   0.089619
> 
> tic-toc ratio
> 
>    0.82668   0.67796   0.64309   0.60929   0.64459   0.60940   0.81277
>   0.56196   0.83986   0.87788
> 
> cputime
> 
>    0.108007   0.132008   1.364085   1.500094   1.368086   1.500093
> 0.116007   0.164011   0.096006   0.104006
>    0.092006   0.088005   0.876055   0.916057   0.880055   0.916057
> 0.092006   0.092006   0.084005   0.088005
> 
> cputime ratio
> 
>    0.85185   0.66666   0.64223   0.61067   0.64327   0.61067   0.79311
>   0.56097   0.87500   0.84615
> 
> Here the std/var computations are slown down by some 35-45%. This is
> less favorable, though certainly no disaster.
> I think the Octave statistics subcommunity should discuss what would
> they appreciate best. Is anyone depending on the speed of std/var?
> Opinions about skipping NaNs? Given Octave's NA support, it may be
> better to just skip NAs, like R does.
> 
> There were also suggestions to move the statistics functions
> completely out of Octave. Personally, I'd vote to retain just the
> stuff from statistics/base, because I sometimes use functions thereof
> despite not being a statistician.
> 
> regards
> 


Thanks for confirming the test. You asked for "opinions about skipping
NaN's, and the Octave NA's support". Here are some thoughts on that issue.

Concerning the question whether NaN's and NA should be handled separately.
- - Just because R has NA's is not necessarily a good reason why Octave
needs it, too. Possible advantages need to be explained.

- - In statistical and probabilistic applications skipping both, NaN and
NA, is a reasonable approach - there is no need to distinguish NaN from NA.

- - In case NaN's are used for error handling, the question is how is NA
improving the error handling? The main advantage would be that less
NaN's need to be handled, but NA come with additional costs of added
complexity and possible confusion (causing more programming errors, slow
down of development speed, as well as performance loss). Therefore, if
NA's should get special support, the benefits of this concept should be
made clear.

- - The benefits of the NaN-toolbox over the traditional approach are:
(i) functions are doing more often the right thing,
(ii) applications are less likely to fail due to NaN-related issues.
(iii) its more likely that users unaware of the NaN-issue get it right
in the first place,
(iv) no need to think about whether nanmean or mean is the right function;
(v) of course using always nanmean(), etc. would also do, but its nicer
to write only mean(), etc.;
Basically, the idea is to make the use of these functions easier. The
use of NA in addition to NaN's is detrimental to this aim. So the
advantage of using NA's is not clear.


cheers,
   Alois



-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkm+QfcACgkQzSlbmAlvEIjdJwCfa4ILHFsiL/jTZN+91QbgTM1e
AqkAn2vpndklkrDUnl7Nscww2yRRqY6U
=rxRq
-----END PGP SIGNATURE-----