Re: poll vs. epoll

[Dan Kegel]

Shachar wrote:
> I noticed that in server/fd.c, the wineserver is using "poll" to select 
> between file descriptors. The application is going through this code 
> over 2000 times a second, with over 380 file descriptors each time. I am 
> wondering whether this can be the cause of the slowdown.
>
> One of the possible solutions to this would be to use epoll instead. 
> This, of course, would have to be backed by a configure check, as not 
> all systems for which wine is intended support epoll. Another, arguably 
> better, solution would be to use libevent for this purpose. Libevent has 
> the distinct advantage that it automatically chooses the best tool for 
> the job (epoll, poll, /dev/poll, or if all else fails, select).

By all means, let's try epoll.
FWIW, I wrote a wrapper layer that illustrates how to detect
whether epoll etc. are available.  I'm convinced that *runtime*
detection is the only way to go.  Compile time detection is insufficient.
My code is at http://kegel.com/rn
If you actually try to use it, let me know.  I expect it might
be useful mostly as a guide.  It's edge-trigger oriented, but
you can trivially add the flag (or remove the flag) needed to
get level-triggered behavior again if you really need it.
I highly recommend using edge-triggered behavior, though.
- Dan

poll vs. epoll

[Shachar Shemesh]

Dan Kegel wrote:
> Shachar wrote:
> > I noticed that in server/fd.c, the wineserver is using "poll" to 
> > select between file descriptors. The application is going through 
> > this code over 2000 times a second, with over 380 file descriptors 
> > each time. I am wondering whether this can be the cause of the slowdown.
> >
> > One of the possible solutions to this would be to use epoll instead. 
> > This, of course, would have to be backed by a configure check, as not 
> > all systems for which wine is intended support epoll. Another, 
> > arguably better, solution would be to use libevent for this purpose. 
> > Libevent has the distinct advantage that it automatically chooses the 
> > best tool for the job (epoll, poll, /dev/poll, or if all else fails, 
> > select).
>
> By all means, let's try epoll.
> FWIW, I wrote a wrapper layer that illustrates how to detect
> whether epoll etc. are available.  I'm convinced that *runtime*
> detection is the only way to go.  Compile time detection is insufficient.
> My code is at http://kegel.com/rn

Sure will have a look.
> If you actually try to use it, let me know.  I expect it might
> be useful mostly as a guide.  It's edge-trigger oriented, but
> you can trivially add the flag (or remove the flag) needed to
> get level-triggered behavior again if you really need it.
> I highly recommend using edge-triggered behavior, though.

I'm sure that edge trigger yields better performance. The problem, 
however, what with all the potential races edge trigger introduces, and 
the fact I'm not sufficiently familiar with the wineserver semantics, 
that going edge trigger in a bug free way right now is beyond me.
> - Dan

Shachar

poll vs. epoll

[Dan Kegel]

Shachar Shemesh wrote:
> > FWIW, I wrote a wrapper layer that illustrates how to detect
> > whether epoll etc. are available.  I'm convinced that *runtime*
> > detection is the only way to go.  Compile time detection is insufficient.
> > My code is at http://kegel.com/rn
>
> Sure will have a look.

cool!
i
> > If you actually try to use it, let me know.  I expect it might
> > be useful mostly as a guide.  It's edge-trigger oriented, but
> > you can trivially add the flag (or remove the flag) needed to
> > get level-triggered behavior again if you really need it.
> > I highly recommend using edge-triggered behavior, though.
>
> I'm sure that edge trigger yields better performance. The problem, 
> however, what with all the potential races edge trigger introduces, and 
> the fact I'm not sufficiently familiar with the wineserver semantics, 
> that going edge trigger in a bug free way right now is beyond me.

"potential race conditions" is the wrong way to think about
it, really.
Switching to edge triggered epoll from select() or poll() is
always an interesting intellectual challenge; you're
fundamentally switching to an idiom where the app has
to remember more than it did before.
Once you've done it a few times, it gets easier.

If I have time, I'll have a look at the state machine
inside wineserver and see how tricky it'd be.
- Dan

poll vs. epoll

[Shachar Shemesh]

Shachar Shemesh wrote:
> Dan Kegel wrote:
> > By all means, let's try epoll.
> > FWIW, I wrote a wrapper layer that illustrates how to detect
> > whether epoll etc. are available.  I'm convinced that *runtime*
> > detection is the only way to go.

That's fine, except that compiling your library on a machine that has 
epoll, and then trying to run it on a machine without will not work. It 
will not load if runtime glibc doesn't have epoll. I'm using "syscall" 
to work around that problem in wine.
> > Compile time detection is insufficient.
> > My code is at http://kegel.com/rn
>
> Sure will have a look.

It doesn't compile (rn.c is not including <sys/epoll.h>). When I fix 
that, it checks whether epoll_create works. If it does, it sets all 
handlers to use sigio. I don't think this library is quite stable enough :-)

In any case, it seems that it's interface is not ideal for wineserver. 
Libevent, on the other hand......

Shachar

poll vs. epoll

[Dan Kegel]

Shachar Shemesh wrote:
> It doesn't compile (rn.c is not including <sys/epoll.h>). When I fix 
> that, it checks whether epoll_create works. If it does, it sets all 
> handlers to use sigio. I don't think this library is quite stable enough 
> :-)

You're a tough customer :-)  It's quite close; guess I should polish it up a bit.
> In any case, it seems that it's interface is not ideal for wineserver. 
> Libevent, on the other hand......

Now don't go and do level-triggered stuff just because it's easier :-)

I don't think it's fair to say level-triggered is ideal for
wineserver.  In fact, wineserver is an example of the kind
of program that is easier to convert to edge-triggering
than most programs, since it's small and self-contained.

Sigh.  I wish my wrists were in better shape; I'd convert it
myself.  As it is, he who does the work gets to choose interfaces.
- Dan

poll vs. epoll

[Shachar Shemesh]

Dan Kegel wrote:
> Shachar Shemesh wrote:
> > It doesn't compile (rn.c is not including <sys/epoll.h>). When I fix 
> > that, it checks whether epoll_create works. If it does, it sets all 
> > handlers to use sigio. I don't think this library is quite stable 
> > enough :-)
>
> You're a tough customer :-)  It's quite close; guess I should polish 
> it up a bit.
> > In any case, it seems that it's interface is not ideal for 
> > wineserver. Libevent, on the other hand......
>
> Now don't go and do level-triggered stuff just because it's easier :-)

That's not it at all, and edge vs. level is not part of my 
considerations. Libevent does support a wider variety of selection 
interfaces, and with wider platform support, than your library.
> I don't think it's fair to say level-triggered is ideal for
> wineserver.  In fact, wineserver is an example of the kind
> of program that is easier to convert to edge-triggering
> than most programs, since it's small and self-contained.

Can you give benchmarks for performance differences between the two? The 
more I think about it, the more I'm getting the impression that going 
edge trigger means we need to maintain our own cache of not-yet-useful 
data, as well as risking starvation. I'm sure there are cases where this 
is preferable, but can you explain why this is such a case?

Also, can you show me how to do edge trigger via poll?
> Sigh.  I wish my wrists were in better shape; I'd convert it
> myself.  As it is, he who does the work gets to choose interfaces.
> - Dan

I'll qualify the starvation claim.

Suppose we have five fds we are watching. Suppose one (let's call it 
"3") of them is really really intensive in it's request rate. Using the 
current interface (as used in the preliminary patch I sent), each time 
we call epoll we will see that 3 is active, but any time any other fd 
has anything to do, it will be handled.

Suppose we go edge triggered now. We call epoll, and it's likely that 3 
will be the only one active. We will call the 3 handling function, which 
will try to exhaust the requests arriving on 3 before returning. No it's 
a problem - requests potentially are never exhausted on 3. When do we 
exit the handler to do other stuff? We would need to write some 
mechanism to introduce this fairness ourselves.

In short, if you are going edge trigger, your relative scheduling 
priority is your responsibility, as well as keeping all partial memory 
buffered. With level trigger, the kernel does that for you. Is there any 
reason to assume that we can do that better than the kernel?

Shachar

poll vs. epoll

[Dan Kegel]

Shachar Shemesh wrote:
> > Now don't go and do level-triggered stuff just because it's easier :-)
>
> That's not it at all, and edge vs. level is not part of my 
> considerations. Libevent does support a wider variety of selection 
> interfaces, and with wider platform support, than your library.

Don't get me wrong.  Libevent is good stuff.  Niels is a very good guy.
I don't think platform support is an issue (which platform do you need?)
The one interface rn is missing, I think, is a timer.
Buffered events would be a fine addition, too.
But rn has the basic notification stuff; it was intended to focus on those.
> > I don't think it's fair to say level-triggered is ideal for
> > wineserver.  In fact, wineserver is an example of the kind
> > of program that is easier to convert to edge-triggering
> > than most programs, since it's small and self-contained.
>
> Can you give benchmarks for performance differences between the two?

The essential difference is that level-triggered means more notifications
coming from kernel space, which always means higher overhead.  The difference
is going to be slight.

I have also noticed that in some situations where the interest mask
is hard to compute, using edge triggered is much easier, because you
never have to compute it.
> The more I think about it, the more I'm getting the impression that going 
> edge trigger means we need to maintain our own cache of not-yet-useful 
> data

The same cache is maintained in the kernel for you if you use level triggering.
> as well as risking starvation.

There is no risk of starvation in a properly written program.
> Also, can you show me how to do edge trigger via poll?

