5 ms·

Because this is focused on how the data structure works it doesn't mention lots of nice API design choices in Rust. The one I particularly want to call out bec

Because this is focused on how the data structure works it doesn't mention lots of nice API design choices in Rust. The one I particularly want to call out because it came up this morning is providing both Vec::reserve and Vec::reserve_exact Vec::reserve lets us hint about our upcoming capacity expectations without damaging the O(1) amortized growth which is the whole point of this collection type, but it can waste some memory to achieve this. This is probably what you want in most code. 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. 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.

smallstepforman 1y ago
From your description, I cannot determine the difference. Engineers like exact things, whats this fuzzy concept called “hint”?
- throwaway173738 1y ago
  Suppose I think I may need 128 entries at some point, but the vector is allocated with room for 16 entries by default. I may not want to allocate and then immediately allocate again. But if I get to a 17th entry then I’m already causing allocation. So I might as well allocate 128 at that time so there are no more allocations at all.
  - demurgos 1y ago
    I believe that you are describing `Vec::with_capacity` which allows to change the initial reserved memory on construction. `reserve` and `reserve_exact` are used when mutating an existing vec. What you provide is not the total wanted capacity but the additional wanted capacity. `reserve` allows to avoid intermediate allocation. Let's say that you have a vec with 50 items already and plan to run a loop to add 100 more (so 150 in total). The initial internal capacity is most likely 64, if you just do regular `push` calls without anything else, there will be two reallocations: one from 64 to 128 and one from 128 to 256. If you call `reserve(100)`, you'll be able to skip the intermediate 64 to 128 reallocation: it will do a single reallocation from 64 to 256 and it will be able to handle the 100 pushes without any reallocation. If you call `reserve_exact(100)`, you'll get a single reallocation for from 64 to 150 capacity, and also guarantee no reallocation during the processing loop. The difference is that `reserve_exact` is better if these 100 items were the last ones you intended to push as you get a full vec of capacity 150 and containing 150 items. However, if you intend to push more items later, maybe 100 more, then you'd need to reallocate and break the amortized cost guarantees. With `reserve`, you don't break the amortized cost if there are follow-up inserts; at the price of not being at 100% usage all the time. In the `reserve` case, the capacity of 256 would be enough and let you go from 150 to 250 items without any reallocation. In short, a rule of thumb could be: - If creating a vec and you know the total count, prefer `Vec::with_capacity` - If appending a final chunk of items and then no longer adding items, prefer `Vec::reserve_exact` - If appending a chunk of items which may not be final, prefer `Vec::reserve`
    - rsyring 1y ago
      This should be in the docs or a blog post somewhere. Very clear explanation.
      - demurgos 1y ago
        That's a nice idea, thank you. I have personal blog, I'll try to clean it up a bit and provide performance measurements so it's worth posting. Regarding the official documentation, I've returned to read them. I agree that the docs would benefit from more discussion about when to use each method. In particular, the code examples are currently exactly the same which is not great. Still, the most critical piece of information is there [0] > Prefer `reserve` if future insertions are expected. If anyone wants to reuse my explanation above, feel free to do it; no need to credit. [0]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve_exact https://doc.rust-lang.org/std/vec/struct.Vec.html#method.res...
      - unshavedyak 1y ago
        It is, though not worded as nicely as the GP comment. docs: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve_exact https://doc.rust-lang.org/std/vec/struct.Vec.html#method.res...
  - arka2147483647 1y ago
    All the functions mentioned above, even the cpp one, will reserve atleast the number of elements given to resize() or resize_exact(), but may reserve more than that. After some pondering, and reading the rust documentation, I came to the conclusion that te difference is this: reserve() will grow the underlaying memory area to the next increment, or more than one increment, while reserve_exact() will only grow the underlaying memory area to the next increment, but no more than that. Eg, if grow strategy is powers of two, and we are at pow(2), then reserve() may skip from pow(2) to pow(4), but reserve_exact() would be constrained to pow(3) as the next increment. Or so i read the documentation. Hopefully someone can confirm?
    - swiftcoder 1y ago
      > even the cpp one, will reserve atleast the number of elements given The C++ one, however, will not reserve more than you ask for (in the case that you reserve greater than the current capacity). It's an exact reservation in the rust sense. > reserve() will grow the underlaying memory area to the next increment, or more than one increment, while reserve_exact() will only grow the underlaying memory area to the next increment, but no more than that No, not quite. Reserve will request as many increments as it needs, and reserve_exact will request the exact total capacity it needs. Where the docs get confusing, is that the allocator also has a say here. In either case, if you ask for 21 items, and the allocator decides it prefers to give you a full page of memory that can contain, say, 32 items... then the Vec will use all the capacity returned by the allocator.
      - kbolino 1y ago
        As far as I can tell, in the current implementation, reserve_exact is indeed exact. The only situation in which the capacity after calling reserve_exact will not equal length + additional is when it was already greater than that. Even if the allocator gives more than the requested amount of memory, the excess is ignored for the purposes of Vec's capacity: https://github.com/rust-lang/rust/blob/4b57d8154a6a74d2514cd3a674c1f29a588f224a/library/alloc/src/raw_vec/mod.rs#L728 https://github.com/rust-lang/rust/blob/4b57d8154a6a74d2514cd... Of course, this can change in the future; in particular, the entire allocator API is still unstable and likely won't stabilize any time soon.
