http://GameProgrammer.Com

Programming

GP Mailing List
     Thread Index
     Date Index

ATXGPSIG List
     Thread Index
     Date Index

Google
>

Home

Wise2Food


Fast Event Processing in SDL

Bob Pendleton


Download Source in .tar.gz
Download Source in .zip
    Download Test Programs:
             thread1.c
             thread2.c
             thread3.c
             thread4.c
Part2: Fast Event Library Documentation


I've been spending a lot of time testing and playing with SDL (Simple DirectMedia Layer). To say the least, SDL has made me a very happy camper. Most of the time it simply works. If I had one complaint about SDL it would be with the documentation. But, since I have the source code I can always UTSL (Use The Source Luke) and find out exactly what it really does under the covers. That is one of the biggest advantages of using Open Source software, you have access to the source if you need it.

When I test a library like SDL I like to find a project that will let me do the testing I want to do and maybe get something useful as a result of the work. I was looking for a project that would test the SDL thread and network APIs so I decided to build a threaded network IO handler that would just sit off to the side of a game and send events when a TCP connection was made or closed, when data was available on a connection or when a UDP message arrived. That would let me handle the network the same way I handle the keyboard or mouse and it seems to me like a very natural way to handle network IO in an interactive program of any kind, and it is especially good for games where players are connected over a network.

I started out by testing the event handling system in SDL. If you are going to use events to handle network connections the event handling system must be reliable and be able to handle the volume of network events that a game is going to generate. So, the first piece of code I wrote was designed to stress test the event system. The code uses two threads. One thread generates events as fast as it can and the other thread reads them as fast as it can.

Stressing a system will often find flaws that you won't find any other way. The first time I ran the stress test it reported that it was handling an astounding number of events/second. I thought the event system could handle the job. Then I noticed that it ran so fast because my events were being lost. The fastest way to do something is to not do it at all. Reading the code I found that SDL_PushEvent() returns 0 (zero) if the event queue is full and doesn't push the event. The documentation says it returns 0 when the event is pushed and -1 when it isn't. Cool. [This problem was corrected in the 1.2.5 release of SDL. In all later versions the code works as documented] After debugging that and complaining about it on the SDL mailing list I went on to write some real tests of the SDL event processing system.

Since SDL_PushEvent() will just drop events when the queue is full the first question I had to answer is how to wait for the event queue to not be full? You don't have to wait for it to be empty, just not full. I looked through the documentation, and since SDL_PushEvent() is documented as being thread safe it would seem like there should be a way for a thread to wait for the queue to empty out. If it is there I didn't find it in the documentation or the code. I looked at SDL_WaitEvent() to see how it waits for events to show up. It seemed reasonable to me to use a similar method to wait for the queue to empty out.

Digging through the SDL_WaitEvent() code is when I got my nose rubbed in the fact that SDL is designed to work on operating systems that do not support threads. SDL_WaitEvent waits for events to arrive in the queue the simplest way possible, it uses SDL_Delay() to wait for 10 milliseconds and then checks to see if there are any events waiting. Checking the queue 100 times per second and possibly polling tor input events 100 times per second is great for single threaded games and it gives you the same results whether you OS supports threads or not. So, I decide to see what would happen if I used the same technique to wait for the queue to empty. If the queue is full, just wait a while and try again. This approach to the problem is not the one you'll find in text books. But, you don't learn anything by believing everything you read in text books.

I wrote a simple test program that has two threads. One thread is the SDL main thread and it waits for events to be put in the queue and when it gets an event, it just ignores it. The other thread does nothing but try to stuff events into the queue and it waits when the queue is full. The code that waits for the event queue to empty out looks like this:

while (-1 == (val = SDL_PushEvent(&ev)))
{
 SDL_Delay(10);
}

It just sits in a loop pushing events until the queue is full and then it waits for ten milliseconds. If the queue is now empty it pushes more events. If not, it waits a little longer. (Why 10 milliseconds instead of 1? The minimum wait time guaranteed by by SDL is 10 milliseconds. You can tell it to wait for less than 10 milliseconds but there is no guarantee that is will wait for less time.)

Timing tests tell you how fast your test program actually runs. But, they don't tell you that your test program is correct. My first test program ran and gave me a result. But, I knew the result was wrong because it as unreasonably good. Before you trust the results of a test program you need to estimate the performance and then compare the test results with your estimate. If you can't reconcile your estimated performance and the measured performance you have a problem. Either your test program is broken, or your understanding of the system is wrong. In either case you have to keep looking at the problem until the estimated results match the measured results.

