lkml.org 
[lkml]   [2000]   [Oct]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
On Mon, Oct 23, 2000 at 11:14:35AM -0700, Linus Torvalds wrote:
> [ Small treatize on "scalability" included. People obviously do not
> understand what "scalability" really means. ]
>
> In article <39F28A86.1D07DBFF@alumni.caltech.edu>,
> Dan Kegel <dank@alumni.caltech.edu> wrote:
> >I ran a benchmark to see how long a call to poll() takes
> >as you increase the number of idle fd's it has to wade through.
> >I used socketpair() to generate the fd's.
> >
> >Under Solaris 7, when the number of idle sockets was increased from
> >100 to 10000, the time to check for active sockets with poll()
> >increased by a factor of only 6.5. That's a sublinear increase in time,
> >pretty spiffy.
>
> Yeah. It's pretty spiffy.
>
> Basically, poll() is _fundamentally_ a O(n) interface. There is no way
> to avoid it - you have an array, and there simply is _no_ known
> algorithm to scan an array in faster than O(n) time. Sorry.

One problem in Linux is that it scans multiple times. At least 4 times
currently: copyin, setup of wait queues, ask for results, copyout. copyin
and copyout are relatively cheap (and could be made even cheaper with
/dev/poll), the problem are the two other passes which involve a lot
of function pointer calls which generally cause pipeline stalls in modern
CPUs.

It would be possible to setup a file -> fdnum reverse table (possibly cached
over poll calls, I think Solaris does that) and let the async events directly
change the bits in the output buffer in O(1). This would save one pass.
It may also be possible to cache the wait queue setup over polls, this
would make poll much cheaper in terms of cache lines used.

Also the current 2.4 poll is very wasteful both in memory and cycles
for small numbers of fd. I did some experiments with a poll fast path
for small ns by falling back to the 2.0 stack allocation method, and
it decreased latency dramatically (>-30%). It also saves a lot of memory,
because all the daemons only polling for a few fds wouldn't use two
additional pages to their stack page [patches are availble, I just didn't
want to submit them during code freeze]


-Andi

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 12:41    [W:0.283 / U:0.268 seconds]
©2003-2011 Jasper Spaans. Advertise on this site