programming - 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}

Internal`Bag 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?

Answer

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}