Facebook's std::vector optimization • Hacker News Board

Re: Facebook's std::vector optimization

#81

Post by yoklov » Sun, Aug 31, 2014, 3:22 AM UTC

kabdib wrote: post #62

colomon wrote: post #37

Earlier quoted context omitted.

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.

Are you sure? You're not allowed to invalidate iterators or pointers to elements in a deque, so it shouldn't be reallocating memory (aside from its underlying map of nodes, which will need to grow very rarely).

Libstdc++ describes how it's implemented here: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-...

Libc++ doesn't have as descriptive a comment but it's impemented basically the same way here https://github.com/llvm-mirror/libcxx/blob/master/include/de...

Re: Facebook's std::vector optimization

#82

Post by pbw » Sun, Aug 31, 2014, 3:32 AM UTC

shadytrees wrote: post #64

pbw wrote: post #43

Are there benchmarks, speedup? Seems strange to leave out that information or did I just miss it?

Yes! https://www.google.com/search?q=folly+facebook+benchmarks

I don't see the results. Like a graph that shows std::vector vs. folly. I mean isn't that the entire point?

Re: Facebook's std::vector optimization

#83

Post by amadvance » Sun, Aug 31, 2014, 8:34 AM 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…

I implemented what you describe using the BSR (BitScanReverse) instruction as base of an indirect addressing of an exponentially growing data size.

Essentially, instead of a direct addressing like V[i], you can do VV[log2(i)][i]. Where log2() is implemented with a single BSR instruction.

The addressing table for the first level is very small in size, and it can be assumed always in cache.

Here the .h/.c source: https://github.com/amadvance/tommyds/blob/master/tommyds/tom...

https://github.com/amadvance/tommyds/blob/master/tommyds/tom...

Did you used something different ?

Re: Facebook's std::vector optimization

#84

Post by eps » Sun, Aug 31, 2014, 9:46 AM UTC

thomasahle wrote: post #70

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? Solving the equations suggest a fibonacci like sequence, seeded by something like "2, 3, 4, 5". Continuing 9, 14, 23 etc.

There was an academic paper in the 70s on Fibonacci-based allocation strategy... though I can't seem to find it now. So the idea is definitely not new :)

Re: Facebook's std::vector optimization

#85

Post by nly » Sun, Aug 31, 2014, 10:08 AM UTC

amadvance wrote: post #83

kabdib wrote: post #31

Earlier 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…

I implemented what you describe using the BSR (BitScanReverse) instruction as base of an indirect addressing of an exponentially growing data size. Essentially, instead of a direct addressing like V[i], you can do VV[log2(i)][i]. Where log2() is implemented with a single BSR instruction. The addressing table for the first level is very small in size, and it can be assumed always in cache. Here the .h/.c source: https…

Re: Facebook's std::vector optimization

#86

Post by nly » Sun, Aug 31, 2014, 10:27 AM UTC

yoklov wrote: post #81

kabdib wrote: post #62

Earlier quoted context omitted.

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.

Are you sure? You're not allowed to invalidate iterators or pointers to elements in a deque, so it shouldn't be reallocating memory (aside from its underlying map of nodes, which will need to grow very rarely). Libstdc++ describes how it's implemented here: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-... Libc++ doesn't have as descriptive a comment but it's impemented basically the same way here https…

You might not want to use deque because of how much memory it can use while still small, e.g. libc++s implementation uses a 4KiB page:

http://rextester.com/VIB96468

In the GNU stdlibc++ implementation the object itself is pretty large (and they use a page size of 512 bytes):

http://rextester.com/RHYKB83240

Re: Facebook's std::vector optimization

#87

Post by thomasahle » Sun, Aug 31, 2014, 10:34 AM UTC

judk wrote: post #72

thomasahle wrote: post #70

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? 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?

Without 4, the sequence would be 2, 3, 5. Then the next value would be 9 by fibonacci. But that's bigger than the 5 we get from adding up all the unallocated pieces (2 and 3).

We could use just 2, 3, 4 as a seed, but we can't use the fibonacci formula before the fourth element is added. Try some different seeds for yourself, it's trickier than you'd think.

Re: Facebook's std::vector optimization

#88

Post by jheriko » Sun, Aug 31, 2014, 1:30 PM UTC

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.

if std::vector is your bottleneck you have bigger problems i suspect.

reminds me a bit of eastl as well... which is much more comprehensive: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n227...

Re: Facebook's std::vector optimization

#89

Post by huhtenberg » Sun, Aug 31, 2014, 2:30 PM UTC

pjmlp wrote: post #27

xroche wrote: post #13

Earlier quoted context omitted.

How realloc is insecure ? The only lacking construct is a "moved" operator, which would re-assign pointer members, for example, when moving this to another location.

Typical security exploit with realloc is attacking code that assumes realloc always success and never moves, thus keeping all pointers around.

Assuming that realloc() always succeeds is one thing, I can believe there's code that makes it. But I'd very much like to look at the code that assumes that realloc() never moves the block. This sounds a remarkably elaborate assumption to make, hardly an oversight due to ignorance.

Re: Facebook's std::vector optimization

#90

Post by byuu » Sun, Aug 31, 2014, 4:46 PM UTC

nly wrote: post #79

jlebar wrote: post #76

If 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*.

Seems like that would prevent small string optimization (a union of a small char array and the heap char pointer.) That lets me store about 85% of the strings in my assembler without any heap allocation, and is a huge win in my book.