scodec/scodec-bits — pull request #16 by pchiusano (2014-08-05 19:11:49+00:00)
Title: Implementation of buffered ByteVectors

Adds support for 'buffered' `ByteVector`s. Given a `b: ByteVector`, `b.bufferBy(512)` returns a buffered `ByteVector` with a buffer chunk size of 512. (`b.buffer` picks a default buffer size). A buffered vector supports `++` and `:+` in O(1) by allowing (non-RT-breaking) updates to a mutable scratch buffer, and by keeping a queue of `ByteVector` chunks (essentially delaying when appends are paid for).

Since buffered vectors retain a queue of chunks, they also support fast `take` and `drop` for small _n_, as these can be implemented by dequeuing just the first few chunks rather than paying the logarithmic cost for the entire tree. This works out nicely if a buffered vector that has been built up will be consumed in a linear fashion via a series of `take`/`drop` calls.

Here are some typical times for building up a 1 million element `ByteVector`, one byte at a time:

```
buffered :+ 0.0365625s per trial; 32 trials
buffered ++ 0.0889375s per trial; 16 trials
unbuffered 1.21s per trial; 1 trials
```

There are pretty good scalacheck properties, testing for consistency with unbuffered vectors, and also testing concurrent access, since the implementation relies on ensuring that at most one thread of control ever updates the mutable scratch space at the end of a buffered vector.

Also see [implementation notes here](https://github.com/pchiusano/scodec-bits/blob/topic/fast-snoc-squashed/src/main/scala/scodec/bits/ByteVector.scala#L1270)