akka/akka — pull request #462 by oschulz (2012-05-17 23:34:49+00:00)
Title: Review Request: ByteString performance improvements and support for binary I/O

Request for REVIEW (*not* ready for merge yet!)
Some more testing code and documentation will probably be required, but I'd be glad to get an opinion on this from Victor et al. before I continue to polish. :-)

This represents a major modification and extension ByteString to

* Improve ByteString performance (up to almost 10x for some operations)
* Add support for binary I/O (encoding and decoding of primitive data types)

Changes in detail:

* A new class ByteIterator, implementing a high performance iterator for ByteStrings
* Several ByteString method implementations now simply redirect to ByteIterator
* ByteIterator has methods like getInt, getInts, etc. to support binary data decoding
* ByteStringBuilder has new methods like putInt, putInts, etc. to support binary data encoding
* There is an InputStream wrapper for ByteIterator and an OutputStream wrapper for ByteStringBuilder for easy integration of Java I/O code
* There is a new abstract class ContByteString, representing a contiguous ByteStrings, to complement CompactByteString

The implementation avoids copying of any data, even for chunked ByteStrings (where at all possible).

### Performance improvements

Performance of the previous ByteString implementation was slow due to a lot of implicit boxing/unboxing of Byte values. ByteString was also lacking an optimized Iterator.

Here's a quick example, iterating over an 1 MB ByteString (run many times after pre-warming JIT).

Native array performance:

```scala
var acc: Int = 0

// Runtime per execution: 1840 us
for (b <- array) { acc += b }
```

Previous ByteString implementation:

```scala
var acc: Int = 0

// Runtime per execution: 11716 us
for (b <- bytes) { acc += b }

// Runtime per execution: 7373 us
val it = bytes.iterator; while (it.hasNext) {acc += it.next()}
```

New ByteString implementation:

```scala
var acc: Int = 0

// Runtime per execution: 1864 us
for (b <- bytes) { acc += b }

// Runtime per execution: 832 us
val it = bytes.iterator; while (it.hasNext) {acc += it.next()}
```

### Binary I/O support

Previously, ByteString was not well suited for applications that have to handle high volumes of binary IO, especially with more complex data structures.

Example: Decoding frames from a binary data stream. The frame format might look like this (synthetic example):

```
frameLen: Int
n: Int
m: Int
n times {
a: Short
b: Long
}
data: m times Double
```

You want to decode this to arrays (or something else which is fast) of a, b and data.

n and m might be on the order of 10000 or more. You can now efficiently decode this in the following fashion:

```scala
implicit val byteOrder = java.nio.ByteOrder.BIG_ENDIAN

val FrameDecoder = for {
frameLenBytes <- IO.take(4)
frameLen = frameLenBytes.iterator.getInt
frame <- IO.take(frameLen)
} yield {
val in = frame.iterator

val n = in.getInt
val m = in.getInt

val a = ArrayBuilder.make[Short]()
val b = ArrayBuilder.make[Long]()

for (i <- 1 to n) {
a += in.getShort
b += in.getInt
}

val data = Array.ofDim[Double](m)
in.getDoubles(data)

(a.result, b.result, data)
}
```

This looks very natural and closely follows the example data format specification. In a nice Scala application, one would, of course, create specialized Short/Long/Double containers instead of mutable Arrays.

You can also do stuff like this:

```scala
val bytes: ByteString = ...
val in: bytes.iterator
... = in.getInt()
... = in.get...
val rest: ByteString = in.toSeq
```

with no copying from bytes to rest involved. In general, conversions from ByteString to ByteIterator and vice versa are O(1) for non-chunked ByteStrings and O(nChunks) for chunked ByteStrings.

Encoding of data also is very natural, using the extended ByteStringBuilder (resp. an IndexByteStringBuffer in general):

```scala
implicit val byteOrder = java.nio.ByteOrder.BIG_ENDIAN

val frameBuilder = ByteStringBuilder()

val n = a.length
val m = data.length

frameBuilder.putInt(n)
frameBuilder.putInt(m)

for (i <- 0 to n-1) {
frameBuilder.putShort(a(i))
frameBuilder.putLong(b(i))
}
frameBuilder.putDoubles(data)
val frame = frameBuilder.result()
```

Then you send it:

```scala
stream.send(ByteStringBuilder().putInt(frame.length).result)
stream.send(frame)
```