Re: Linux's implementation of poll() not scalable?

From: Jordan Mendelson (
Date: Mon Oct 23 2000 - 19:00:45 EST

Dan Kegel wrote:
> Linus Torvalds wrote:
> > Dan Kegel wrote:
> >> [ ]
> >> [ With only one active fd and N idle ones, poll's execution time scales
> >> [ as 6N on Solaris, but as 300N on Linux. ]
> >
> > 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.
> > ...
> > Under Linux, I'm personally more worried about the performance of X etc,
> > and small poll()'s are actually common. So I would argue that the
> > Solaris scalability is going the wrong way. But as performance really
> > depends on the load, and maybe that 10000 entry load is what you
> > consider "real life", you are of course free to disagree (and you'd be
> > equally right ;)

> The way I'm implementing RT signal support is by writing a userspace
> wrapper to make it look like an OO version of poll(), more or less,
> with an 'add(int fd)' method so the wrapper manages the arrays of pollfd's.
> When and if I get that working, I may move it into the kernel as an
> implementation of /dev/poll -- and then I won't need to worry about
> the RT signal queue overflowing anymore, and I won't care how scalable
> poll() is.

An implementation of /dev/poll for Linux already exists and has shown to
be more scalable than using RT signals under my tests. A patch for 2.2.x
and 2.4.x should be available at the Linux Scalability Project @ in the patches

It works fairly well, but I was actually somewhat disappointed to find
that it wasn't the primary cause for the system CPU suckage for my
particular system. Granted, when you only have to poll a few times per
second, the overhead of standard poll() just isn't that bad.

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

This archive was generated by hypermail 2b29 : Mon Oct 23 2000 - 21:00:22 EST