Messages in this thread | | | Subject | RE: [Patch][RFC] epoll and half closed TCP connections | From | Alan Cox <> | Date | 14 Jul 2003 09:14:16 +0100 |
| |
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.
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |