On Thu, 11 Nov 1999 17:18:57 -0800, "David Schwartz"
<davids@webmaster.com> said:
> The cost of the poll itself is O(n), but the higher the load, the
> fewer times we call poll because it takes us longer to get back to it
> and we find more active fds per poll.
Sure, it's well known that on busy internet servers, the number of fds
which are active at any point in time is likely to be only a fraction of
the total number. The trouble is that you have a lot of slow links with
dropped packets on the internet --- it's not at all comparable to the
traffic profile on a LAN. Your connection table _will_ become dominated
by these slow connections for the simple reason that slow connections
linger longer than fast ones.
Over the last two years at Usenix, there have been presentations
showing real life benchmark figures for real internet servers on Digital
Unix using (1) old, unoptimised poll; (2) a highly optimised poll; and
(3) an event-based server. The event loop won hands down.
> A properly implemented signal based I/O will likely be O(n). If
> there are 10,000 connections each handing me one packet per second, I
> will need 10,000 signals per second. If the kernel is smart enough not
> to send me another signal for the same connection if I haven't already
> processed the previous one, isn't that likely to be >O(n) since each
> signal requires checking n pending signals.
You are O(n) in this case anyway for the simple reason that you need to
read and write each fd. However, in real life, this simply doesn't
happen on the internet. The papers above estimated that at any point
only about 10% of their connections were live, and for any given poll()
only a fraction of those had new data to process. That is a _big_
overhead for poll.
--Stephen
-
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/