RE: [Patch][RFC] epoll and half closed TCP connections

[Alan Cox <alan@lxorguk.ukuu.org.uk>]

On Llu, 2003-07-14 at 00:09, Davide Libenzi wrote:
> On Sun, 13 Jul 2003, David Schwartz wrote:
> 
> > 	It's not O(N) with 'poll' and 'select'. Twice as many file descriptors
> > means twice as many active file descriptors which means twice as many
> > discovered per call to 'poll'. If the calls to 'poll' are further apart
> 
> It is O(N), if N if the number of fds queried. The poll code does "at least"
> 2 * N loops among the set (plus other stuff), and hence it is O(N). Even
> if you do N "nop" in your implementation, this becomes O(N) from a
> mathematical point of view.

You need to apply queue theory and use a model of the distribution of
data arrival on the inputs/outputs to actually tell. The its O(N) claim
is like most such claims and probably only useful if data arrives
infinitely slowly and you have infinite ram and cache is not a factor.

For some loads poll/select are actually extremely efficient. X clients
batch commands up and there is a cost to switching between tasks for
different clients. Viewed as an entire system you actually get quite
interesting little graphs, especially in the critical load cases where
select/poll's batching effect makes throughput increase rapidly at 100%
CPU load, even if it gets you there far too early. Ditto with
webservers.