# Fastest data structure for a priority queue

… depends on the number of events to be handled.

I could not use the PQs I’ve seen in Julia because they did not handle multiple identical event times, so took this as an exercise.

My events have the following structure:

``````(time, variable_number_and_types_of_args)
``````

I see two performance limiting factors:

• searching in the times for the insertion point
• storing the events with variable number of arguments

The following works, but can we do better?

``````mutable struct Pqueue
times::Vector{Float16}           # event times
data::Vector{Tuple}              # event data
end
Pqueue() = Pqueue(Float16[], Any[])  # constructor (empty queue)

function push_pq(pq::Pqueue, t, d)
left = searchsortedfirst(pq.times, t)
insert!(pq.times, left, t)
insert!(pq.data, left, d)
end

function pop_pq(pq::Pqueue)
t = popfirst!(pq.times)
d = popfirst!(pq.data)
return (t, d)
end

function testm(m, n)
pq = Pqueue();
for i = 1:n
if randn() > 0
push_pq(pq, i + m*rand(), Tuple(rand()));
else
push_pq(pq, i + m*rand(), (rand(), 2));
end
if i > m
d = pop_pq(pq);
end
end
println(length(pq.times))
end

# run tests varying number of pending events
for m = Int.([5, 5e1, 5e2, 5e3, 5e4])
@time  testm(m, Int(1e6))
end

``````

For example, how to use a single array of struct?

Will try the timings.
Can we get allocations down?

Can’t you use the `PriorityQueue` type from DataStructures.jl, and then just use `(time,counter)` as the key, where `counter` is a unique id (e.g. a counter incremented for each event)? Because Julia uses lexicographical order for tuples, this should do what you want, I think?

1 Like

Thanks, yes, possible. I prefer to have a principled solution, as usually a decent PQ has.

What do you mean with “multiple identical event times” how does PriorityQueue fail for that??

See

Yes but you wrote

which I read as non-uniqueness of priorities and not non-uniqueness of keys.

In my application event times are used as keys to determine their priority, I must schedule a series of events to happen at the same time in the future.

I think you are mixing up the terminology (keys, priority). Or me. But scheduling different events to happen at the same time seems to be no problem with PriorityQueue

The application is similar to simulation of logic gate circuits with delays.
PriorityQueue is dictionary or hash based if I understand correctly. A dictionary works with unique keys.
Storing and launching a set of events with one key is of course no problem.
But this set can have its origin from different sources at different previous time points.
You would need additional infrastructure to merge these events.
Everything is possible, but usually events are kept individually.

Don’t you want a sorted multi dict from data structures.jl?

1 Like

Interesting find, thanks!

While `SortedMultiDict` provides for “infrastructure” to handle multiple priorities (now I see my previous confused wording, thx @mschauer) for a single key, it shares the other limitation of the whole DataStructure family:

The keys must be of the same type as one another; the values must also be of one type.

I need to handle arbitrary data/values/priorities, as does my code above.

Generally for these kind of “collection” type data structures, the keys (i.e priorities) need to be of the same type, or at least comparable to each other. For example, It wouldn’t make sense if say you have one key be a string and another key be an array. Arbitrary type values would technically be fine since values are just associated to keys, and not used in the comparison.

If you need your “keys” to be of multiple types, then one approach would be define how you would compare all the values of the different possible types, which might not be very feasible if there are many possible types for your “keys”

I think there is a confusion again, at least for me.
In my priority queue (or generally accepted?), a key is what determines what comes next when you do a pop, according to what you sort: “due times” when an event is to happen. The other part is data or payload. In the DataStructure doc this part is also called priorities for “due tasks”.

So, my keys are times and all Float64. Data is tuples of variable interpretation, length, and type. A useful data format is for example (fun, args…).

You have Float64 times and yet they collide?

In any case, for a SortedMultiDict you’d just iterate over them and they’d come in order of the time/key and if there are same key they’d come in order of when they were inserted. I don’t see the issue.

The “limitations” you mention are not really limitations. You agree that your keys are all Float64 so they’re “the same type as one another” and the values can all be `Any` if you don’t have a common thing.

