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

61–70 of 142 posts

Re: Under the hood: Vec<T>

#61

Post by sesm »

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 wad easy to teach to Java devs just by using one mnemonic: PECS = Producer Extends, Consumer Super

Re: Under the hood: Vec<T>

#62

Post by swiftcoder »

arka2147483647 wrote: post #53
throwaway173738 wrote: post #43

Earlier quoted context omitted.

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.

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

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

Re: Under the hood: Vec<T>

#63

Post by kannanvijayan »

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?

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.

Re: Under the hood: Vec<T>

#64

Post by adgjlsfhk1 »

lossolo wrote: post #46
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…

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

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

Re: Under the hood: Vec<T>

#65

Post by swiftcoder »

germandiago wrote: post #48

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.

Re: Under the hood: Vec<T>

#66

Post by [deleted] »

arka2147483647 wrote: post #53
throwaway173738 wrote: post #43

Earlier quoted context omitted.

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.

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

[deleted]

Re: Under the hood: Vec<T>

#67

Post by swiftcoder »

constantcrying wrote: post #14

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"

Re: Under the hood: Vec<T>

#68

Post by kbolino »

swiftcoder wrote: post #62
arka2147483647 wrote: post #53

Earlier quoted context omitted.

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

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

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.

Re: Under the hood: Vec<T>

#69

Post by dathinab »

blacklion wrote: post #35

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.

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

Re: Under the hood: Vec<T>

#70

Post by echelon »

germandiago wrote: post #49
LoganDark wrote: post #12

Earlier quoted context omitted.

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.

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.

Post reply on HN