Re: False alarm (Re: reshape slowdown?)

[Paul Kienzle]

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
-------------------------------------------------------------