Improve the way we grow buffers

[julienrf]

Improve the way we grow buffers

[szeiger]

More generally we need to compare all implementations in this project with the current collections library to get the necessary bug fixes and performance improvements. This started out as a strawman proposal for a new design, we shouldn't expect that the current implementations are correct or fast.

[Ichoran]

Sometime soon we need an initial go/no-go decision on this design. Once it's "go", or even once we anticipate it being "go", we can start worrying about correctness and performance. (Of course if a design would prevent correctness or performance, we should evaluate it earlier.)

Anyway, with regard to buffer resizing, I usually personally use a clipped bit shift operation that uses values of size (1 << n)-1, but in some cases it is essential that we have powers of two, and it's kind of nice if the sizes always agree just to keep it conceptually simpler. Given that array overhead is around 20 bytes and compressed pointers are 4, allocating less than 4 things into an array seems highly questionable.

In my usual fast-and-dirty benchmarking, allocating an array of AnyRef of length 4 is about 25% slower than allocating an array of length 2; 8 is about 45% slower than 4; and 16 is about 66% slower than 4, roughly consistent with an array creation model of 1.5 ns + 0.3 ns / object pointer. Obviously this will vary by machine, but unless we're sure that we need tiny arrays only, I would say that 8 is probably the way to go.

This suggest an algorithm like

val twice = end * 2
val newSize = 
  if (twice < 0) {
    if (end == Int.MaxValue) throw new Exception("TODO--write sane message")
    else Int.MaxValue
  }
  else if (twice < 8) 8
  else twice

is the way to go. In my tests this barely slows things down at all in a tight loop.

[julienrf]

I implemented this algorithm in bbcb391 (in the benchmark branch, because they were preventing ArrayBuffer benchmarks to run)