Using Circular Buffers as mutable.ArrayBuffer

Scala Standard Library
1

Circular-buffers are very simple data structures that uses a start and end pointers on a resizable-array which provides strictly better performance than vanilla resizable arrays. Specifically, without sacrificing space and implementation complexity, clear(), prepend(), trimStart() and trimEnd() and removes from start or end become constant-time and all other operations stay the same complexity.

I have a working example with tests here:

import scala.collection.mutable
import scala.reflect.ClassTag

/**
  * A data structure that provides O(1) get, update, length, append, prepend, clear, trimStart and trimRight
  * @tparam A
  */
class CircularBuffer[A: ClassTag](initialSize: Int = 1<<4) extends mutable.Buffer[A] {
  private var array = Array.ofDim[A](initialSize)
  private var start, end = 0

  override def apply(idx: Int) = {
    checkIndex(idx)
    array(mod(start + idx))
  }

  override def update(idx: Int, elem: A) = {
    checkIndex(idx)
    array(mod(start + idx)) = elem
  }

  override def length = mod(mod(end) - mod(start))

  override def +=(elem: A) = {
    ensureCapacity()
    array(mod(end)) = elem
    end += 1
    this
  }

  override def clear() = start = end

  override def +=:(elem: A) = {
    ensureCapacity()
    start -= 1
    array(mod(start)) = elem
    this
  }

  override def prependAll(xs: TraversableOnce[A]) =
    xs.toSeq.reverse.foreach(x => x +=: this)

  override def insertAll(idx: Int, elems: Traversable[A]) = {
    checkIndex(idx)
    if (idx == 0) {
      prependAll(elems)
    } else {
      val shift = (idx until size).map(this)
      end = start + idx
      this ++= elems ++= shift
    }
  }

  override def remove(idx: Int) = {
    val elem = this(idx)
    remove(idx, 1)
    elem
  }

  override def remove(idx: Int, count: Int) = {
    checkIndex(idx)
    if (idx + count >= size) {
      end = start + idx
    } else if (count > 0) {
      if (idx == 0) {
        start += count
      } else {
        ((idx + count) until size).foreach(i => this(i - count) = this(i))
        end -= count
      }
    }
  }

  /**
    * Trims the capacity of this CircularBuffer's instance to be the current size
    */
  def trimToSize(): Unit = resizeTo(size)

  override def iterator = indices.iterator.map(apply)

  override def trimStart(n: Int) = if (n >= size) clear() else if (n >= 0) start += n

  override def trimEnd(n: Int) = if (n >= size) clear() else if (n >= 0) end -= n

  override def head = this(0)

  override def last = this(size - 1)

  private def mod(x: Int) = Math.floorMod(x, array.length)

  private def resizeTo(len: Int) = {
    require(len >= size)
    val array2 = Array.ofDim[A](len)
    val (l, r) = (mod(start), mod(end))
    if (l <= r) {
      Array.copy(src = array, srcPos = l, dest = array2, destPos = 0, length = size)
    } else {
      val s = array.length - l
      Array.copy(src = array, srcPos = l, dest = array2, destPos = 0, length = s)
      Array.copy(src = array, srcPos = 0, dest = array2, destPos = s, length = r)
    }
    end = size
    start = 0
    array = array2
  }

  private def checkIndex(idx: Int) = if(!isDefinedAt(idx)) throw new IndexOutOfBoundsException(idx.toString)

  private def ensureCapacity() = if (size == array.length - 1) resizeTo(2 * array.length)
}

I propose we replace the current implementation of mutable.ArrayBuffer with CircularBuffers. I filed SI-10167. Thoughts?

5 Likes
2

That seems an interesting idea.

However, accessing or updating an element requires one more addition and one modulo* operation, on top of the bound checks. In fact, you’re using floorMod which seems slower— and since its argument seems always positive you should be able to use % (which isn’t fast, though).

To use this to replace ArrayBuffer (instead of adding to it) one would have to ensure the overhead is negligible, even when the memory access cost is minimal (e.g. when the entire array is in L1 cache). That’s far from obviously true.

However, the expert on these matters is @Ichoran, so let me defer to him.

3

I think that’s an interesting idea! The timing is good as a group of us are currently working on a strawman design for new collections. You might add an issue (or, even better, a PR) here:

https://github.com/scala/collection-strawman

2 Likes
4

How about adding a new CircularBuffer collection alongside ArrayBuffer?

The other question is whether to make it the default mutable Seq. That would probably be less of an issue since if you’re relying on characteristics of ArrayBuffer you should be explicitly using that class anyway.

2 Likes
5

Yeah, that sounds like the right tack to me. As @Blaisorblade points out, the characteristics aren’t identical, and folks have established expectations of ArrayBuffer, so replacing the implementation with an entirely different data structure seems a bit iffy to me – not least, because a circular buffer isn’t what I expect an implementation of “array buffer” to be.

But adding it as a new data structure seems totally uncontroversial, and potentially quite useful. And making it the default mutable Seq is an intriguing idea, although I can’t say I’ve got a handle on all the ramifications there…

2 Likes
6

Although my very naive benchmarks did not show any regressions (obviously the prepend and trims are constant time now) from mutable.ArrayBuffer, I agree with you. floorMod was introduced in Java 8 so we can get rid of it especially as the second argument is positive here. Also, if we always allocate arrays whose sizes are powers of 2, its trivial to calculate mod: x mod y = x & (y -1) when y is power of 2.

2 Likes
7

It’s critical (and less obvious) that also the first argument is non-negative — -1 % 10 = -1, unlike with floorMod.

