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

81–90 of 142 posts

Re: Under the hood: Vec<T>

#81

Post by adgjlsfhk1 »

lossolo wrote: post #72
adgjlsfhk1 wrote: post #64

Earlier quoted context omitted.

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

that's exactly the footgun. reserve_exact usage needs to be analyzed globally, while `resere` has the extra fuzziness needed to ensure that you can't mess anything up too badly with it.

Re: Under the hood: Vec<T>

#82

Post by mandarax8 »

arka2147483647 wrote: post #74
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…

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.

That said MSVC,GCC and clang all implement it to allocate an exact value.

Re: Under the hood: Vec<T>

#83

Post by tialaramex »

arka2147483647 wrote: post #74
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…

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.

Because there's only a single function here, it has to either be Vec::reserve or Vec::reserve_exact

If you don't offer Vec::reserve_exact then people who needed that run out of RAM and will dub your stdlib garbage. If you don't offer Vec::reserve as we've seen C++ programmers will say "Skill issue" whenever a noob gets awful performance as a result. So, it's an easy choice.

Re: Under the hood: Vec<T>

#84

Post by lossolo »

khuey wrote: post #76
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 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 yo…

Sure, but this isn't a job for reserve_exact. Vec::reserve is like a framing hammer made for speed and momentum. You might dent a little extra wood (overallocate), but you drive lots of nails fast and keep amortized O(1) growth. reserve_exact is a jeweler's hammer so great when you know the exact setting and won't touch it again, precise fit, zer slack etc.

Now, try to frame a house with jeweler's hammer, tapping in tiny increments and resizing every few boards and you will crawl into quadratic time.

Who is using jeweler's hammer to frame their house?

So what I'm arguing is if you don't misuse reserve_exact, then as you said you still get amortized growth. The OP's example misuses the tool and then blames it for not behaving differently on that first append.

Re: Under the hood: Vec<T>

#85

Post by lossolo »

adgjlsfhk1 wrote: post #81
lossolo wrote: post #72

Earlier quoted context omitted.

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

that's exactly the footgun. reserve_exact usage needs to be analyzed globally, while `resere` has the extra fuzziness needed to ensure that you can't mess anything up too badly with it.

Calling that a "footgun" feels really overstated.

Yes, reserve is the safer default because it gives you slack and preserves amortized growth even if your usage pattern is messy.

But "needs global analysis" isn't unique to reserve_exact. Lots of perf knobs do (chunk sizes, buffering, locking granularity etc). The fix to this is to use the tool where its preconditions actually hold, not to avoid the tool.

So what I'm basically saying is that reserve_exact isn't inherently dangerous, it just assumes you know the final size and won't exceed it etc. If you keep bumping it in tiny steps (pushfive style), that's just misuse so treating it as a flaw is unwarranted.

Re: Under the hood: Vec<T>

#86

Post by constantcrying »

swiftcoder wrote: post #67
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"

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 problem. The problem is that the author has a hard time writing a single paragraph without it. They should seriously consider doing some training in technical or scientific writing.

>, I guess I understand why your username is "constant crying"

What a novel comment. But yes, I do hate the constant positivity, especially in the face of a subpar product.

Re: Under the hood: Vec<T>

#87

Post by LoganDark »

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.

I won't deny that there are lots of emotions surrounding Rust, both for myself and for many others. But there are different ways to write about it, and this article looks more of an emotional style ("here's how my journey went") than a technical one ("here's how this works"). I still find it fun to read, but not everyone will, and that's okay.

Re: Under the hood: Vec<T>

#88

Post by LoganDark »

zelphirkalt wrote: post #23
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.

And then comes the point, where you get a scenario, which is actually, you'd think, at least, something simple, but then gets really tough to express in strongly, statically typed languages, and you might take a step back and consider for a moment, how simple it would be to express this in a language like Python, while still being memory safe. Statically typing things is great, and I enjoy it too, when it is practica…

I find it fun to statically prove correctness of difficult problems. To each their own, though, of course.

Re: Under the hood: Vec<T>

#89

Post by ameliaquining »

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

"The standard library internally overuses macros and you probably shouldn't use them that much in your own code" is at least a respectable opinion in the Rust community, I think.

Re: Under the hood: Vec<T>

#90

Post by rsyring »

demurgos wrote: post #50
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.

I believe that you are describing `Vec::with_capacity` which allows to change the initial reserved memory on construction. `reserve` and `reserve_exact` are used when mutating an existing vec. What you provide is not the total wanted capacity but the additional wanted capacity. `reserve` allows to avoid intermediate allocation. Let's say that you have a vec with 50 items already and plan to run a loop to add 100 more…

This should be in the docs or a blog post somewhere. Very clear explanation.
Post reply on HN