[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: fast hist() / histogram() implementation in C++
|
From: |
Petr Mikulik |
|
Subject: |
Re: fast hist() / histogram() implementation in C++ |
|
Date: |
Fri, 28 May 2004 04:05:57 -0500 |
> About a year ago, a fair amount of effort was put into
> optimizing the hist.m function. I believe that your
> argument for adding a C++ implementation would be better
> if you provided some benchmark examples rather than
> "it is order(s) of magnitude worse".
>
> Take a look at:
> http://www.octave.org/octave-lists/archive/octave-maintainers.2003/msg00084.html
I acknowledge the effort in improving hist.m. Is is as fast as M-language
allows. Unfortunately, using it for large images (e.g. 2D detector data)
like 512^2 and above goes beyond the user patiency (at least, for me). That
was my move to reimplement my own favourite histogram.m into histogram.oct.
The following benchmark shows a proof of concept that native C++
implementation is "a must" for images >= 512^2 -- there, calculation
times by hist.m start to exceed 1 second @ 2 GHz Pentium. Three histogram
calculation methods are presented.
timeM: time of Octave's hist.m
timeC: time of my histogramC.oct, linear bins
timeCL: time of my histogramC.oct, log bins
(this uses interval bisection)
Times are in seconds, relative to Linux 2.4.21 @ Pentium 2.4 GHz.
Testing matrix was 1./hilb(ndata) with
a_ndata=[128, 256, 400, 512, 1024, 2048];
for number of bins
a_nbins=[3, 10, 20, 30, 40, 50, 60, 100, 200];
Particular results:
ndata nbins timeM timeC timeCL timeM/C timeM/CL
128 3 0.049 0.002 0.001 31 51
128 10 0.020 0.001 0.001 17 14
128 20 0.035 0.001 0.002 30 23
128 30 0.044 0.001 0.002 38 27
128 40 0.038 0.001 0.002 33 22
128 50 0.039 0.001 0.002 33 20
128 60 0.038 0.001 0.002 33 19
128 100 0.039 0.001 0.002 33 17
128 200 0.040 0.001 0.003 33 14
256 3 0.020 0.003 0.002 7 9
256 10 0.068 0.003 0.004 21 15
256 20 0.129 0.003 0.005 39 27
256 30 0.166 0.004 0.005 47 33
256 40 0.178 0.003 0.006 54 31
256 50 0.234 0.003 0.007 70 33
256 60 0.166 0.003 0.006 51 27
256 100 0.166 0.003 0.008 50 21
256 200 0.166 0.003 0.010 50 17
400 3 0.047 0.007 0.005 7 10
400 10 0.154 0.007 0.010 22 16
400 20 0.306 0.007 0.011 42 29
400 30 0.505 0.007 0.013 70 38
400 40 0.419 0.007 0.013 58 33
400 50 0.424 0.007 0.014 59 31
400 60 0.421 0.007 0.017 58 25
400 100 0.499 0.007 0.018 69 27
400 200 0.416 0.007 0.022 57 19
512 3 0.075 0.012 0.007 6 11
512 10 0.250 0.011 0.015 22 16
512 20 0.560 0.011 0.020 49 28
512 30 0.744 0.011 0.018 65 40
512 40 0.762 0.011 0.020 67 38
512 50 0.822 0.011 0.022 72 38
512 60 0.748 0.011 0.022 65 34
512 100 0.828 0.011 0.031 72 27
512 200 0.741 0.011 0.032 65 23
1024 3 0.349 0.039 0.026 9 13
1024 10 0.980 0.042 0.059 23 17
1024 20 2.040 0.045 0.142 45 14
1024 30 3.443 0.051 0.077 67 45
1024 40 3.469 0.048 0.086 73 40
1024 50 3.443 0.044 0.102 78 34
1024 60 3.438 0.044 0.087 78 39
1024 100 3.525 0.045 0.108 78 33
1024 200 3.482 0.044 0.121 79 29
2048 3 1.141 0.160 0.131 7 9
2048 10 4.037 0.172 0.238 23 17
2048 20 8.074 0.170 0.269 48 30
2048 30 16.600 0.169 0.287 98 58
2048 40 16.509 0.175 0.318 94 52
2048 50 16.423 0.245 0.373 67 44
2048 60 16.405 0.255 0.347 64 47
2048 100 16.392 0.184 0.482 89 34
2048 200 16.306 0.177 0.565 92 29
Statistical results over particular results;
lines are min, median, mean and max:
ndata nbins timeM timeC timeCL timeM/C timeM/CL
128 3 0.020 0.001 0.001 6 9
456 40 0.422 0.009 0.018 50 27
728 57 2.711 0.043 0.078 50 28
2048 200 16.600 0.255 0.565 98 58
Thus, in average, 50x speedup is achieved for linearly spaced bins,
and 27x for logarithmically (or whichever non-linearly) spaced bins.
Thus, Octave would greatly profit from a histc.oct function.
Petr Mikulik
*******************************************************************
Appendix. The benchmark code:
1;
% Benchmark function:
function [timeM, timeC, timeCL] = histBench ( ndata, nbins )
a=1./hilb(ndata);
a=a(:);
tic; [x1,x2]=hist(a,nbins); timeM=toc;
tic; [x1,x2]=histogramC(a,nbins); timeC=toc;
tic; [x1,x2]=histogramC(a,nbins,1); timeCL=toc;
endfunction
% Benchmark code:
a_ndata=[128, 256, 400, 512, 1024, 2048];
a_nbins=[3, 10, 20, 30, 40, 50, 60, 100, 200];
res_index=0;
for k=1:length(a_ndata)
ndata=a_ndata(k);
for m=1:length(a_nbins)
res_index=res_index+1;
nbins=a_nbins(m);
[timeM,timeC,timeCL]=histBench(ndata,nbins);
res(res_index,1:7)=[ndata, nbins, timeM, timeC, timeCL, timeM/timeC,
timeM/timeCL];
fprintf('\n\n-----\n\n');
fprintf('ndata\tnbins\ttimeM\ttimeC\ttimeCL\ttimeM/C\ttimeM/CL\n');
fprintf('% 5i\t% 4i\t%.3f\t%.3f\t%.3f\t%5.0f\t%5.0f\n', res');
end
end
fprintf('\n\n');
fprintf('Statistical results of the above\n');
fprintf('Lines are min, median, mean and max:\n\n');
statRes(1,:)=min(res);
statRes(2,:)=median(res);
statRes(3,:)=mean(res);
statRes(4,:)=max(res);
fprintf('% 5i\t% 4i\t%.3f\t%.3f\t%.3f\t%5.0f\t%5.0f\n', statRes');
% eof
-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.
Octave's home on the web: http://www.octave.org
How to fund new projects: http://www.octave.org/funding.html
Subscription information: http://www.octave.org/archive.html
-------------------------------------------------------------