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

71–80 of 142 posts

Re: Under the hood: Vec<T>

#71

Post by zozbot234 »

sesm wrote: post #60
germandiago wrote: post #48

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

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.

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.

Re: Under the hood: Vec<T>

#72

Post by lossolo »

adgjlsfhk1 wrote: post #64
lossolo wrote: post #46

Earlier quoted context omitted.

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

Quadratic pushfive is just a cautionary tale about misusing reserve_exact. Basically use reserve_exact when you know the final size (reserve once), or you're doing a one off tight sizing where memory footprint matters.

Don't pre reserve inside pushfive, just push the 5 elements (Vec handles growth) or if you know how many times you'll call pushfive in a loop, reserve up front once vec.reserve(5 * times) or use reserve instead of reserve_exact for incremental growth.

Re: Under the hood: Vec<T>

#73

Post by zozbot234 »

kannanvijayan wrote: post #63
branko_d wrote: post #33

Earlier quoted context omitted.

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

Note that the Rust folks are working on a "safe-transmute" facility that may end up introducing a kind of variance to the language.

Re: Under the hood: Vec<T>

#74

Post by arka2147483647 »

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…

https://en.cppreference.com/w/cpp/container/vector/reserve.h...

says

> Increase the capacity of the vector (the total number of elements that the vector can hold without requiring reallocation) to a value that's greater or equal to new_cap.

I belive that the behaviour of reserve() is implementation defined.

Re: Under the hood: Vec<T>

#75

Post by dathinab »

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.

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 instead of Unique, 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>` (up to 4 due to alignment, but I think this optimization isn't guaranteed in this context)

Like it could be just a `Vec { ptr: *const T, cap: usize, len: usize, _marker: PhantomData }`, 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).

Re: Under the hood: Vec<T>

#76

Post by khuey »

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

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.

Re: Under the hood: Vec<T>

#77

Post by sesm »

zozbot234 wrote: post #71
sesm wrote: post #60

Earlier quoted context omitted.

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.

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

Re: Under the hood: Vec<T>

#78

Post by spoiler »

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.

To be fair, that is just the typical Reddit (or any social media platform) experience

Re: Under the hood: Vec<T>

#79

Post by mring33621 »

germandiago wrote: post #55
LoganDark wrote: post #13

Earlier quoted context omitted.

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

Python properly paired with typing is very competent IMHO.

I would like to learn how to do this well!

Re: Under the hood: Vec<T>

#80

Post by tialaramex »

kbolino wrote: post #68
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…

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

Maybe more interestingly, line 659, slightly above that, explains that we know we got [u8] but today the ordinary Rust allocator promises capacity is correct, so we just ignore the length of that slice.

We could, as that comment suggests, check the slice and see if there's enough room for more than our chosen capacity. We could also debug_assert that it's not less room, 'cos the Allocator promised it would be big enough. I dunno if that's worthwhile.

Post reply on HN