To figure out how fast the test should run I looked at the SDL event code and saw that the queue can hold at most 127 items and since SDL_WaitEvent() looks at the queue 100 times per second we know that SDL_WaitEvent() can not remove more than (127 * 100) = 12,700 events/second and you can't push more than 12,700 events into the queue in a second.

When I did short tests, 1 to 10 second long, I got events/second rates ranging from 6000 to just less than 12700. When I ran it for 1,000 seconds I saw a consistent 6350 events/second. If the 10 millisecond wait in my event pushing code and the wait in the SDL_WaitEvent() code were added together to give a 20 millisecond wait we would expect to see a maximum of 6,350 (6,350 = 127 * 100 / 2) events/second being moved through the queue. When I ran the test on a faster machine I got almost exactly 12,700 events per second. On the faster machine the event processing goes fast enough that the two waits overlap, while on the slow machine are executed in sequence. I was able to reconcile the test results with the estimate and so I trust the results.

Being able to handle more than 6,000 events/second is perfectly acceptable for many applications. From the point of view of my event driven network library, 6,000 events/second is great for the client side of a game. But, it isn't so good for a server. Because I would like to use the same library for both the client and the server I wanted to see if I could make this code run a little faster.

The next step was to write my own version of SDL_WaitEvent() and use a semaphore and a condition variable to control access to the event queue. A semaphore is a simple mutual exclusion operator also known as a mutex. A mutex is used by threads to keep more that one thread from touching a variable or running a section of code at the same time. Having more than one thread changing the same data at the same time leads to horrible bugs that are hard to find. In this case I needed a mutex to keep the contents of the queue consistent. A condition variable is just a way for one thread to let other threads know that something has happened. One or more threads can wait on a condition, and when another thread signals that the condition has occurred the waiting threads wake up an go about their business.

I wanted to make as few changes as possible so I wrote a simple replacement routine that does the same things that SDL_WaitEvent() does, but it uses a semaphore to make sure that only one thread is changing the queue at a time, and it also signals the condition variable when it removes an event from the queue so the sending thread can wake up and send more events. The code sending events pushes events into the queue until it is full and then waits on the condition. This way the queue still gets checked 100 times/second, and it ensures that regular SDL events aren't lost. The new event sending code looks like:

SDL_LockMutex(eventLock);
while (-1 = SDL_PushEvent(&ev))
{
SDL_CondWait(eventWait, eventLock);
}
SDL_UnlockMutex(eventLock);

And my WaitEvent code looks like:

int WaitEvent(SDL_Event *ev)
{
int val = 0;
while (0 >=  SDL_PollEvent(ev))
{
SDL_Delay(10);
}
SDL_CondSignal(eventWait);
return val;
}

When I tested this code I found that it consistently handled 12,700 events/second. That result makes sense because the sending thread wakes up soon after an event is removed from the queue. Since the sending code always wakes up shortly after an event is removed from the queue the WaitEvent() code always finds a full queue when it wakes up and it wakes up 100 times/second. This is more than fast enough for client code and fast enough for a lot of server applications.

At this point I was caught by the problem and had to see what happened when I got rid of the delay in WaitEvent(). So I did. I wrote a version of WaitEvent() that returns events until the queue is empty and then waits on a condition variable. And, I wrote a version of my event sending thread that sends events until the queue is full and then waits on a condition variable. My new WaitEvent() signals whenever it takes an event out of the queue and my event pushing code signals whenever it pushes an event into the queue. This approach to the problem gets rid of all the delays but does adds a lot of mutex control overhead. Most operating system work very hard to make mutex operations as fast as possible so using mutexes rarely creates a performance problem.

This way of doing things has one very serious problem. It locks out all of the SDL input events that are generated through SDL_PollEvent(). Even though the SDL_PollEvent() is called by my WaitEvent() code it only gets called if my event pushing code pushes an event. No matter how fast this new version runs it isn't worth anything if it kills the SDL input code. That problem stopped me for a little while until I realized that an SDL timer could be used to broadcast a signal to wake up all waiting threads. So, I set up a timer that fires 100 times per second and wakes up all waiting threads. When I tested that code I found that it got the SDL events and it was able to push over 30,000 events per second from my event pushing thread to the main SDL thread. I believe that the speed I'm seeing is only limited by the speed of my test machine, and not by anything in my code or in SDL.

Being able to process 30,000 events/second means that client code will never be slowed down by my new event processing code and a server is more likely to be slowed down by the speed of disk drives or the network connection than by my event code. If we assume that messages between the client and server are 100 bytes long then 30,000 events/second represents roughly 3 megabytes/second on the network. That limit would not become a concern until you reach the size of a large commercial multi-player game. But, they don't use low end PCs as servers.

Part 2:Fast Event Library Documentation


Copyright © 2002 Robert C. Pendleton. All rights reserved.