> David Schwartz writes:
> > To repeat, consider a typical use of poll:
> >
> > 1) Call poll.
>
> Kernel does O(n) work.
>
> > 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.
>
> This argument is fallacious. The kernel is doing O(n) work in
> poll(2). You are in effect ignoring the other costs in your loop.
> Furthermore, you are being inconsistent, because you count other
> overheads (particularly syscall overheads) against the signal-based
> scheme.
Aren't the two of you counting differently? If I'm reading correctly,
David Schwartz is counting the amt of work per busy FD, and you're
counting the amount of work per poll call. The latter is O(n), with n
= the number of FDs. The former is O(n) when there's 1 busy FD per
loop. However, if enough work is coming in that all FDs are busy each
time time poll is called, then poll is going to take O(1) (because if
it takes O(#FDs) per call and all FDs are busy it's taking
O(#FDs/#FDs=1) per busy FD). Thus David Schwartz' claim that poll
does scale well - the % of time spent in poll will peak at the maximum
load such that only one FD is busy for each loop, and then it will
drop as the load continues to climb - more FDs will be busy for each
poll call both because the load is higher and because doing the work
will be acting on multiple FDs (so that doing the work will delay the
next call to poll & thus further increase the # of busy FDs by the
time that poll is called).
So, as load goes to infinity, one would expect the amount of time in
poll to be O(1) in units of work to do, the same as working with
events. Of course, with events, it's always O(1), which has it's own
benefits.
But, I'm not convinced this argument holds in general as system load
goes to infinity. Other things could be a fcn of the load (such as
the # of processes doing polls on large #s of FDs) which would
prevent the above asymptotic behavior from being reached.
-- Harvey Stein Bloomberg LP hjstein@bfr.co.il- 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/