A deep dive into SmallVector:push_back

Post by im3w1l » Wed, Jul 01, 2026, 5:23 PM UTC

tialaramex wrote: post #7

im3w1l wrote: post #6

So one thing I thought of when reading this is that very often it is known ahead of time (at runtime or even compile-time) how many push_backs will be done. The programmer could make a reserve call but doesn't bother since the efficiency gain is minimal. The gain is minimal for doing this optimization at one location. But doing it everywhere, that could matter. Pushing back in a loop could maybe be optimized to a sin…

In C++ programmers are often taught not to use their reservation API for this purpose because it's designed in such a way that if you don't have perfect foresight you can destroy amortization and thus get much worse performance. For example Bjarne Stroustrup suggests you should use reservation for "avoiding invalidation of iterators" instead.

Sorry I completely messed up in communicating my point: That it would be nice if the compiler would do it for us automatically in the many simple cases. That's what I tried to say, but didn't say, when I said it could matter fixing it everywhere.

Post by dzaima » Wed, Jul 01, 2026, 5:35 PM UTC

tialaramex wrote: post #10

oneshtein wrote: post #8

Earlier quoted context omitted.

API should have reserve_at_least(n) and reserve_exactly(n), instead of one reserve(n), which works as reserve_exactly(n), but described as reserve_at_least(n).

I agree that this is the better design. Rust calls these Vec::reserve and Vec::reserve_exact Zig calls the analagous methods ensureTotalCapacity and ensureTotalCapacityPrecise It's worth mentioning that talk of "exact" and "precise" may be misleading because it probably makes sense to (and despite that word exact Vec does explicitly say it might) discern that the actual allocation was big enough for slightly more ite…

Note that glibc does provide a malloc_usable_size to query the size of a malloc'd block; not standard though of course.

A problem with just directly exposing such is it makes precise sanitizing impossible, as you'd have to tolerate some out-of-intended-bounds reads/writes. (and making the sanitizer always give exact-size allocations would also be bad as that'd end up not testing code paths that may break when they're not)

Re: A deep dive into SmallVector:push_back

Re: A deep dive into SmallVector:push_back