Facebook's std::vector optimization
github.com
Facebook's std::vector optimization
1–10 of 93 posts
Re: Facebook's std::vector optimization
#2[deleted]
Re: Facebook's std::vector optimization
#3TLDR; The author of malloc and std::vector never talked to each other. We fixed that!
... also most types are memmovables
Re: Facebook's std::vector optimization
#4You 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...
Re: Facebook's std::vector optimization
#5Yep, 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 ?
Re: Facebook's std::vector optimization
#6Then 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")
Re: Facebook's std::vector optimization
#7Yep, 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 ?
If you need to realloc a fixed size array, souldn't you use a std::vector instead?
Re: Facebook's std::vector optimization
#8Yep, 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 ?
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.
Re: Facebook's std::vector optimization
#9Yep, 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.
Re: Facebook's std::vector optimization
#10When 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 programmer, and dynamic allocation is one of the things that I very much avoid if I don't have to - I prefer constant-space algorithms. If it means a scan of the data first to find out the right size before allocating, then I'll do that - modern CPUs are very fast "going in a straight line", and realloc costs add up quickly.
Another thing that I've done, which I'm not entirely sure would be possible in "pure C++", is to adjust the pointers pointing to the object if reallocation moves it (basically, add the difference between the old and new pointers to each reference to the object); in theory I believe this involves UB - so it might not be "100% standard C" either, but in practice, this works quite well.