an ircd with a few thousand clients was cpu bound on poll()/select()
/dev/poll and kqueue/epoll were game changing
But few knew the trick so it didn't catch on.
with poll()/select() I don't see how you can avoid checking every FD at least once (poll's fd counter aside), vs. epoll() only returning those in the desired state
(and I don't think you could do tricks like epoll_wait() on an epoll fd)
Fork some child processes, and keep an AF_UNIX socketpair() open to them so you can pass them file descriptiors with SCM_RIGHTS.
Have the main process divide up the fds it is waiting on into a "hot" subset and cold subsets of size at most N, and for each cold subset pick a child process P. fds can be moved between hot and cold at any time, and generally you will move them to hot after they have woken and been used, and move them to cold after a few consecutive poll-cycles where they were not ready. Don't move fds to cold subsets belonging to child processes that you don't want to wake, though.
When the main process is ready to "poll everything", have it iterate over each child process that is not already sleeping, and send a message over the socketpair(), containing a list of fd_set additions and removals to that child's wait-for subset, including the type of poll (read, write, etc).
For each fd where the child doesn't have the real file descriptor yet, pass that over the socketpair() as part of the message. (If threads are usable instead of processes, there's no need to send the file descriptor. But on old systems, the system threads were often implemented by userspace multiplexing with poll/select anyway, so it wasn't a good idea to use threads with this technique.)
As well as a list of changes, this message tells the child process to run poll/select on its subset, and then reply with the set of fds that are ready (and their readiness type).
After issuing all the child process messages, the main process does its own poll/select, to wait for hot fds and replies from the child processes.
The reason this has different scaling properties, despite the overheads, is that each child handles a limited size subset, messages scale with the amount of change activity not the size of sets, and ideally the "coldest" fds end up gathered together in child processes that continue to sleep between a large number of main process polls, so the number of active child processes and messages scales with the amount of change activity as well.
Keep in mind, even active fds are removed from the wait-for subset if they've recently reported they are ready and the poll loop hasn't read/written them yet. So it has similar algorithmic properties to epoll.
As a bonus in the case of select(), the fds in the child processes have smaller values than in the main process. So in addition to the number of fds polled per cycle scaling with the amount of activity instead of the total number of fds, the fd_set bitset size does not grow with the total number of fds either. In the main process the bitset size does grow, but it's possible to juggle fd values with dup2() to overcome that.
that is indeed clever and I agree would practically improve the performance drastically for many (most?) workloads
worst case scenario (say all your sockets have a approximately the same chance of waking up): the behaviour devolves into the same as for poll() though?
as a broadcast medium: IRC has some annoying qualities in this regard (inline PINGs at regular intervals, events visible by nearly all that trigger socket avalanches, etc)
To picture it, maybe it helps to consider low and high uniform probabilities. If the uniform probability is a low enough per wait call, epoll/kqueue/etc have low cost per wait call, but so does this child-select method, because most child processes don't wake on each wait call. If the uniform probability is high enough, epoll/kqueue/etc return most of the fds, scaling just like the cost of select/poll, and child-select. So epoll/kqueue/etc and child-select match at the extremes, modulo constant factors.
In general, with a constant-bounded subset size, you can say the cost of unnecessary fd polls is amortised over the necessary fd polls, because unnecessary fd polls only occur in child processes that wake due to a necessary fd poll. So the algorithmic big-O scaling of this method is still the same as epoll/kqueue/etc as the number of fds increases and the probability varies, whether it's uniform or non-uniform.
No guarantees about the constant factors, though. You'd still want to tune parameters, to have enough and not too many in each subset. Constant-bounded subset size ensures scaling but not necessarily optimal performance. You can relax the constant bound and still keep the worst-case big-O scaling, if it's adaptive in the right sort of way, to better handle non-uniform probabilities with fewer processes.
Every network also seemed to have its own fork of ircd (and at least one rewrote it from scratch), so could have just been that the ones I used patched it in and others didn’t.