Interesting / unexpected performance of binary heaps

[sbromberger]

I've been using mutable_binary_minheap for a Dijkstra calculation and am getting reasonable performance for betweenness centrality (which basically does all-pairs Dijkstra) in a large graph:

julia> g = readgraph("/Users/seth/Downloads/pgp2.jgz")
{39796, 301498} directed graph   # {number of vertices, number of edges}
julia> @time z = betweenness_centrality(g);
    1426 seconds      (3768 M allocations: 328 GB, 21.91% gc time)

Realizing that I really didn't need the mutability (I'm just push!ing and pop!ping), I switched over to binary_minheap, thinking that I'd get at least the same, but possibly better, performance. However:

julia> @time z = betweenness_centrality(g);
    1743 seconds      (8469 M allocations: 385 GB, 28.40% gc time

These results are repeatable (I ran each test 3 times).

Why would binary_minheap be so much slower than its mutable counterpart, and why would it require more than twice the number of allocations (note that the amount of memory allocated is also different, but maybe not significantly so)?

Thanks for any assistance / insight.

[ChrisRackauckas]

Could this have been due to the type instability?

https://github.com/JuliaCollections/DataStructures.jl/pull/263

[laborg]

I've compared BinaryHeap vs MutableBinaryHeap using the benchmark script in bench_heap on master and BinaryHeap is always faster. e.g.:

julia> results["BinaryHeap"]["pop"]
2-element BenchmarkTools.BenchmarkGroup:
  tags: []
  "Int64" => 2-element BenchmarkTools.BenchmarkGroup:
          tags: []
          "10^3" => 1-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "Min" => Trial(33.508 μs)
          "10^1" => 1-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "Min" => Trial(119.000 ns)
  "Float64" => 2-element BenchmarkTools.BenchmarkGroup:
          tags: []
          "10^3" => 2-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "SlowMin" => Trial(59.742 μs)
                  "Min" => Trial(37.784 μs)
          "10^1" => 2-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "SlowMin" => Trial(136.000 ns)
                  "Min" => Trial(119.000 ns)

julia> results["MutableBinaryHeap"]["pop"]
2-element BenchmarkTools.BenchmarkGroup:
  tags: []
  "Int64" => 2-element BenchmarkTools.BenchmarkGroup:
          tags: []
          "10^3" => 1-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "Min" => Trial(49.894 μs)
          "10^1" => 1-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "Min" => Trial(178.000 ns)
  "Float64" => 2-element BenchmarkTools.BenchmarkGroup:
          tags: []
          "10^3" => 2-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "SlowMin" => Trial(74.890 μs)
                  "Min" => Trial(47.017 μs)
          "10^1" => 2-element BenchmarkTools.BenchmarkGroup:
                  tags: []
                  "SlowMin" => Trial(216.000 ns)
                  "Min" => Trial(169.000 ns)

julia>