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

41–50 of 93 posts

Re: Facebook's std::vector optimization

#41

Post by DonPellegrino »

dbaupp wrote: post #39
chickenandrice wrote: post #36

Greetings Facebook, several decades ago welcomes you. Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now. Most of the time if performance and allocation is so critical, you're better off not using a vector anyway. A fixed sized array is much more cache friendl…

> More to the point, who would use a c++ library from Facebook? Hopefully don't need to explain the reasons here. Could you explain them for those of us not in the loop? Does Facebook have a bad reputation for C++?

I would also like expanations, because Facebook actually has a good reputation when it comes to their compiled languages engineers. Their C++ and D engineers built HHVM/Hack, their OCaml engineers built some great analysis tools and much of the supporting code for the HHVM/Hack platform, etc., the list goes on, so I'd like to know why someone would want to avoid their C++ library based on the "Facebook" name only.

Re: Facebook's std::vector optimization

#42

Post by saurik »

marksamman wrote: post #8
bnegreve wrote: post #7

Earlier quoted context omitted.

If you need to realloc a fixed size array, souldn't you use a std::vector instead?

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.

Actually, I don't think it is possible to implement vector in the way you describe (so I'd argue that in fact there is not even a single working implementation that does that): using new[] will cause a default construction of all the elements, but std::vector must copy construct (or, in C++11, move construct, but never assign) the elements from the old array to the new array. AFAIK all implementations of std::vector thereby have a separate phase of allocating memory for the underlying storage of the array (which is done using an allocator, and which essentially cannot be implemented in terms of new) and constructing the elements (which is done using the placement new operator in a loop as it copies the data).

The real issue here is that std::allocator doesn't support realloc. (Note that you couldn't really use realloc as spec'd, though, because in the case where it fails to reallocate in place it blows away the old memory area and copies the data itself, which would have incorrect semantics: this is actually discussed in the article from Facebook as the "notorious design of realloc()" which made the usage of jemalloc required for this task. However, std::allocator could still have features for handling this situation, and implements based on malloc would simply have to not support the reallocate functionality. I imagine if more allocators actually supported the idea of reallocation this could be proposed to the committee.)

That said, the statement that std::vector can't grow the chunk in place is still way too heavy-handed: std::vector will grow its size in place within the memory area allocated to it by deconstructing and constructing elements within the over-sized memory area it has allocated. In general, this memory area grows by doubling in size whenever the capacity is breached, which leads to vector having amortized constant time complexity to insert a new element.

Re: Facebook's std::vector optimization

#44

Post by saurik »

chickenandrice wrote: post #36

Greetings Facebook, several decades ago welcomes you. Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now. Most of the time if performance and allocation is so critical, you're better off not using a vector anyway. A fixed sized array is much more cache friendl…

(As someone who started doing professional game development in 2000, I will concur that every single point mentioned in this article, including the usage of an IsRelocatable template trait, is common knowledge in the game developer community.)

Re: Facebook's std::vector optimization

#45

Post by nly »

saurik wrote: post #42
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.

Actually, I don't think it is possible to implement vector in the way you describe (so I'd argue that in fact there is not even a single working implementation that does that): using new[] will cause a default construction of all the elements, but std::vector must copy construct (or, in C++11, move construct, but never assign) the elements from the old array to the new array. AFAIK all implementations of std::vector…

> which is done using an allocator, and which essentially cannot be implemented in terms of new

Actually the standard says std::allocator just calls the global operator new function[0]. When you call construct(), placement-new is then used to construct the objects in place. This makes it easy to replace the memory allocator globally as well as on a per-container basis.

[0] http://en.cppreference.com/w/cpp/memory/new/operator_new

Re: Facebook's std::vector optimization

#46

Post by mackal »

dbaupp wrote: post #39
chickenandrice wrote: post #36

Greetings Facebook, several decades ago welcomes you. Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now. Most of the time if performance and allocation is so critical, you're better off not using a vector anyway. A fixed sized array is much more cache friendl…

> More to the point, who would use a c++ library from Facebook? Hopefully don't need to explain the reasons here. Could you explain them for those of us not in the loop? Does Facebook have a bad reputation for C++?

I think its more of a "lol Facebook" than actual Facebook having a bad reputation. They do have a lot of money to hire talented engineers, it maybe that this solution is poor in the edge case the other post was talking about, but it may also be possible their solution is poor for Facebook. Facebook also contributes A LOT to open source projects and you can see their employee email domain all over open source projects.

I could also probably speculate their thinking along the lines of backdoors or something. But Facebook does have a good reputation with open source projects, so I wouldn't be too worried about that. (As in no more worried than some other random project)

Re: Facebook's std::vector optimization

#47

Post by mraison »

chickenandrice wrote: post #36

Greetings Facebook, several decades ago welcomes you. Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now. Most of the time if performance and allocation is so critical, you're better off not using a vector anyway. A fixed sized array is much more cache friendl…

> most of us had in-house stl libraries for decades now

I've no doubt there has been many talented programmers for decades, but what about open-sourcing these "in house" libraries if they are so great, to avoid countless other programmers the need to reinvent the wheel? I think it would be more constructive than bashing Facebook for being late to the party.

Re: Facebook's std::vector optimization

#48

Post by otterley »

chickenandrice wrote: post #36

Greetings Facebook, several decades ago welcomes you. Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now. Most of the time if performance and allocation is so critical, you're better off not using a vector anyway. A fixed sized array is much more cache friendl…

> Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now.

OTOH, game programmers don't share this kind of knowledge on public fora as freely as Internet companies do. It may be "old news" to you, but it was unpublished. Knowledge is great, but dissemination is even better.

Re: Facebook's std::vector optimization

#49

Post by bnastic »

chickenandrice wrote: post #36

Greetings Facebook, several decades ago welcomes you. Game programmers figured out the same and arguably better ways of doing this since each version of std::vector has been released. This is but a small reason most of us had in-house stl libraries for decades now. Most of the time if performance and allocation is so critical, you're better off not using a vector anyway. A fixed sized array is much more cache friendl…

Yeah, you would need to provide an explanation. Facebook's folly is the best, cleanest set of low-level c++ libs I've ever seen.

The fact the something has been done in industry 'x' does not negate the value of this article/library.

Re: Facebook's std::vector optimization

#50

Post by thrownaway2424 »

darkpore wrote: post #4

You can get around a lot of these issues by reserving the size needed up front, or using a custom allocator with std::vector. Not as easy, but still doable. The reallocation issue isn't fixable this way however...

You can use a feedback directed optimization pass to choose the initial size.
Post reply on HN