- mytailorisrich 1y ago
  The difference according to Rust doc itsef: reserve() > Reserves capacity for at least additional more elements to be inserted in the given Vec<T>. The collection may reserve more space to speculatively avoid frequent reallocations. reserve_exact() > Reserves the minimum capacity for at least additional more elements to be inserted in the given Vec<T>. Unlike reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations... Prefer reserve if future insertions are expected. So if you know you'll need n now but will probably need more later, use reserve(). If you know n is all you'll need, use reserve_exact(). Vec<T> is a contiguous growable array, so the optimization game is to minimise allocations, reallocations (to keep it contiguous), and unused allocated memory.
  - deleted 1y ago
    [deleted]
  - kstrauser 1y ago
    I could look this up, but I’m enjoying reading this conversation. Do reserve and reserve_exact increment the capacity, or ensure there’s still at least that much capacity remaining? If the former, if I reserve(1) 10 times in a row, does that mean it could be rounding up to a thousand elements (say, because of the page table size) each time?
    - tialaramex 1y ago
      At least that much remaining. For both Vec::reserve and Vec::reserve_exact the parameter is an unsigned integer representing how many more items you expect to need space for. So reserve(1) 10 times in a row will just repeatedly ensure there's enough space for at least 1 more item, which after the first time there certainly is† There's an excellent chance the capacity check in particular got inlined, so the optimized machine code will not "actually" call a function ten times, it'll call it once and then maybe emit a single capacity check inline, the subsequent checks even a crap 1980s optimiser will go "We do not need to check that again" and skip it. † If the Vec is full and can't grow, which really can happen for Zero Size Types in particular, then this panics, and what happens next is a compile time choice, in debug likely it just tells you what went wrong and suggests how to make a backtrace. In the ordinary case that we instead got to keep running then it succeeded.
- pornel 1y ago
  reserve() reallocates by at least doubling the capacity. reserve_exact() reallocates by exactly what you ask for. If you reserve() space for 1 more element a 1000 times, you will get ~30 reallocations, not 1000. This inexact nature is useful when the total size is unknown, but you append in batches. You could implement your own amortised growth strategy, but having one built-in makes it simple for different functions to cooperate.
  - teo_zero 1y ago
    > If you reserve() space for 1 more element a 1000 times, you will get ~30 reallocations, not 1000. Surely you mean ~10 reallocations, because 2^10=1024, right?
