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.
The guy who tried this at EA didn't last long there.
Facebook's std::vector optimization
61–70 of 93 posts
Re: Facebook's std::vector optimization
#62Earlier quoted context omitted.
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…
No, that's quite intentional. If you don't need contiguous memory, you can consider using std::deque. http://www.cplusplus.com/reference/deque/deque/
There are weasel words in the standard that let implementations still be pretty inefficient. The problem is that memory reallocation is a leaky abstraction, and an interface that doesn't make guarantees about memory behavior can't be relied upon at scale.
The implementation of std::deque I just read uses a circular queue, resized to a power of two upon growth. It would exhibit the same bad performance as std::vector.
Re: Facebook's std::vector optimization
#63Show 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.
Re: Facebook's std::vector optimization
#64Are there benchmarks, speedup? Seems strange to leave out that information or did I just miss it?
Re: Facebook's std::vector optimization
#65Earlier quoted context omitted.
Actually, game companies as well as various indie developers have widely distributed this knowledge. Some examples of places to look/things to search for implementations or similar/better: -GDC Slide Decks -Game Programming Data Structure/Performance Books -Game Industry Publications - ex: Game Programming Gems -EA STL -Game Dev Sites -Any available source to various engines/games in the last many years should have m…
http://lmgtfy.com/?q=std%3A%3Avector+games
I went and actually checked the first 6 links in this search, and none of them really address the problems brought up in the OP. If you're going to be arrogant about this issue, you should at least be correct.
Re: Facebook's std::vector optimization
#66Show 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.
Games and other high performance users generally used to stay away from the STL. Sony had their own version of STL which addressed some of these issues.
Re: Facebook's std::vector optimization
#67Earlier quoted context omitted.
But * * has an entirely different meaning in C/C++.
Only as a prefix operator; * has a pointer-related meaning for prefix and an arithmetic meaning for infix, there's no reason * * shouldn't be the same.
That'd be a syntactic ambiguity (in C-type languages) between "a * * b" being a to the power of b (i.e. "(a) * * (b)") or "a * * b" being a times the dereferencing of the pointer b (i.e. "(a) * (*b)"). You may be able to disambiguate this by prescedence, though it would be very ugly in the lexer (you could never have a STARSTAR token, it would have to be handled in the grammar) and would be terribly confusing.
Re: Facebook's std::vector optimization
#68Earlier quoted context omitted.
It's likely to distinguish it from XOR, which is the carat operator in many programming languages.
It is still weird. * * is the other established convention used for exponentiation in languages like Python, Ada, m4, and others.
It's math, not computer code. ^ means exponentiatuon. The author was just being weird.
Re: Facebook's std::vector optimization
#69Apparently the libstdc++ people aren't entirely convinced by the growth factor claims:
Re: Facebook's std::vector optimization
#70The 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.