Coming from a position of extreme Rust ignorance & C++ brain poisoning:
Here’s the issue: waiting_for_elements is a Vec<Waker>. The channel cannot know how many tasks are blocked, so we can’t use a fixed-size array. 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.
Why isn't a structure that does amortized allocation an option here? I appreciate the design goal was "no allocations in steady-state", but that's what you'd expect if you were using C++'s std::vector: After a while the reserved space for the vector gets "big enough".
One typical approach is double-buffering the allocation but it doesn't work here because you need to pull out the waker list to call `wake()` outside of the mutex. You could try to put the allocation back, but you have to acquire the lock again.
I had an implementation that kept a lock-free waker pool around https://docs.rs/wakerpool/latest/wakerpool/ but now you're paying for atomics too, and it felt like this was all a workaround for a deficiency in the language.
Intrusive lists are the "correct" data structure, so I kept pushing.
I had the same question. I would think that with rust’s Vec, no allocation would occur at steady state. Vec does not automatically resize when removing elements.
Yeah, I'm also not sure what the author is talking about, std::vec also does amortized allocation and never shrinks. There are a bevy of more complicated vector classes in Rust if you need different behaviors, but off the top of my head I don't know why std::vec wouldn't work here.
Here’s the issue: waiting_for_elements is a Vec<Waker>. The channel cannot know how many tasks are blocked, so we can’t use a fixed-size array. 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.
Why isn't a structure that does amortized allocation an option here? I appreciate the design goal was "no allocations in steady-state", but that's what you'd expect if you were using C++'s std::vector: After a while the reserved space for the vector gets "big enough".