Is there a faster way to implement a FIFO (queue) ?

Hi, I was wondering if somebody could comment on my use of array indexing. I have a recursive function which uses some initial conditions passed in. I use it in the following manner.

ic = [x_i ic(1:end-1)];

ic is a long vector. x_i is a double.

This line seems to be taking a lot of execution time, about 50% of the total time Matlab spends in this function (using Profiler). The rest of the code is set of vectorized computations; I believe they are as fast as they can be.

I made one small adjustment and it made it a bit faster.

ic(2:end) = ic(1:end-1);
ic(1) = x_i;

This improved the execution time and these two lines take 40% of the total execution time of the function.

Could anybody suggest any better way of implementing this FIFO array.

Thanks for your time and comments.

[Brian Harris]

See this answer: Fast FIFO Array. The circleshift one (which is really just to realign the last answer) is fast because its just a moving pointer "ic=mod(i,Nmax+i)" so doens't move anything. Its really just a circular buffer.

Answer 1

[Bruno Luong]

If you don't need to retreive the whole FIFO in order, but read and write element by element, then the best way is NOT rearrange the FIFO buffer

FIFO=nan(1,1000);
n = length(FIFO);

nbreadwrte = 1e6;
% Use index to mark place of the oldest element
tic
for i=1:nbreadwrte
    % readcell
    oldout = FIFO(mod(i-1,n)+1);
    newin = rand(1);
    % write, recent MATLAB do inplace change of internal data
    FIFO(mod(i-1,n)+1) = newin;
end
toc

Elapsed time is 0.125412 seconds.

tic
for i=1:nbreadwrte
    % readcell
    oldout = FIFO(1);
    newin = rand(1);
    % write
    FIFO = [newin FIFO(1:end-1)];
end
toc

Elapsed time is 1.157002 seconds.

for i=1:nbreadwrte
    % readcell
    oldout = FIFO(1);
    newin = rand(1);
    % write
    FIFO(2:end) = FIFO(1:end-1);
    FIFO(1) = newin;
end
toc

Elapsed time is 2.945253 seconds.