When your program is decomposed in a series of callbacks, which are called in response to external events, we are talking about event-driven programming (EDP). Many events are essentially asynchronous meaning that we have to use multi-threading to tackle them. Multi-threading assumes that common data structures should be synchronized, and we are off into a wonderful but complex world of synchronization primitives, specialized algorithms, and so on. But what is the most common case for EDP? GUI.
By necessity GUI are driven by external events generated by mouse, keyboard, the windowing system, and so on. “It would be too much to force stupid programmers to use synchronization primitives for simple dialog boxes” — thought ancient vendors. The main purpose of GUI is to reflect changes in graphical form, but usually an end-user has one display, and one video card — the output device requires your graphics code to be serialized too. “We have to do something!” — decided vendors. And they did. So the concept of a message pump was born.
The concept is simple, yet it solves many problems associated with the asynchronous nature of events. Let’s assume that our application has a “main” or dedicated thread, which is called the GUI thread. This thread has an associated message queue. All coming events for our application are converted into messages and placed into the queue. The queue itself is a synchronized structure with a serialized access, so it really doesn’t matter that actual events are asynchronous and can come simultaneously. The message contains enough information to classify the event (e.g., a mouse move event), extract possible parameters (e.g., coordinates), and even some bookkeeping information (e.g., a timestamp of the event). The GUI thread checks the queue for new events and dispatch them to be processed by registered entities (callbacks, event handlers, actions). If the queue is empty the GUI thread can trigger a special “idle” pseudo-event, which can be used for some non-essential tasks, like an eye-candy animation.
As you can see this schema solves a lot of problems and it doesn’t require multi-threading with its complexity. What is the trade-off? In order to support the illusion that events are processed as soon as they come, all event processing code should be quick. Otherwise it’ll lead to unresponsive programs, the potential message queue overflow, and unprocessed events. What if we do need to launch some massive computations? It is easy: delegate them to the worker thread, which will run with the lower priority than the GUI thread (to keep our app responsive), and which will send us messages about its progress and when it is done.
Let’s sum the EDP up: there is an external complex system, which produces some useful events. We create our program as a set of callbacks to process the events we are interested in. The workflow is essentially controlled by external means. Obviously our program can be as rich/restricted as the set of exposed events. We keep all event processing small and quick to support the illusion of multi-threading.
What I described above is how GUI applications work in Windows (details.aspx)), X (see detail here and here), and MacOS (details), so it covers pretty much all operating systems. There are many toolkits that put OOP face on EDP like MFC (details), ATL, Qt, GTK+, and so on. Read the references to get the gory details. Some of them I’ll mention below.
In reality the message pump is more complex than that. For example low-level events can be processed and replaced with high-level events (e.g., converting two subsequent mouse clicks into a double click), the queue itself can implement a sophisticated priority mechanism for different classes of messages, some messages can be collapsed into a smaller number of messages, some synthetic messages can be generated from existing messages, and so on.
What if we want to add some additional event to our system? It is easy: we convert it into a message, put it in the queue, and voila. Now we should watch for our custom message and process it when it is found.
What kind of events are there? We already mentioned mouse events, keyboard events, and some system events. There are two more important classes of events: expose events (when the system notifies that part of a window needs repainting), and timer events. What is so special about them? Let me count the ways:
- On Windows expose events (WM_PAINT) and timer events (WM_TIMER) are of low priority. They can be extracted only if there are no other events in the queue. For example, the timer event is not going to be processed until all mouse move events are processed (and they can keep coming).
- Both Windows and X can collapse several expose events into one by combining their damage areas.
- X can skip subsequent mouse move events, and enter/leave events.
But where is the message loop? It is hidden from us by the browser. We cannot access it. It means that we cannot use any technique available to regular GUI applications:
- We cannot pre-process events.
- We cannot modify the message pump with custom code. No “idle” event processing is possible.
- We cannot post custom messages to ourselves through the message loop.
And because we don’t have worker threads, we cannot play nice with messages when we have heavy processing tasks.
More than that: we have only a small slice of the message loop. All expose events are processed by the browser, and we don’t see them. That’s right, all repainting is done by the browser itself. It is good, right? Yes, to a degree. In fact it takes time, which is proportional to the complexity of the picture, and the complexity is controlled by us, but we cannot optimize the process. Let’s take a simple example: imagine that we just moved a dialog box (an absolutely positioned rectangular island of DOM nodes) 1 inch to the right. Browser will regenerate 1 inch of background on the left (whatever was hidden under the dialog box), and it will redraw the dialog in the new place. It will not deduce that the simple rectangular copy of the dialog picture is enough due to multiple internal reasons. Both repaints are going to be proportional to the repainted area and the complexity of data describing those areas, and we cannot control them. Is it bad? If complexity of the picture is high, the repainting can take a long time causing the message queue overflow and some key events can be lost.
There is a common idiom that if we want to “schedule” some code until the idle time, we just set a timer for 0ms to execute the code. Timer events are passed through the message queue and in effect they will be extracted and processed when all other pending messages are processed. That’s how it looks:
The thinking goes like that: “The timer code can see that I use 0 so no delay is expected. Instead of executing the full-blown delay the timer just posts a proper message in the message queue effectively scheduling my code to the earliest possible execution. Some people are telling me that timers have problems, but by using 0ms delay I eliminate all possible nastiness associated with timers — because there is no timer involved! — gaining the benefit of accessing the message queue emulating custom messages I can use for my advantage.”
Another common idiom comes from the internal/programmatic event processing domain (e.g., from aspect-oriented programming). In some cases a programmer has an access to the start event in some calculations she is interested in, but she wants to wait until the processing of the event is finished to do something. If there is no finish event, the programmer can record all relevant parameters on the start event, and “schedule” the code for later execution, when the event is already processed. It is done using the same “setTimeout(myCode, 0)” idiom.
Personally I classify these idioms as “stupid tricks” and try to avoid them. But I am guilty as any of using them. Read on.
While this code may work as a replacement for specific message pump techniques, it comes at a price. Obviously it costs some time to create a timer, but it is not the main problem. As you saw above the fact that the timer events are serialized by the message queue introduces an indeterminable delay, because there is no time guarantee on the message processing. And browsers themselves can delay processing to run some other tasks ranging from repainting the window in response to expose events to running a garbage collector. See data collected by John Resig (#1 and #2).
Another problem is the timer resolution, which may cause the quantization of timeouts rounding up or down requested times to available time quanta. For example on Windows the regular timer can have a resolution of 10-25ms, which is a big improvement over the Windows 9X kernel. And so-called high resolution timer can go down to 1ms depending on hardware. Usually browsers use what’s available and expose to us regular timers, so we will have some error in our timeouts. It is ok, if our timeouts are in seconds. If we want to measure 10s and the error was 10ms, the mistake is only 0.1% — pretty darn good, if you ask me. On the other hand, if we asked for 1ms, and the result was 10ms — we have a problem. If a timer uses some minimal timeout to approximate all small timeouts — we have a big problem.
Unfortunately this is the case.
I ran this code on different browsers and different operating systems and it turned out that all of them have the minimal timeout time. Setting the timeout time lower than that value doesn’t reduce the timeout. The minimal values are:
|Ubuntu 7.10 Linux||Firefox 18.104.22.168||10ms|
|Opera 9.50 Alpha||11ms|
|Windows XP SP2||Internet Explorer 6||16ms|
|Internet Explorer 7||16ms|
|Internet Explorer 8||16ms|
|Opera 9.50 beta||15ms|
|Mac OS X 10.5.2||Safari 3.0.4||10ms|
How do I know that this is a timeout? It doesn’t consume CPU cycles while waiting.
As you can see from the table the minimal timeout depends on OS — ~10ms for Linux and MacOS X, and ~15ms for Windows XP. The notable exception was Firefox 3 on Windows XP, which uses 10ms as the minimal timeout. Most probably it changes the timer’s resolution.
To sum it up: “0ms timeout” triggers the minimal timeout, which is 10-15ms depending on OS and browser. Using 0ms incurs substantial penalty, which is the most obvious when you use “0ms timeout” repeatedly — instead of the “scheduling” effect you are getting an artificially reduced fire rate, when your “timeout” code fires 60-100 times per second even if it is capable to fire much faster. If we are talking about some animation task it is equivalent to limiting the number of frames per second (FPS).
- Try to keep your event handlers quick.
- Try to reduce the visual complexity of things you want to animate.
- Do not rely on timers being exact.
- Be very careful when using “0ms timeout” idioms — the timeout is not 0, and it can be detrimental for your problem.
- Always consider the potential of accumulating “0ms timeouts” into something bigger, especially when doing some task repeatedly.
- Do not count on “0ms timeout” being a constant value across different OS and browsers.
- Try to avoid “stupid tricks” — usually their use is a good indicator that something is wrong with your code.