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

111–120 of 142 posts

Re: Under the hood: Vec<T>

#111

Post by steveklabnik »

James_K wrote: post #7

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.

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

Re: Under the hood: Vec<T>

#112

Post by tialaramex »

vlovich123 wrote: post #100
swiftcoder wrote: post #62

Earlier quoted context omitted.

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

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

The global allocator GlobalAlloc::alloc method does indeed return a naked pointer

But the (not yet stable) Allocator::allocate returns Result, 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 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.

Re: Under the hood: Vec<T>

#113

Post by tialaramex »

vlovich123 wrote: post #99
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…

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

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 2. L + N 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...

Re: Under the hood: Vec<T>

#114

Post by Narishma »

ozgrakkurt wrote: post #27
assbuttbuttass wrote: post #26

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

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

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

Re: Under the hood: Vec<T>

#115

Post by johnisgood »

Klonoar wrote: post #38
johnisgood wrote: post #34

Earlier quoted context omitted.

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.

Fair enough.

Re: Under the hood: Vec<T>

#116

Post by tialaramex »

zdimension wrote: post #42
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.

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 >. 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 will be the same size, one byte with no extra work.

Re: Under the hood: Vec<T>

#117

Post by TinkersW »

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…

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.

Re: Under the hood: Vec<T>

#118

Post by swiftcoder »

constantcrying wrote: post #86
swiftcoder wrote: post #67

Earlier quoted context omitted.

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

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.

Re: Under the hood: Vec<T>

#119

Post by sesm »

zozbot234 wrote: post #91
sesm wrote: post #77

Earlier quoted context omitted.

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

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

Re: Under the hood: Vec<T>

#120

Post by sedatk »

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

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

Post reply on HN