This discussion will not go anywhere without sorting out that Priority Queue · DataStructures.jl uses “key”, “value” in the opposite way. So: It doesn’t matter if the times collide for a PriorityQueue from DataStructures. I think I said that.

2 Likes

Thanks @mschauer for this clarification, strange choice.
Here is the test code with DataStructures/PriorityQueue:

``````
using DataStructures

Pqueue() = PriorityQueue{Any, Float16}()

function testm(m, n)
pq = Pqueue();
for i = 1:n
if randn() > 0
#enqueue!(pq, i + m*rand(), Tuple(rand()));
enqueue!(pq, Tuple(rand()), i + m*rand());
else
#enqueue!(pq, i + m*rand(), (rand(), 2));
enqueue!(pq, (rand(), 2), i + m*rand());
end
if i > m
d = dequeue!(pq);
end
end
println(m)
end

# run tests varying number of pending events
for m = Int.([5, 5e1, 5e2, 5e3, 5e4])
@time  testm(m, Int(1e6))
end
``````

and timing

``````5
0.970011 seconds (10.47 M allocations: 306.696 MiB, 6.56% gc time)
50
0.990156 seconds (11.09 M allocations: 314.963 MiB, 5.22% gc time)
500
1.149040 seconds (12.87 M allocations: 350.281 MiB, 5.04% gc time)
5000
1.163019 seconds (13.78 M allocations: 355.716 MiB, 5.32% gc time)
50000
1.340612 seconds (14.23 M allocations: 367.543 MiB, 9.16% gc time)
``````

vs. timing of my code above

``````5
0.298179 seconds (3.51 M allocations: 107.208 MiB, 8.42% gc time, 4.43% compilation time)
50
0.338175 seconds (3.51 M allocations: 107.003 MiB, 9.77% gc time)
500
0.319229 seconds (3.50 M allocations: 106.807 MiB, 5.75% gc time)
5000
0.377245 seconds (3.50 M allocations: 107.121 MiB, 7.56% gc time)
50000
0.794678 seconds (3.50 M allocations: 109.315 MiB, 3.33% gc time)
``````

Interesting. Looks like my sorted list method has (for tcalc = a*m^b) a lower factor a but a higher exponent b, with a break-even point perhaps at m = 1e6 pending events for the hash-based DataStruct pq.

I’ve used heap queues for priority sorting. The python implementation uses a list and a unique indexing pattern under the hood. I’m not familiar with the implementation, but it is indeed performant. I suspect a similar pattern would work well in Julia.

Thanks @carl-aa. I looked at the theory part (not the implementation), looks like an ordinary binary heap.
prioqueue.pdf (wm.edu) pp25 ranks the binary heap among the slowest implementations. It quickly finds the next event in O(log(n)), but then loses out on costly operations to rebalance the tree.

For me it boils down to (anyone disagreeing, please speak up or provide improvements)

• According to the paper, for less than 10 pending events, a simple unsorted list beats them all. My simplistic view: for a binary search in an ordered list, log2(10) is already larger than 3, multiply with search index calculation including division takes about the same effort.
• For less than 1e6 pending events, use a sorted-list based PQ and use binary search for insertion. The last point is regularly neglected in textbooks and you end up with O(n) instead of O(log(n)).
• For more events, use a hash-based PQ as in DataStructures.jl
1 Like

If you don’t need to change the times for the entries and only use `enqueue` and `dequeue` you can make your queue a

``````PriorityQueue{Base.RefValue{Any} , Float16}()
``````

and enqueue and dequeue only `Ref{Any}(your_value)`. Then Julia can handle them efficiently until you need to unbox. You could even figure out a `HashedRef` too.

Thanks for the insights. I’m working on a couple algorithms that rely on efficiently maintaining a priority queue, and I’ll have to give your different takes a closer look. I think my use case fits in the 1e6 bucket, so I’ll benchmark the sorted list plus binary insert and see how it compares to `heapq`. Not sure if I have the scale to support something like the hash-bashed PQ. But it’d be fun to see if the implementation would be efficient in Python.