10 CommentsOldest to Newest
Wouldn’t that solution force the entire array to be reshuffled every time a new value is added?
Like Petter, I wonder if this should be considdered an efficient implementation or only an easy one?
I use a few rinbuffers here and there and they are all implemented like this, because it is easy. However, the line buffer = [newValue buffer(1:end-1)] gives the optimizer in me the shivers. Is that just me?
I profiled this with a really large amount of data, more iterations and longer buffer. That part of the video is on the “cutting room floor”. Basically, there is a negligible performance hit. To be a real test, it would need to be done in context to see if this architecture is a problem.
This video is in keeping with one of the central themes of my programming style: “Avoid premature optimization”. If I were to try and avoid the churn that this circular buffer goes through, the complexity and readability would suffer.
I am not sure if this is still relevant but yes the discussed implementation is very inefficient. I have created a buffer class in matlab because I need multiple
circular buffers. This buffer class implements the buffer, display, and subsref functions in matlab code and the push_front and push_back functions in c code. This is because you cannot pass arguments by reference in Matlab. Matlab only makes a copy of the arguments when the arguments change inside a m file. But since you add an element to the buffer Matlab does make a copy. In a c mex implementation this does not happen and one can efficiently add a new element. Also I use a double length circular buffer to allow for linear adressing instead of circular buffer adressing
This is the kind of thing that makes an excellent MATLAB Central File Exchange entry if you are willing to share.
Remco—I recently implemented a double-ended queue class using a circular buffer. Because I subclassed handle, no data copies are made. My push_front and push_back (don’t remember if I actually used those names) manipulate an internal circular buffer directly. A copy gets made only when the buffer gets full and has to be resized, but that happens in a C++ implementation as well.
For anyone who is looking to create a buffer “Matrix” instead of an Array(nx1 or 1xn matrix), the code can be modified to:
buffSize = 10;
circBuff = nan(3,buffSize);
for newest = 1:1000;
circBuff = [circBuff(1,2:end) newest; circBuff(2,2:end) newest; circBuff(3,2:end) newest; ]
I just uploaded my solution for a fast circular buffer to
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));
For a better circular buffer I implemented different ways to append values.
For small buffers using the simple method of copy-all is the fastest.
Depending on the buffer size I want to allow different append functions to be used, but it seems as if I cannot reach to the speed of the copy-all method if the buffer is a property of a class:
a) obj.raw = [ obj.raw(2:end,:); vec(:) ] b) raw = [ raw(2:end,:); vec(:) ]
‘a’ takes twice as much time in matlab 2014a as ‘b':
It seems to me as if matlab makes an internal copy when using ‘a’, which it does not when using ‘b’.
But in OO programming I cannot avoid ‘a’ and switch to ‘b’.
Any idea how to speedup ‘a’?
Different impementations for a circular buffers including speedtests for comparison can be found in circVBuf on Matlab Central.
The problem described in the last comment got fixed lately.