- charcircuit 1y ago
  Hint means that the implementation is free to ignore it. It's just some extra metadata that the implementation can optionally make use of.
  - NobodyNada 1y ago
    In this case, the implementation is not free to ignore calls to reserve or reserve_exact -- the documentation makes explicit guarantees about this: "After calling reserve, capacity will be greater than or equal to self.len() + additional". This matters for performance reasons, and also because unsafe code is allowed to use the extra capacity of the vector -- e.g. you can write to the unused space and then call set_len to insert elements in-place. If `reserve` did not guarantee the requested capacity was allocated, this would cause buffer overflows. The documentation for these functions is very carefully worded to explain exactly what each method does and does not guarantee. Both functions have the exact same hard guarantees: after calling the function, the vector will have at least enough capacity for the additional elements. The difference is in what the methods try to do without guaranteeing exact behavior: reserve follows the usual amortized growth pattern, while reserve_exact tries to avoid overallocating. These are described as best-effort performance optimizations rather than guarantees you can rely on because 1) the amortized growth strategy is subject to change between platforms and compiler versions, and 2) memory allocators typically don't support arbitrarily-sized blocks of memory, and instead round up to the nearest supported size.
lossolo 1y ago
> 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.
- adgjlsfhk1 1y ago
  > 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.
  - lossolo 1y ago
    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.
panzi 1y ago
Just today I saw a (2 year old) video on that very topic in Rust and C++: https://www.youtube.com/watch?v=algDLvbl1YY https://www.youtube.com/watch?v=algDLvbl1YY Towards the end they mention what to use instead in C++ to get the same characteristics as Rust's Vec::reserve: vec.insert( vec.cend(), std::move_iterator(newElems.begin()), std::move_iterator(newElems.end()) );
- tialaramex 1y ago
  This is roughly analogous to Vec's specialised Extend implementation. Like that feature it only helps if you've got a similar API shape you're adapting. If we need to make newElems then we're probably not getting a perf win from this.
TinkersW 1y ago
Reserve(reserve_exact in rust lingo) as a concept doesn't throw away amortized growth promise, so this entire post makes no sense. You would need a very shitty implementation to achieve anything close to what you are describing(perhaps only allocating in powers of 2), and even then it would recover fairly quickly.

smallstepforman 1y ago

From your description, I cannot determine the difference. Engineers like exact things, whats this fuzzy concept called “hint”?

throwaway173738 1y ago
Suppose I think I may need 128 entries at some point, but the vector is allocated with room for 16 entries by default. I may not want to allocate and then immediately allocate again. But if I get to a 17th entry then I’m already causing allocation. So I might as well allocate 128 at that time so there are no more allocations at all.
- demurgos 1y ago
  I believe that you are describing `Vec::with_capacity` which allows to change the initial reserved memory on construction. `reserve` and `reserve_exact` are used when mutating an existing vec. What you provide is not the total wanted capacity but the additional wanted capacity. `reserve` allows to avoid intermediate allocation. Let's say that you have a vec with 50 items already and plan to run a loop to add 100 more (so 150 in total). The initial internal capacity is most likely 64, if you just do regular `push` calls without anything else, there will be two reallocations: one from 64 to 128 and one from 128 to 256. If you call `reserve(100)`, you'll be able to skip the intermediate 64 to 128 reallocation: it will do a single reallocation from 64 to 256 and it will be able to handle the 100 pushes without any reallocation. If you call `reserve_exact(100)`, you'll get a single reallocation for from 64 to 150 capacity, and also guarantee no reallocation during the processing loop. The difference is that `reserve_exact` is better if these 100 items were the last ones you intended to push as you get a full vec of capacity 150 and containing 150 items. However, if you intend to push more items later, maybe 100 more, then you'd need to reallocate and break the amortized cost guarantees. With `reserve`, you don't break the amortized cost if there are follow-up inserts; at the price of not being at 100% usage all the time. In the `reserve` case, the capacity of 256 would be enough and let you go from 150 to 250 items without any reallocation. In short, a rule of thumb could be: - If creating a vec and you know the total count, prefer `Vec::with_capacity` - If appending a final chunk of items and then no longer adding items, prefer `Vec::reserve_exact` - If appending a chunk of items which may not be final, prefer `Vec::reserve`
  - rsyring 1y ago
    This should be in the docs or a blog post somewhere. Very clear explanation.
    - demurgos 1y ago
      That's a nice idea, thank you. I have personal blog, I'll try to clean it up a bit and provide performance measurements so it's worth posting. Regarding the official documentation, I've returned to read them. I agree that the docs would benefit from more discussion about when to use each method. In particular, the code examples are currently exactly the same which is not great. Still, the most critical piece of information is there [0] > Prefer `reserve` if future insertions are expected. If anyone wants to reuse my explanation above, feel free to do it; no need to credit. [0]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve_exact https://doc.rust-lang.org/std/vec/struct.Vec.html#method.res...
    - unshavedyak 1y ago
      It is, though not worded as nicely as the GP comment. docs: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.reserve_exact https://doc.rust-lang.org/std/vec/struct.Vec.html#method.res...
- arka2147483647 1y ago
  All the functions mentioned above, even the cpp one, will reserve atleast the number of elements given to resize() or resize_exact(), but may reserve more than that. After some pondering, and reading the rust documentation, I came to the conclusion that te difference is this: reserve() will grow the underlaying memory area to the next increment, or more than one increment, while reserve_exact() will only grow the underlaying memory area to the next increment, but no more than that. Eg, if grow strategy is powers of two, and we are at pow(2), then reserve() may skip from pow(2) to pow(4), but reserve_exact() would be constrained to pow(3) as the next increment. Or so i read the documentation. Hopefully someone can confirm?
  - swiftcoder 1y ago
    > even the cpp one, will reserve atleast the number of elements given The C++ one, however, will not reserve more than you ask for (in the case that you reserve greater than the current capacity). It's an exact reservation in the rust sense. > reserve() will grow the underlaying memory area to the next increment, or more than one increment, while reserve_exact() will only grow the underlaying memory area to the next increment, but no more than that No, not quite. Reserve will request as many increments as it needs, and reserve_exact will request the exact total capacity it needs. Where the docs get confusing, is that the allocator also has a say here. In either case, if you ask for 21 items, and the allocator decides it prefers to give you a full page of memory that can contain, say, 32 items... then the Vec will use all the capacity returned by the allocator.
    - kbolino 1y ago
      As far as I can tell, in the current implementation, reserve_exact is indeed exact. The only situation in which the capacity after calling reserve_exact will not equal length + additional is when it was already greater than that. Even if the allocator gives more than the requested amount of memory, the excess is ignored for the purposes of Vec's capacity: https://github.com/rust-lang/rust/blob/4b57d8154a6a74d2514cd3a674c1f29a588f224a/library/alloc/src/raw_vec/mod.rs#L728 https://github.com/rust-lang/rust/blob/4b57d8154a6a74d2514cd... Of course, this can change in the future; in particular, the entire allocator API is still unstable and likely won't stabilize any time soon.
mytailorisrich 1y ago
The difference according to Rust doc itsef: reserve() > Reserves capacity for at least additional more elements to be inserted in the given Vec<T>. The collection may reserve more space to speculatively avoid frequent reallocations. reserve_exact() > Reserves the minimum capacity for at least additional more elements to be inserted in the given Vec<T>. Unlike reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations... Prefer reserve if future insertions are expected. So if you know you'll need n now but will probably need more later, use reserve(). If you know n is all you'll need, use reserve_exact(). Vec<T> is a contiguous growable array, so the optimization game is to minimise allocations, reallocations (to keep it contiguous), and unused allocated memory.
- deleted 1y ago
  [deleted]
- kstrauser 1y ago
  I could look this up, but I’m enjoying reading this conversation. Do reserve and reserve_exact increment the capacity, or ensure there’s still at least that much capacity remaining? If the former, if I reserve(1) 10 times in a row, does that mean it could be rounding up to a thousand elements (say, because of the page table size) each time?
  - tialaramex 1y ago
    At least that much remaining. For both Vec::reserve and Vec::reserve_exact the parameter is an unsigned integer representing how many more items you expect to need space for. So reserve(1) 10 times in a row will just repeatedly ensure there's enough space for at least 1 more item, which after the first time there certainly is† There's an excellent chance the capacity check in particular got inlined, so the optimized machine code will not "actually" call a function ten times, it'll call it once and then maybe emit a single capacity check inline, the subsequent checks even a crap 1980s optimiser will go "We do not need to check that again" and skip it. † If the Vec is full and can't grow, which really can happen for Zero Size Types in particular, then this panics, and what happens next is a compile time choice, in debug likely it just tells you what went wrong and suggests how to make a backtrace. In the ordinary case that we instead got to keep running then it succeeded.
pornel 1y ago
reserve() reallocates by at least doubling the capacity. reserve_exact() reallocates by exactly what you ask for. If you reserve() space for 1 more element a 1000 times, you will get ~30 reallocations, not 1000. This inexact nature is useful when the total size is unknown, but you append in batches. You could implement your own amortised growth strategy, but having one built-in makes it simple for different functions to cooperate.
- teo_zero 1y ago
  > If you reserve() space for 1 more element a 1000 times, you will get ~30 reallocations, not 1000. Surely you mean ~10 reallocations, because 2^10=1024, right?
charcircuit 1y ago
Hint means that the implementation is free to ignore it. It's just some extra metadata that the implementation can optionally make use of.
- NobodyNada 1y ago
  In this case, the implementation is not free to ignore calls to reserve or reserve_exact -- the documentation makes explicit guarantees about this: "After calling reserve, capacity will be greater than or equal to self.len() + additional". This matters for performance reasons, and also because unsafe code is allowed to use the extra capacity of the vector -- e.g. you can write to the unused space and then call set_len to insert elements in-place. If `reserve` did not guarantee the requested capacity was allocated, this would cause buffer overflows. The documentation for these functions is very carefully worded to explain exactly what each method does and does not guarantee. Both functions have the exact same hard guarantees: after calling the function, the vector will have at least enough capacity for the additional elements. The difference is in what the methods try to do without guaranteeing exact behavior: reserve follows the usual amortized growth pattern, while reserve_exact tries to avoid overallocating. These are described as best-effort performance optimizations rather than guarantees you can rely on because 1) the amortized growth strategy is subject to change between platforms and compiler versions, and 2) memory allocators typically don't support arbitrarily-sized blocks of memory, and instead round up to the nearest supported size.

lossolo 1y ago

> 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.

adgjlsfhk1 1y ago
> 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.
- lossolo 1y ago
  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.

panzi 1y ago

Just today I saw a (2 year old) video on that very topic in Rust and C++: https://www.youtube.com/watch?v=algDLvbl1YY https://www.youtube.com/watch?v=algDLvbl1YY Towards the end they mention what to use instead in C++ to get the same characteristics as Rust's Vec::reserve: vec.insert( vec.cend(), std::move_iterator(newElems.begin()), std::move_iterator(newElems.end()) );

tialaramex 1y ago
This is roughly analogous to Vec's specialised Extend implementation. Like that feature it only helps if you've got a similar API shape you're adapting. If we need to make newElems then we're probably not getting a perf win from this.

TinkersW 1y ago

Reserve(reserve_exact in rust lingo) as a concept doesn't throw away amortized growth promise, so this entire post makes no sense. You would need a very shitty implementation to achieve anything close to what you are describing(perhaps only allocating in powers of 2), and even then it would recover fairly quickly.