Facebook's std::vector optimization

Post by kabdib » Sat, Aug 30, 2014, 3:05 PM UTC

userbinator wrote: post #10

When the request for growth comes about, the vector (assuming no in-place resizing, see the appropriate section in this document) will allocate a chunk next to its current chunk This is assuming a "next-fit" allocator, which is not always the case. I think this is why the expansion factor of 2 was chosen - because it's an integer, and doesn't assume any behaviour of the underlying allocator. I'm mostly a C/Asm progra…

Post by [deleted] » Sat, Aug 30, 2014, 3:12 PM UTC

kenperkins wrote: post #32

> ... Rocket surgeon That's a new one. Usually it's rocket scientist or brain surgeon. What exactly does a rocket surgeon do? :)

Post by Sidnicious » Sat, Aug 30, 2014, 3:19 PM UTC

14113 wrote: post #34

Is it normal to notate powers using double caret notation? (i.e. ^^) I've only ever seen it using a single caret (^), in what presumably is meant to correspond to an ascii version of Knuth up arrow notation ( https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation ). I found it a bit strange, and confusing in the article having powers denoted using ^^, and had to go back to make sure I wasn't missing anything.

Post by colomon » Sat, Aug 30, 2014, 3:28 PM UTC

kabdib wrote: post #31

userbinator wrote: post #10

When the request for growth comes about, the vector (assuming no in-place resizing, see the appropriate section in this document) will allocate a chunk next to its current chunk This is assuming a "next-fit" allocator, which is not always the case. I think this is why the expansion factor of 2 was chosen - because it's an integer, and doesn't assume any behaviour of the underlying allocator. I'm mostly a C/Asm progra…

I solved an "realloc is really costly" problem by ditching the memory-is-contiguous notion, paying a little more (really just a few cycles) for each access rather than spending tons of time shuffling stuff around in memory. This eliminated nearly all reallocations. The extra bit of computation was invisible in the face of cache misses. I'm guessing that most customers of std::vector don't really need contiguous memor…

Post by dbaupp » Sat, Aug 30, 2014, 3:31 PM UTC

chickenandrice wrote: post #36

Greetings Facebook, several decades ago welcomes you. Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now. Most of the time if performance and allocation is so critical, you're better off not using a vector anyway. A fixed sized array is much more cache friendl…