Back in January I wrote about a charming result concerning how much memory should be increased when reallocating. Via Artur Malabarba, I came across a tweet by Wilfred Hughes
Learnt a fascinating, non-obvious (to me) fact that resizing a vector's memory by a factor of 2 is optimally bad https://t.co/eBiOrqgzzM
— Wilfred Hughes (@_wilfredh) August 30, 2014
pointing to Facebook’s implementation of the idea. The FBVector.md file at the link explains why they use a factor of 1.5 instead of 2 (it misses the beautiful result about the golden ratio, though).
Their implementation of the C++ std::vector library has other optimizations, which are also interesting. If you’re working in C++, you should definitely give it a look.
In my original post, I remarked that “none of this is of great import.” The folks at Facebook have shown that that was wrong.