Is a priority queue necessary for event simulation?

Question

Right now in my basic event simulation engine, I simply just resort the list of event objects to update by their priorities every step of the simulation. I do this because new events can be created during event updates and are appended to the list and when an event expires, I just "swap and pop" it with the last event in the list for performance. Should I just be using two priority queues instead? It seems like the n log n of sorting every step is at least the same if not less costly than dequeing all the events (n log n?) putting each unexpired one in another list that is built into the priority queue for the next update step.

EDIT: I think it would be more apt to refer to the 'events' as 'processes' instead and the whole thing as more of a process scheduling simulation then. Each object in the queue has it's state updated in priority order and then only if it has expired (entered some sort of conclusion state) does it get discarded and not reinserted into the queue. This is how having just a single priority queue could be a problem; when an object is reinserted, it will still have the lowest priority and would just be pulled out again. I was considering using a second queue to insert all newly spawned process objects and ones that did not expire into, not considering priority, then I could just build heap and swap it with the active queue before the start of the next update cycle.

Roland Ewald · Accepted Answer · 2012-07-12T19:38:34.343

Typically, you should use one event queue in a (sequential) discrete-event simulator. I am not quite sure what you mean with 'expired' events, but if these events shall be ignored because they are not valid anymore, a simple solution would be to just discard them instead of processing them, e.g. see this pseudo Java code:

 while (!terminationConditionMet() && !eventQueue.isEmpty()) {
   Event currentEvent = eventQueue.getNextEvent();
   if(currentEvent.isExpired())
     continue;
   List<Event> newEvents = currentEvent.process();
   eventQueue.addEvents(newEvents); 
 }

Generally (for large enough event sets), this should be much faster than re-sorting the event list after each step.

BTW many event queue implementations achieve a dequeue in O(1), and even though for some operations their worst case performance might not be better than sorting, the actual implementations work much better (i.e. they have smaller constants/better average performance). If you are working with Java, you might want to look at JAMES II, which offers several event queue implementations and is open source (disclaimer: I am one of the devs).

EDIT (addressing re-formulated question):

In general, a convenient way of implementing a process-based discrete-event simulation are coroutines, see for example this report for details. If you want to stick to your implementation, however, you could still change the priority to a tuple (timeStep,processPriority) and use an adapted version of the above pseudo-code as follows:

while (!terminationConditionMet() && !queue.isEmpty()) {

 //Read out event
 Tuple minTime = queue.getMinTime();
 ProcessEvent currentEvent = queue.dequeue();

 //Execute event
 List<ProcessEvent> newlySpawnedProcesses = processEvent.process();

 //Re- and enqueue new events
 int nextTimeStep = minTime.getTime() + 1;
 if(!currentEvent.finalStateReached())
   queue.requeue(currentEvent, new Tuple(nextTimeStep, currentEvent.getPriority())); 
 for(ProcessEvent event : newlySpawnedProcesses)
   queue.enqueue(event, new Tuple(nextTimeStep, event.getPriority()));     
}

Of course, this assumes that you are using an event queue implementation that is generic enough to allow you to specify your own kind of time/priority ordering, e.g. by specifying a custom comparator.

So if an event should be processed again, it itself is the lone item of `newEvents`? Also, could any weirdness arise from adding an event with a lower priority than the current one being processed? In a way it would seem like it would get an extra processing vs. events with higher priorities that were added in the same update cycle. — abr, Jul 10 '12 at 17:04
Yes, any event caused by the processing of the `currentEvent` would be in `newEvents`, and this could include the event itself (although this is rather unusual, as it somewhat breaks the metaphor of `event`, ie. something that simply happens [once] and may lead to new events). If the re-insertion of events happens regularly in your application, you could also retrieve (but not dequeue) the current event and then `requeue` it with a new priority. Some event queues specifically built for simulation offer this operation. This might be much cheaper than enqueueing a new event. — Roland Ewald, Jul 11 '12 at 05:52
Anyhow, beware of _premature optimization_: before you make event scheduling overly complicated, use a profiler to see if this is really a performance bottleneck. Regarding the 'weirdness' of adding lower priority events, this strongly depends on your application. One danger I see is that you could be 'stuck' at a certain priority (time) or even go _backwards_ in time (which, again, breaks the metaphore). Instead, you could think of making your priority two-dimensional, eg. tuples (time,event-priority), and allow rescheduling of lower/higher-priority events at the current time. — Roland Ewald, Jul 11 '12 at 06:00
Ah yes, coroutines. I am basically trying to "fake" coroutines like you might see in Lua in Java. — abr, Jul 12 '12 at 17:11
Ah, I see. Have you had a look at http://stackoverflow.com/questions/2846428/available-coroutine-libraries-in-java and http://stackoverflow.com/questions/2846664/implementing-coroutines-in-java? In any case, good luck with that! — Roland Ewald, Jul 12 '12 at 19:46

Is a priority queue necessary for event simulation?

1 Answers1