From: Rainer Weikusat on
David Schwartz <davids(a)webmaster.com> writes:
> On Apr 30, 9:51�am, Chris Friesen <cbf...(a)mail.usask.ca> wrote:
>
>> While it handles large indexes better than select, poll still becomes
>> inefficient when the total number of descriptors is large.
>
> Only if comparatively few of the descriptors are active. The cost of a
> call to 'poll' is roughly O(n). If the number of descriptors
> discovered ready is usually one, that sucks. But if the number of
> descriptors discovered per call is also O(n), then its efficiency does
> not go down as the number of descriptors goes up.

This statement doesn't really make sense. 'Big Oh' is supposed to
communicate some information regarding how the execution cost of an
algorithm changes in response to changes in the number of items it
needs to process. Invoking poll and returning from poll requires that
a struct pollfd is copied in and out of the kernel for each descriptor
in the interest set. This copy requires at least an O(n) algorithm,
meaning, the cost of it will be proportional to the number of
descriptors which are supposed to be polled. The cost of the userspace
algorithm examining the results is proportional to the average
distance between the first and last active descriptor in the struct
pollfd array which may or may not increase when the amount of
supposed-to-be-polled descriptors increases.

But the real issue is actually that a struct pollfd is a fairly large
thing. It needs 64 bits of data, meaning, for more than 16
descriptors, the copying cost associated with invoking poll and
returning from poll will exceed the copying cost of doing the same
with select.
From: David Schwartz on
On May 2, 2:13 pm, Rainer Weikusat <rweiku...(a)mssgmbh.com> wrote:

> This statement doesn't really make sense. 'Big Oh' is supposed to
> communicate some information regarding how the execution cost of an
> algorithm changes in response to changes in the number of items it
> needs to process. Invoking poll and returning from poll requires that
> a struct pollfd is copied in and out of the kernel for each descriptor
> in the interest set. This copy requires at least an O(n) algorithm,
> meaning, the cost of it will be proportional to the number of
> descriptors which are supposed to be polled. The cost of the userspace
> algorithm examining the results is proportional to the average
> distance between the first and last active descriptor in the struct
> pollfd array which may or may not increase when the amount of
> supposed-to-be-polled descriptors increases.

Exactly. Now, imagine you double the number of descriptors. The cost
of the 'poll' operation itself doubles. But the number of descriptors
discovered ready will more than double. It will double simply because
twice as many descriptors means twice as many ready descriptors in the
same amount of time (assuming the average activity per descriptor is
constant). But double the amount of work will mean more time elapsed
between two calls to 'poll'.

So if you double the number of descriptors, each call to 'poll' takes
twice as long, but discovers more than twice the number of ready
descriptors. The cost of 'poll' per unit of work done goes *down* as
the number of descriptors goes up. (Assuming you don't have a
degenerate case like only one active descriptor. Again, 'poll's worst-
case behavior is *really* bad.)

DS
From: boltar2003 on
On Fri, 30 Apr 2010 08:04:14 -0700 (PDT)
David Schwartz <davids(a)webmaster.com> wrote:
>> Also poll doesn't return the amount of time left if in timeout mode and
>> something happens unlike select.
>
>You mean "unlike what my implementation of 'select' happens to do".

It doesn't just "happen to do". Its been the de facto behaviour for years
and is bloody useful if you're writing a realtime app.

B2003

From: boltar2003 on
On Fri, 30 Apr 2010 12:19:49 -0400
"Bill Cunningham" <nospam(a)nspam.invalid> wrote:
>boltar2003(a)boltar.world wrote:
>> On Fri, 30 Apr 2010 14:29:44 +0200
>> Rainer Weikusat <rweikusat(a)mssgmbh.com> wrote:
>
>> Also poll doesn't return the amount of time left if in timeout mode
>> and something happens unlike select.
>
> So you would say go with select() then? I'm certainly not knowledgable
>enough to do anything manually here. I'm going to log into my server with
>telnet. I know there's that timeval struct with poll().

poll() is probably more efficient, but select() is easier to use for someone
not used to writing server network code.

B2003

From: boltar2003 on
On Fri, 30 Apr 2010 13:57:30 -0700 (PDT)
David Schwartz <davids(a)webmaster.com> wrote:
>> For really high-performance servers that need to deal with large numbers
>> (tens of thousands) of descriptors, POSIX doesn't really have a
>> solution. =A0Various OS-specific options exist (kqueue on BSD, epoll on
>> Linux, /dev/epoll on Solaris, etc.)
>
>And many of these techniques outperform 'select' or 'poll' even when
>the number of descriptors is small, so the only downside is usually
>added implementation complexity. Also important, the worst-case
>behavior of these mechanisms is *way* better than 'select' or 'poll'.

Anyone who has a program that is dealing with thousands of descriptors
should really think about going multiprocess or multithreaded. A single
threaded program dealing with that many descriptors sounds like a recipe
for inefficient processing.

B2003