I created an issue
<https://github.com/JuliaLang/DataStructures.jl/issues/95> in
DataStructures.jl but was unsure whether or not that was the right
approach. In any case, I'll restate the question here with apologies for
any inappropriate duplication.
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 in clean
environments).
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.
