Mercurial > forge
comparison extra/testfun/speed.m @ 0:6b33357c7561 octave-forge
Initial revision
author | pkienzle |
---|---|
date | Wed, 10 Oct 2001 19:54:49 +0000 |
parents | |
children | 143f3827b789 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:6b33357c7561 |
---|---|
1 ## Copyright (C) 2000-2001 Paul Kienzle | |
2 ## | |
3 ## This program is free software; you can redistribute it and/or modify | |
4 ## it under the terms of the GNU General Public License as published by | |
5 ## the Free Software Foundation; either version 2 of the License, or | |
6 ## (at your option) any later version. | |
7 ## | |
8 ## This program is distributed in the hope that it will be useful, | |
9 ## but WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
11 ## GNU General Public License for more details. | |
12 ## | |
13 ## You should have received a copy of the GNU General Public License | |
14 ## along with this program; if not, write to the Free Software | |
15 ## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | |
16 | |
17 ## speed(f, init, max_n, f2, tol, err) | |
18 ## | |
19 ## Determine the execution time of an expression for various n. | |
20 ## The n are log-spaced from 1 to max_n. For each n, an | |
21 ## initialization expression is computed to create whatever | |
22 ## data are needed for the test. | |
23 ## | |
24 ## f is the expression to evaluate. | |
25 ## max_n = 100 is the maximum test length to run. | |
26 ## init = "x = randn(n, 1);" | |
27 ## Initialization expression for function argument values. Use 'k' | |
28 ## for the test number and 'n' for the size of the test. This should | |
29 ## compute values for all variables listed in args. Note that init | |
30 ## will be evaluated first for k=0, so things which are constant | |
31 ## throughout the test can be computed then. | |
32 ## f2 = [] | |
33 ## is an alternative expression to evaluate, so the speed of the two | |
34 ## can be compared | |
35 ## tol = eps | |
36 ## if tol is inf, then no comparison will be made between the | |
37 ## results of express f and expression f2. Otherwise, expression | |
38 ## f should produce a value v and expression f2 should produce | |
39 ## a value v2, and these shall be compared using assert(v,v2,tol,err) | |
40 ## | |
41 ## r = speed (...) | |
42 ## Returns the average speedup ratio instead of displaying and plotting. | |
43 ## | |
44 ## Some global variables are also referenced. Choose values suitable to | |
45 ## your machine and your work style. | |
46 ## speed_test_plot = 1 | |
47 ## if true, plot a nice speed comparison graph | |
48 ## speed_test_numtests = 25 | |
49 ## number of vector lengths to test | |
50 ## | |
51 ## Some comments on the graphs. The line on the speedup ratio graph | |
52 ## should be larger than 1 if your function is faster. The slope on | |
53 ## the runtime graph shows you the O(f) speed characteristics. Where it | |
54 ## is flat, execution time is O(1). Where it is sloping, execution time | |
55 ## is O(n^m), with steeper slopes for larger n. Generally vectorizing | |
56 ## a function will not change the slope of the run-time graph, but it | |
57 ## will shift it relative to the original. | |
58 ## | |
59 ## Example | |
60 ## % If you had an original version of xcorr using for loops and | |
61 ## % another version using FFT, you could compare the run speed | |
62 ## % for various lags as follows, or for a fixed lag with varying | |
63 ## % vector lengths as follows: | |
64 ## | |
65 ## speed("v=xcorr(x,n)", "x=rand(128,1);", 100, ... | |
66 ## "v2=xcorr_orig(x,n)", 100*eps,'rel') | |
67 ## speed("v=xcorr(x,15)", "x=rand(20+n,1);", 100, ... | |
68 ## "v2=xcorr_orig(x,n)", 100*eps,'rel') | |
69 ## | |
70 ## % Assuming one of the two versions is in xcorr_orig, this would | |
71 ## % would compare their speed and their output values. Note that the | |
72 ## % FFT version is not exact, so we specify an acceptable tolerance on | |
73 ## % the comparison (100*eps), and the errors should be computed | |
74 ## % relatively, as abs( (x-y)./y ) rather than absolutely as abs(x-y). | |
75 ## | |
76 ## Example | |
77 ## speed("strrep(s,x,y)", "s=blanks(n);x=' ';y='b';", 100) | |
78 ## | |
79 ## Type example('speed') to see some real examples. Note for | |
80 ## obscure reasons, you can't run examples 1 and 2 directly using | |
81 ## demo('speed'). Instead use: | |
82 ## eval(example('speed',1)) | |
83 ## eval(example('speed',2)) | |
84 | |
85 ## TODO: consider two dimensional speedup surfaces for functions like kron. | |
86 function __ratio_r = speed (__f1, __init, __max_n, __f2, __tol, __err) | |
87 if nargin < 1 || nargin > 6, | |
88 usage("speed_test(f, init, max_n, f2, tol, err)"); | |
89 endif | |
90 if nargin < 2 || isempty(__init), | |
91 __init = "x = randn(n, 1);"; | |
92 endif | |
93 if nargin < 3 || isempty(__max_n), __max_n = 100; endif | |
94 if nargin < 4, __f2 = []; endif | |
95 if nargin < 5 || isempty(__tol), __tol = eps; endif | |
96 if nargin < 6 || isempty(__err), __err = []; endif | |
97 | |
98 global speed_test_plot = 1; | |
99 global speed_test_numtests = 25; | |
100 | |
101 __test_n = uniq(round(logspace(0,log10(__max_n),speed_test_numtests))); | |
102 __torig = __tnew = zeros (size(__test_n)) ; | |
103 | |
104 disp (["testing..........", __f1, "\ninit: ", __init]); | |
105 | |
106 ## make sure the functions are freshly loaded by evaluating them at | |
107 ## test_n(1); firt have to initialize the args though. | |
108 n=1; k=0; | |
109 eval ([__init, ";"]); | |
110 if !isempty(__f2), eval ([__f2, ";"]); endif | |
111 eval ([__f1, ";"]); | |
112 | |
113 ## run the tests | |
114 for k=1:length(__test_n) | |
115 if (k > 1) | |
116 n=__test_n(k); | |
117 eval ([__init, ";"]); | |
118 endif | |
119 | |
120 printf ("n%i=%i ",k, n) ; fflush(1); | |
121 | |
122 eval (["__t=time();", __f1, "; __v1=ans; __t = time()-__t;"]); | |
123 if (__t < 0.25) | |
124 eval (["__t2=time();", __f1, "; __t2 = time()-__t2;"]); | |
125 eval (["__t3=time();", __f1, "; __t3 = time()-__t3;"]); | |
126 __t = min([__t,__t2,__t3]); | |
127 endif | |
128 __tnew(k) = __t; | |
129 | |
130 if !isempty(__f2) | |
131 eval (["__t=time();", __f2, "; __v2=ans; __t = time()-__t;"]); | |
132 if (__t < 0.25) | |
133 eval (["__t2=time();", __f2, "; __t2 = time()-__t2;"]); | |
134 eval (["__t3=time();", __f2, "; __t3 = time()-__t3;"]); | |
135 endif | |
136 __torig(k) = __t; | |
137 if !isinf(__tol) | |
138 assert(__v1,__v2,__tol,__err); | |
139 endif | |
140 endif | |
141 | |
142 end | |
143 | |
144 if !isempty(__f2), | |
145 # Don't keep zero times | |
146 idx = find ( __tnew>sqrt(eps) & __torig>sqrt(eps) ) ; | |
147 ratio = mean (__torig(idx) ./ __tnew(idx)); | |
148 if (nargout == 1) | |
149 __ratio_r = ratio; | |
150 else | |
151 printf ("\nmean runtime ratio of %s / %s : %g\n", __f2, __f1, ratio); | |
152 endif | |
153 else | |
154 if (nargout == 1) | |
155 _ratio_r = mean(__tnew); | |
156 else | |
157 printf ("\nmean runtime: %g\n", mean(__tnew)); | |
158 endif | |
159 endif | |
160 | |
161 if (speed_test_plot && nargout == 0 && !isempty(__f2)) | |
162 | |
163 if (gnuplot_has_multiplot) subplot(121); endif | |
164 xlabel("test length"); | |
165 title (__f1); | |
166 ylabel("speedup ratio"); | |
167 semilogx ( __test_n(idx), __torig(idx)./__tnew(idx) , | |
168 ["-*r;", strrep(__f1,";","."), "/", strrep(__f2,";","."), ";"], | |
169 __test_n(idx), __tnew(idx)./__torig(idx) , | |
170 ["-*g;", strrep(__f2,";","."), "/", strrep(__f1,";","."), ";"]); | |
171 if (gnuplot_has_multiplot) | |
172 subplot (122); | |
173 else | |
174 input ("Press any key for the next graph:", "s"); | |
175 endif | |
176 | |
177 ## convert best execution time to milliseconds. | |
178 __torig = 1000*__torig; | |
179 __tnew = 1000*__tnew; | |
180 | |
181 ylabel ("best execution time (ms)"); | |
182 title (["init: ", __init]); | |
183 loglog ( __test_n (idx), __tnew (idx), ["*-g;", strrep(__f1,";","."), ";" ], | |
184 __test_n (idx), __torig (idx), ["*-r;", strrep(__f2,";","."), ";"]) | |
185 title (""); xlabel (""); ylabel (""); oneplot(); | |
186 elseif (speed_test_plot && nargout == 0) | |
187 __tnew = 1000*__tnew; | |
188 xlabel("test length"); | |
189 ylabel ("best execution time (ms)"); | |
190 title ([__f1, " init: ", __init]); | |
191 loglog ( __test_n, __tnew, "*-g;;"); | |
192 title (""); xlabel (""); ylabel (""); oneplot(); | |
193 endif | |
194 | |
195 endfunction | |
196 | |
197 %!demo if 1 | |
198 %! function x = build_orig(n) | |
199 %! ## extend the target vector on the fly | |
200 %! for i=0:n-1, x([1:10]+i*10) = 1:10; endfor | |
201 %! endfunction | |
202 %! function x = build(n) | |
203 %! ## preallocate the target vector | |
204 %! if (prefer_column_vectors), x = zeros(n*10, 1); | |
205 %! else x = zeros(1, n*10); endif | |
206 %! for i=0:n-1, x([1:10]+i*10) = 1:10; endfor | |
207 %! endfunction | |
208 %! | |
209 %! disp("-----------------------"); | |
210 %! type build_orig; | |
211 %! disp("-----------------------"); | |
212 %! type build; | |
213 %! disp("-----------------------"); | |
214 %! | |
215 %! disp("Preallocated vector test.\nThis takes a little while..."); | |
216 %! speed('build', 'build_orig', 1000, 'v=n;'); | |
217 %! clear build build_orig | |
218 %! disp("Note how much faster it is to pre-allocate a vector."); | |
219 %! disp("Notice the peak speedup ratio."); | |
220 %! clear build build_orig | |
221 %! endif | |
222 | |
223 %!demo if 1 | |
224 %! function x = build_orig(n) | |
225 %! for i=0:n-1, x([1:10]+i*10) = 1:10; endfor | |
226 %! endfunction | |
227 %! function x = build(n) | |
228 %! idx = [1:10]'; | |
229 %! x = idx(:,ones(1,n)); | |
230 %! if (prefer_column_vectors), x = reshape(x, n*10, 1); | |
231 %! else x = reshape(x, 1, n*10); endif | |
232 %! endfunction | |
233 %! | |
234 %! disp("-----------------------"); | |
235 %! type build_orig; | |
236 %! disp("-----------------------"); | |
237 %! type build; | |
238 %! disp("-----------------------"); | |
239 %! | |
240 %! disp("Vectorized test. This takes a little while..."); | |
241 %! speed('build', 'build_orig', 1000, 'v=n;'); | |
242 %! clear build build_orig | |
243 %! disp("-----------------------"); | |
244 %! disp("This time, the for loop is done away with entirely."); | |
245 %! disp("Notice how much bigger the speedup is then in example 1."); | |
246 %! endif |