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

Re: Facebook's std::vector optimization

#11

Post by mlvljr » Sat, Aug 30, 2014, 12:44 PM UTC

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…

The latter nicely addresses to the recent HN discussion about "Friendly C"; may I ask what kind of software you are building, incidentally? (...don't tell it's medical :O)

Re: Facebook's std::vector optimization

#12

Post by dalke » Sat, Aug 30, 2014, 12:44 PM UTC

ck2 wrote: post #6

Then the teleporting chief would have to shoot the original As an aside, there was a great Star Trek novel where there was a long range transporter invented that accidentally cloned people. (I think it was "Spock Must Die")

There's also the ST:TNG episode "Second Chances". http://en.wikipedia.org/wiki/Second_Chances_%28Star_Trek:_Th... where Riker is duplicated. (There's also the good/bad Kirk in 'The Enemy Within', and the whole mirror universe concept, but those aren't duplicates.)

Re: Facebook's std::vector optimization

#13

Post by xroche » Sat, Aug 30, 2014, 12:45 PM UTC

pjmlp wrote: post #9

xroche wrote: post #5

Yep, this is my biggest issue with C++: you now have lambdas functions and an insane template spec, but you just can not "realloc" a new[] array. Guys, seriously ?

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.

Re: Facebook's std::vector optimization

#14

Post by bnegreve » Sat, Aug 30, 2014, 12:57 PM UTC

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.

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

Re: Facebook's std::vector optimization

#15

Post by xroche » Sat, Aug 30, 2014, 1:10 PM UTC

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.

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

Re: Facebook's std::vector optimization

#16

Post by marksamman » Sat, Aug 30, 2014, 1:37 PM UTC

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.

guarantee != possibility. There's no guarantee with realloc, but there's no possibility with new[], copy and delete[].

You can't grow the size you allocated with new[] in-place, and because you need to retain the existing data it's not safe to delete[] the old buffer, call new[] and hope that it points to the previous memory address and assume that the existing data remains intact.

A realloc implementation can try to grow the buffer if there's contiguous space, and if it succeeds it doesn't need to deallocate or copy anything. I haven't had a look at realloc implementations so I don't know if that, or other optimizations are done in practice, but I assume that realloc's worst performance case is somewhere around new[], copy and delete[]'s best case.

The copy mechanism in std::vector may also have a significant overhead over realloc if it has to call the copy constructor (or ideally move constructors in C++11) of every object in the vector, although I can imagine a C++ equivalent of realloc doing so too.

Re: Facebook's std::vector optimization

#17

Post by CJefferson » Sat, Aug 30, 2014, 1:42 PM UTC

I'm glad to see this catch on and the C level primitives get greater use.

This has been a well known problem in the C++ community for years, in particular Howard Hinnant put a lot of work into this problem. I believe the fundamental problem has always been that C++ implementations always use the underlying C implementations for malloc and friends, and the C standards committee could not be pursaded to add the necessary primitives.

A few years ago I tried to get a reallic which did not move (instead returned fail) into glibc and jealloc and failed. Glad to see someone else has succeeded.

Re: Facebook's std::vector optimization

#18

Post by [deleted] » Sat, Aug 30, 2014, 1:43 PM UTC

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.

[deleted]

Re: Facebook's std::vector optimization

#19

Post by bnegreve » Sat, Aug 30, 2014, 1:51 PM UTC

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.

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 'allocate' call.

Edit2: So I've implemented an allocator that behaves (almost) like a described above but I admit that it's a bit more hacky than I though. Drop me an email if you're interested.

Re: Facebook's std::vector optimization

#20

Post by cliff_r » Sat, Aug 30, 2014, 1:56 PM UTC

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.