If you're interested in these sorts of micro-optimizations, you may find Mozilla's nsTArray (essentially std::vector) interesting.<p>One of its unusual design decisions is that the array's length and capacity is stored next to the array elements themselves. This means that nsTArray stores just one pointer, which makes for more compact DOM objects and so on.<p>To make this work requires some cooperation with Firefox's allocator (jemalloc, the same one that FB uses, although afaik FB uses a newer version). In particular, it would be a bummer if nsTArray decided to allocate space for e.g. 4kb worth of elements and then tacked on a header of size 8 bytes, because then we'd end up allocating 8kb from the OS (two pages) and wasting most of that second page. So nsTArray works with the allocator to figure out the right number of elements to allocate without wasting too much space.<p>We don't want to allocate a new header for zero-length arrays. The natural thing to do would be to set nsTArray's pointer to NULL when it's empty, but then you'd have to incur a branch on every access to the array's size/capacity.<p>So instead, empty nsTArrays are pointers to a globally-shared "empty header" that describes an array with capacity and length 0.<p>Mozilla also has a class with some inline storage, like folly's fixed_array. What's interesting about Mozilla's version, called nsAutoTArray, is that it shares a structure with nsTArray, so you can cast it to a const nsTArray*. This lets you write a function which will take an const nsTArray& or const nsAutoTArray& without templates.<p>Anyway, I won't pretend that the code is pretty, but there's a bunch of good stuff in there if you're willing to dig.<p><a href="http://mxr.mozilla.org/mozilla-central/source/xpcom/glue/nsTArray.h" rel="nofollow">http://mxr.mozilla.org/mozilla-central/source/xpcom/glue/nsT...</a>
<i>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</i><p>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.<p>I'm mostly a C/Asm programmer, and dynamic allocation is one of the things that I very much avoid if I don't have to - I prefer constant-space algorithms. If it means a scan of the data first to find out the right size before allocating, then I'll do that - modern CPUs are <i>very</i> fast "going in a straight line", and realloc costs add up quickly.<p>Another thing that I've done, which I'm not entirely sure would be possible in "pure C++", is to adjust the pointers pointing to the object if reallocation moves it (basically, add the difference between the old and new pointers to each reference to the object); in theory I believe this involves UB - so it might not be "100% standard C" either, but in practice, this works quite well.
I'm glad to see this catch on and the C level primitives get greater use.<p>This has been a well known problem in the C++ community for years, in particular Howard Hinnant put a lot of work into this problem. I believe the fundamental problem has always been that C++ implementations always use the underlying C implementations for malloc and friends, and the C standards committee could not be pursaded to add the necessary primitives.<p>A few years ago I tried to get a reallic which did not move (instead returned fail) into glibc and jealloc and failed. Glad to see someone else has succeeded.
I think the Folly small vector library is much more interesting and can yield better performance (if you hit the sweet spot).<p><a href="https://github.com/facebook/folly/blob/master/folly/docs/small_vector.md" rel="nofollow">https://github.com/facebook/folly/blob/master/folly/docs/sma...</a><p>From what I understand, using a "rvalue-reference ready" vector implementation with a good memory allocator must work at least as good as FBVector.
Apparently the libstdc++ people aren't entirely convinced by the growth factor claims:<p><a href="https://gcc.gnu.org/ml/libstdc++/2013-03/msg00059.html" rel="nofollow">https://gcc.gnu.org/ml/libstdc++/2013-03/msg00059.html</a>
The bit about special 'fast' handling of relocatable types should be obviated by r-value references and move constructors in C++11/14, right?<p>I.e. if we want fast push_back() behavior, we can use a compiler that knows to construct the element directly inside the vector's backing store rather that creating a temporary object and copying it into the vector.
You can get around a lot of these issues by reserving the size needed up front, or using a custom allocator with std::vector. Not as easy, but still doable.<p>The reallocation issue isn't fixable this way however...
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 (<a href="https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation" rel="nofollow">https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation</a>).
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.
Yep, this is my biggest issue with C++: you now have lambdas functions and an insane template spec, but you just can not "realloc" a new[] array. Guys, seriously ?
The factor-2 discussion is quite interesting. What if we could make the next allocated element always fit exactly in the space left over by the old elements?<p>Solving the equations suggest a fibonacci like sequence, seeded by something like "2, 3, 4, 5". Continuing 9, 14, 23 etc.
For big vectors, if there is obvious way, I always hint vector with reserve() - for example knowing in advance how much would be copied, even if a bit less gets copied (or even if a bit more, at the cost of reallocation :().
<i>Then the teleporting chief would have to shoot the original</i><p>As an aside, there was a great Star Trek novel where there was a long range transporter invented that accidentally cloned people.<p>(I think it was "Spock Must Die")
i used to be a big fan of this sort of stuff, but the better solution for many of the problems described is to avoid array resizing.<p>if std::vector is your bottleneck you have bigger problems i suspect.<p>reminds me a bit of eastl as well... which is much more comprehensive: <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html" rel="nofollow">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...</a>
If you're spending a lot of time changing the size of a std::vector array, then maybe std::vector isn't the right type of structure to begin with...
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.<p>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 friendly, makes pooling quite easy, and eliminates other performance costs that suffer from std::vector's implementation.<p>More to the point, who would use a c++ library from Facebook? Hopefully don't need to explain the reasons here.
Show me a programmer who is trying to reoptimize the STL, and I'll show you a programmer who is about to be laid off.<p>The guy who tried this at EA didn't last long there.