Select Page

What is the event queue design pattern? The event queue behavioral pattern allows you to keep track of work that needs to be done and let some other code actually perform the task.

You get several benefits from the event queue design pattern:

  • Code that has an interesting event doesn’t need to wait for the event to complete. It can just post an event and continue.
  • Normally, events are handled on a first-in, first-out order but your code can change this if needed. The code that’s posting an event doesn’t need to worry about the order.
  • An event queue decouples the sender of events from the handlers and allows each to proceed at their on pace.
  • Event queues can be handled locally by a single object or can be distributed where many different objects use the queue to pull work from.

If you’d like to read the book that describes this pattern along with diagrams and sample code, then you can find Game Programming Patterns at the Resources page.¬†You can find all my favorite books and resources at this page to help you create better software designs.

Listen to the full episode or you can read the full transcript below for more.

Transcript

The basic description says that this pattern stores a collection of either notifications or requests that will be handled in a first-in, first-out order. That’s the description from the book Game Programming Patterns and there’s a couple things I don’t agree with. By the way, if you read the book and compare it with my thoughts, you’ll gain even more insight. There are many things that I don’t explain from the book and things like this where I’ll recommend something different.

First is the request part. An event queue isn’t a good choice of a pattern if you need to make a request. Usually, requests imply that you expect a reply. If your requests don’t need a reply, then okay, they might fit with this pattern.

The second is the part about fist-in, first-out. This is usually called FIFO. Think of a line. I mean the kind where you wait in a line. Let’s say you’re at the post office and all the clerks are busy but nobody is waiting yet. You get in line and you’re the first in the line. While you’re waiting, another person arrives and gets in line after you. When a clerk becomes available at this time, who’s turn is it? Since you were the first in line, it’s your turn. This is a FIFO, or first-in, first-out.

You probably wouldn’t be very happy if the line obeyed last-in, first out rules. If that was the case, you’d be stuck in that line all day as long as somebody else kept on arriving. Note that this is not cutting in line. That only happens in real life. Computers are normally too polite for stuff like that.

But last-in, first-out queues are common in programming. They can also be called first-in, last out. It means the same thing, really.

The reason I disagree about the order of the processing is because you could have an event queue that obeys either order. Or maybe even a hybrid where normally events are processed on a first-come, first-served approach while some events only get processed when the queue is empty.

Alright, enough of the rambling. I haven’t even explained what this pattern is about yet and here I am discussing the finer points of queue orders.

Imagine you work as a secretary for a busy manager and the manager walks over with a couple tasks that you need to perform. What does the manager do after letting you know about the tasks? Well, a smart manager will write each task separately on paper, or in separate emails, or in individual work orders however that sort of thing is tracked. Then after making sure you know about the tasks, the manager will continue with other things. In other words, the manager lines up the work you need to do. If another task comes along while you’re still working on the first one, then the new task gets recorded the same way.

This is an event queue.

The old way of dealing with this before computers was for each person to have an in box and an out box on their desks.

Or the company could have a more centralized in box where employees could pull work items from whenever needed. Whether the system is centralized or distributed, it’s still an event queue.

Without this system, an inefficient manager would have to wait for you to complete both tasks before leaving to do other work.

I’ll give you a common example of how computers use an event queue and explain how you can implement an event queue right after this message from our sponsor.

( Message from Sponsor )

Back when computers could only do one thing at a time and run only one application at a time, there wasn’t as much need for event queues. The running application had full control over the computer. But think about how things happen today. You have a computer with a single keyboard and many different applications running at the same time. When you type, instead of the application asking the keyboard for the keys that were pressed, the operating system takes care of this and makes sure to send the keys to whichever application is currently in focus. If you click on another window with the mouse and cause that window to move to the foreground, then keyboard activity will start getting routed to that application instead.

The way this works is the operating system posts an event each time a key is pressed. It’s actually a little more complicated because there’s separate key-down, key-up, and key-pressed events.

An application is usually waiting for events like this to arrive so it can do something with them. After processing one key press, it goes back to waiting for another event. And if several events arrive quickly before the application can process them all, then the extra events get put in a queue so they won’t get forgotten or lost.

Episode 77 describes the observer design pattern and a lot of people compare this event queue pattern with the observer. To me, they’re very different patterns. Here’s why. In the observer pattern, you have to explicitly request to be notified of something. And objects that can be observed continue on as normal whether they’re being observed or not. If no other code is observing an object when something interesting happens, then the notification of that event goes nowhere.

