Fastest data structure for a priority queue

General Usage Performance
1

… 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?
Bad memory, there was already the hint

Will try the timings.
Can we get allocations down?

2

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
3

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

4

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

5

See

6

Yes but you wrote

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

7

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.

8

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

9

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.

10

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

1 Like
11

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.

12

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”

13

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…).

14

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.

15

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
16

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.

17

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.

18

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
19

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.

20

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.