3 ms·
One thing I've been mulling over recently is that many containers like vector in C++ for example, have almost no state. That is to say, we at most might have a
by mhh__ 5y ago
One thing I've been mulling over recently is that many containers like vector in C++ for example, have almost no state.
That is to say, we at most might have a bit of logic to tune whether we do *1.5 or *2 on realloc, but why not more?
There must be patterns we can exploit in common use cases to be sneaky and do less malloc-ing. Profile guided? Runtime? I might have some results by Christmas, I have some ideas.
Food for thought: Your container has a few bytes of state to make decisions with, your branch predictor has a few megabytes these days.
- viraptor 5y agoWhile some heuristics would be nice if they improve the situation, a lot of apps still leave performance on the table by not estimating the capacity well. You don't have to be very clever about growth if you know that this vector will always have 3 elements and that one will have N that you can estimate from data size.
- gary_0 5y agoPlease don't give the C++ people any more ideas, my compile times are already bad enough!
- mhh__ 5y agoThis could actually make your compiler a lot faster, compilers are really hard to maintain an efficient memory strategy in due to all the moving parts
- jabl 5y agoThe size increase factor for vector is a compromise between performance and wasting memory. It's also a fairly hot code path, so you don't want to run some complicated code there to estimate the 'optimal' factor. About the best you can do is if you know beforehand roughly how big it will be, is to reserve that capacity with std::vector::reserve().
- mhh__ 5y agoMalloc is at best a few hundred cycles, that's quite a lot of work if you can keep your data in L1. If you do a bit of work now you can save reallocs later. Think bigger than changing the coefficient, there probably is no optimal factor.
- mst 5y agoIsn't that basically what slab/pool type allocators help with or am I being an idiot?
- account42 5y ago> About the best you can do is if you know beforehand roughly how big it will be, is to reserve that capacity with std::vector::reserve(). But be careful not to call reserve() in a loop adding data to a vector - will allocated exactly what you request and not do exponential growth.
- steerablesafe 5y agostd::vector would mostly benefit from an improved allocator interface, where it requests N bytes, but the allocator can give more than that and report the actual value.
- kevincox 5y agoFor example folly's vector performs this optimization: https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md#the-jemalloc-connection https://github.com/facebook/folly/blob/master/folly/docs/FBV...
- account42 5y agoYou can look forward to C++23 then: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0401r6.html http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p040...