Under the hood: Vec(marma.dev)
marma.dev
Under the hood: Vec
https://marma.dev/articles/2025/under-the-hood-vec-t
141 comments
Hey, author here :).
Thank you for your critique and you are right, I struggled with this chapter a lot.
I will read the link to get a better understanding of this type and update the section.
If I may ask, do you have more sources where I can read up on the history and current uses of unique besides the rustonomicon?
Thank you again for your engagement! It is very helpful to get these insights from people with more knowledge.
Thank you for your critique and you are right, I struggled with this chapter a lot.
I will read the link to get a better understanding of this type and update the section.
If I may ask, do you have more sources where I can read up on the history and current uses of unique besides the rustonomicon?
Thank you again for your engagement! It is very helpful to get these insights from people with more knowledge.
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.
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.
> 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. 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.
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.
> 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 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.
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.
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.
> 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.
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.
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.
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.
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.
Just today I saw a (2 year old) video on that very topic in Rust and C++: 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())
);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.
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.
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.
From your description, I cannot determine the difference. Engineers like exact things, whats this fuzzy concept called “hint”?
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.
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`
`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`
This should be in the docs or a blog post somewhere. Very clear explanation.
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.res...
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.res...
It is, though not worded as nicely as the GP comment.
docs: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.res...
docs: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.res...
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?
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?
> 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.
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.
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/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.
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.
Maybe more interestingly, line 659, slightly above that, explains that we know we got [u8] but today the ordinary Rust allocator promises capacity is correct, so we just ignore the length of that slice.
We could, as that comment suggests, check the slice and see if there's enough room for more than our chosen capacity. We could also debug_assert that it's not less room, 'cos the Allocator promised it would be big enough. I dunno if that's worthwhile.
We could, as that comment suggests, check the slice and see if there's enough room for more than our chosen capacity. We could also debug_assert that it's not less room, 'cos the Allocator promised it would be big enough. I dunno if that's worthwhile.
https://en.cppreference.com/w/cpp/container/vector/reserve.h...
says
> Increase the capacity of the vector (the total number of elements that the vector can hold without requiring reallocation) to a value that's greater or equal to new_cap.
I belive that the behaviour of reserve() is implementation defined.
says
> Increase the capacity of the vector (the total number of elements that the vector can hold without requiring reallocation) to a value that's greater or equal to new_cap.
I belive that the behaviour of reserve() is implementation defined.
Because there's only a single function here, it has to either be Vec::reserve or Vec::reserve_exact
If you don't offer Vec::reserve_exact then people who needed that run out of RAM and will dub your stdlib garbage. If you don't offer Vec::reserve as we've seen C++ programmers will say "Skill issue" whenever a noob gets awful performance as a result. So, it's an easy choice.
If you don't offer Vec::reserve_exact then people who needed that run out of RAM and will dub your stdlib garbage. If you don't offer Vec::reserve as we've seen C++ programmers will say "Skill issue" whenever a noob gets awful performance as a result. So, it's an easy choice.
That said MSVC,GCC and clang all implement it to allocate an exact value.
> 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.
It would be nice if this were true but AFAIK the memory allocator interface is busted - Rust inherits the malloc-style from C/C++ which doesn’t permit the allocator to tell the application “you asked for 128 bytes but I gave you an allocation for 256”. The alloc method just returns a naked u8 pointer.
It would be nice if this were true but AFAIK the memory allocator interface is busted - Rust inherits the malloc-style from C/C++ which doesn’t permit the allocator to tell the application “you asked for 128 bytes but I gave you an allocation for 256”. The alloc method just returns a naked u8 pointer.
The global allocator GlobalAlloc::alloc method does indeed return a naked pointer
But the (not yet stable) Allocator::allocate returns Result<NonNull<[u8]>, AllocError> --- that is, either a slice of bytes OR a failure.
Vec actually relies on Allocator not GlobalAlloc (it's part of the standard library so it's allowed to use unstable features)
So that interface is allowed to say you asked for 128 bytes but here's 256. Or, more likely, you asked for 940 bytes, but here's 1024. So if you were trying to make a Vec<TwentyByteThing> and Vec::with_capacity(47) it would be practical to adjust this so that when the allocator has 1024 bytes available but not 940 we get back a Vec with capacity 51 not 47.
But the (not yet stable) Allocator::allocate returns Result<NonNull<[u8]>, AllocError> --- that is, either a slice of bytes OR a failure.
Vec actually relies on Allocator not GlobalAlloc (it's part of the standard library so it's allowed to use unstable features)
So that interface is allowed to say you asked for 128 bytes but here's 256. Or, more likely, you asked for 940 bytes, but here's 1024. So if you were trying to make a Vec<TwentyByteThing> and Vec::with_capacity(47) it would be practical to adjust this so that when the allocator has 1024 bytes available but not 940 we get back a Vec with capacity 51 not 47.
You misread the documentation. Reserve-exact is precisely that - the growth strategy is ignored and you are ensured that at least that many more elements can be inserted without a reallocation. Eg reserve_exact(100) on an empty Vec allocates space for 100 elements.
By contrast reserve will allocate space for the extra elements following the growth strategy. If you reserve(100) on an empty Vec the allocation will be able to actually insert 128 (assuming the growth strategy is pow(n))
By contrast reserve will allocate space for the extra elements following the growth strategy. If you reserve(100) on an empty Vec the allocation will be able to actually insert 128 (assuming the growth strategy is pow(n))
Actually that's not quite correct.
Vec::reserve(100) on an empty Vec will give you capacity 100, not 128 even though our amortization is indeed doubling.
The rules go roughly like this, suppose length is L, present capacity is C, reserve(N):
1. L + N < C ? Enough capacity already, we're done, return
2. L + N <= C * 2 ? Ordinary doubling, grow to capacity C * 2
3. Otherwise, try to grow to L + N
This means we can grow any amount more quickly than the amortized growth strategy or at the same speed - but never less quickly. We can go 100, 250, 600, 1300 and we can go 100, 200, 400, 800, 1600 - but we can''t do 100, 150, 200, 250, 300, 350, 400, 450, 500...
Vec::reserve(100) on an empty Vec will give you capacity 100, not 128 even though our amortization is indeed doubling.
The rules go roughly like this, suppose length is L, present capacity is C, reserve(N):
1. L + N < C ? Enough capacity already, we're done, return
2. L + N <= C * 2 ? Ordinary doubling, grow to capacity C * 2
3. Otherwise, try to grow to L + N
This means we can grow any amount more quickly than the amortized growth strategy or at the same speed - but never less quickly. We can go 100, 250, 600, 1300 and we can go 100, 200, 400, 800, 1600 - but we can''t do 100, 150, 200, 250, 300, 350, 400, 450, 500...
[deleted]
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.
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.
> 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?
Surely you mean ~10 reallocations, because 2^10=1024, right?
Hint means that the implementation is free to ignore it. It's just some extra metadata that the implementation can optionally make use of.
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.
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.
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.
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]
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?
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?
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.
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.
That makes sense, and it's how I'd hope it'd work. I can imagine all sorts of cases where I'm getting data from an external source, like an API request returning some mudball of data monstrosity, where the easiest path doesn't give all the information at once.
Nice. I truly do appreciate the developer ergonomics that went into Rust. Its APIs are pleasantly well thought out.
Nice. I truly do appreciate the developer ergonomics that went into Rust. Its APIs are pleasantly well thought out.
This article feels too long and rambly considering how little actual technical information it provides.
This comment feels at odds with HN guidelines, if you're going to criticise at least offer some advice on how to improve.
I don't think the point of the article is the technical information, I think it's more of an emotional expression. Still valuable, just differently, I suppose.
Like much of what surrounds Rust. Looks quite emotional to me. If you do not know what I mean, go to the Rust reddit and discuss and compare on solid grounds without using an extremely flattering tone.
You will see armies of fanatics voting negative.
You will see armies of fanatics voting negative.
If you actually look at the Rust subreddit: https://www.reddit.com/r/rust/top/?sort=top&t=all
The fifth and eighth articles are explicitly negative about Rust. The seventh is about serious bugs in the Rust ecosystem.
Let's look at the top comment on the highest post: https://www.reddit.com/r/rust/comments/1cdqdsi/lessons_learn...
It's Josh Triplett, long time team member. It starts like this:
> First of all, thank you very much for taking the time to write this post. People who leave Rust usually don't write about the issues they have, and that's a huge problem for us, because it means we mostly hear from the people who had problems that weren't serious enough to drive them away. Thank you, seriously, for caring enough to explain the issues you had in detail.
This is a very different vibe than the one you're describing.
It's true that the Rust subreddit can brush criticism off, but that's also because there are a lot of low-quality criticisms of Rust, and seeing the same thing over and over again can be frustrating. But I've never seen a well thought out post that's critical get downvoted, they're often upvoted, and discussed in a very normal way.
That said, it's reddit, so there's always gonna be some garbage posts.
The fifth and eighth articles are explicitly negative about Rust. The seventh is about serious bugs in the Rust ecosystem.
Let's look at the top comment on the highest post: https://www.reddit.com/r/rust/comments/1cdqdsi/lessons_learn...
It's Josh Triplett, long time team member. It starts like this:
> First of all, thank you very much for taking the time to write this post. People who leave Rust usually don't write about the issues they have, and that's a huge problem for us, because it means we mostly hear from the people who had problems that weren't serious enough to drive them away. Thank you, seriously, for caring enough to explain the issues you had in detail.
This is a very different vibe than the one you're describing.
It's true that the Rust subreddit can brush criticism off, but that's also because there are a lot of low-quality criticisms of Rust, and seeing the same thing over and over again can be frustrating. But I've never seen a well thought out post that's critical get downvoted, they're often upvoted, and discussed in a very normal way.
That said, it's reddit, so there's always gonna be some garbage posts.
To be fair, that is just the typical Reddit (or any social media platform) experience
I won't deny that there are lots of emotions surrounding Rust, both for myself and for many others. But there are different ways to write about it, and this article looks more of an emotional style ("here's how my journey went") than a technical one ("here's how this works"). I still find it fun to read, but not everyone will, and that's okay.
It's what you call an "educational post".
The Rust community is doing a fantastic job of training both the next generation as well as those looking to dip their toes in.
The Rust community is doing a fantastic job of training both the next generation as well as those looking to dip their toes in.
Oh, I never knew that Rust had variance. I always just assumed everything was invariant. Strange that they've got no way to write it down in the type system.
In prehistoric Rust, variance used to be named more explicitly. However, the terminology of covariant and contravariant subtyping of lifetimes is a language theory jargon. This is the right perspective for language design, but programmers using the language don't necessarily use these terms.
It's been replaced with a "by example" approach. It's much easier to teach it: just add a fake field that acts if you had this type in your struct. Rust then figures out all of the details it needs.
It's been replaced with a "by example" approach. It's much easier to teach it: just add a fake field that acts if you had this type in your struct. Rust then figures out all of the details it needs.
Years ago, I introduced Flow gradual typing (JS) to a team. It has explicit annotations for type variance which came up when building bindings to JS libraries, especially in the early days.
I had a loose grasp on variance then, didn't teach it well, and the team didn't understand it either. Among other things, it made even very early and unsound TypeScript pretty attractive just because we didn't have to annotate type variance!
I'm happy with Rust's solution here! Lifetimes and Fn types (especially together) seem to be the main place where variance comes up as a concept that you have to explicitly think about.
I had a loose grasp on variance then, didn't teach it well, and the team didn't understand it either. Among other things, it made even very early and unsound TypeScript pretty attractive just because we didn't have to annotate type variance!
I'm happy with Rust's solution here! Lifetimes and Fn types (especially together) seem to be the main place where variance comes up as a concept that you have to explicitly think about.
Note that this works because Rust doesn't have inheritance, so variance only comes up with respect to lifetimes, which don't directly affect behavior/codegen. In an object-oriented language with inheritance, the only type-safe way to do generics is with variance annotations.
Variance is an absolute disaster when it comes to language pedagogy. One of the smartest things Rust ever did was avoiding mentioning it in the surface-level syntax.
Why? It's just a property of type transformation.
Assuming Parent <- Child ("<-" denotes inheritance):
- If Generic<Parent> <- Generic<Child>: it's covariant.
- If Generic<Parent> -> Generic<Child>: it's contravariant.
- Otherwise: it's invariant.
Or at least it's that straightforward in C#. Are there complications in Rust?
Assuming Parent <- Child ("<-" denotes inheritance):
- If Generic<Parent> <- Generic<Child>: it's covariant.
- If Generic<Parent> -> Generic<Child>: it's contravariant.
- Otherwise: it's invariant.
Or at least it's that straightforward in C#. Are there complications in Rust?
The difficulty is that even trivial generic types aren't cleanly one or the other. A mutable reference type is covariant on read, and contra on write.
Scala was the first language in my exposure to try to simplify that away by lifting the variance annotations into the type parameter directly. It reduced some of the power but it made things easier to understand for developers. A full variance model would annotate specific features (methods) of a type as co/contra/invariant.
I'm not sure what approach C# takes - I haven't looked into it.
Rust doesn't expose variances for data structures at all. It exposes them for traits (type classes) and lifetimes, but neither of those are accessible in a higher order form. Trait usage is highly constrained and so is lifetime usage.
Traits mainly can be used as bounds on types. Some subset of traits, characterized as object traits, can be used as types themselves, but only in an indirect context. These are highly restricted. For example, if you have traits T and U where U extends T, and you have a reference `&dyn U`, you can't convert that to a `&dyn T` without knowledge of the underlying concrete type. You _can_ convert `&A where A: U` to `&B where B: T`, but that just falls out of the fact that the compiler has access to all the concrete type and trait definitions there and can validate the transform.
Rust's inheritance/variance story is a bit weird. They've kept it very minimal and constrained.
Scala was the first language in my exposure to try to simplify that away by lifting the variance annotations into the type parameter directly. It reduced some of the power but it made things easier to understand for developers. A full variance model would annotate specific features (methods) of a type as co/contra/invariant.
I'm not sure what approach C# takes - I haven't looked into it.
Rust doesn't expose variances for data structures at all. It exposes them for traits (type classes) and lifetimes, but neither of those are accessible in a higher order form. Trait usage is highly constrained and so is lifetime usage.
Traits mainly can be used as bounds on types. Some subset of traits, characterized as object traits, can be used as types themselves, but only in an indirect context. These are highly restricted. For example, if you have traits T and U where U extends T, and you have a reference `&dyn U`, you can't convert that to a `&dyn T` without knowledge of the underlying concrete type. You _can_ convert `&A where A: U` to `&B where B: T`, but that just falls out of the fact that the compiler has access to all the concrete type and trait definitions there and can validate the transform.
Rust's inheritance/variance story is a bit weird. They've kept it very minimal and constrained.
> A mutable reference type is covariant on read, and contra on write.
No it isn't. The type is covariant because a reference is a subtype of all parent types. The the function read must have it's argument invariant because it both takes and returns an instance of the type. I think you're confusing the variance of types for the variance of instances of those types. Read is effectively a Function(t: type, Function(ref t, t)). If it was covariant as you suggest, we would have a serious problem. Consider that (read Child) works by making a memory read for the first (sizeof Child) bytes of it's argument. If read were covariant, then that would imply you could call (read Child) on a Parent type and get a Parent back, but that won't work because (sizeof Child) can be less than (sizeof Parent). Read simply appears covariant because it's generic. (read Child) ≠ (read Parent), but you can get (read Parent). It also appears contravariant because you can get (read Grandchild).
Scala doesn't simplify anything, that's just how variance works.
No it isn't. The type is covariant because a reference is a subtype of all parent types. The the function read must have it's argument invariant because it both takes and returns an instance of the type. I think you're confusing the variance of types for the variance of instances of those types. Read is effectively a Function(t: type, Function(ref t, t)). If it was covariant as you suggest, we would have a serious problem. Consider that (read Child) works by making a memory read for the first (sizeof Child) bytes of it's argument. If read were covariant, then that would imply you could call (read Child) on a Parent type and get a Parent back, but that won't work because (sizeof Child) can be less than (sizeof Parent). Read simply appears covariant because it's generic. (read Child) ≠ (read Parent), but you can get (read Parent). It also appears contravariant because you can get (read Grandchild).
Scala doesn't simplify anything, that's just how variance works.
Even in your own description, it is clear that with regards to _correctness_, the variance model bifurcates between the read and the write method.
The discussion about the type sizes is a red herring. If the type system in question makes two types of differing sizes not able to be subtypes of each other, then calling these things "Child" and "Parent" is just a labeling confusion on types unrelated by a subtyping relationship. The discussion doesn't apply at all to that case.
The variance is a property of the algorithm with respect to the type. A piece of code that accepts a reference to some type A and only ever reads from it can correctly accept a reference to a subtype of A.
A piece of code that accepts a reference to a type A and only ever writes to it can correctly accept a reference to a supertype of A.
In an OO language, an instance method is covariant whenever the subject type occurs in return position (read analogue), and it's contravariant whenever the subject type occurs in a parameter position (write analogue). On instance methods where both are present, you naturally reduce to the intersection of those two sets, which causes them to be annotated as invariant.
The discussion about the type sizes is a red herring. If the type system in question makes two types of differing sizes not able to be subtypes of each other, then calling these things "Child" and "Parent" is just a labeling confusion on types unrelated by a subtyping relationship. The discussion doesn't apply at all to that case.
The variance is a property of the algorithm with respect to the type. A piece of code that accepts a reference to some type A and only ever reads from it can correctly accept a reference to a subtype of A.
A piece of code that accepts a reference to a type A and only ever writes to it can correctly accept a reference to a supertype of A.
In an OO language, an instance method is covariant whenever the subject type occurs in return position (read analogue), and it's contravariant whenever the subject type occurs in a parameter position (write analogue). On instance methods where both are present, you naturally reduce to the intersection of those two sets, which causes them to be annotated as invariant.
> A piece of code that accepts a reference to some type A and only ever reads from it can correctly accept a reference to a subtype of A.
The same is true of a piece of code that writes through the reference or returns it. That's how sub-typing works.
> A piece of code that accepts a reference to a type A and only ever writes to it can correctly accept a reference to a supertype of A.
Have you ever programmed in a language with subtyping? Let me show you an example from Java (a popular object oriented programming language).
I've seen a lot of people in this comment section talking about read and write which I find really odd. They have nothing to do with variance. The contravariant property is a property of function values and their parameters. It is entirely unrelated to the body of the function. A language without higher order functions will actually never have a contravariant type within it. This is why many popular OOP languages do not have them.
The same is true of a piece of code that writes through the reference or returns it. That's how sub-typing works.
> A piece of code that accepts a reference to a type A and only ever writes to it can correctly accept a reference to a supertype of A.
Have you ever programmed in a language with subtyping? Let me show you an example from Java (a popular object oriented programming language).
class Parent {}
class Child {
int x;
}
class Example {
static void writeToChild(Child c) {
c.x = 20;
}
static void main() {
writeToChild(new Parent());
}
}
I've seen a lot of people in this comment section talking about read and write which I find really odd. They have nothing to do with variance. The contravariant property is a property of function values and their parameters. It is entirely unrelated to the body of the function. A language without higher order functions will actually never have a contravariant type within it. This is why many popular OOP languages do not have them.
> The same is true of a piece of code that writes through the reference or returns it. That's how sub-typing works.
But it is not true that it is correctly typed with respect to a a supertype of A (it is not valid to call the code with a reference to a supertype of A).
Code that only writes through the reference is correctly typed with respect to a super-type of A (it is valid to call the code with a reference to a supertype of A).
> Have you ever programmed in a language with subtyping?
Sigh, keep that snark for the twitter battles. I don't care enough about this to get snippy about it or to deal with folks who do.
But it is not true that it is correctly typed with respect to a a supertype of A (it is not valid to call the code with a reference to a supertype of A).
Code that only writes through the reference is correctly typed with respect to a super-type of A (it is valid to call the code with a reference to a supertype of A).
> Have you ever programmed in a language with subtyping?
Sigh, keep that snark for the twitter battles. I don't care enough about this to get snippy about it or to deal with folks who do.
> Code that only writes through the reference is correctly typed with respect to a super-type of A (it is valid to call the code with a reference to a supertype of A).
I'm not trying to be snarky, I genuinely want to know what you think of that code snippet I showed you. You claim it should work, but anyone with an understanding of programming would tell you it shouldn't. You can't write to a member variable that doesn't exist. Have you encountered inheritance before? Do you know what a “super-type” is? The mistake you're making here is very basic and I should like to know your level of experience.
I'm not trying to be snarky, I genuinely want to know what you think of that code snippet I showed you. You claim it should work, but anyone with an understanding of programming would tell you it shouldn't. You can't write to a member variable that doesn't exist. Have you encountered inheritance before? Do you know what a “super-type” is? The mistake you're making here is very basic and I should like to know your level of experience.
Note that the Rust folks are working on a "safe-transmute" facility that may end up introducing a kind of variance to the language.
It's not particularly easy to teach what that actually means and why it's a thing. It's quite easy to show why in general G<A> cannot be a subtype of G<B> even if A is a subtype of B, it's rather more involved pedagogically to explain when it can, and even more confusing when it's actually the other way around (contravariance).
Anyway, Rust has no subtyping except for lifetimes ('a <: 'b iff 'a lasts at least as long as 'b) , so variance only arises in very advanced use cases.
Anyway, Rust has no subtyping except for lifetimes ('a <: 'b iff 'a lasts at least as long as 'b) , so variance only arises in very advanced use cases.
I’m getting old. I can understand the words, but not the content. At this point, show me dissassembly so that I can understand what actually happens on the fundamental byte/cpu instruction level, then I can figure out what you’re trying to explain.
Nothing really happens on the instruction level because this is all type system logic.
I think this might be the issue.
If something has zero effect in the end, why should I care about in the first place?
Variance doesn't affect generated code because it acts earlier than that: determining whether code is valid or not and in doing so preventing invalid code (UB) from being compiled in the first place.
The simplest example of incorrect variance → UB is that `&'a mut T` must be invariant in T. If it were covariant, you could take a `&'a mut &'static T`, write a `&'b T` into it for some non-static lifetime `'b` (since `'static: 'b` for all `'b`), and then... kaboom. 'b ends but the compiler thought this was a `&'a mut &'static T`, and you've got a dangling reference.
`&'a mut T` can't be covariant in T for a similar reason: if you start with a `&'a mut &'b T`, contravariance would let you cast it to a `&'a mut &'static T`, and then you'd have a `&'static T` derived from a `&'b T`, which is again kaboom territory.
So, variance’s effect is to guide the compiler and prevent dangling references from occurring at runtime by making code that produces them invalid. Neither of the above issues is observable at runtime (barring compiler bugs) precisely because the compiler enforces variance correctly.
The simplest example of incorrect variance → UB is that `&'a mut T` must be invariant in T. If it were covariant, you could take a `&'a mut &'static T`, write a `&'b T` into it for some non-static lifetime `'b` (since `'static: 'b` for all `'b`), and then... kaboom. 'b ends but the compiler thought this was a `&'a mut &'static T`, and you've got a dangling reference.
`&'a mut T` can't be covariant in T for a similar reason: if you start with a `&'a mut &'b T`, contravariance would let you cast it to a `&'a mut &'static T`, and then you'd have a `&'static T` derived from a `&'b T`, which is again kaboom territory.
So, variance’s effect is to guide the compiler and prevent dangling references from occurring at runtime by making code that produces them invalid. Neither of the above issues is observable at runtime (barring compiler bugs) precisely because the compiler enforces variance correctly.
It doesn't have zero effect. Like everything about type systems, it helps prevent incorrect, and possibly unsound, code from compiling. So I guess the giant runtime effect is that you either have a program to run or not.
Sure, you can keep telling me that and it doesn't stay. I'm completely happy writing Rust, and I am aware it needs variance to work in principle and when I do need that information I know the magic words to type into doc search.
It's like how I can hold in my head how classical DH KEX works and I can write a toy version with numbers that are too small - but for the actual KEX we use today, which is Elliptic Curve DH I'm like "Well, basically it's the same idea but the curves hurt my head so I just paste in somebody else's implementation" even in a toy.
Sorry?
It's like how I can hold in my head how classical DH KEX works and I can write a toy version with numbers that are too small - but for the actual KEX we use today, which is Elliptic Curve DH I'm like "Well, basically it's the same idea but the curves hurt my head so I just paste in somebody else's implementation" even in a toy.
Sorry?
One day the rote example finally made sense to me, and I go back to it every time I hear about variance.
Got a Container<Animal> and want to treat it as a Container<Cat>? Then you can only write to it: it's ok to put a Cat in a Container<Cat> that's really a Container<Animal>.
Reading from it is wrong. If you treat a Container<Animal> like a Container<Cat> and read from it, you might get a Dog instead.
The same works in reverse, treating a Container<Cat> like a Container<Animal> is ok for read, but not for write.
Got a Container<Animal> and want to treat it as a Container<Cat>? Then you can only write to it: it's ok to put a Cat in a Container<Cat> that's really a Container<Animal>.
Reading from it is wrong. If you treat a Container<Animal> like a Container<Cat> and read from it, you might get a Dog instead.
The same works in reverse, treating a Container<Cat> like a Container<Animal> is ok for read, but not for write.
The usual way of phrasing this is, famously, https://en.wikipedia.org/wiki/A_white_horse_is_not_a_horse
It wad easy to teach to Java devs just by using one mnemonic: PECS = Producer Extends, Consumer Super
Luckily variance only affects lifetimes, and these are already barely understood even without lifetimes. If you ignore them, the need for variance disappears.
> but programmers using the language don't necessarily use these terms.
this always annoyed me about the python type annotations, you are supposed to already know what contravariant / covariant / invariant means, like: `typing.TypeVar(name, covariant=False, contravariant=False, infer_variance=False)`
Its used in documentation and error messages too:
> the SendType of Generator behaves contravariantly, not covariantly or invariantly.
https://docs.python.org/3/library/typing.html#annotating-gen...
this always annoyed me about the python type annotations, you are supposed to already know what contravariant / covariant / invariant means, like: `typing.TypeVar(name, covariant=False, contravariant=False, infer_variance=False)`
Its used in documentation and error messages too:
> the SendType of Generator behaves contravariantly, not covariantly or invariantly.
https://docs.python.org/3/library/typing.html#annotating-gen...
1 point by James_K 0 minutes ago | root | parent | next | edit | delete [–]
That's horrible design. I was utterly perplexed whenever the compiler asked me to add one of those strange fields to a struct. If it had just asked me to include the variance in generic parameters, I would have had no such confusion. Asking programmers to learn the meaning of an important concept in programming is entirely reasonable, especially in Rust which is a language for advanced programmers that expects knowledge of many other more complicated things.
What's more, the implicit variance approach might create dangerous code. It is possible to break the interface for a module without making any change to its type signature. The entire point of types is to provide a basic contract for the behaviour of an object. A type system with variance in it that doesn't let you write it down in the signature is deficient in this property.
That's horrible design. I was utterly perplexed whenever the compiler asked me to add one of those strange fields to a struct. If it had just asked me to include the variance in generic parameters, I would have had no such confusion. Asking programmers to learn the meaning of an important concept in programming is entirely reasonable, especially in Rust which is a language for advanced programmers that expects knowledge of many other more complicated things.
What's more, the implicit variance approach might create dangerous code. It is possible to break the interface for a module without making any change to its type signature. The entire point of types is to provide a basic contract for the behaviour of an object. A type system with variance in it that doesn't let you write it down in the signature is deficient in this property.
[deleted]
https://doc.rust-lang.org/reference/subtyping.html#variance
Lifetimes imply the need for the idea of variance.
Lifetimes imply the need for the idea of variance.
Rather, any language with both generics and subtyping needs to consider variance, and Rust doesn't have subtyping in general, but lifetimes do technically have subtyping relationships, so lifetimes are the only place where this matters, and fortunately Rust can just infer the right behavior based on some simple type-level heuristics.
Unfortunately, more like. I'd much rather have some explicit syntax for it that potentially never realise it's a feature. I was baffled beyond belief the first time the compiler asked me to put a ghost in my struct.
Aside from better documentation (it would be quite nice if rustdoc automatically showed the computed variance for types where it mattered), what would writing it down in the type system get you?
Separately, if everything were invariant, you wouldn't be able to use a `&'static T` where a `&'non_static T` was expected, which would be quite unpleasant!
Separately, if everything were invariant, you wouldn't be able to use a `&'static T` where a `&'non_static T` was expected, which would be quite unpleasant!
I'm sure all these layers are good engineering and provide meaningful safety guarantees, but it sure makes the code harder to understand if you want to see how things are implemented.
Another example, I was trying to see how i64::isqrt is implemented, but first you have to wade through layers of macros
Another example, I was trying to see how i64::isqrt is implemented, but first you have to wade through layers of macros
"The standard library internally overuses macros and you probably shouldn't use them that much in your own code" is at least a respectable opinion in the Rust community, I think.
Yep. Heck, I've barely even written any macros at all.
This is just how rust and c++ code is in my experience.
Even C is like that in its most popular stdlib implementation (glibc).
C++ is bc of compatibility with god knows how many standards, but at the end it is simpler than it looks at first sight. The uglification of names in the std lib make it disgusting to read. If only that was removed it would improve a lot.
It is not clear, does compiler explicitly knows about properties of `NonNull` (for example, that it has neutral value to collapse `Option<NonNull<T>>`), so it is part of compiler, or it is expressed in type system, so it is part of standard library?
Same question about other «signal» types.
Same question about other «signal» types.
> part of compiler, or it is expressed in type system, so it is part of standard library
compiler + standard library (core library to be more specific)
`NonNull` is mostly "just" a library type in the core libary, but it uses two unstable/nightly attributes to tell the compiler about it's special properties (see other answers, also to be clear its not a `lang_item` attribute but something other types can use, too).
The special thing about core/std in rust is that due to it being part of the specific compiler version it can use (some, careful considered) subset of unstable features as long as they work for that specific use case and don't "leak"/accidentally stabilize through it.
But this attributes are in progress of getting replaces with a new mechanism of pattern annotations. I.e. NonNull will be annotated with attribute which contains a `1..` pattern (i.e. value is 1 or larger) but other patterns are getting support, too. (The second attribute to enforce/guarantee niche optimizations might still be needed for stability guarantees.)
And I think??? there are plans to stabilize this new mechanism, but I'm absolutely not sure what the state of this is (RFC accepted?, stabilization open/likely/decided? implementation done/partial?). I'm currently not in the loop.
So in the long future you probably can write your own types with other niches e.g. a u8 with `..127` (MSB unused).
compiler + standard library (core library to be more specific)
`NonNull` is mostly "just" a library type in the core libary, but it uses two unstable/nightly attributes to tell the compiler about it's special properties (see other answers, also to be clear its not a `lang_item` attribute but something other types can use, too).
The special thing about core/std in rust is that due to it being part of the specific compiler version it can use (some, careful considered) subset of unstable features as long as they work for that specific use case and don't "leak"/accidentally stabilize through it.
But this attributes are in progress of getting replaces with a new mechanism of pattern annotations. I.e. NonNull will be annotated with attribute which contains a `1..` pattern (i.e. value is 1 or larger) but other patterns are getting support, too. (The second attribute to enforce/guarantee niche optimizations might still be needed for stability guarantees.)
And I think??? there are plans to stabilize this new mechanism, but I'm absolutely not sure what the state of this is (RFC accepted?, stabilization open/likely/decided? implementation done/partial?). I'm currently not in the loop.
So in the long future you probably can write your own types with other niches e.g. a u8 with `..127` (MSB unused).
For anyone wondering, NonNull (along with other "constrained" types like NonZero integers) uses internal compiler attributes (https://doc.rust-lang.org/src/core/ptr/non_null.rs.html#72):
You can technically use those for your own types, but it requires nightly, obviously.
#[rustc_layout_scalar_valid_range_start(1)]
You can technically use those for your own types, but it requires nightly, obviously.
However, Rust does automatically provide a niche if you make a simple enumeration which doesn't occupy all bit patterns and we don't need compiler-only features, or even unstable Rust, this Just Works™.
If you have a USHoliday enum, with values like Juneteenth the fact is there's not that many US national holidays, so both USHoliday and Option<USHoliday> will be the same size, one byte with no extra work.
If you have a USHoliday enum, with values like Juneteenth the fact is there's not that many US national holidays, so both USHoliday and Option<USHoliday> will be the same size, one byte with no extra work.
It's a mix of both. https://doc.rust-lang.org/src/core/ptr/non_null.rs.html#72-7...
#[rustc_layout_scalar_valid_range_start(1)]
#[rustc_nonnull_optimization_guaranteed]
Can anyone compare it to C++ in terms of memory layout for typical implementations?
It should be more-or-less the same on typical implementations. You might have 3 pointers instead of 1 pointer and 2 lengths, or some mix thereof, but they are all equivalent in memory layout.
The vector implementation on my machine uses three pointers: start, end, and end-of-storage. It's basically the same, but uses addresses rather than counts. The valarray implementation uses a pointer and a single count.
That's one of major problems I have with Rust docs and community. The best way to explain most things in Rust to experienced dev, is by comparison to C++. But all the docs and blog posts explicitly target newbies and avoid comparison with C++ at all cost.
I disagree, Rust and C++ are very different languages with significant impedance mismatches once you go beyond the common C-like subset. Referencing C++ as a matter of course in docs and blog posts would just cause confusion. If you want a modern language that really is a lot closer to C++ you may want to check out Carbon.
Rust was created as a C++ replacement, borrows the 'zero cost abstractions' motto from C++, relies on RAII for resource management like C++ (not many languages do it), has the same approach to concurrency (in-place mutation guarded by locks), uses the codegen backend that was created for C++. It's mostly a C++ subset with more guardrails.
Edit: RAII
Edit: RAII
It's nowhere near a C++ subset. The way it works under the hood is quite different, and even trying to add some of the underlying mechanisms to C++ (such as what they call "trivially relocatable types", or "destructing moves") has been quite difficult.
Actually, we already discussed Rust move semantics on this website some time ago: https://news.ycombinator.com/item?id=43059293
And again, the best way to explain this is by comparison to C++
And again, the best way to explain this is by comparison to C++
https://archive.is/Cqr4E (if their site blocks your browser)
I gave up half way through. The constant description of deep emotional feelings when it comes to something as sober as data types in the rust standard library make this rather hard to read. It is difficult to untangle the point the author is trying to make from the constant bombardment with deep emotional writing.
If a little lighthearted banter counts as "deeply emotional", I guess I understand why your username is "constant crying"
Even if you do not expect a professional tone it is totally bizarre to write a technical article (which I would have liked to understand, since the question is interesting to me) as if you are talking to a toddler. The allusions to Grand conspiracy theories and grave emotional turns which are everywhere make the article sound as if it was written for children.
I do not like lighthearted banter, but this is not the problem. The problem is that the author has a hard time writing a single paragraph without it. They should seriously consider doing some training in technical or scientific writing.
>, I guess I understand why your username is "constant crying"
What a novel comment. But yes, I do hate the constant positivity, especially in the face of a subpar product.
I do not like lighthearted banter, but this is not the problem. The problem is that the author has a hard time writing a single paragraph without it. They should seriously consider doing some training in technical or scientific writing.
>, I guess I understand why your username is "constant crying"
What a novel comment. But yes, I do hate the constant positivity, especially in the face of a subpar product.
Some people like to have fun. Is it so hard to look away from the things you don't personally like?
As to the underlying topic, this is a very introductory article - I warrant 20 minutes with the source code, and you'd reach the same level of understanding.
As to the underlying topic, this is a very introductory article - I warrant 20 minutes with the source code, and you'd reach the same level of understanding.
While safe Rust may be relatively simple to write, and certainly easier to write than safe C, this article has someone added to my belief that unsafe Rust is far too difficult to write. Perhaps some of this is deliberate, as a kind of defence mechanism against people using it willy-nilly, it still seems over-designed.
It's a pretty normal experience for lookin at standard libraries (I mean look at cpython, where you now need to know C++, cpython interpreter internal,C++ std in addition to all the complicated meta class magic you normally don't need to care about.)
Like in Vec we have following things most normal rust code wouldn't do:
- Unique<u8> instead of Unique<T>, to micro optimize code size
- RawVec, RawVecInner, due to the previous point, internal structure of libstd, relations to libcore/liballoc usage and more clean separation between unsafe and safe code etc. Which a "just my own vec" impl might not have
- internal `Unique` helper type to reuse code between various data structures in std
- the `NonNull` part is another micro optimization which might save 1-4 byte for `Option<Vec<T>>` (up to 4 due to alignment, but I think this optimization isn't guaranteed in this context)
Like it could be just a `Vec<T> { ptr: *const T, cap: usize, len: usize, _marker: PhantomData<T> }`, but that wouldn't have quite the maximized (and micro optimized) fine tuning which tends to be in std libraries but not in random other code. (I mean e.g. the code size micro-opt. is irrelevant for most rust code, but std goes into _all_ (std using) rust code, so it's needed.
But anyway, yes, unsafe rust can be hard. Especially if you go beyond "straight forward C bindings" and write clever micro optimized data structures. It's also normally not needed.
But also "straight forward C bindings" can be very okay from complexity _as long as you don't try to be clever_ (which in part isn't even rust specific, it tends to just become visible in rust).
Like in Vec we have following things most normal rust code wouldn't do:
- Unique<u8> instead of Unique<T>, to micro optimize code size
- RawVec, RawVecInner, due to the previous point, internal structure of libstd, relations to libcore/liballoc usage and more clean separation between unsafe and safe code etc. Which a "just my own vec" impl might not have
- internal `Unique` helper type to reuse code between various data structures in std
- the `NonNull` part is another micro optimization which might save 1-4 byte for `Option<Vec<T>>` (up to 4 due to alignment, but I think this optimization isn't guaranteed in this context)
Like it could be just a `Vec<T> { ptr: *const T, cap: usize, len: usize, _marker: PhantomData<T> }`, but that wouldn't have quite the maximized (and micro optimized) fine tuning which tends to be in std libraries but not in random other code. (I mean e.g. the code size micro-opt. is irrelevant for most rust code, but std goes into _all_ (std using) rust code, so it's needed.
But anyway, yes, unsafe rust can be hard. Especially if you go beyond "straight forward C bindings" and write clever micro optimized data structures. It's also normally not needed.
But also "straight forward C bindings" can be very okay from complexity _as long as you don't try to be clever_ (which in part isn't even rust specific, it tends to just become visible in rust).
I think most of the complexity here comes from trying to write as little unsafe code as possible (and not repeating any unsafe operation in multiple places, hence the many layered abstractions).
If you were to implement Vec without layering, it would be no more complicated than writing a dynamic array in C (but more verbose due to all the unsafe blocks and unabbreviated names)
If you were to implement Vec without layering, it would be no more complicated than writing a dynamic array in C (but more verbose due to all the unsafe blocks and unabbreviated names)
Notably, some of the abstraction is actually there to prevent the compiler from generating a lot of redundant code. The process of monomorphization (turning polymorphic generic code into usable machine code for particular types) can seriously bloat the size of binaries.
When I was young I peeked into the C++ stdlib, which is probably the best thing to compare this to. It was orders of magnitude worse.
Would you consider this to be indicative of the quality of the C++ language? I think the standard library should usually be an example of optimal code with respect to performance, and when it is very complicated this would indicate, to me, that the language makes good code complicated.
If you look at an advanced C library, you'll see perhaps some odd tricks or nifty algorithms, but you probably won't see something that leaves you scratching your head about what the code is even asking the computer to do.
If you look at an advanced C library, you'll see perhaps some odd tricks or nifty algorithms, but you probably won't see something that leaves you scratching your head about what the code is even asking the computer to do.
stdlib code was always impenetrable to me, this was one of the reasons I moved away from C++.
Even the earlier versions of this code that used unsafe were much simpler. The implementation has grown in complexity over time to address real needs.
Here's what it looked like at 1.0.0: https://github.com/rust-lang/rust/blob/1.0.0/src/libcollecti...
Here's what it looked like at 1.0.0: https://github.com/rust-lang/rust/blob/1.0.0/src/libcollecti...
Unsafe Rust does have tooling to help you not make some kinds of mistakes, but by its nature you have to be able to press on after the tools can't help you.
For example MIRI can understand pointer twiddling under strict provenance. It'll synthesize provenance for the not-really-pointers it is working with and check what you wrote works when executed. But if your algorithm can't work with strict provenance (and thus wouldn't work for CHERI hardware for example) but your target is maybe an x86-64 Windows PC so you don't care, you can write exposed or even just arbitrary "You Gotta Believe Me" pointer twiddling, MIRI just can't check it any more when you do that, so, hope you never make mistakes.
For example MIRI can understand pointer twiddling under strict provenance. It'll synthesize provenance for the not-really-pointers it is working with and check what you wrote works when executed. But if your algorithm can't work with strict provenance (and thus wouldn't work for CHERI hardware for example) but your target is maybe an x86-64 Windows PC so you don't care, you can write exposed or even just arbitrary "You Gotta Believe Me" pointer twiddling, MIRI just can't check it any more when you do that, so, hope you never make mistakes.
Yes, it is indeed very difficult to write unsafe rust, also very difficult to write anything low level and reusable
I love how it shows that you can have both performance and safety without jumping through hoops. The little details of memory management really shape how we end up writing code, often without even noticing. Rust makes it possible to get close to the hardware while still keeping you out of the usual trouble spots. It’s one of those things you appreciate more the longer you use it
Erm what? The article contradicts this. I'd push back on "without jumping through hoops". The article itself demonstrates 6 layers of abstraction (Vec<T> -> RawVec<T> -> RawVecInner -> Unique<u8> -> NonNull<u8> -> *const u8) built on unsafe primitives. The standard library does the hoop-jumping for you, which is valuable, but the hoops exist, they're just relocated.
I bet Vec's implementation is full of unsafe blocks and careful invariant management. Users face different hoops: lifetime wrangling, fighting the borrow checker on valid patterns, Pin semantics, etc. Rust trades runtime overhead for upfront costs: compile-time complexity and developer time wrestling with the borrow checker which is often the right trade, but it's not hoop-free.
The "close to hardware" claim needs qualification too. You're close to hardware through abstractions that hide significant complexity. Ada/SPARK gives formal correctness guarantees but requires proof effort and runtime checks (unless you use SPARK which is a subset of Ada). C gives you actual hardware access but manual memory management. Each has trade-offs - Rust's aren't magically absent.
I bet Vec's implementation is full of unsafe blocks and careful invariant management. Users face different hoops: lifetime wrangling, fighting the borrow checker on valid patterns, Pin semantics, etc. Rust trades runtime overhead for upfront costs: compile-time complexity and developer time wrestling with the borrow checker which is often the right trade, but it's not hoop-free.
The "close to hardware" claim needs qualification too. You're close to hardware through abstractions that hide significant complexity. Ada/SPARK gives formal correctness guarantees but requires proof effort and runtime checks (unless you use SPARK which is a subset of Ada). C gives you actual hardware access but manual memory management. Each has trade-offs - Rust's aren't magically absent.
It's fine https://github.com/model-checking/verify-rust-std/issues/283 https://github.com/model-checking/verify-rust-std/pull/481 (But until two weeks ago, it wasn't - you could in theory cause UB by writing purely safe code within the Vec<T> implementation.)
I had no idea, that is wild, especially considering how everyone has been outcrying "Rust is safe". Thanks for the info though.
One should wonder what else is there... but they do not wonder, they are sadly rigid with their thinking that Rust is the perfect memory safe language with zero runtime overhead.
One should wonder what else is there... but they do not wonder, they are sadly rigid with their thinking that Rust is the perfect memory safe language with zero runtime overhead.
It's not real unsoundness because it only applies within the private implementation details of Vec<T> - you still can't cause UB from outside code. But it's a real oversight that only proves how hard writing unsafe code is.
You know you can discuss languages without the weird emotional labeling from your last paragraph, right?
Plenty of people wonder. It’s part of building the language.
Plenty of people wonder. It’s part of building the language.
Fair enough.
Most of those are abstractions, but not a runtime overhead. NonNull even enables an optimization not available to most other languages.
And you can wonder, is this accidental complexity? Or is this necessary complexity?
And you can wonder, is this accidental complexity? Or is this necessary complexity?
I come from a Swift/Kotlin background and I've been learning Rust for fun in my spare time
From what I heard online I was expecting it to be a lot harder to understand!
The moving/borrowing/stack/heap stuff isn't simple by any means, and I'm sure as I go it will get even harder, but it's just not as daunting as I'd expected
It helps that I love compiler errors and Rust is full of them :D Every error the compiler catches is an error my QA/users don't
From what I heard online I was expecting it to be a lot harder to understand!
The moving/borrowing/stack/heap stuff isn't simple by any means, and I'm sure as I go it will get even harder, but it's just not as daunting as I'd expected
It helps that I love compiler errors and Rust is full of them :D Every error the compiler catches is an error my QA/users don't
The language and associated tooling keep improving.
Over the course of the last decade I've made several attempts to learn Rust, but was always frustrated with having code that reasonably should compile, but didn't and I had to run the build to even find that out.
Now we have rust-analyzer and non-lexical lifetimes, both tremendously improving the overall experience.
I still don't enjoy the fact that borrows are at the struct level, so you can't just borrow one field (there's even a discussion on that somewhere in Rust's) repo, but I can work around that.
To drive the point home: I'm a frontend developer. This is a very different environment compared to what I'm used to, yet I can be productive in it, even if at a slower pace in comparison.
Over the course of the last decade I've made several attempts to learn Rust, but was always frustrated with having code that reasonably should compile, but didn't and I had to run the build to even find that out.
Now we have rust-analyzer and non-lexical lifetimes, both tremendously improving the overall experience.
I still don't enjoy the fact that borrows are at the struct level, so you can't just borrow one field (there's even a discussion on that somewhere in Rust's) repo, but I can work around that.
To drive the point home: I'm a frontend developer. This is a very different environment compared to what I'm used to, yet I can be productive in it, even if at a slower pace in comparison.
Rust is not the most productive language by any means... it is hardened AF if you avoid unsafe, but productive?
I can code much faster in almost any language compared to Rust. It creates mental overhead. For example, to compare it to siblings, Swift and C++ (yes, even C++, but with a bit of knowledge of good practices) lets you produce stuff more easily than Rust.
It is just that Rust, compared to C++, comes extra-hardened. But now go get refactor your Rust code if you started to add lifetimes around... things get coupled quickly. It is particularly good at hardening and particularly bad at prototyping.
They seem to be the opposite in the absence of borrowing without a garbage collector, since you need to mark the lifetime in some way.
I can code much faster in almost any language compared to Rust. It creates mental overhead. For example, to compare it to siblings, Swift and C++ (yes, even C++, but with a bit of knowledge of good practices) lets you produce stuff more easily than Rust.
It is just that Rust, compared to C++, comes extra-hardened. But now go get refactor your Rust code if you started to add lifetimes around... things get coupled quickly. It is particularly good at hardening and particularly bad at prototyping.
They seem to be the opposite in the absence of borrowing without a garbage collector, since you need to mark the lifetime in some way.
Rust is not that bad at prototyping, you need to use the right featureset when writing quick prototype code. Don't use lifetimes, use clone() and Rc/Arc freely to get around borrow-checker issues. Use .unwrap() or .expect("etc.") whenever you're not sure how to pass an error back to the caller. Experiment with the "Any" trait for dynamic typing and downcasts, etc. The final code will still be very high-performance for prototype code, and you can use the added boilerplate to guide a refactoring into a "proper" implementation once the design stabilizes.
Thanks for the advice. That makes sense I guess.
In fact, most of the time, I would favor styles like this even for not prototyping.
At the end, refactoring is also something natural. I would reserve lifetimes for the very obvious cases wirh controlled propagation or for performance-sensitve spots.
In fact, most of the time, I would favor styles like this even for not prototyping.
At the end, refactoring is also something natural. I would reserve lifetimes for the very obvious cases wirh controlled propagation or for performance-sensitve spots.
> It helps that I love compiler errors and Rust is full of them :D Every error the compiler catches is an error my QA/users don't
amen! I despise Python even though I used to love it, and that's because it's full of runtime errors and unchecked exceptions. The very instant I learned more strongly typed languages, I decided never to go back.
amen! I despise Python even though I used to love it, and that's because it's full of runtime errors and unchecked exceptions. The very instant I learned more strongly typed languages, I decided never to go back.
And then comes the point, where you get a scenario, which is actually, you'd think, at least, something simple, but then gets really tough to express in strongly, statically typed languages, and you might take a step back and consider for a moment, how simple it would be to express this in a language like Python, while still being memory safe.
Statically typing things is great, and I enjoy it too, when it is practical, but I don't enjoy it, when it becomes more complicated than the actual thing I want to express, due to how the type system of that particular language or third party tool (in Python) works.
Statically typing things is great, and I enjoy it too, when it is practical, but I don't enjoy it, when it becomes more complicated than the actual thing I want to express, due to how the type system of that particular language or third party tool (in Python) works.
I find it fun to statically prove correctness of difficult problems. To each their own, though, of course.
Python properly paired with typing is very competent IMHO.
I would like to learn how to do this well!
Well, the ideal is to install mypy and have a linter in your editor/IDE. It will immediately highlight lots of things for you.
mypyc is also fun
But this is wrong, it is no longer the case that `Unique` implies any extra optimizations, since it was since recognized that having these optimizations on a low-level unsafe building block is actually undesirable. Further, the `as_ref` functions mentioned in the article are not used by `Vec`'s internals. They are anyways only marked unsafe because they create references, not because of anything special with `Unique`.
Nowadays, all that `Unique` does is interact with `dropck` in a quirky way, the "exception to the exception." It is quite complicated and I always have to read up on it. It is explained in the Rustonomocon, in the "Click here to see why" section of this chapter: https://doc.rust-lang.org/nomicon/phantom-data.html#an-excep...