# Fastest data structure for a priority queue

**URL:** <https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472>\
**Category:** Performance\
**Tags:** data\_structures\
**Created:** [September 20, 2021, 3:25pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472 "2021-09-20T15:25:40Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 20, 2021, 3:25pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/1 "2021-09-20T15:25:40Z")

</div>

… 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:

```julia
(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?

```julia
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

> [@Create an empty array, then insert (Priority Queue)](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/5):
>
> You can use a `Vector{Any}` which can hold any kind of object.

Will try the timings.  
Can we get allocations down?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 20, 2021, 3:44pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/2 "2021-09-20T15:44:48Z")

</div>

> [@Bardo](#):
>
> 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.

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?

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 20, 2021, 3:50pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/3 "2021-09-20T15:50:51Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 20, 2021, 4:06pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/4 "2021-09-20T16:06:39Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 20, 2021, 4:15pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/5 "2021-09-20T16:15:55Z")

</div>

See

> [@Create an empty array, then insert (Priority Queue)](https://discourse.julialang.org/t/create-an-empty-array-then-insert-priority-queue/63425/6):
>
> [http://juliacollections.github.io/DataStructures.jl/v0.11/priority-queue.html](http://juliacollections.github.io/DataStructures.jl/v0.11/priority-queue.html)
> 
> It requires unique priority keys, however (which is a bit annoying to be honest).

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 20, 2021, 4:18pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/6 "2021-09-20T16:18:23Z")

</div>

Yes but you wrote

> [@mschauer](#):
>
> multiple identical event times

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

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 20, 2021, 4:39pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/7 "2021-09-20T16:39:50Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 20, 2021, 6:38pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/8 "2021-09-20T18:38:11Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 20, 2021, 6:59pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/9 "2021-09-20T18:59:37Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [September 21, 2021, 12:11pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/10 "2021-09-21T12:11:23Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 21, 2021, 12:40pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/11 "2021-09-21T12:40:06Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![SL6Trip](https://avatars.discourse-cdn.com/v4/letter/s/4da419/32.png) [@SL6Trip](https://discourse.julialang.org/u/SL6Trip)\
**Post date:** [September 21, 2021, 3:15pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/12 "2021-09-21T15:15:20Z")

</div>

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”

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 21, 2021, 3:33pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/13 "2021-09-21T15:33:33Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [September 21, 2021, 5:15pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/14 "2021-09-21T17:15:01Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 21, 2021, 6:24pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/15 "2021-09-21T18:24:32Z")

</div>

This discussion will not go anywhere without sorting out that [Priority Queue · DataStructures.jl](http://juliacollections.github.io/DataStructures.jl/v0.11/priority-queue.html) 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.

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 21, 2021, 9:16pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/16 "2021-09-21T21:16:28Z")

</div>

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

```julia

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

```julia
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

```julia
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.

---

<div class="post-metadata">

**Author:** ![carl-aa](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carl-aa/32/28089_2.png) [@carl-aa](https://discourse.julialang.org/u/carl-aa)\
**Post date:** [September 23, 2021, 10:24pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/17 "2021-09-23T22:24:45Z")

</div>

I’ve used heap queues for priority sorting. The [python implementation](https://docs.python.org/3/library/heapq.html) 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.

---

<div class="post-metadata">

**Author:** ![Bardo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bardo/32/21601_2.png) [@Bardo](https://discourse.julialang.org/u/Bardo)\
**Post date:** [September 24, 2021, 11:18am UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/18 "2021-09-24T11:18:27Z")

</div>

Thanks @carl-aa. I looked at the theory part (not the implementation), looks like an ordinary binary heap.  
[prioqueue.pdf (wm.edu)](https://www.cs.wm.edu/~andreas/umsa/presentations/prioqueue.pdf) 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

---

<div class="post-metadata">

**Author:** ![mschauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mschauer/32/13946_2.png) [@mschauer](https://discourse.julialang.org/u/mschauer)\
**Post date:** [September 24, 2021, 3:50pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/19 "2021-09-24T15:50:38Z")

</div>

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

```julia
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.

---

<div class="post-metadata">

**Author:** ![carl-aa](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carl-aa/32/28089_2.png) [@carl-aa](https://discourse.julialang.org/u/carl-aa)\
**Post date:** [September 24, 2021, 4:52pm UTC](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472/20 "2021-09-24T16:52:28Z")

</div>

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.

[Next page](https://discourse.julialang.org/t/fastest-data-structure-for-a-priority-queue/68472.md?page=2)