How is it reasonable to expect that previously freed memory would be available later for the vector to move to?
Facebook's std::vector optimization
71–80 of 93 posts
Re: Facebook's std::vector optimization
#72The 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? Solving the equations suggest a fibonacci like sequence, seeded by something like "2, 3, 4, 5". Continuing 9, 14, 23 etc.
he golden ratio and then rounding down.
What's the point of putting 4 into the seed sequence?
Re: Facebook's std::vector optimization
#73When 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…
Contiguity, a semblance of control over what stays in cache what doesn't and potential for vectorization is precisely the reason that I use std:vector when I do. I cannot emphasize this enough. Getting the cache behavior correct pretty much makes or breaks my code, in the sense it often dominates performance characteristics once I have got the algorithm correct. One can have speedups of several tens of multipliers. You may work on a project where performance is irrelevant, but that does not mean performance is universally irrelevant.
In short std:vector has served me well, I dont want it to lose performance.
Re: Facebook's std::vector optimization
#74Is 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.
It's likely to distinguish it from XOR, which is the carat operator in many programming languages.
Understandable, but in every other mathematical context (LaTeX for example) a single caret is used as the exponential operator. I guess it's just a convention that's different in different cultures/crowds.
Re: Facebook's std::vector optimization
#75Show me a programmer who is trying to reoptimize the STL, and I'll show you a programmer who is about to be laid off. The guy who tried this at EA didn't last long there.
The STL is not optimized at all in this case, this is precisely the point. And like it or not, but Facebook has talented engineers to do that.
The STL isn't a library that can be optimized - it's a interface definition with expected complexity requirements. By it's nature (i.e. not tied to a platform) it doesn't have specific benchmark numbers. Specific implementations (e.g. MSVCRT, the GC++ implementation, the clang implementation) can be, and are.
Re: Facebook's std::vector optimization
#76If you're interested in these sorts of micro-optimizations, you may find Mozilla's nsTArray (essentially std::vector) interesting.
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.
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.
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.
So instead, empty nsTArrays are pointers to a globally-shared "empty header" that describes an array with capacity and length 0.
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.
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.
http://mxr.mozilla.org/mozilla-central/source/xpcom/glue/nsT...
Re: Facebook's std::vector optimization
#77> ... Rocket surgeon That's a new one. Usually it's rocket scientist or brain surgeon. What exactly does a rocket surgeon do? :)
Re: Facebook's std::vector optimization
#78For 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 :().
Re: Facebook's std::vector optimization
#79If you're interested in these sorts of micro-optimizations, you may find Mozilla's nsTArray (essentially std::vector) interesting. 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. To make this work requires some cooperation with Firefox's all…
> One of its unusual design decisions is that the array's length and capacity is stored next to the array elements itself.
GNU stdlibc++ does this for std::string so you get prettier output in the debugger. The object itself only contains a char*.
Re: Facebook's std::vector optimization
#80Show me a programmer who is trying to reoptimize the STL, and I'll show you a programmer who is about to be laid off. The guy who tried this at EA didn't last long there.
> The guy who tried this at EA didn't last long there.
Paul Pedriana, the man responsible for the lions share of the EASTL work, started at Maxis before it was acqired by EA in 1997. EASTL has been in continuous development for more than 10 years.