Futures-rs: join_all can do quadratic unneeded polling

[jimblandy]

It's disappointing that, even though we know exactly which elements, when polled, will be able to make progress, join_all simply polls every future in the vector every time it is polled. Because it uses the same Waker to poll all the elements, it loses information about which events are relevant to which elements.

Example: Say we're doing a bunch of writes to different sockets in parallel. Each future in the sequence corresponds to a separate file descriptor, so when epoll says that one is ready, there is exactly one element that is worth polling. If the file descriptors become ready one at a time, we will have done O(n^2) polls by the time the join_all is ready.

The genius of futures is that they're not busy-waiting, but this ... looks a lot like busy-waiting, just along a different axis. If this could be fixed, it would bring futures closer to the pure "Let the epolls fall where they may" ideal.

One fix would be to spawn each of those futures back out to the executor, let the executor run them individually, and then have them each populate their elements of the vector and signal when everything is done.

Edit: There is also FuturesUnordered, but it seems to me it's possible for join_all to be both ordered and efficient.

[Nemo157]

That's why there is the more powerful FuturesUnordered API which is mentioned in the join_all docs, or as you mention you can spawn each individual future out to the executor (although, I don't know if there are nice APIs to do that at the moment, it seems like something using futures::lock::Mutex could be built relatively easily).

The main usecase I see for join_all is a variable small number of elements where the quadratic polling is likely to be less overhead than the additional tracking of multiple wakers required by FuturesUnordered. That's probably a very limited set of uses (either you statically know the number of elements and can use one of the tuple-based functions, or you have enough elements that FuturesUnordered is the better choice).

[jimblandy]

Thanks for the pointer to FuturesUnordered. I should have seen that.

I shouldn't have to choose between ordering and efficiency, though, should I? If it's more efficient to call FuturesUnordered and then re-order them into a vector, then that should be the implementation of join_all.

[cramertj]

It [is] more efficient to use join_all though in the case that you have a tiny set of futures that are easy to poll, since FuturesUnordered requires a separate custom-built atomic linked list which allocates each future independently.

[jimblandy]

@cramertj I'm not sure I understand - did you mean, "It _is_ more efficient to use join_all..." above? In the case of a few elements, it seems like join_all's Box<[Fut]> is pretty nice.

[cramertj]

Ah, yes-- sorry, typo-- I've amended it, thanks.