Skip to content

Instantly share code, notes, and snippets.

@pchiusano

pchiusano/buffer.scala

Created August 6, 2014 01:21
Show Gist options
  • Save pchiusano/b1100e4cffba48ab0405 to your computer and use it in GitHub Desktop.
Save pchiusano/b1100e4cffba48ab0405 to your computer and use it in GitHub Desktop.
Download ZIP
Buffer type with purely functional API, using a mutable buffer and cheap copy-on-write scheme
Raw
buffer.scala
import java.util.concurrent.atomic._
import collection.mutable.ArrayBuffer
/**
* Buffer type with purely functional API, using mutable
* `ArrayBuffer` and cheap copy-on-write scheme.
* Idea described by Bryan O'Sullivan in http://www.serpentine.com/blog/2014/05/31/attoparsec/
*/
class Buffer[A](id: AtomicLong, stamp: Long, values: ArrayBuffer[A], size: Int) {
/** Snoc a value onto the end of this `Buffer`, possibly using (unobservable) mutation of `values`! */
def :+(a: A): Buffer[A] =
if (id.compareAndSet(stamp, stamp+1)) { // threads race to be able to mutably update 'values'
values += a
new Buffer(id, stamp+1, values, size+1)
}
else // losers are forced to make a copy of the buffer
new Buffer(new AtomicLong(0), 0, ArrayBuffer.empty[A] ++ values.take(size) :+ a, size + 1)
def toSeq: Seq[A] = values.view.take(size)
override def toString = "Buffer(" ++ toSeq.mkString(", ") ++ ")"
}
object Buffer {
def empty[A]: Buffer[A] = new Buffer(new AtomicLong(0), 0, ArrayBuffer.empty[A], 0)
}
@pchiusano
Copy link
Author

Sample REPL session:

scala> val x = Buffer.empty[Int]
x: Buffer[Int] = Buffer()

scala> val y = x :+ 1 // will update internal buffer mutably! O(1)
y: Buffer[Int] = Buffer(1)

scala> val z = x :+ 2 // will make a copy of the buffer before modifying it
z: Buffer[Int] = Buffer(2)

scala> val yy = y :+ 3 // again, will update mutably
yy: Buffer[Int] = Buffer(1, 3)

scala> y // old values are still valid
res8: Buffer[Int] = Buffer(1)

scala> z 
res9: Buffer[Int] = Buffer(2)

@pchiusano
Copy link
Author

This idea also being used for fast buffered byte vectors in the scodec-bits project.

@pchiusano
Copy link
Author

Interestingly, this idea can be extended to deal with a large number of mutable APIs. Our only requirement is that the mutation be 'append-only'. That is, once a value is set, it must never be updated again. For instance, we can have a purely functional Map data type which updates values in place, subject only to the requirement that we never overwrite the value of a key (or if we need to, we need to then make a copy).

This seems to relate to the limited form of mutation provided by use of laziness, except that unlike laziness, we don't need to construct the whole computation 'in advance' to take advantage of it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment