3 ms·

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 immed

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.

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.