Thread Subject:

circshift is 50 times slower than using a loop

Matias Nordin pointed on a recent thread that circshift can be very slow.
I recently came across this fact in a different application, in which I need to do circshifts
repeatedly on a modestly sized 1D array. So I did some tests, see code below.
Amazingly it seems that for a 1D array of size 100, Matlab's circshift is 50 times slower than simply using a loop. Even using Matlab's colon notation directly is slower than a loop.
For larger arrays the colon notation is the fastest method.
I have not tried shifts by more than 1 place though I expect it would be similar.
For 2D arrays the effect is still there, though less extreme.
For circshift the CPU time hardly depends on the array size, indicating a significant startup overhead as the Matlab code does some checks on the array.
On my Linux PC this startup time is about 0.2ms.
The message seems to be that you should never use circshift!


% CHECK SPEED OF CIRCSHIFT VS OTHER METHODS. PCM 23/6/09

clear
n=100;nloop=10000;
x=linspace(-1,1,n);
u=sin(pi*x);

% CIRCSHIFT - VERY SLOW
t=cputime;
for j=1:nloop
   uc=circshift(u,[0,1]);
end
time_circshift=cputime-t

% LOOP - MUCH FASTER - FASTEST IF n < 250
t=cputime;
for j=1:nloop
   for k=2:n; ul(k)=u(k-1);end;ul(1)=u(n);
end
time_loop=cputime-t

% MATRIX MULTIPLY
t=cputime;
shiftmat=diag(ones(n-1,1),1);shiftmat(n,1)=1;
for j=1:nloop
   um=u*shiftmat;
end
time_matrix=cputime-t

% SPARSE MATRIX MULTIPLY - FASTEST IF 250 < n < 600
t=cputime;
shiftmatsparse=sparse(shiftmat);
for j=1:nloop
   ums=u*shiftmatsparse;
end
time_sparse_matrix=cputime-t

% MATLAB COLON NOTATION - FASTEST IF n > 600
t=cputime;
for j=1:nloop
   us=[u(n) u(1:n-1)];
end
time_colon=cputime-t

checks=[norm(ul-uc),norm(ul-um),norm(ul-ums),norm(ul-us)]

In article <h1ql1h$p8s$1@fred.mathworks.com>, etzpcm@gmail.com says...
> Matias Nordin pointed on a recent thread that circshift can be very slow.
> I recently came across this fact in a different application, in which I need to do circshifts
> repeatedly on a modestly sized 1D array. So I did some tests, see code below.
> Amazingly it seems that for a 1D array of size 100, Matlab's circshift is 50 times slower than simply using a loop. Even using Matlab's colon notation directly is slower than a loop.
> For larger arrays the colon notation is the fastest method.
> I have not tried shifts by more than 1 place though I expect it would be similar.
> For 2D arrays the effect is still there, though less extreme.
> For circshift the CPU time hardly depends on the array size, indicating a significant startup overhead as the Matlab code does some checks on the array.
> On my Linux PC this startup time is about 0.2ms.
> The message seems to be that you should never use circshift!
>

FYI, circshift is doing some error checking and your other codes do not.
also, you are timing lots of small (length 100) circshifts so the error
checking counts a lot. If you time fewer iterations of larger arrays,
your results will likely differ and come a bit closer.

--
Loren
http://blogs.mathworks.com/loren