Re:Drop millions of allocations by using a linked list (2015)
by gpderetta on Friday March 12, 2021 @11:52AM
(#26437794)
MSVC STL uses the golden ratio instead of doubling for std::vector allocation which means that you can reuse contiguous runs of previously deallocated chunks to fulfill future allocations, while still meeting the standard asymptotic O(1) bound on push_back.
I believe that GCC's libstdc++ tested the strategy on a set of real programs and didn't measure any actual difference so they still use doubling.
I believe that GCC's libstdc++ tested the strategy on a set of real programs and didn't measure any actual difference so they still use doubling.