This pattern is not intended to watch other code but to set up a place where work can be added with the confidence that it’ll be attended to soon.

This does bring up another interesting difference. The observer pattern doesn’t just notify the observing code that something happened. It calls into each observer right away. The observer code usually gets a simple message that something changed and must make other calls to figure out what happened. This works because the observer gets involved immediately.

But because an event queue is designed more around doing the work at some later point, then when your code finally starts working on the event, it may not be able to make the same calls to figure out what happened. Things could have changed. You can’t rely on the current state of the computer to tell you what was happening when the event was originally placed in the queue. Because of this, events placed in event queues tend to have relevant other information placed in the queue with them.

Think of how the operating system sends events from the keyboard. When it sends an event that the letter ‘A’ was pressed, it also needs to include the state of the special keys, Shift, Control, Alt, Command, etc. It has to do this because when your application finally gets around to processing that key press, the state of the special keys may not be the same anymore.

Another design pattern sometimes compared with this one is the command pattern. The command pattern is also used to turn a command into an object that can get passed around to some other code and executed at a later time.

You can use the command pattern with an event queue if you want but they are different.

Commands are things that represent something that needs to be done. But an event queue can hold other events that might be important or might even be ignored. It’s up to you to decide how your code will respond to an event in an event queue.

When you want to implement an event queue, you’ll need methods like addEvent, removeEvent, and maybe peekEvent. Any code that wants to post new events just calls addEvent. And usually only your code that processes events needs to call removeEvent or peekEvent. This code will normally have a loop that runs for as long as you need to process events and just keeps removing and processing events. The peekEvent is useful when you want to either see what’s next or check if there’s any event at all waiting to be removed.

You might want to use a data structure called a ring buffer to hold events.

This structure is like an array that has a fixed size only instead of always treating the first memory location as the first item, a ring buffer keeps indexes of the first and last items. You don’t need this complexity in real life because when you’re waiting in line and it’s your turn, you walk up to the counter and everybody else moves forward. That moving forward part is what computers try to avoid. So when your code places an object such as an event in a ring buffer, it doesn’t need to move. It just stays in the same memory location. What moves instead is the concept of which item is first. It works sort of like this.

Let’s say you walk into a new post office that has seats for everybody to sit down instead of standing for an hour or more. If you’re the first in line, then you get a sign to hold. And the last person in line also gets a sign. Now, when you arrive, you don’t just sit anywhere. You go to the person holding the last sign, take that sign because you’re now the last person and sit down next to the person who used to hold the last sign. If there are no more seats, because the seats are not arranged in a circle but in a line, and the person who was holding the last sign is sitting in the last seat, then you still take the last sign and instead go sit at the front in the first seat. Just because you’re sitting in the first seat doesn’t mean it’s your turn next. Remember, you’re still holding the last sign. And you’ll continue holding the last sign until somebody else comes along to take it from you and then that person will sit next to you.

Now, whenever a clerk becomes available, the person who gets up will be the one holding the first sign. Before walking to the clerk, the first person will hand the first sign to whoever is sitting next to them. The pattern continues and the first and last signs each move through the seats without anybody needing to scoot over each time somebody is served.

It’s possible for this structure to run out of room and you’ll need to be careful. If you do need to allocate a bigger array, then, yes, you’ll need to move events to the bigger array.

There are usually classes that you can use to implement a ring buffer already. If not and you need to write one, then the scenario that I described about the shifting signs in the post office is actually fairly similar to how it would be implemented in code.

I mentioned earlier about hybrid event queues.

This is how Windows manages paint events.

If you don’t know what a paint event is, it has nothing to do with latex house paint.

This is the event that’s sent to an application whenever the application needs to redraw its window. Let’s say that Windows adhered to a strict first-in, first-out event queue. Your application gets a message that the ‘A’ key was just pressed so it adds the letter ‘A’ to the display. This means the window needs to draw the letter ‘A’. So you get a paint event and update the screen with the letter ‘A’. Then the letter ‘B’ is pressed. And you again have to paint the window. Normally, this isn’t exactly what happens because even the fastest typist can’t keep up with the speed that applications can process events. I just used key presses as a simple example.

But there are many other events that can arrive in rapid succession. If each one of these events caused the application to repaint the window, then things would slow down.

So instead, what Windows does is hold the paint event until there’s no other events in the queue. Then when the application goes to get the next event, that’s when it gets the paint event. Sure, it’s possible that yet another event gets posted to the queue right after that which also needs some drawing. But there’s only so much the operating system can do. Computers haven’t yet figured out how to predict the future.