mpilquist/scodec — pull request #3 by pchiusano (2013-12-23 23:53:10+00:00)
Title: New and improved BitVector implementation

Squashed version of #2, which can be closed.

`BitVector` is now a balanced binary tree of byte vectors, with some extra logic to handle trailing bits. Indexing into a `BitVector` is done with `Long` (to allow vectors of sizes greater than 250MB or so), and `take`, `drop`, and `++` are all log time operations. The new `BitVector` no longer extends the Scala collections due to the move to `Long` based indexing, but all the operations that are used in `scodec` are implemented directly for `BitVector`, so all the existing code still compiles.

The new implementation relies on the efficiency of `ByteVector.take/drop/slice`, but does not rely on the efficiency of `ByteVector.updated` - trailing bits are always left alone and only when flattening a `BitVector` to a `ByteVector` are these bits cleared. Thus, `BitVector(hugeByteVector).take(13).toByteVector` will only be calling `updated` on a two byte slice of `hugeByteVector`, rather than clearing those bits on `hugeByteVector`. So this implementation should work fine for 'dumber' `ByteVector` implementations that just make a full copy of the underlying bytes.

I added lots of scalacheck properties, including merging the `x.take(m) ++ x.drop(m) == x` property from master. All tests are passing.

Other notes:

* The `++` operation merges small bit vectors (those below 512 bytes) into flat byte vectors, but if the vectors are very small (both below 256 bits), it prefers to wait until the combined size is divisible by 8. This is to avoid having weird bit lengths sprinkled throughout the tree that would result in needing to shift individual bytes when flattening. I haven't tried tuning these constants, but that would be something interesting to play with and profile.
* A few operations, like `reverse`, `reverseByteOrder`, and the pairwise binary operators like `and` and `or`, could be written more efficiently to take advantage of the tree structure. Currently, they do the dumbest possible thing of just flattening the overall vector (which makes them roughly equivalent to what was there before).
* I found it worked out a little nicer to have a `Drop` constructor separate from the flat `Bytes` constructor. This way each flat `Bytes` slice starts on a byte boundary, and there are fewer places in the code where you need to worry about byte-boundary issues. If you look at the implementation of `drop`, it actually only creates a `Drop` node if it needs to split a byte in two, otherwise it just takes a whole-byte slice of some underlying `ByteVector`.