# Efficient circular buffer?

I wish to create an efficient circular buffer. That is, I wish to keep a fixed length list while appending a new value and dropping the oldest, repeatedly.

As we know lists in Mathematica are implemented as arrays and Append etc. are slow on long lists. For example:

big = Range@1*^7;

Do[big = Append[Rest@big, RandomInteger@99], {100}] // AbsoluteTiming


{2.2100031, Null}

InternalBag and related functions are appropriate for a continually accumulating list but do not appear to be applicable to this situation.

Is there an efficient means to have a large circular buffer in Mathematica?

-
I think Append is slow because it is functional, i.e. it copies original and return a modified copy, remaining argument intact. – Suzan Cioc Jan 19 '13 at 19:37
Your circular buffer sounds to me like a queue. I don't know whether a queue can be faster than a list. You might play with Lichtbau's code ((library.wolfram.com/conferences/devconf99/lichtblau/Links/…) to find out. – DavidC Jan 19 '13 at 20:22
How about using linkedlist of java? – s.s.o Jan 19 '13 at 20:38
Unqueuing The @dude's link together with the style of Leonids file-backed lists for integration with normal syntax might do for something pretty – ssch Jan 19 '13 at 20:40
@s.s.o Too much overhead for JLink Java method calls. I tested it a few times having in mind similar problems. – Leonid Shifrin Jan 19 '13 at 21:05

You can implement an imperative-style circular buffer.

big = Range@1*^7;
size = Length@big;
pointer = size;
updateElement[new_Integer] := (pointer = 1 + Mod[pointer, size]; big[[pointer]] = new)

Do[updateElement[RandomInteger@99], {100}] // AbsoluteTiming


{0.000374, Null}

To bring the buffer back to the normal form use

big = RotateLeft[big, Mod[pointer, size]]; // AbsoluteTiming
pointer = size;


{0.034542, Null}

If you don't need a list to be in the normal form on each step this could be 10^4 times faster than Append[Rest[...]]

Do[big = Append[Rest@big, RandomInteger@99], {100}] // AbsoluteTiming


{5.884157, Null}

-
You beat me to it, +1. – VF1 Jan 19 '13 at 22:22
Really nice solution, clean and simple! +1 – sebhofer Jan 20 '13 at 2:07
Nick, I held off Accepting this for a long time because my envisioned application does require the list in normal form at each step, which means this isn't faster, and I was curious to see if any other methods would be suggested. However, for the question as written this is excellent, so a belated Accept and +1! :-) – Mr.Wizard Mar 18 '13 at 5:54

You can hold circular buffer in global variable and write functions to modify it.

Something like this

In[29]:= Circular = {{}, 1, 1}

Out[29]= {{}, 1, 1}

In[30]:= SetCircularSize[x_] := Circular[[1]] = ConstantArray[0, x];

In[31]:= SetCircularSize[10]

Out[31]= {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

In[32]:= Circular

Out[32]= {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 1, 1}

In[34]:= AppendCircular[x_] := Block[{},
Circular[[1, Circular[[3]]++]] = x;
(* manage indice *)
];

In[35]:= AppendCircular[12]

In[36]:= Circular

Out[36]= {{12, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 1, 2}

In[37]:= AppendCircular[17]

In[38]:= Circular

Out[38]= {{12, 17, 0, 0, 0, 0, 0, 0, 0, 0}, 1, 3}

-
Wait... I feel like I'm missing something here. Wouldn't that just produce an error once you get to the end of Circular[[1]]? And what's Circular[[2]] good for? – sebhofer Jan 20 '13 at 1:59
Yes, but I hadn't finish the work. You should develop the idea. Upon reaching the end of list you should wrap index accordingly. Also you should drag tail index. – Suzan Cioc Jan 20 '13 at 12:39

Whenever I'm looking for something akin to mutability I can typically get by via storing things in downvalues of variables. Here is a simple version of your ciruclar buffer that just writes the values to the downvalues of a unique symbol, and instead of passing the actual values around pass a small object of the form: buffer[var,n,l], where var is the symbol used for storage, n is the current location, and l is the length of the buffer.

SetAttributes[buffer, HoldAll];
newBuffer[n_] := Unique[] // buffer[#, 1, n] &;

append[buffer[var_, n_, l_], value_] :=
(var[n] = value; buffer[var, #, l] &@Mod[n + 1, l, 1])

read[buffer[var_, n_, l_], m_] /; 1 <= n <= l := var[Mod[m - n + 1, l, 1]]


Then you can create a new buffer and fill it up with values:

bigBuffer = newBuffer[1*^7];
i = 1;
fullbuffer = Nest[append[#, i++] &, bigBuffer, 1*^7];


And then add new values as:

Do[fullbuffer =
append[fullbuffer, RandomInteger@99], {100}] // AbsoluteTiming
(* {0.001000, Null} *)


To compare your orignal test on my system is:

big = Range@1*^7;
Do[big = Append[Rest@big, RandomInteger@99], {100}] // AbsoluteTiming
{5.430311, Null}


With this implementation you'll still have a unnecessary copying of the object used to represent the buffer, but it's very small, and if you really wanted to avoid copying it, n could similarly be stored as a down-value of the symbol (using var["current"] for instance). This might be a good idea anyway, as that avoids spawning off different objects that point to different locations in the buffer.

-

I agree with a previous comment that this sounds like a queue. The following solution uses the JVMTools package, and the queue creation is done with Scala.

Get@ToFileName[{$HomeDirectory,"JavaTools"},"JavaTools.m"]  Define the queue creation and insertion of initial data in Scala, compile it, and set up the symbol q for later use: ScalaCode["def q(initial:Array[Int])= { var lq=new scala.collection.mutable.Queue[Int] lq ++= initial lq }"]  Use it and create a new queue with a 10 million range: myq =q[Range@10000000]  To enfore the fixed size we write a simple wrapper for the enqueue method. If the limit is reached, dequeue the first element before insertion, otherwise insert directly: enq[elem_]:=With[{}, If[myq@length[]>=10000000, myq@dequeue[] ]; myq[($plus\$eq)[MakeJavaObject@elem]]
];


For dequeue we don't need a wrapper, we can use the dequeue method of the Queue class directly:

myq@dequeue[]


First element (only peeks at the first element without removing it, as dequeue does):

myq@front[]


Last element (without removal):

myq@last[]


Length:

myq@length[]
`

Explanations, in no particular order:

• I generally prefer Scala over Java for various reasons, too numerous to write down here. However, JVMTools supports Java code as well (and C# and F#). I could also have used Java's LinkedList here, or a queue class from .Net.
• JVMTools uses JLink, and JLink (qua MathLink) ensures that primitive arrays (here: array of Integers) are passed as one chunk, not element by element, so there is no worry of slowing things down when passing the range of 10 million integers that the o/p uses (basically JLink manages MathLink, and with MathLink you get native speed for primitive arrays). Every subsequent insertion is assumed to be element by element (lists could also be inserted with ++=, again using native speed, not shown here).
• The enqueue method of Scala's mutable Queue is constant time, thus very efficient.
• Scala's Queue class has an enormous plethora of methods (incl. filtering, mapping, comparison, sorting, slicing, iterating, etc., see the ScalaDoc here), giving the programmer another set of tools that are already written, instead of having to write them yourself. The o/p doesn't mention a requirement of additional queue management features, but I mention it to underscore the power and flexibility of using Scala's queue class, running in the JVM.
• I generally like to outsource huge data sets to the JVM, I don't like to have that in the kernel. The JVM is truly tested and VERY memory-stable, runs on 3 billion devices, and has an automatic garbage collector (thus, when the queue is no longer needed, the garbage collector frees up the allocated memory pretty quickly).
-
If the problem is really about initializing the queue with a range of integers, and not arbitrary integers, we could speed this up further by not even passing the initial ten million integers over with JLink/MathLink, but I assume the initial range is only an example. Otherwise we could do that in Scala as well and not in M, getting these execution times down to 0. – Andreas Lauschke Jan 20 '13 at 5:32