Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Under the hood: Vec

marma.dev

Post reply on HN
Print view View original

31–40 of 142 posts

Re: Under the hood: Vec<T>

#31

Post by tialaramex »

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.

Re: Under the hood: Vec<T>

#32

Post by lpghatguy »

pornel wrote: post #15
James_K wrote: post #8

Earlier quoted context omitted.

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…

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.

Re: Under the hood: Vec<T>

#33

Post by branko_d »

kibwen wrote: post #24
pornel wrote: post #15

Earlier quoted context omitted.

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…

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 - If Generic : it's covariant.

- If Generic -> Generic: it's contravariant.

- Otherwise: it's invariant.

Or at least it's that straightforward in C#. Are there complications in Rust?

Re: Under the hood: Vec<T>

#34

Post by johnisgood »

zozbot234 wrote: post #30
johnisgood wrote: post #21

Earlier quoted context omitted.

Erm what? The article contradicts this. I'd push back on "without jumping through hoops". The article itself demonstrates 6 layers of abstraction (Vec -> RawVec -> RawVecInner -> Unique -> NonNull -> *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 i…

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

Re: Under the hood: Vec<T>

#35

Post by blacklion »

It is not clear, does compiler explicitly knows about properties of `NonNull` (for example, that it has neutral value to collapse `Option>`), 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.

Re: Under the hood: Vec<T>

#36

Post by tialaramex »

branko_d wrote: post #33
kibwen wrote: post #24

Earlier quoted context omitted.

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 - If Generic : it's covariant. - If Generic -> Generic : it's contravariant. - Otherwise: it's invariant. Or at least it's that straightforward in C#. Are there complications in Rust?

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?

Re: Under the hood: Vec<T>

#37

Post by Sharlin »

branko_d wrote: post #33
kibwen wrote: post #24

Earlier quoted context omitted.

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 - If Generic : it's covariant. - If Generic -> Generic : it's contravariant. - Otherwise: it's invariant. Or at least it's that straightforward in C#. Are there complications in Rust?

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 cannot be a subtype of G 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.

Re: Under the hood: Vec<T>

#38

Post by Klonoar »

johnisgood wrote: post #34
zozbot234 wrote: post #30

Earlier quoted context omitted.

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

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.

Re: Under the hood: Vec<T>

#39

Post by zozbot234 »

johnisgood wrote: post #34
zozbot234 wrote: post #30

Earlier quoted context omitted.

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

It's not real unsoundness because it only applies within the private implementation details of Vec - you still can't cause UB from outside code. But it's a real oversight that only proves how hard writing unsafe code is.

Re: Under the hood: Vec<T>

#40

Post by smallstepforman »

tialaramex wrote: post #31

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 s…

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