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

Re: Facebook's std::vector optimization

#91

Post by r-s » Sun, Aug 31, 2014, 6:07 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…

There is a major use case for std::vector having contiguous memory, which is passing a reference to the first element of a vector into a function expecting a pointer. This is fine assuming the vector is not empty.

Re: Facebook's std::vector optimization

#92

Post by pjmlp » Mon, Sep 01, 2014, 8:36 AM UTC

huhtenberg wrote: post #89

pjmlp wrote: post #27

Earlier quoted context omitted.

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.

Lots of enterprise code with off-shoring provide entertainment of code quality.

Re: Facebook's std::vector optimization

#93

Post by nly » Mon, Sep 01, 2014, 3:04 PM UTC

byuu wrote: post #90

nly wrote: post #79

Earlier quoted context omitted.

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

Indeed, they don't do SSO. Reference counted COW, which violates the standard.