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

91–100 of 142 posts

Re: Under the hood: Vec<T>

#91

Post by zozbot234 »

sesm wrote: post #77
zozbot234 wrote: post #71

Earlier quoted context omitted.

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

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.

Re: Under the hood: Vec<T>

#92

Post by kstrauser »

mytailorisrich wrote: post #47
smallstepforman wrote: post #40

Earlier quoted context omitted.

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

The difference according to Rust doc itsef: reserve() > Reserves capacity for at least additional more elements to be inserted in the given Vec . 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 . Unlike reserve, this will not deliberately over-allocate to speculati…

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?

Re: Under the hood: Vec<T>

#93

Post by pornel »

smallstepforman wrote: post #40
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”?

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.

Re: Under the hood: Vec<T>

#94

Post by Grayskull »

Sharlin wrote: post #57
smallstepforman wrote: post #44

Earlier quoted context omitted.

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?

Re: Under the hood: Vec<T>

#95

Post by ameliaquining »

lpghatguy wrote: post #32
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…

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

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.

Re: Under the hood: Vec<T>

#96

Post by tialaramex »

kstrauser wrote: post #92
mytailorisrich wrote: post #47

Earlier quoted context omitted.

The difference according to Rust doc itsef: reserve() > Reserves capacity for at least additional more elements to be inserted in the given Vec . 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 . Unlike reserve, this will not deliberately over-allocate to speculati…

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?

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.

Re: Under the hood: Vec<T>

#97

Post by charcircuit »

smallstepforman wrote: post #40
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”?

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

Re: Under the hood: Vec<T>

#98

Post by bobbylarrybobby »

James_K wrote: post #8
5- wrote: post #5

related: https://doc.rust-lang.org/nomicon/vec/vec.html

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.

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!

Re: Under the hood: Vec<T>

#99

Post by vlovich123 »

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…

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

Re: Under the hood: Vec<T>

#100

Post by vlovich123 »

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…

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

Post reply on HN