Hacker News Reader

Comment by agentultra | Hacker News Reader

> Using a Vec means we allocate memory every time we queue a waker. And that allocation is taken and released every time we have to wake.

Is that so? On every push back? I’d expect it’d only do an allocation when the current array segment is almost full… as a vector you might write by hand or like the ones in the C++ standard libraries do.

View on HN

This surprised me too, so I checked: https://doc.rust-lang.org/std/vec/struct.Vec.html#capacity-a...

"Vec does not guarantee any particular growth strategy when reallocating when full, nor when reserve is called. The current strategy is basic and it may prove desirable to use a non-constant growth factor. Whatever strategy is used will of course guarantee O(1) amortized push."

Seems it should be amortized just like in C++?

I don't want to tell the Rust folks what they should do but as a potential user I'd be more interested in the language if it was explicit (or the rules we clear and deterministic at the least). This claim took me a bit by surprise and I'd be upset if I'd encountered it in production code.

I think explicitly stating what it doesn’t guarantee is the right thing to do. Otherwise, the API becomes tied to your implementation through implicit details, which can prevent future generic performance improvements (e.g. unordered_map pointer stability in C++ prevents the implementation from being changed to a different representation like absl::flat_hash_map, even though that’s a guarantee that most people don’t care about).

Re: performance considerations. This is important, but for a performance critical application, any compiler, library etc version change can cause regressions, so it seems better to benchmark often and then tackle this, rather than make assumptions based on implicit (or even explicit) guarantees.

You do get some determinism, in that as long as the length of the vector is less than its capacity, it will never reallocate the buffer when new elements are added. And there are plenty of functions like Vec::with_capacity(), Vec::reserve(), Vec::reserve_exact(), etc. which let you control the capacity. The only unspecified part is by how much the capacity grows when the vector does have to reallocate.

Reply on news.ycombinator.com