# Fast(er) priority queues?

**URL:** <https://discourse.julialang.org/t/fast-er-priority-queues/81269>\
**Category:** Performance\
**Tags:** question\
**Created:** [May 18, 2022, 4:10pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269 "2022-05-18T16:10:21Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 18, 2022, 4:10pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/1 "2022-05-18T16:10:21Z")

</div>

Hi there!  
Recently I wanted to accelerate Dijkstra’s algorithm, and I ended up implementing a really dumb priority queue based on two sorted vectors. Surprisingly, in some settings, it significantly speeds up the algorithm. Would something like that deserve a place in DataStructures.jl?

See [here](https://gdalle.github.io/FastPriorityQueues.jl/dev/) for the rationale and [there](https://gdalle.github.io/FastPriorityQueues.jl/dev/benchmarks/) for the benchmark.

Ping @oxinabox @mschauer @mbesancon

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [May 18, 2022, 4:21pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/2 "2022-05-18T16:21:22Z")

</div>

It would be worth benchmarking this in 1.9 (`Dict` is about 30% faster for a lot of operations), and with `SwissDict` and `RobinDict` from `DataStructures`.

---

<div class="post-metadata">

**Author:** ![suavesito](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/suavesito/32/34386_2.png) [@suavesito](https://discourse.julialang.org/u/suavesito)\
**Post date:** [May 18, 2022, 6:29pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/3 "2022-05-18T18:29:42Z")

</div>

Just a notice, the link in the page of benchmarkings is broken. Is it the same as this “[Priority Queues and Dijkstra’s Algorithm](https://www.cs.utexas.edu/ftp/techreports/tr07-54.pdf)”?

(BTW, nice package. 🙂 )

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [May 18, 2022, 7:54pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/4 "2022-05-18T19:54:44Z")

</div>

I have to point out that I have a package with a faster priority queue for years (as it can be seen in [Priority queue choice - #3 by Henrique\_Becker](https://discourse.julialang.org/t/priority-queue-choice/42783/3)), and it did not make into DataStructures.jl. In general, I do not find very hard to outperform the data structures from `DataStructures.jl`.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 19, 2022, 3:53am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/5 "2022-05-19T03:53:09Z")

</div>

Yes it’s the same, but it is not broken on my browser 🤷

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 19, 2022, 3:56am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/6 "2022-05-19T03:56:10Z")

</div>

Yes indeed, I cite your Discourse discussion with Moritz in my package docs 🙃 Maybe I should include a more explicit reference to your package itself, sorry about that. Until this morning, the distinction between priority queue and heap was not very clear in my mind tbh 😅

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 19, 2022, 3:57am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/7 "2022-05-19T03:57:45Z")

</div>

Did you try to contribute to DataStructures.jl though?

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 19, 2022, 4:00am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/8 "2022-05-19T04:00:07Z")

</div>

Great, I’ll take a look! My implementation is really dumb btw, and I can probably do better, at this point it is really more of a POC.  
In fact, I’m not even sure that it deserves to go into DataStructures.jl: maybe the performance gap tells us more about Dijkstra than it does about priority queues

---

<div class="post-metadata">

**Author:** ![suavesito](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/suavesito/32/34386_2.png) [@suavesito](https://discourse.julialang.org/u/suavesito)\
**Post date:** [May 19, 2022, 4:06am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/9 "2022-05-19T04:06:28Z")

</div>

Don’t pay attention, look like it was temporal. It works now. 😅

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [May 20, 2022, 12:28am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/10 "2022-05-20T00:28:55Z")

</div>

I do remember some brief discussion with @oxinabox, but they have a very similar datastructure (their mutable binary heap). My heap has some extra functionality (it is k-ary with the arity coded in type space by means of a type parameter, for example) but I think it deviated a little from what is expected from `DataStructures.jl`, as they have more than a heap type and try to have all of them to share a similar interface.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 20, 2022, 4:47am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/11 "2022-05-20T04:47:06Z")

</div>

I’ll benchmark against their heaps as well if I have time. What stopped me sofar is that the API is slightly different (no `enqueue!` or `dequeue!` function) but I can specialize Dijkstra to work with that

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [May 20, 2022, 11:05am UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/12 "2022-05-20T11:05:55Z")

</div>

A few gotchas:  
`no_priority_updates` makes no sense for `PriorityQueue`, because it can’t have a duplicate key. The error is not triggered in the unweighted version because a the heuristic distance of a vertex is never re-updated, as the first check always correspond to the shortest. I removed it.

Benchmarking with unweighted graph is suspicious. As said above, it cause the distance to never be re-updated. Also, the priority queue will always hold only to different weights: the one of the vertex being evaluated, and this value + 1, which may not be very representative of the use case of a priority queue. So I added benchmark for weighted graphs also.

Here is my code:

```julia
using BenchmarkTools
using DataStructures
using FastPriorityQueues
using Graphs
using LinearAlgebra
using SparseArrays
using Test

function dijkstra_priority_updates!(
    q::Q, g::AbstractGraph{T}, s::Integer, w=weights(g)
) where {Q,T}
    d = fill(Inf, nv(g))
    d[s] = 0.
    enqueue!(q, s, 0.)
    while !isempty(q)
        u, k = first(q)
        dequeue!(q)
        d[u] = k
        for v in outneighbors(g, u)
            if d[u] + w[u, v] < d[v]
                d[v] = d[u] + w[u, v]
                d[v] == Inf ? enqueue!(q, v, d[v]) : q[v] = d[v]
            end
        end
    end
    return d
end

function dijkstra_no_priority_updates!(
    q::Q, g::AbstractGraph{T}, s::Integer, w=weights(g)
) where {Q,T}
    d = fill(Inf, nv(g))
    d[s] = 0.
    enqueue!(q, s, 0.)
    while !isempty(q)
        u, k = first(q)
        dequeue!(q)
        if k <= d[u]
            d[u] = k
            for v in outneighbors(g, u)
                if d[u] + w[u, v] < d[v]
                    d[v] = d[u] + w[u, v]
                    enqueue!(q, v, d[v])
                end
            end
        end
    end
    return d
end

function random_weights(g)
    srcs = src.(edges(g))
    dsts = dst.(edges(g))
    w = rand(ne(g))
    Symmetric(sparse(srcs, dsts, w, ne(g), ne(g))) # assuming src < dst
end

n = 10
g = Graphs.grid([n, n])
w = random_weights(g)

d1 = dijkstra_priority_updates!(PriorityQueue{Int,Float64}(), g, 1)[end];
d2 = dijkstra_no_priority_updates!(VectorPriorityQueue{Int,Float64}(), g, 1)[end];
d3 = dijkstra_no_priority_updates!(SortedVectorPriorityQueue{Int,Float64}(), g, 1)[end];
@test d1 ≈ d2 ≈ d3

d1 = dijkstra_priority_updates!(PriorityQueue{Int,Float64}(), g, 1, w)[end];
d2 = dijkstra_no_priority_updates!(VectorPriorityQueue{Int,Float64}(), g, 1, w)[end];
d3 = dijkstra_no_priority_updates!(SortedVectorPriorityQueue{Int,Float64}(), g, 1, w)[end];
@test d1 ≈ d2 ≈ d3

n = 100
g = Graphs.grid([n, n])
w = random_weights(g)

@benchmark dijkstra_priority_updates!(PriorityQueue{Int,Float64}(), $g, 1)
@benchmark dijkstra_no_priority_updates!(VectorPriorityQueue{Int,Float64}(), $g, 1)
@benchmark dijkstra_no_priority_updates!(SortedVectorPriorityQueue{Int,Float64}(), $g, 1)

@benchmark dijkstra_priority_updates!(PriorityQueue{Int,Float64}(), $g, 1, $w)
@benchmark dijkstra_no_priority_updates!(VectorPriorityQueue{Int,Float64}(), $g, 1, $w)
@benchmark dijkstra_no_priority_updates!(SortedVectorPriorityQueue{Int,Float64}(), $g, 1, $w)

```

And here are the results:

```julia
julia> @benchmark dijkstra_priority_updates!(PriorityQueue{Int,Float64}(), $g, 1)
BenchmarkTools.Trial: 124 samples with 1 evaluation.
 Range (min … max): 39.799 ms … 45.018 ms ┊ GC (min … max): 15.24% … 13.04%
 Time (median): 40.171 ms ┊ GC (median): 15.15%
 Time (mean ± σ): 40.327 ms ± 559.114 μs ┊ GC (mean ± σ): 15.12% ± 0.23%

        ▄ █▅▂▅ ▂                                           
  ▃▃▆▆▇▇█▇▆████▇█▆▆▅█▅▁▆▆▁▅█▃▃▆▅▁▁▁▁▅▁▃▁▁▁▁▁▃▁▁▅▁▅▁▁▁▁▅▁▃▁▁▁▁▃ ▃
  39.8 ms Histogram: frequency by time 41.6 ms <

 Memory estimate: 87.80 MiB, allocs estimate: 70130.

julia> @benchmark dijkstra_no_priority_updates!(VectorPriorityQueue{Int,Float64}(), $g, 1)
BenchmarkTools.Trial: 540 samples with 1 evaluation.
 Range (min … max): 9.181 ms … 11.195 ms ┊ GC (min … max): 0.00% … 15.54%
 Time (median): 9.234 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 9.264 ms ± 115.018 μs ┊ GC (mean ± σ): 0.03% ± 0.67%

        █▃                                                     
  ▆▇▃▃▂███▆▅▃▄▃▃▄▃▄▃▃▃▂▃▃▃▃▃▃▂▂▂▁▂▂▂▁▂▂▁▂▁▂▂▁▁▁▂▁▁▂▁▁▁▁▁▁▁▁▂▂ ▃
  9.18 ms Histogram: frequency by time 9.6 ms <

 Memory estimate: 92.97 KiB, allocs estimate: 7.

julia> @benchmark dijkstra_no_priority_updates!(SortedVectorPriorityQueue{Int,Float64}(), $g, 1)
BenchmarkTools.Trial: 2913 samples with 1 evaluation.
 Range (min … max): 1.670 ms … 3.855 ms ┊ GC (min … max): 0.00% … 45.78%
 Time (median): 1.691 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 1.708 ms ± 96.639 μs ┊ GC (mean ± σ): 0.21% ± 2.14%

     ▂▂▇█▆▄▁                                                  
  ▂▃▆████████▅▃▂▂▂▂▂▂▃▃▄▄▄▄▄▄▃▃▂▂▂▃▃▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  1.67 ms Histogram: frequency by time 1.81 ms <

 Memory estimate: 92.97 KiB, allocs estimate: 7.

julia> @benchmark dijkstra_priority_updates!(PriorityQueue{Int,Float64}(), $g, 1, $w)
BenchmarkTools.Trial: 79 samples with 1 evaluation.
 Range (min … max): 61.760 ms … 66.214 ms ┊ GC (min … max): 12.46% … 11.60%
 Time (median): 64.585 ms ┊ GC (median): 15.68%
 Time (mean ± σ): 63.763 ms ± 1.416 ms ┊ GC (mean ± σ): 14.24% ± 1.65%

     ▅▅ ▅▅ ▂ ▂██▅▂▂ ▂ ▂ ▂   
  ▅███████▅█▅█▅▅▁▁▁▅▁▅█▁▁▅▁▁▁▁▁▁▁▁▁▁▁▁▁▁▅▅▁██████▁██▅▅▁▅█▁▁██ ▁
  61.8 ms Histogram: frequency by time 65.8 ms <

 Memory estimate: 154.20 MiB, allocs estimate: 70086.

julia> @benchmark dijkstra_no_priority_updates!(VectorPriorityQueue{Int,Float64}(), $g, 1, $w)
BenchmarkTools.Trial: 151 samples with 1 evaluation.
 Range (min … max): 32.278 ms … 34.562 ms ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 33.061 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 33.132 ms ± 597.476 μs ┊ GC (mean ± σ): 0.00% ± 0.00%

   ▁▃ ▁▄ █ ▆▁ ▁ ▁ ▁ ▁ ▁ ▆ ▃ ▄    
  ▇██▆██▇█▄▄██▇▁▇▆▄▁▄█▇▆▁▆▆█▄▇▇▁█▄▆▄▆▄▇▆▇▁▁▁▆▄▁▁▇▁█▄█▇█▇▆█▇█▇▄ ▄
  32.3 ms Histogram: frequency by time 34.1 ms <

 Memory estimate: 121.47 KiB, allocs estimate: 8.

julia> @benchmark dijkstra_no_priority_updates!(SortedVectorPriorityQueue{Int,Float64}(), $g, 1, $w)
BenchmarkTools.Trial: 1204 samples with 1 evaluation.
 Range (min … max): 3.982 ms … 7.216 ms ┊ GC (min … max): 0.00% … 24.18%
 Time (median): 4.065 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 4.142 ms ± 243.461 μs ┊ GC (mean ± σ): 0.07% ± 1.06%

  █▅▅▆▇▅▅▄▃▃▃▁▁ ▁                                              
  █████████████████▇██▇▆█▅▇▆██▇▄▅▅▄▄▆▅▇▆▆▅▅▆▆▅▄▆▆▁▅▁▄▄▄▅▅▅▆▄▆ █
  3.98 ms Histogram: log(frequency) by time 5.11 ms <

 Memory estimate: 121.47 KiB, allocs estimate: 8.

```

So I still get a huge speedup.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 20, 2022, 12:26pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/13 "2022-05-20T12:26:15Z")

</div>

I think the huge speedup we both saw is due to a bias in my initial code. For some reason, the function `first` is very inefficient when applied to a `DataStructures.PriorityQueue`, and that explains most of the gap. Replace `u, k = first(q); dequeue!(q)` with `u, k = dequeue_pair!(q)` and we go back to a x2 speedup instead of x10.

To confirm this, I replaced `dijkstra_priority_updates!` with `Graphs.dijkstra_shortest_path`, and the results changed drastically.

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [May 20, 2022, 12:39pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/14 "2022-05-20T12:39:43Z")

</div>

Indeed, I also get much better timings with dequeue\_pair, I will post the new benchmark

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 20, 2022, 1:08pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/15 "2022-05-20T13:08:42Z")

</div>

![plot_12](https://global.discourse-cdn.com/julialang/original/3X/c/9/c91fa61f150794e69d0c4eb6de1fc1a2656aa125.png)  
 ![plot_14](https://global.discourse-cdn.com/julialang/original/3X/d/5/d53f2937a5ccf7259906e38fbb6c673888bfb800.png)  
Here’s what I get when correcting this bug (source code is in FastPriorityQueues.jl)

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [May 20, 2022, 1:09pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/16 "2022-05-20T13:09:12Z")

</div>

**Edit: passed weights in the benchmark**  
Here are the results:  
 ![plot](https://global.discourse-cdn.com/julialang/original/3X/5/4/54f44e476f9fe2553d695d77c26d313883060f0a.png)

This is run on weighted grids, PriorityQueue use priority updates, while the three other data structures don’t. As expected, Priority queue behave similarly as the Graphs.jl implementation, while the `SortedVectorPriorityQueue` and `HeapPriorityQueue` are a little bit faster. `VectorPriorityQueue` just seems not worth it.

Here is my code, based on the actual benchmark of `FastPriorityQueues`:

```julia
using FastPriorityQueues
using BenchmarkTools #src
using DataStructures
using FastPriorityQueues
using Graphs
using Plots
using Test
using SparseArrays
using LinearAlgebra
using Random

function dijkstra_priority_updates!(
    q::Q, g::AbstractGraph{T}, s::Integer, w=weights(g)
) where {Q,T}
    d = fill(Inf, nv(g))
    d[s] = 0.
    enqueue!(q, s, 0.)
    while !isempty(q)
        u, k = dequeue_pair!(q)
        d[u] = k
        for v in outneighbors(g, u)
            if d[u] + w[u, v] < d[v]
                d[v] = d[u] + w[u, v]
                d[v] == Inf ? enqueue!(q, v, d[v]) : q[v] = d[v]
            end
        end
    end
    return d
end

function dijkstra_no_priority_updates!(
    q::Q, g::AbstractGraph{T}, s::Integer, w=weights(g)
) where {Q,T}
    d = fill(Inf, nv(g))
    d[s] = 0.0
    enqueue!(q, s, 0.0)
    while !isempty(q)
        u, d_u = dequeue_pair!(q)
        if d_u <= d[u]
            d[u] = d_u
            for v in outneighbors(g, u)
                d_v = d[u] + w[u, v]
                if d_v < d[v]
                    enqueue!(q, v, d_v)
                    d[v] = d_v
                end
            end
        end
    end
    return d
end

function random_weights(g)
    srcs = src.(edges(g))
    dsts = dst.(edges(g))
    rng = Xoshiro(1234);
    w = rand(rng, ne(g))
    Symmetric(sparse(srcs, dsts, w, ne(g), ne(g))) # assuming src < dst
end

test_dijkstra_default(g, w=weights(g)) = Graphs.dijkstra_shortest_paths(g, 1, w).dists[end];
test_dijkstra_priority_updates(g, qtype, w=weights(g)) = dijkstra_priority_updates!(qtype(), g, 1, w)[end];
test_dijkstra_no_priority_updates(g, qtype, w=weights(g)) = dijkstra_no_priority_updates!(qtype(), g, 1, w)[end];

g_small = Graphs.grid([10, 10])
w_small = random_weights(g_small)

d1 = test_dijkstra_default(g_small);
d2 = test_dijkstra_priority_updates(g_small, PriorityQueue{Int,Float64});
d3 = test_dijkstra_no_priority_updates(g_small, VectorPriorityQueue{Int,Float64});
d4 = test_dijkstra_no_priority_updates(g_small, SortedVectorPriorityQueue{Int,Float64});
d5 = test_dijkstra_no_priority_updates(g_small, HeapPriorityQueue{Int,Float64});
@test d1 ≈ d2 ≈ d3 ≈ d4 ≈ d5

d1 = test_dijkstra_default(g_small, w_small);
d2 = test_dijkstra_priority_updates(g_small, PriorityQueue{Int,Float64}, w_small);
d3 = test_dijkstra_no_priority_updates(g_small, VectorPriorityQueue{Int,Float64}, w_small);
d4 = test_dijkstra_no_priority_updates(g_small, SortedVectorPriorityQueue{Int,Float64}, w_small);
d5 = test_dijkstra_no_priority_updates(g_small, HeapPriorityQueue{Int,Float64}, w_small);
@test d1 ≈ d2 ≈ d3 ≈ d4 ≈ d5

function compare_dijkstra_versions(n_values, weighted=true)
    speed_gains = Dict(
        "PriorityQueue" => Float64[],
        "VectorPriorityQueue" => Float64[],
        "SortedVectorPriorityQueue" => Float64[],
        "HeapPriorityQueue" => Float64[],
    )
    memory_gains = Dict(
        "PriorityQueue" => Float64[],
        "VectorPriorityQueue" => Float64[],
        "SortedVectorPriorityQueue" => Float64[],
        "HeapPriorityQueue" => Float64[],
    )
    for n in n_values
        @info "Testing grids of side length $n"
        g = Graphs.grid([n, n])
        if weighted
            w = random_weights(g)
        else
            w = weights(g)
        end
        _, t0, m0, _, _ = @timed for _ in 1:5
            test_dijkstra_default(g, w)
        end
        _, t1, m1, _, _ = @timed for _ in 1:5
            test_dijkstra_priority_updates(g, PriorityQueue{Int,Float64}, w);
        end
        _, t3, m3, _, _ = @timed for _ in 1:5
            test_dijkstra_no_priority_updates(g, VectorPriorityQueue{Int,Float64}, w);
        end
        _, t4, m4, _, _ = @timed for _ in 1:5
            test_dijkstra_no_priority_updates(g, SortedVectorPriorityQueue{Int,Float64}, w);
        end
        _, t5, m5, _, _ = @timed for _ in 1:5
            test_dijkstra_no_priority_updates(g, HeapPriorityQueue{Int,Float64}, w
![plot|600x400](upload://fDd1mzQVRFHaBpzZ096T9iTkNYI.png)
);
        end
        push!(speed_gains["PriorityQueue"], t0 / t1)
        push!(speed_gains["VectorPriorityQueue"], t0 / t3)
        push!(speed_gains["SortedVectorPriorityQueue"], t0 / t4)
        push!(speed_gains["HeapPriorityQueue"], t0 / t5)
        push!(memory_gains["PriorityQueue"], m0 / m1)
        push!(memory_gains["VectorPriorityQueue"], m0 / m3)
        push!(memory_gains["SortedVectorPriorityQueue"], m0 / m4)
        push!(memory_gains["HeapPriorityQueue"], m0 / m5)

    end
    return speed_gains, memory_gains
end

# To gain precision, we could replace the built-in `@elapsed` with `@belapsed` from [BenchmarkTools.jl](https://github.com/JuliaCI/BenchmarkTools.jl).

n_values = [10, 30, 100, 300, 1000]
speed_gains, memory_gains = compare_dijkstra_versions(n_values)

# Finally, let us plot the results.

settings = [
    "PriorityQueue", "SortedVectorPriorityQueue", "VectorPriorityQueue", "HeapPriorityQueue"
]
S = length(settings)
N = length(n_values)

# And we follow up with memory use

plt = plot(;
    title="Dijkstra with no priority updates",
    xlabel="Grid side length",
    ylabel="Memory gain wrt. Graphs.jl",
    ylim=(0, Inf),
    xticks=(1:N, string.(n_values)),
    margin=5Plots.mm,
    # legend_position=:topleft
)
for (k, setting) in enumerate(settings)
    bar!(
        plt,
        (1:N) .+ 0.7 * (k - (S + 1) / 2) / S,
        memory_gains[setting];
        label=setting,
        bar_width=0.7 / S,
    )
end
plt

# First we compare execution time

plt = plot(;
    title="Dijkstra with no priority updates",
    xlabel="Grid side length",
    ylabel="Speed gain wrt. Graphs.jl",
    ylim=(0, Inf),
    xticks=(1:N, string.(n_values)),
    margin=5Plots.mm,
    legend_position=:legend
)
for (k, setting) in enumerate(settings)
    bar!(
        plt,
        (1:N) .+ 0.7 * (k - (S + 1) / 2) / S,
        speed_gains[setting];
        label=setting,
        bar_width=0.7 / S,
    )
end
plt

```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 20, 2022, 1:13pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/17 "2022-05-20T13:13:31Z")

</div>

OK so this sounds more reasonable than my initial (outrageous) claims 😅  
If these speedups can be observed on other types of graphs, maybe it would be worth it to switch to a heap-based Dijkstra. In particular, I’m curious about what would happen with dense graphs

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [May 20, 2022, 2:20pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/18 "2022-05-20T14:20:40Z")

</div>

**Edit: passed weights in the benchmark**  
Went a bit further, it looks like this:  
 ![plot2](https://global.discourse-cdn.com/julialang/original/3X/d/4/d41739bb0959a33b32146f0df36b95987580d277.png)  
`HeapPriorityQueue` seems to scale pretty good, `SortedVectorPriorityQueue` scales badly.

---

<div class="post-metadata">

**Author:** ![etienne\_dg](https://avatars.discourse-cdn.com/v4/letter/e/fbc32d/32.png) [@etienne\_dg](https://discourse.julialang.org/u/etienne_dg)\
**Post date:** [May 20, 2022, 2:36pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/19 "2022-05-20T14:36:16Z")

</div>

On your benchmark, `SortedVectorPriorityQueue` and `HeapPriorityQueue` seems to be slower than on mine, I will try to dig into it.

**Edit** Oups, did not passed weights in the function 😅. I will fix the benchmarks

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 20, 2022, 3:45pm UTC](https://discourse.julialang.org/t/fast-er-priority-queues/81269/20 "2022-05-20T15:45:53Z")

</div>

Okay then, looks like the heap is a serious contender. `HeapPriorityQueue` is just a dumb wrapper to be able to use `enqueue!`/`dequeue!`, but if we go that way we might as well directly use `push!`/`pop!` in Dijkstra

[Next page](https://discourse.julialang.org/t/fast-er-priority-queues/81269.md?page=2)