Under the hood: Vec<T>

https://marma.dev/articles/2025/under-the-hood-vec-t

by r4um • 10 months ago

174 137 10 months ago

marma.dev

rossant• 10 months ago

Tangent but nice web design.

herywort• 10 months ago

First thing I did was toggle reader view, it's noticeably more responsive scrolling there.

veber-alex• 10 months ago

This article feels too long and rambly considering how little actual technical information it provides.

LoganDark5• 10 months ago

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.

germandiago7• 10 months ago

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.

commandersaki• 10 months ago

This comment feels at odds with HN guidelines, if you're going to criticise at least offer some advice on how to improve.

5-• 10 months ago

James_K8• 10 months ago

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.

tialaramex11• 10 months ago

https://doc.rust-lang.org/reference/subtyping.html#variance

Lifetimes imply the need for the idea of variance.

pornel2• 10 months ago

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.

bobbylarrybobby2• 10 months ago

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!

Vipsy• 10 months ago

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

alickz• 10 months ago

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

LoganDark5• 10 months ago

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.

Tade0• 10 months ago

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.

johnisgood3• 10 months ago

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.

ozy• 10 months ago

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?

zozbot2347• 10 months ago

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

James_K8• 10 months ago

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.

SonOfLilit• 10 months ago

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.

tonyedgecombe• 10 months ago

stdlib code was always impenetrable to me, this was one of the reasons I moved away from C++.

James_K8• 9 months ago

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.

tialaramex11• 10 months ago

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.

hmry• 10 months ago

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)

kbolino2• 10 months ago

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.

ozgrakkurt2• 10 months ago

Yes, it is indeed very difficult to write unsafe rust, also very difficult to write anything low level and reusable

dathinab2• 10 months ago

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

steveklabnik3• 10 months ago

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

constantcrying2• 10 months ago

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.

swiftcoder4• 10 months ago

If a little lighthearted banter counts as "deeply emotional", I guess I understand why your username is "constant crying"

constantcrying2• 10 months ago

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.

gblargg• 10 months ago

https://archive.is/Cqr4E (if their site blocks your browser)

assbuttbuttass• 10 months ago

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

ozgrakkurt2• 10 months ago

This is just how rust and c++ code is in my experience.

germandiago7• 10 months ago

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.

Narishma• 10 months ago

Even C is like that in its most popular stdlib implementation (glibc).

ameliaquining2• 10 months ago

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

steveklabnik3• 10 months ago

Yep. Heck, I've barely even written any macros at all.

tialaramex11• 10 months ago

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.

smallstepforman2• 10 months ago

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

throwaway173738• 10 months ago

Suppose I think I may need 128 entries at some point, but the vector is allocated with room for 16 entries by default. I may not want to allocate and then immediately allocate again. But if I get to a 17th entry then I’m already causing allocation. So I might as well allocate 128 at that time so there are no more allocations at all.

mytailorisrich• 10 months ago

The difference according to Rust doc itsef:

reserve()

Reserves capacity for at least additional more elements to be inserted in the given Vec<T>. The collection may reserve more space to speculatively avoid frequent reallocations.

reserve_exact()

Reserves the minimum capacity for at least additional more elements to be inserted in the given Vec<T>. Unlike reserve, this will not deliberately over-allocate to speculatively avoid frequent allocations... Prefer reserve if future insertions are expected.

So if you know you'll need n now but will probably need more later, use reserve(). If you know n is all you'll need, use reserve_exact().

Vec<T> is a contiguous growable array, so the optimization game is to minimise allocations, reallocations (to keep it contiguous), and unused allocated memory.

pornel2• 10 months ago

reserve() reallocates by at least doubling the capacity.

reserve_exact() reallocates by exactly what you ask for.

If you reserve() space for 1 more element a 1000 times, you will get ~30 reallocations, not 1000.

This inexact nature is useful when the total size is unknown, but you append in batches. You could implement your own amortised growth strategy, but having one built-in makes it simple for different functions to cooperate.

charcircuit• 10 months ago

Hint means that the implementation is free to ignore it. It's just some extra metadata that the implementation can optionally make use of.

lossolo4• 10 months ago

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

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

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

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

adgjlsfhk12• 10 months ago

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

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

khuey• 10 months ago

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.

panzi• 10 months ago

Just today I saw a (2 year old) video on that very topic in Rust and C++: https://www.youtube.com/watch?v=algDLvbl1YY 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())
    );

tialaramex11• 9 months ago

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

TinkersW• 10 months ago

Reserve(reserve_exact in rust lingo) as a concept doesn't throw away amortized growth promise, so this entire post makes no sense.

You would need a very shitty implementation to achieve anything close to what you are describing(perhaps only allocating in powers of 2), and even then it would recover fairly quickly.

blacklion• 10 months ago

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.

conradludgate• 10 months ago

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]

This declares that NonNull cannot be outside of the range (1..). These magic attributes are only allowed to be used by the stdlib, and they're direct compiler instructions. Nonnull is special because the optimisation is guaranteed so the compiler does have special code to handle it, but other types can be optimised without compiler changes.

zdimension• 10 months ago

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):

  #[rustc_layout_scalar_valid_range_start(1)]

This gives rustc enough information to perform niche optimizations such as collapsing Option<NonNull<T>>.

You can technically use those for your own types, but it requires nightly, obviously.

tialaramex11• 10 months ago

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.

dathinab2• 10 months ago

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

germandiago7• 10 months ago

Can anyone compare it to C++ in terms of memory layout for typical implementations?

username223• 10 months ago

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.

sesm4• 10 months ago

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.

zozbot2347• 10 months ago

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.

swiftcoder4• 10 months ago

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.

sedatk• 10 months ago

Since a NonNull<T> can never be null, the compiler knows it can use the 0 address to represent the None variant when it sees an Option<NonNull<T>>

I didn't know this about Rust. That's awesome.

danhau• 10 months ago

Same optimizations apply to the various NonZero types, IIRC.

jojomodding2• 10 months ago

The explanation of `Unique` is a bit botched. `Unique` was originally intended to convey uniqueness in the sense of `noalias`, so that more compiler optimizations are possible similar to what happens around mutable references. This is what the article seems to suggest is going on .

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

marekzan• 10 months ago

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.

Under the hood: Vec<T>

Related Stories