It is O(1) for poll.
> The event model only ever uses poll if the event queue overflows, which
> is expected to be a rare occurrence (it *never* happens during heavy
> local-load benchmarking with phhttpd).
Then you are using an O(n) mechanism when an O(1) mechanism is available.
To repeat, consider a typical use of poll:
1) Call poll.
2) Do the work that poll found.
3) Repeat.
Now, assume that we are fully loaded, so we never block. Each call to poll
takes O(n) time, where 'n' is the number of connections we are handling.
Each call to poll returns O(n) ready connections to operate on. Step 2 takes
O(n) time. So the number of calls to poll has order O(1/n). The overall
overhead of poll is O(1) -- constant.
Even if only one in a thousand connections are ready per call to poll, that
still means that the amount of time we spend in '1' and '2' is O(n). While
each call to poll takes O(n) time, it returns O(n) ready file descriptors.
Overall, poll is O(1) for high-load applications.
Of course, the time spent in step 2 is going to be the predominant factor
here. So the overhead of poll will drop into the noise as load increases. In
fact, the percentage of file descriptors that are ready per call to poll is
not constant. It goes _up_ with load, since it takes us longer to get back
to 'poll'. So poll is actually even better than this analysis suggests.
Of course, most real world applications won't push the limits in either
case. So events lower CPU cost at typical loads that should make it much
better. However, it is _not_ more scalable than poll. In fact, when you push
it to the limits, it falls back on poll precisely because poll is more
ultimately scalable.
DS
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/