Messages in this thread | | | Subject | Re: Max tcp connections | From | (Harvey J. Stein) | Date | 17 Nov 1999 09:08:33 -0500 |
| |
Richard Gooch <rgooch@ras.ucalgary.ca> writes:
> 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/
| |