[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: False alarm (Re: reshape slowdown?)
From: |
Paul Kienzle |
Subject: |
Re: False alarm (Re: reshape slowdown?) |
Date: |
Wed, 23 Feb 2005 08:04:53 -0500 |
On Feb 23, 2005, at 6:07 AM, address@hidden wrote:
After reading your mails, I cheched the timing on my box (Celeron
600 MHz with 320 Mbyte RAM/Debian 3.1 testing, kernel 2.4,
Octave 2.1.57).
s=rand(3000);
tic, s'; toc
ans = 8.18339100014418 !!!
Is this the normal difference between the two distibutions or
something is utterly wrong with my computer/operation system
installation/octave installation ?
I get the same result on my 1G PPC with 512 Mb with octave 2.1.55.
The results hold across a wide range of sizes. An increase in speed
as the array gets bigger until the operation time becomes significant
then a decrease as big-O effects take over.
The following shows the big-O effects on my machine.
n=15;
t=zeros(1,n);
d=ceil(logspace(2.3,3.5,n));
for i=1:n, s=rand(d(i)); tic; s'; t(i) = toc; end
loglog(d,t,'-x;;')
wpolyfit(log10(d.^2),log10(t),1)
The fit is excellent, and shows O(d^2.37) behaviour.
Replacing s' with s+1 shows O(d^2) behaviour.
Looking at octave CVS, the code is:
Array<T> result (dim_vector (nc, nr));
for (int j = 0; j < nc; j++)
for (int i = 0; i < nr; i++)
result.xelem (j, i) = xelem (i, j);
This algorithm is O(d^2). Assuming it hasn't changed since 2.1.55,
presumably the details of the timing have to do with cache sizes
and other hardware and OS details rather than the algorithm.
The behaviour on my linux box with octave 2.1.64 is more like what
I expect: an increase in speed as the array gets bigger, a constant
speed while the array is in memory, and a rapid decrease once
virtual memory comes into play.
- Paul
-------------------------------------------------------------
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
-------------------------------------------------------------
- reshape slowdown?, Dmitri A. Sergatskov, 2005/02/21
- Re: reshape slowdown?, David Bateman, 2005/02/22
- Re: reshape slowdown?, John W. Eaton, 2005/02/22
- False alarm (Re: reshape slowdown?), Dmitri A. Sergatskov, 2005/02/22
- False alarm (Re: reshape slowdown?), John W. Eaton, 2005/02/22
- Re: False alarm (Re: reshape slowdown?), Dmitri A. Sergatskov, 2005/02/22
- Re: False alarm (Re: reshape slowdown?), Francesco Potorti`, 2005/02/23
- Re: False alarm (Re: reshape slowdown?), mavram, 2005/02/23
- Re: False alarm (Re: reshape slowdown?),
Paul Kienzle <=
- Re: False alarm (Re: reshape slowdown?), Dmitri A. Sergatskov, 2005/02/25
- Re: False alarm (Re: reshape slowdown?), John W. Eaton, 2005/02/23