Comment by lossolo | Hacker News Reader

Comment by lossolo | Hacker News Reader

Parent Full thread

> Vec::reserve_exact is a more narrow idea - we can hint about the ultimate capacity needed, if we're wrong and later need more capacity this has a significant performance cost because we thew away the amortized growth promise to get this, but we don't waste memory.

The claim that using reserve_exact "throws away the amortized growth promise" is wrong. You don't disable amortized growth, you just won't get extra headroom from that call. If you guessed too small, you may pay an extra reallocation later. Rust's Vec still provides amortized O(1) push overall.

> C++ only provides the equivalent of Vec::reserve_exact which makes this a footgun but if you use this call when you really needed the other one you trash your perf, as a result of which people teaching C++ tend to just say don't use reservation to uh, reserve capacity, but now you're leaving perf on the table so that's not great.

It's not a reserve_exact only footgun. The standard says reserve(n) makes capacity at least n, implementations may allocate exactly n ( and many do), but they're allowed to overallocate and future growth remains amortized. Used properly (when you know or can bound the size), reserve is a common and recommended optimization.

> The claim that using reserve_exact "throws away the amortized growth promise" is wrong

Well, in some sense this depends on what exactly you think you're amortizing over. If you `Vec::reserve` with size N, fill to N, and then append a single element you get the usual amortized O(1) growth of an append (or at least you can, the docs for `Vec::reserve` say it may reserve additional space, not that it must). But if you `Vec::reserve_exact` with size N, fill to N, and then append a single element you are guaranteeing that that first append triggers a potentially O(N) resize.

From that point on in either case you would get the usual amortized growth of course.

Sure, but this isn't a job for reserve_exact. Vec::reserve is like a framing hammer made for speed and momentum. You might dent a little extra wood (overallocate), but you drive lots of nails fast and keep amortized O(1) growth. reserve_exact is a jeweler's hammer so great when you know the exact setting and won't touch it again, precise fit, zer slack etc.

Now, try to frame a house with jeweler's hammer, tapping in tiny increments and resizing every few boards and you will crawl into quadratic time.

Who is using jeweler's hammer to frame their house?

So what I'm arguing is if you don't misuse reserve_exact, then as you said you still get amortized growth. The OP's example misuses the tool and then blames it for not behaving differently on that first append.

> if you `Vec::reserve_exact` with size N, fill to N, and then append a single element you are guaranteeing that that first append triggers a potentially O(N) resize.

The documentation does not guarantee this, because memory allocators can't typically allocate arbitrarily-sized blocks of memory, instead rounding to the nearest supported size. For example, for small allocations glibc malloc allocates in multiples of 8 bytes, with a minimum size of 24 bytes. So if you make a 35-byte allocation, there will be 5 bytes of wasted space at the end which you could theoretically use to store more elements without reallocating if your collection grows.

If you're using the system allocator, Rust can't take advantage of this, because the C malloc/free APIs don't provide any (portable) way for the allocator to inform the application about this excess capacity. But Rust's (currently unstable) API for custom allocators does expose this information, and the documentation is written to allow Vec to take advantage of this information if available. If you reserve_exact space for 35 u8's, and your allocator rounds to 40 bytes (and informs the Vec of this the allocator API), then the vector is allowed to set its capacity to 40, meaning the next append would not trigger a resize.

On current stable Rust, this is all just theoretical and Vec works as you describe -- but the documentation specifically does not promise this because the situation is expected to change in the future.

> The claim that using reserve_exact "throws away the amortized growth promise" is wrong

The key part is that multiple calls reserve_exact will cause repeated allocations. The classic example is if someone defines a `pushfive` function that uses reserve_exact to increase the size by 5, and then pushes 5 times. Calling this function in a loop will take quadratic time since each reserve_exact call increases the array size. With reserve, the runtime is linear as expected.

Quadratic pushfive is just a cautionary tale about misusing reserve_exact. Basically use reserve_exact when you know the final size (reserve once), or you're doing a one off tight sizing where memory footprint matters.

Don't pre reserve inside pushfive, just push the 5 elements (Vec handles growth) or if you know how many times you'll call pushfive in a loop, reserve up front once vec.reserve(5 * times) or use reserve instead of reserve_exact for incremental growth.

that's exactly the footgun. reserve_exact usage needs to be analyzed globally, while `resere` has the extra fuzziness needed to ensure that you can't mess anything up too badly with it.

Calling that a "footgun" feels really overstated.

Yes, reserve is the safer default because it gives you slack and preserves amortized growth even if your usage pattern is messy.

But "needs global analysis" isn't unique to reserve_exact. Lots of perf knobs do (chunk sizes, buffering, locking granularity etc). The fix to this is to use the tool where its preconditions actually hold, not to avoid the tool.

So what I'm basically saying is that reserve_exact isn't inherently dangerous, it just assumes you know the final size and won't exceed it etc. If you keep bumping it in tiny steps (pushfive style), that's just misuse so treating it as a flaw is unwarranted.

> reserve_exact isn't inherently dangerous

Dangerous is perhaps overstating it, but the only utility reserve(_exact) has is performance and predictability. If using the API can be worse than doing nothing, I think it warrants being referred to as a footgun.

Reply on news.ycombinator.com