Bad “optimization” of `BytesMut` re-allocations

[steffahn]

Reading

bytes/src/bytes_mut.rs

Lines 577 to 579 in 68afb40

	// If there's enough free space before the start of the buffer, then
	// just copy the data backwards and reuse the already-allocated
	// space.

I felt like this can completely kill the asymptotics of BytesMut. And sure enough, e.g. this example:

on a full BytesMut, a million bytes, doing 10'000 get_u8 and put_u8 operations moves the entire contents of the BytesMut 10'000 times, resulting in a run-time (in the playground) of up to 1 second, instead of less than a millisecond.

use bytes::{BytesMut, BufMut, Buf};

use std::time;

fn main() {
    let mut bytes = BytesMut::with_capacity(1024);
    bytes.put_bytes(0, 1_000_000);
    assert_eq!(bytes.capacity(), 1_000_000);
    let start = time::Instant::now();
    for _ in 0..10_000 {
        bytes.get_u8();
        bytes.put_u8(0);
    }
    println!("{:>9.3?} - 10'000 × get+put (each moving all the data)", start.elapsed());
    let start = time::Instant::now();
    bytes.put_u8(0);
    println!("{:>9.3?} - one put (re-allocating)", start.elapsed());
    let start = time::Instant::now();
    for _ in 0..10_000 {
        bytes.get_u8();
        bytes.put_u8(0);
    }
    println!("{:>9.3?} - 10'000 × get+put (no allocations or moves)", start.elapsed());
}

633.147ms - 10'000 × get+put (each moving all the data)
 71.792µs - one put (re-allocating)
223.719µs - 10'000 × get+put (no allocations or moves)

(playground)

The optimization here is bad, since usually automatic re-allocations follow the principle that the capacity has to grow by a constant factor each time, whereas moving the data might only increase the capacity by a tiny bit. This isn't a re-allocation; it just copies all the data, but really the actual “allocation” part of a re-allocation is cheap, it always is the copying that it's all about.

Vec (currently) uses a factor 2, so I suggest that this “optimization” should really only ever trigger if the gained capacity, i.e. self.capacity() - self.len() + off, increases the previous capacity, self.capacity() at least by a factor of two, i.e. if

• (current condition still relevant): self.capacity() - self.len() + off >= additional, and also
• (new condition): off >= self.capacity()

Interesting consequence: This also has the effect that copy_nonoverlapping can be used.