Sounds excellent—and that works even for negative x. Power-of-2 sizes are sufficient to ensure the asymptotic complexity. There’s no point in non-power-of-2 sizes, as long as you always double the size when resizing.

In fact, if you want to trade off time for space (in constant factors, not asymptotically), you can multiply the array size by any number > 1 — 2 is just the standard choice, but any factor works, while adding a constant to the size doesn’t. Picking less than 2 reduces the maximum amount of empty slots but makes resizes more frequent. IIRC, the Cormen book has the details. I don’t remember many resizable arrays offering this amount of control so I’d leave it out and stick to power-of-2 sizes.

Last nitpick: for better constant factors, you want to use Java’s arraycopy inside resize, since that does a single boundary check for the entire operation.

9

If this is to become a bit more generic it could be considered dimensions like in an array. As new values are added the dimension rolls around. But since more usages will be 1D, 2D, 3D maybe you can have a 1D, 2D, 3D optimised special case.

E.g. https://docs.scipy.org/doc/numpy/reference/generated/numpy.roll.html

10

Forgive me if I’m wrong, but the data structure described is not a Circular Buffer, because Circular Buffers are not growable.

A circular buffer, circular queue, cyclic buffer or ring buffer is a fixed size queue that on overflow will throw an exception, or drop either the head or the entire buffer. Source: https://en.wikipedia.org/wiki/Circular_buffer - and making it growable does not necessarily make it more useful, because the fixed size (and consequently its behaviour on overflow) is the whole point.

I do have simple implementations for such circular buffers for reference:

  1. for dropping the head: DropHeadOnOverflowQueue
  2. for dropping the entire buffer: DropAllOnOverflowQueue

Also, the most famous implementation is the Disruptor.

I concede that I might be wrong and there are people here knowing much more than I do.

But if I am correct please don’t overload the term, because having precise meanings for CS notions is useful.

Thanks,

1 Like
11

Good point. Actually, in general “buffer” tends to refer to fixed-length data structures, so ArrayBuffer and Buffer in Scala maybe aren’t the best names either. In JavaScript for example ArrayBuffer is a fixed-length raw data buffer. But it may be too late to change the terminology in Scala.

ArrayDeque might be a good name for the “resizing circular buffer” structure. Deques do normally resize, so it’s a deque that also behaves like an array. In Java ArrayDeque uses a circular buffer internally, though it does not provide random access to elements.

I guess we could also call it ArraySeqDeque, since it’s capable of behaving like a Seq and deque, and it’s implemented as an array, but I prefer ArrayDeque.

3 Likes
12

I think a growable, mutable circular buffer, as a general purpose mutable data structure, is a wonderful idea.

Whether we call it a “circular buffer” or something else doesn’t really matter to me. Both growable and non-growable circular buffers would be valuable, but non-growable circular buffers are a more specific use case where-as growable circular buffers can replace all sorts of things:

  • mutable.Buffer
  • mutable.Queue
  • mutable.Stack

After all, growable circular buffers are basically Deques, and provide really fast adding/removing at the start/end. This is in addition to providing similar performance characteristics to a normal growable-array buffer for normal growable-array operations (indexed-lookup, iteration, indexed-replacement, …), , without much implementation complexity.

For what it’s worth, I have wanted this enough that I have implemented it twice already:

I think a growable circular buffer would be a wonderful general-purpose mutable data structure, and would serve well as a “default” mutable data structure.

2 Likes
13

I agree with everything you said, I felt the need for it myself, I just think we shouldn’t use the name Circular Buffer. Name it something else please. ArrayDeque for example is probably fine and more specific, as many users know what a Deque is and they’ll immediately see it’s backed by an Array, so cool, it means it has good traversal / indexing performance, etc.

2 Likes
14

ArrayDeque (or something like that) sounds indeed like an improvement—that name is also used by C++'s STL (http://www.cplusplus.com/reference/deque/deque/). I was also confused I hadn’t seen this before—I just wasn’t recognizing a deque because of the name (and because I last saw them ages ago). And calling this a ring buffer confused me too — ring buffers are what you need, for instance, when you receive video streaming.

15

FWIW, Wikipedia also mentions growing circular buffers here.

Another alternative to “growable circular buffers” are hashed array trees. They are also very simple - basically instead of doubling allocation and copying when full, we allocate a fixed block each time we reach capacity. They are asymptotically as fast as “growable circular buffers” but only allocates O(sqrt(n)) extra space instead of O(n/2) extra space. In practice random-access might be slightly slower because of locality.

16

They compare more to normal ArrayBuffer—head insertions aren’t O(1) but O(n). I’m not sure they should be in the core—but a goal of the new collection libraries, IIRC, is to simplify creating new Scala collections.

18

I have a PR ready for strawman-collections: https://github.com/scala/collection-strawman/pull/49

3 Likes
19

I agree with you re: the name, CircularBuffer, I would usually associate it with the ‘Disruptor’ and other implementations. Where I’ve seen it used (algos) it has traditionally been a fixed size/lockless data structure.

20

I have a question - should this go in Scala 2.13 or Scala 2.12.x?

The code can be easily put into Scala 2.12 - https://github.com/scala/collection-strawman/pull/49/files

The only thing is binary compatibility against Scala 2.12.0 - does adding an extra class matter? If yes, can we introduce this as a private class and just change mutable.{Queue, Stack, Buffer} to use this instead?

21

The pull request for this is ready for full review:

Also provided some proof of concept implementations of Stacks and Queues using this data structure.

Preliminary benchmarks look great but soliciting additional code reviews and benchmarking.