Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Facebook's std::vector optimization

github.com

Post reply on HN
Print view View original

21–30 of 93 posts

Re: Facebook's std::vector optimization

#21

Post by xroche »

bnegreve wrote: post #19
bnegreve wrote: post #14

Earlier quoted context omitted.

It's the same with realloc: there is no guarantee that it will grow the chunk in place.

In reply to sibling posts. - if you need dynamic storage you should use a std::vector instead of new []. - with std::vector-s, if you want to save the cost of the copy you can redefine the vector allocator to use realloc or even mremap. Edit @xroche: For example, you can create an allocator that manages an initial chunk of memory (allocated with malloc) and grows it when it's required using realloc inside the 'alloca…

I'm skeptical with the ability to have movable objects with just a dedicated allocator. How do you handle that with only allocate() and deallocate() ?

Edit² @bnegreve: but how do you handle moved blocks then ? And this would involve copying all objects anyway, because this is the std::vector's logic to allocate+memcpy+deallocate when the capacity is reached. The only solution is to ... rewrite std::vector, which is precisely what FB did :)

Re: Facebook's std::vector optimization

#22

Post by CJefferson »

bnegreve wrote: post #14
marksamman wrote: post #8

Earlier quoted context omitted.

You probably should, but the problem is still there because std::vector implementations don't use realloc. They call new[] with the new size, copy over the data and delete[] the old chunk. This eliminates the possibility to grow the vector in-place.

It's the same with realloc: there is no guarantee that it will grow the chunk in place.

The main issue is that you can't say to realloc "if you can't expand in place, just leave it"

This is occasionally annoying in C, but not a great issue. In C++, just memcpying classes leads to awful things happening.

Re: Facebook's std::vector optimization

#23

Post by coliveira »

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…

std::vector is supposed to work in the common cases, so you don't need to manually realloc for small/medium sized vectors. If you need to handle a lot of data, avoiding realloc is still an issue and you should pre-compute the length and use vector::resize (or the length-aware constructor).

Re: Facebook's std::vector optimization

#27

Post by pjmlp »

xroche wrote: post #13
pjmlp wrote: post #9

Earlier quoted context omitted.

Why should C++persist in C insecure design decisons? Besides realloc can force a memory move anyway. Its behavior depends from implementation and memory state.

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.

Re: Facebook's std::vector optimization

#28

Post by marksamman »

cliff_r wrote: post #20

The bit about special 'fast' handling of relocatable types should be obviated by r-value references and move constructors in C++11/14, right? 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.

emplace_back was added in C++11 which does just that: http://en.cppreference.com/w/cpp/container/vector/emplace_ba...

Re: Facebook's std::vector optimization

#29

Post by aktau »

xroche wrote: post #15
bnegreve wrote: post #14

Earlier quoted context omitted.

It's the same with realloc: there is no guarantee that it will grow the chunk in place.

No. Modern realloc are efficient, when moving large memory blocks, because they rely on the kernel ability to quickly relocate memory regions without involving memcpy() (through mremap() on Linux). Edit: shamelessly citing my blog entry on this subject: http://blog.httrack.com/blog/2014/04/05/a-story-of-realloc-a...

Fantastic blog post! Now I don't have to start digging myself :). I've always thought realloc could do a few optimizations, glad to find out the details.

Re: Facebook's std::vector optimization

#30

Post by davidtgoldblatt »

xroche wrote: post #15
bnegreve wrote: post #14

Earlier quoted context omitted.

It's the same with realloc: there is no guarantee that it will grow the chunk in place.

No. Modern realloc are efficient, when moving large memory blocks, because they rely on the kernel ability to quickly relocate memory regions without involving memcpy() (through mremap() on Linux). Edit: shamelessly citing my blog entry on this subject: http://blog.httrack.com/blog/2014/04/05/a-story-of-realloc-a...

This isn't true for either of the common high performance mallocs. tcmalloc doesn't support mremap at all, and jemalloc disables it in its recommended build configuration. glibc will remap, but any performance gains that get realized from realloc tricks would probably be small compared to the benefits of switching to a better malloc implementation.
Post reply on HN