There is no need for that, since Linux and *BSD all support some
form of edge-triggered notification.  However, if we want to
support ancient operating systems, it wouldn't be too hard to
add poll() support to rn under the covers, and present the edge-triggered
interface to the user.
> I'll qualify the starvation claim.
>
> Suppose we have five fds we are watching. Suppose one (let's call it 
> "3") of them is really really intensive in it's request rate. Using the 
> current interface (as used in the preliminary patch I sent), each time 
> we call epoll we will see that 3 is active, but any time any other fd 
> has anything to do, it will be handled.
>
> Suppose we go edge triggered now. We call epoll, and it's likely that 3 
> will be the only one active. We will call the 3 handling function, which 
> will try to exhaust the requests arriving on 3 before returning. No it's 
> a problem - requests potentially are never exhausted on 3. When do we 
> exit the handler to do other stuff? We would need to write some 
> mechanism to introduce this fairness ourselves.

Yes, but that's easy.  It's about four lines of code.
> In short, if you are going edge trigger, your relative scheduling 
> priority is your responsibility, as well as keeping all partial memory 
> buffered. With level trigger, the kernel does that for you.

What's this about partial memory buffering?  Sounds like you're inventing
a difficulty here.

- Dan

poll vs. epoll

[Shachar Shemesh]

Dan Kegel wrote:
> Shachar Shemesh wrote:
> > > Now don't go and do level-triggered stuff just because it's easier :-)
> >
> > That's not it at all, and edge vs. level is not part of my 
> > considerations. Libevent does support a wider variety of selection 
> > interfaces, and with wider platform support, than your library.
>
> Don't get me wrong.  Libevent is good stuff.  Niels is a very good guy.
> I don't think platform support is an issue (which platform do you need?)

We are trying to have as wide support as we can, obviously.
> The one interface rn is missing, I think, is a timer.

Which wineserver needs.
> Buffered events would be a fine addition, too.
> But rn has the basic notification stuff; it was intended to focus on 
> those.

But then why NOT use libevent :-) If you are really itching, why not 
just add edge trigger to libevent?
> > The more I think about it, the more I'm getting the impression that 
> > going edge trigger means we need to maintain our own cache of 
> > not-yet-useful data
>
> The same cache is maintained in the kernel for you if you use level 
> triggering.

True, but that does save me on writing and debugging. After all, that's 
why libraries are there for to begin with.

Also, it would seem to me that keeping data in the fd cache until it's 
actually needed saves on copies. Isn't that the case?
> > Also, can you show me how to do edge trigger via poll?
>
> There is no need for that, since Linux and *BSD all support some
> form of edge-triggered notification.

For Linux platforms prior to epoll, what's there?
> > I'll qualify the starvation claim.
> >
> > Suppose we have five fds we are watching. Suppose one (let's call it 
> > "3") of them is really really intensive in it's request rate. Using 
> > the current interface (as used in the preliminary patch I sent), each 
> > time we call epoll we will see that 3 is active, but any time any 
> > other fd has anything to do, it will be handled.
> >
> > Suppose we go edge triggered now. We call epoll, and it's likely that 
> > 3 will be the only one active. We will call the 3 handling function, 
> > which will try to exhaust the requests arriving on 3 before 
> > returning. No it's a problem - requests potentially are never 
> > exhausted on 3. When do we exit the handler to do other stuff? We 
> > would need to write some mechanism to introduce this fairness ourselves.
>
> Yes, but that's easy.  It's about four lines of code.

I'm sure it is. So is managing the buffers etc. Thing is - why go into 
it at all if the difference is small?

As an aside I'll mention that I'd like to see those four lines :-)
> What's this about partial memory buffering?  Sounds like you're inventing
> a difficulty here.

It may be that I'm referring to a difficulty that also exists in the 
usual case. I'm talking about half received "packets" of information on 
stream entities (such as TCP sockets and pipes).
> - Dan

Shachar

poll vs. epoll

[Mike Hearn]

> That's fine, except that compiling your library on a machine that has 
> epoll, and then trying to run it on a machine without will not work. It 
> will not load if runtime glibc doesn't have epoll. I'm using "syscall" 
> to work around that problem in wine.

Why not use dlopen?

poll vs. epoll

[Dan Kegel]

Mike Hearn wrote:
> > That's fine, except that compiling your library on a machine that has 
> > epoll, and then trying to run it on a machine without will not work. 
> > It will not load if runtime glibc doesn't have epoll. I'm using 
> > "syscall" to work around that problem in wine.
>
> Why not use dlopen?

Maybe he's referring to the case where libc.so doesn't have
the epoll bindings, but the underlying kernel does?
- Dan

poll vs. epoll

[Mike Hearn]

> Maybe he's referring to the case where libc.so doesn't have
> the epoll bindings, but the underlying kernel does?

Oh yes, I bet that's it. I never really thought about that before but I 
guess there's no reason why libc would always support every feature of 
the kernel. Thanks Dan!