Vector documentation improvement suggestion

[Markvy]

I have a few quibbles with the following page

https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#memory-handling

First, it says that "it can be mathematically proven that a growth factor of 2 is rigorously the worst possible because it never allows the vector to reuse any of its previously-allocated memory". This doesn't sound right. After all, a growth factor of 10 also doesn't allow the vector to reuse memory; how is 2 any worse than 10?

Later, we have "But any number smaller than 2 guarantees that you'll at some point be able to reuse the previous chunks." This is false. In fact, 1,5 is barely small enough. The real cutoff happens at Fibonacci numbers, I think. That is, if the vector grows at the rate of Fibonacci numbers, (where fib(0) = 0 and fib(1) = 1, and the initial array has size fib(2)) then using the well known identity that sum(fib(j) for j in 2..n) equals fib(n+2) - 2. So, at the time that you are copying an array of size fib(n+1) into a fresh array of size fib(n+2), all the space that you freed from your old arrays is not enough: you fall short by two elements. The growth rate for Fibonacci is roughly 1.618033988749895. I don't know how to prove that things work fine as long as you use something smaller, but a short Python script I wrote to simulate this backs me up (in addition to it making intuitive sense).

Hope this helps. It's your documentation of course, and if you think this is not worth fixing, it's your call :)

[yfeldblum]

@andralex
@Gownta

[andralex]

Yah, the golden cut is the threshold. Proof is simple. cc @simpkins

[yfeldblum]

Thanks, @andralex.

Would anyone like to submit some changes to the documentation?