So, I have several asynchronous entities that produce timestamped events.

Another entity receives these and can create their own events. And insert them into its own event queue.

A problem I’m running into is what’s the best way to process events in sorted order? I’m currently using a big ol heap but really don’t like the access patterns... idk if the data access patterns matter a whole lot as each event can be expensive to process.

how do you keep your events sorted? What’s the best way to insert new ones and Process them in order

Hi, faced the problem modeling electronic logic circuits, so necessitating strict ordering to respect the causality principle.

The best performance I could obtain was with a simple doubly-linked list (with pooled nodes) hosted in a unique "simulator" entity, known to all components in the circuit.

The list is kept ordered by the "simulator" at event insertion:
from head (= most recent) iterate and insert after node with nodeEventTime <= insertedEventTime

Similarly events are consumed in the list order at each frame, while eventTime <= gameTime.
Firing an event might produce new ones, resulting in calling the insertion process again: in that case beware of zero-delay loops!

For consistency inserting an event with eventTime < gameTime is always an error and should trigger the related management procedures (exception in my case).

Other issue: sometimes consuming an event makes a component "change its mind" somewhere. That is it had already emitted an action that was stored for future firing, but needs to update its output according to the new global state. In that case simply remove its formerly planned response and insert the updated one (also the removal is easy with the doubly-linked list).

Hope that helps in your context!

Sounds like a situation where a hashing scheme could work. e.g. have 1 unsorted bucket/array for all events where the time is from 0.0 to 1.0, 1 unsorted bucket where the times are from 1.0 to 2.0, etc. That gives you O(1) append performance, and while the find-min operation is technically O(N) it would operate on a small and cache-coherent block of data.

But a real answer will depend on how large these queues typically get - if it's something like 5 to 10 events then none of this matters.

Hi All.

Thanks for the feedback.

Events ten to come in a flurry of activity and I believe they can get quite large in a small amount of time.
I have not yet measured how large the event queue can get for processing. The idea of bucketing events so sorts will stay on a small element size is very appealing. The only problem here is there can be large variation between event times so I could end up wasting alot of space. A problem is the events don't necessarily come at regular intervals which makes it hard to decide a deltaTime that each bucket would cover.

Linked list seems nice, but then the computer won't really be able to prefetch because the memory will not be contiguous.

A great point you bring up is that I need a better understanding of the event distribution in order to select the best data structure. Right now anything can create an event at anytime and the often come in a big flurry. Which is then followed by periods of relatively less activity.

Knowing the typical arrival pattern is indeed crucial.

If you generally create events in increasing time order, even a simple bubble sort works. 90+% then simply gets appended, with a few doing a relatively small number of iterations to find their right spot. Note that bubble sort is very memory-friendly in its access, so it's less slow nowadays than it used to be.

A mix is also possible. If the event is newer append, else find the right spot using bisection.

Quote

Linked list seems nice, but then the computer won't really be able to prefetch because the memory will not be contiguous.

I'm always pre-allocating the list's nodes (reuse pool based on a stack) if that may help. I don't pay specific attention to cache related issues to be honest, in my case it's to avoid the double performance hit of creating new objects and garbage-collecting them (.NET C#).

Another pattern I've used in some situations is two pools; the sorted long-term pool and the unsorted "new item" pool.  Traversing the very large long-term pool uses one access pattern, traversing the small unsorted "new item" pool uses a different access pattern.

You must use actual measurements to determine when it becomes faster to sort the small pool into the big pool.  For example, perhaps when the small pool reaches 4000 items it becomes faster to swap them around.

Also, as you mention cache issues, many people are surprised to discover that simple linear scans of large data sets are faster than complex algorithms.  While the fancy algorithms may perform orders of magnitude less work, because they are constantly jumping around in memory they suffer from severe memory latency issues; while a simple linear scan may scan thousands of elements, it is using the CPU in the ideal form and can approach the theoretical limits of performance.  5 billion CPU cycles per second with 14 micro-operations per cycle at peak operation allows for processing incredible amounts of data quite quickly.

Generally linear processing works best until you reach several thousand items. Then it is time to turn on your engineer brain.

1 hour ago, frob said:

many people are surprised to discover that simple linear scans of large data sets are faster than complex algorithms

I was in that very case!