[SDL] SDL_WaitEvent in 1.3

[Pierre Phaneuf]

On Fri, Jan 9, 2009 at 2:12 PM, Bob Pendleton <bob at pendleton.com> wrote:

> It is not possible to ensure that you always get every event.

I agree. But there's a big difference between network events that can
get blasted at high speed, and keyboard events that go at up to 20 per
seconds (that's assuming a really advanced 120 wpm touch typist). And
most specifically, losing the KeyUp event corresponding to a KeyDown
would be very annoying (the user could un-stick the key by pressing it
again, but it's far more visible and embarrassing than TCP retries
after dropped packets!). Or, for example, a timer event, I'd be okay
with it arriving late, but *never* arriving would be fairly insulting
(the memory is all pre-allocated when you register the timer, one only
has to walk the priority queue of registered timers to find out the
expired ones).

> Can the application help the OS out? Why yes it can. The application
> can grab all the pending packets when ever possible and queue them up.
> If we do that then the application can act to extend the OS queue
> capacity and reduce the chance of lost packets. Don't believe me? Try
> streams as many UDP/IP packets as you can across a LAN and see the
> effect of application queue size on the total number of lost packets.

TCP has flow control designed into it for that purpose, for example,
and doing user-space queueing foils it. As I mentioned in my last
email, you can't *remove* a queueing step once it's there, so if you
provide one, and it more or less cripples the TCP sliding window, the
application *cannot* "undo the damage". The crippling is done. Where
if the application decides that it needs to queue in order to operate
properly, if there's no queueing provided, it can be added, leaving
the options open.

Also, it's very unclear to me that there is any improvement to get by
moving packets from one queue to the other (from the OS queue to the
application queue). If the buffer isn't big enough, use
setsockopt(SO_RCVBUF). What I found to be optimal for throughput is to
process UDP packets in batches, with a cap for fairness (don't want to
starve the UI for the network).

A common mistake is to process (not just receive into a queue, but
actually *process*) just one packet per notification (which,
incidentally, is what you get if you SDL_PushEvent the packets and
process them using SDL_WaitEvent, since the latter does a
SDL_PumpEvents every time).

I'm quite aware that lossage might be possible, but I'm just saying
that losing information (feedback) about the lossage is also very bad,
preventing correct throttling behaviours from kicking in. A classic
example is a old hack where you could do PPP tunnelled over SSH to
have a home-grown VPN. It turns out that this has very bad latency
implications, because SSH provides a fully-reliable transport (thanks
to using TCP), and TCP actually relies on feedback in the form of lost
packets to notice congestion, so running TCP-over-TCP is a bad idea
(see http://sites.inka.de/~W1011/devel/tcp-tcp.html for a good
explanation). Having an extra queue in SDL loses feedback.

Also, people often underestimate the cost of getting and queueing
spurious events. I once worked on packet capture software, and using a
careful kernel-side packet-matching filter (using "tcpdump -d" and
setsockopt(SO_ATTACH_FILTER)) made the difference between the computer
(a mid-range 1.6 GHz machine, not some dinky ARM board) being
overwhelmed (losing packets at 100% CPU usage) and keep up easily with
a CPU usage in the 10% range. This is related to my point about
application being able to state whether they are interested or not in
an event, instead of just getting everything and letting the
application throw away events it does not need.

> That is how it works in networks, so what about using devices like
> mice and joysticks? Same thing happens actually. It all depends on how
> fast you can get the events from the device but it is still the case
> that the OS has a limited amount of space to hold input from any
> device. But, in the case of a mouse or joystick the device can not
> regenerate the input events. What is an OS to do? In the case of both
> the mouse and the joystick have movement and button push events. When
> the mouse moves you can just modify the event at the top of the queue
> (if it is a movement event) and add the current dx,dy to the existing
> dx,dy and sort of lie about where the mouse has been. The application
> is sure to get the mouses current location, but loses information
> about its path. You can't do that with buttons though... you have to
> generate a new button event for each change of state. So, if the
> application doesn't get mouse/joystick events often enough the OS
> queue fills up and input is just lost.

For the mouse, that's the event coalescing I was talking about, which
does reduce the quality of the input, but is in my opinion better than
"100% accurate, until it becomes utter trash". If your application
isn't keeping up, slowly and gently degrading is much better than
going into some awful stuttering.

For the buttons, one could drop further button events without dropping
other events, and be careful to post one last ButtonRelease before
doing so. They also happen to be very low-intensity events (rarely
more than 10-20 per seconds, I'd guess?) and they can be very easy to
process (update a "button_is_pressed" boolean isn't exactly a ton more
work than dropping the event). Again, there's already a queue in the
display server that could lose those events, so why add our own? Is it
better to lose them inside SDL, somehow (the application doesn't see
them either way)?

> Again, the application can help out by clearing the queue as often as
> possible and storing as many events in application memory as possible.

And rob the display server of chances of applying its own throttling.
Once you've done that, you can't undo it, but you can always add it
later if that's a problem...

> And, think about this: OS developers tend to want to use as little
> space as possible so that the application has as much space as
> possible. It is easy for an application to store thousands of events
> when the OS may only be willing to store a few.

Most input systems are in user-space already, SDL is getting those
over Unix domain sockets or Mach ports, and Windows has a limit of
10,000 messages (SDL's MAXEVENTS is a dinky 128 in comparison!). This
is a non-issue. If we have a platform that does not, then the SDL
driver for that platform can provide some queueing to provide a
minimum expected level of service, but doing that in the generic code
isn't a clear win to me (the SDL core code can definitely provide a
single queue implementation that platform drivers can share, of
course, it should just not be mandatory).

> Oh, yeah... The thing about network packets being lost and the source
> OS being finally responsible for resending lost packets and having to
> pause an application that is trying to send more packets than the
> source machine can queue? Well that is why you can have nonblocking
> network input, but you *can not* have non-blocking network output. You
> can get close to nonblocking network output, but you can't get it
> because if all the queues are full from your application to the
> destination machine, your application *must* pause until the queues
> are emptied. If your are stuck in traffic you must wait for the cars
> in front of you to move before you can more. (OK, I've been known to
> drive off the Interstate through the grass to the frontage road and in
> some cities I have seen people driving on the sidewalks, but even
> those resource fill up. :-)

I use non-blocking sending with small kernel SO_SNDBUF on purpose in
some situations, because I want the explicit feedback from the
network, telling me that I'm overloading it (incidentally, the
recipient buffering everything into user-space would screw this up,
again), and I can coalesce events in a way that makes sense for my
application. For example, in Quadra (a T*tris derivative), there a
"watch" feature where you can see other players blocks as they fall,
but if the bandwidth is too low, you don't get the full sequence of
block moves with a delay, you just get a single "big move",
potentially putting it in its final place, and this is accomplished by
reacting appropriately when send() returns EWOULDBLOCK. This clever
protocol is not possible with SDL_net as of now, by the way, even
though it's completely portable.

When I see the traffic on the road outside the office, I just stay at
the office and work some more. This is "free work" I accomplish
instead of being stuck in traffic. If I lose the feedback, then I can
just try to drive home and hope for the best, where I might or might
not "pause" on the freeway. ;-)

-- 
http://pphaneuf.livejournal.com/