Circular buffer in MATLAB, **without** copying old data

Question

There are some good posts on here (such as this one) on how to make a circular buffer in MATLAB. However from looking at them, I do not believe they fit my application, because what I am seeking, is a circular buffer solution in MATLAB, that does NOT involve any copying of old data.

To use a simple example, let us say that I am processing 50 samples at a time, and I read in 10 samples each iteration. I would first run through 5 iterations, fill up my buffer, and in the end, process my 50 samples. So my buffer will be

[B1 B2 B3 B4 B5]

, where each 'B' is a block of 10 samples.

Now, I read in the next 10 samples, call them B6. I want my buffer to now look like:

[B2 B3 B4 B5 B6]

The catch is this - I do NOT want to copy the old data, B2, B3, B4, B5 everytime, because it becomes expensive in time. (I have very large data sets).

I am wondering if there is a way to do this without any copying of 'old' data. Thank you.

Answer 1

One way to quickly implement a circular buffer is to use modulus to circle back around to the front. This will slightly modify the order of the data from what you specified but may be faster and equivalent if you simply replace the oldest data with the newest so instead of

[B2 B3 B4 B5 B6]

You get

[B6 B2 B3 B4 B5]

By using code like this:

bufferSize = 5;

data = nan(bufferSize,1)';

for ind = 1:bufferSize+2  

    data(mod(ind-1, bufferSize)+1) = ind

end

and this works for arbitrary sized data.

If you're not familiar with modulo, the mod function returns effectively the remainder of a division operation. So mod(3,5) returns3, mod(6,5) returns 1, mod(7,5) returns 2 and so on until you reach mod(10,5) which equals 0 again. This allows us to 'wrap around' the vector by moving back to the start every time we reach the end. The +1 and -1 in the code is because MATLAB starts its vector indices at 1 rather than 0 so to get the math to work out right you have to remove 1 before doing the mod then add it back in to get the right index. The result is that when you try and write the 6th element to your vector is goes and writes it to the 1st position in the vector.

Answer 2

My idea would be to use a cell-array with 5 entries and use a variable to index the sub-array which should be overwritten in the next step. E.g. something like

 a = {ones(10),2*ones(10),3*ones(10),4*ones(10),5*ones(10)};
 index = 1;

in the next step you could then write into the sub-array:

 a{index} = 6*ones(10);

and increase the index like

index = index+1

Obviously, some sort of limitation:

if(index > 5) % FIXED TYPO!!
   index = 1;
end

Would that be for you?

EDIT: One more thing to look at would be the sortation of the entries which would therefore always be shifted by some entries but depending on how you keep on using the data, you could e.g. shift the usage of the data depending on the variable index.

EDIT2: I've got another idea: What about using classes in MATLAB. You could use a handle-class to hold your data thus using the buffer to only reference to the data. This might make it a bit faster, depending on what data (how large the datasets are etc) you hold and how many shifts you'll have in your code. See e.g. here: Matlab -- handle objects

You could use a simple handle class:

classdef Foo < handle   
    properties (SetAccess = public, GetAccess = public)
        x
    end

    methods
        function obj = foo(x)
            % constructor
            obj.x = x;
        end 
    end       
end

Store the data in it:

data = [1 2 3 4];
foo = Foo(data);  % handle object

and then only store the object-reference in the circular buffer. In the posted link the answer shows that the assignment bar = foo doesn't copy the object but really only helds the reference:

foo.x = [3 4]
disp(bar.x)      % would be [3 4]

but as stated, I don't know if that will be faster because of the OOP-overhead. It might be depending on your data... And here some more information about it: http://www.matlabtips.com/how-to-point-at-in-matlab/

Answer 3

I just uploaded my solution for a fast circular buffer to which does not copy old data

http://www.mathworks.com/matlabcentral/fileexchange/47025-circvbuf-m

The main idea of this circular buffer is constant and fast performance and avoiding copy operations when using the buffer in a program:

% create a circular vector buffer
    bufferSz = 1000;
    vectorLen= 7;
    cvbuf = circVBuf(int64(bufferSz),int64(vectorLen));

% fill buffer with 99 vectors
    vecs = zeros(99,vectorLen,'double');
    cvbuf.append(vecs);

% loop over lastly appended vectors of the circVBuf:
    new = cvbuf.new;
    lst = cvbuf.lst;
    for ix=new:lst
       vec(:) = cvbuf.raw(:,ix);
    end

% or direct array operation on lastly appended vectors in the buffer (no copy => fast)
    new = cvbuf.new;
    lst = cvbuf.lst;
    mean = mean(cvbuf.raw(3:7,new:lst));

Check the screenshot to see, that this circular buffer has advantages if the buffer is large, but the size of data to append each time is small as the performance of circVBuf does NOT depend on the buffer size, compared to a simple copy buffer.

The double buffering garanties a predictive time for an append depending on the data to append in any situation. In future this class shall give you a choice for double buffering yes or no - things will speedup, if you do not need the garantied time.