benchmark whether 1.5x is a better growth factor for vectors

[thestinger]

• libc++ and libstdc++ use 2x
• MSVC, Java, boost, etc. all use 1.5x

Using a number lower than the golden ratio is supposed to play better with allocator pools and reduce memory fragmentation.

https://crntaylor.wordpress.com/2011/07/15/optimal-memory-reallocation-and-the-golden-ratio/

[yjh0502]

I run a simple benchmark with changed container growth rate: 2x to 1.5x

Experiment setting:

• Ubuntu 12.10, Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz, 24GB RAM, 120GB SSD, both source code and build directory is on SSD.
• compile rust 5 times with make command. It's better to measure time taken to build stage2 only, but I re-compiled all three stages, just for simplicity.
• Compile time is measured with time
• Two settings
  • incoming branch
  • incoming branch with container growth rate 1.5x (diff: https://gist.github.com/yjh0502/5097287)

Result - average running time:

• growth rate 2.0x: avg 790.01s, stdev 2.05s
• growth rate 1.5x: avg 787.55s, stdev 1.64s

Here's raw data: https://docs.google.com/spreadsheet/ccc?key=0AjFZD5XgU6lFdEhHM0hWTi1NQU9VcHdRVThmOGFub0E#gid=0

Compile time decreases by 2.5 seconds, which is quite marginal in my opinion. Maybe we should test it with some well-known container benchmarks.

[brson]

Removing from 1.0

[emberian]

There are a lot bigger fish to fry, but this is still relevant

[toffaletti]

Just adding to the pile, facebook has done some research on this also: https:/facebook/folly/blob/master/folly/docs/FBVector.md

[thestinger]

We should likely use the jemalloc experimental API instead of malloc, realloc and free like the facebook implementation.

[thestinger]

libc++ uses a 2x multiplier for vector growth too. I think integration with various allocators is a better option than trying to find a good magic number here.