Investigate dynamic Vec growth strategy for jemalloc hugs

[Gankra]

Facebook's alternative C++ STL uses a rather dynamic strategy to ostensibly be friendly for common workloads and jemalloc's size classes. While most of FBVector's stuff is hacking around the fact the move/copy constructors are Awful, this seems applicable to us.

See:

• https://github.com/facebook/folly/blob/fd0b3090840d742492793fe306185550f0300283/folly/FBVector.h#L1165-L1194
• https://github.com/facebook/folly/blob/master/folly/memory/Malloc.h#L206-L223
• https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md
• benchmark whether 1.5x is a better growth factor for vectors #4961

[Gankra]

Note that our strategy current boils down to:

if cap == 0 { 4 } else { 2 * cap }

See: http://doc.rust-lang.org/nightly/src/alloc/raw_vec.rs.html#138-214

Doubling in conjuction with with mem::size_of::<T>() * cap < isize::MAX as an invariant makes size computation basically as efficient as possible.

The cap == 0 check needs to be made anyway to decide if to do an alloc or realloc.

For reference, the change to would be to instead do something like:

if cap == 0 { 
    let new_cap = cmp::max(64 / mem::size_of::<T>(),  1);
    alloc(new_cap);
} else { 
    let new_cap = if pretty_small_or_pretty_big::<T>(cap) { // see FBVector source for details
        cap * 2
    } else { 
        // No need to check match because we're not `pretty_big` (< 1 MB)
        (cap * 3 + 1) / 2 
    };
    realloc(cap, new_cap);
}

This should be a new method, as double is still useful for VecDeque (which requires power of two cap).

[nagisa]

I remember hearing that grow factor of 1.5 is better than 2, but I don't remember where it was or whether it is confirmed in any way.

[jdm]

https://blog.mozilla.org/nnethercote/2014/11/04/please-grow-your-buffers-exponentially/ is useful reading. There's a comment thread about the 1.5 vs. doubling thing, too.

[Gankra]

@nagisa this is the assertion of the second-last link in the OP -- however the last link found negligible gains for Rust in some benchmark.

May want to scour e.g. https://github.com/facebook/folly/blob/master/folly/test/FBVectorTestBenchmarks.cpp.h for interesting workloads.

[Gankra]

Note that applying this logic to with_capacity could be a perf hazard when wanting to do things like convert to a Box.

[gnzlbg]

The only interesting workloads in FBVectorTestBenchmarks.cpp.h#L337 seem to be the pushBack and insert benchmark since reserve should allocate the exact amount a user specifies.