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.025 / U:62.136 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site