But then we ran into problems when we started posting 10,000 messages per second


Once upon a time, a long, long time ago, there was a research team inside Microsoft who was working on alternate models for handling input. I don’t know what eventually came of that project, and I don’t even remember the details of the meeting, but I do remember the punch line, so I’m just going to make up the rest.

The research project broke up the duties of their system into a few components. The two that are important to the story are a driver component which received information from various hardware devices and transmitted that information via the PostMessage function to another component whose job it was to study those input messages and route them to the appropriate application. (In 16-bit Windows, the PostMessage function was specifically written so it could be called from device drivers during hardware interrupts.) Each time the driver received information from a hardware device, it posted a message to its helper program.

Everything seemed to go reasonably smoothly. The device driver received a hardware event, it posted a message to the helper program, and the helper program retrieved the message and processed it. But once they cranked up the hardware devices to produce information at a higher rate (and therefore produced input with much finer resolution), the events started coming in faster and faster, and their design started to collapse under the pressure.

The research team asked to meet with the user interface team to help work out their problems under load. They outlined their design and explained that it worked well at low data rates, “but then we ran onto problems when we started posting 10,000 messages per second.”

At that point, the heads of all the user interface people just sat there and boggled for a few seconds.

“That’s like saying your Toyota Camry has stability problems once you get over 500 miles per hour.”

If you’re going to be pumping huge quantities of data through the message queue, creating a separate message for each one is crazy. Think about it: Suppose you’re posting 10,000 messages per second. The thread whose job it is to process the messages gets pre-empted and doesn’t run for 50 milliseconds. That’s 500 messages behind schedule already. Now suppose it takes a dozen page faults (which take 8ms each, say). Now you’re another 1000 messages behind. Windows NT sets an arbitrary limit of 10,000 unprocessed messages in a message queue so that a runaway program won’t drain the desktop heap and roach everything. A few hiccups in your process will quickly send you over that limit.

For this usage pattern, you want to switch from one event per message to a signal on the transition (or edge triggering).

When the first event occurs, post a single message to the helper program saying there is work to do and set a flag saying helper window has been notified. Meanwhile, stash the information you would have included in the message into a privately-managed queue. If an event arrives when the helper window has been notified flag is set, then don’t post a message; just append the work item to the queue. When the helper window receives the there is work to do message, it calls back into the driver to say Okay, give me some work to do. After it does the work, it calls into the driver to say Okay, what else do you want me to do? (Alternatively, you can have the helper window grab the entire work list at once.) When the helper window asks for work to do and comes back empty-handed, then clear the helper window has been notified flag so the next time an event occurs, a new message will be posted to kick-start the helper window.

Commenter Hayden proposed a number of other mechanisms. The send a list of work items rather than just one technique works well if you know when the list of work items is complete and therefore is ready to send. The second technique is the one I described here; it works well if the producer doesn’t really know when each chunk of incoming work is finished, or if the work that comes in is continuous. The third mechanism merely avoids the message queue altogether and uses a semaphore instead.

The point is not to try to drive your Camry at 500 miles per hour. Find a way to get your work done while keeping the Camry well within its design parameters, or look for a different vehicle.

Comments (4)
  1. Spike says:

    Wow, deja vu here.  I once had a problem with my Honda Del Sol that the engine would hesitate and stutter if I drove at over 130mph for more than two hours continuously.

    The garage could never reproduce the problem and when I told them exactly how to reproduce it they said "Don’t do that."

  2. Keith says:

    So, what you are saying is NOT to use windows? :)

    is Linux an appropriate new vehicle? :)

    what do you suggest? :)

  3. Worf says:

    Wow, these are the days before SetEvent, I’m guessing.

    Create a manually-reset event, and helper app WaitOnSingle/MultipleObject(s) on it. First thing it does after a normal wait is reset the event (arm it so it can receive a new one – this may mean it does a useless loop at the end), then process the queue. Once queue is empty, wait again.

    The interrupt stashes data into the queue, then signals. (if it’s signalled already, SetEvent does nothing).

    The reason for the immediate reset is to avoid a race where you finish processing, but before you reset the event, another event gets in (and is lost).

    Then again, one realizes that auto-reset events work too, since the event does reset until one thread was released. (To release all threads then reset, PulseEvent is your friend).

    Yeah, I guess I’d be lost on 16-bit Windows.

  4. Xepol says:

    Of course, in the 16 bit days, it was pretty easy to overwhelm a system with IO to the point that there was insufficent overhead to process the data.

    One has to wonder how much processing those 10,000 samples a minute actually required and whether that would be the straw that broke the camel’s back no matter what hand off was attemtped.

    To futher your analogy, you can drive slower and make fewer trips by carrying more per trip, but don’t try to move a 10 ton loads with that Camry no matter how slow you go.

Comments are closed.