scala collections circular buffer

Question

Just messing about here, with circular buffers. Is this a sensible implementation or is there a faster/more reliable way to skin this cat?

class CircularBuffer[T](size: Int)(implicit mf: Manifest[T]) {

    private val arr = new scala.collection.mutable.ArrayBuffer[T]()

    private var cursor = 0

    val monitor = new ReentrantReadWriteLock()

    def push(value: T) {
      monitor.writeLock().lock()
      try {
        arr(cursor) = value
        cursor += 1
        cursor %= size
      } finally {
        monitor.writeLock().unlock()
      }
    }

    def getAll: Array[T] = {
      monitor.readLock().lock()
      try {
        val copy = new Array[T](size)
        arr.copyToArray(copy)
        copy
      } finally {
        monitor.readLock().unlock()
      }
    }
  }

Since your buffer is fixed size, use an `Array` as internal representation. — gzm0, Apr 30 '13 at 16:30
You should also take a look at the disruptor, it's basically a circular buffer https://github.com/LMAX-Exchange/disruptor — Noah, Apr 30 '13 at 16:31
gzm0, I didn't want to allocate the entire space, up-front. That's why I've got an upper bound on size but use an ArrayBuffer internally. Is that a bad idea? — irishjava, May 01 '13 at 15:36

Ramón J Romero y Vigil · Answer 1 · 2019-01-30T12:11:56.160

Creation

A type declaration to an existing scala collection class and an appender function is easier to implement than "rolling your own". As noted in the comments this implementation will likely not be as performant as a "true" circular buffer, but it gets the job done with very little coding:

import scala.collection.immutable

type CircularBuffer[T] = immutable.Vector[T]

def emptyCircularBuffer[T] : CircularBuffer[T] = immutable.Vector.empty[T]

def addToCircularBuffer[T](maxSize : Int)(buffer : CircularBuffer[T], item : T) : CircularBuffer[T]  =
  (buffer :+ item) takeRight maxSize

This means that your "CircularBuffer" is actually a Vector and you now get all of the corresponding Vector methods (filter, map, flatMap, etc...) for free:

var intCircularBuffer = emptyCircularBuffer[Int]

//Vector(41)
intCircularBuffer = addToCircularBuffer(2)(intCircularBuffer, 41)

//Vector(41, 42)
intCircularBuffer = addToCircularBuffer(2)(intCircularBuffer, 42)

//Vector(42, 43)
intCircularBuffer = addToCircularBuffer(2)(intCircularBuffer, 43)

//Vector(42)
val evens : CircularBuffer[Int] = intCircularBuffer filter ( _ % 2 == 0)

Indexing

You can similarly add a function for circular indexing:

def circularIndex[T](buffer : CircularBuffer[T])(index : Int) : T = 
  buffer(index % buffer.size)

Just a note: One reason for using a circular buffer is to avoid the memory churn of constantly allocating new arrays of buffer and dropping the old. Using an underlying `Vector` is exactly equivalent to this strategy of allocating arrays to hold new elements and then dropping the arrays when old elements are dequeued. If this is acceptable, and you want to drop data rather than blocking when the buffer is full, this implementation will work—but a real circular buffer will perform better if you're going to process a lot of data. — Sarah G, May 11 '18 at 05:39
@SarahG Noted. I agree that true circular buffer would perform better than my implementation but given the way that the JVM recycles memory, and the way Vectors allocate memory, I do not think the improvement is more than an order of magnitude. Therefore it's a trade-off between the cost of CPU cycles and the cost of developer time to create one. But, I have updated my answer accordingly... — Ramón J Romero y Vigil, May 11 '18 at 09:20

scala collections circular buffer

1 Answers1

Linked