Hi folks, I’m trying to understand the design of the
futures-rs library. From reading through the code it looks like the algorithmic complexity of
select_all() when applied to large vectors is worse than optimal, so I want to check if I’m understanding correctly.
Here’s a specific example. Let’s say my server is trying to handle an incoming network request, and in order to do so I decide to make N=1000 outgoing requests and wait for all of them to return before responding to the original request – for example, to do a search over 1000 leaf servers. Looking through the
join_all() seems to be the idiomatic way to to implement the intended “wait for all to return” semantics.
The implementation of
JoinAll traverses a vector of size N to check which futures are ready, making it an O(N) operation. From my understanding of how
futures-rs works, in the worst case
poll() will be called every time that
Task::unpark() is called (namely, once per response), but may be called less often if some
unpark() calls occur close together in time. This means that in the worst case we make N calls to
JoinAll::poll(), for an overall cost of O(N^2). In contrast, a hand-coded implementation directly against epoll or similar instead of
futures-rs should be able to take only O(N) end-to-end CPU cost, because epoll directly reports the file descriptor that was triggered, avoiding the need for an O(N) scan over a vector.
A similar reasoning also seems to apply to
select_all() when called with wide fanout.
Is my analysis correct? Is there a more efficient idiomatic solution to this problem? When looking further through the
futures-rs code I see
with_unpark_event() whose documentation suggests it may be useful for solving the above problem, but I don’t understand how to apply it.