My default answer to such questions is to suggest profiling (I don't really know/remember the DataStructures code very well).
You can also try the binary heap in Base.Collections. I've not compared them directly. Best, --Tim On Thursday, June 04, 2015 12:43:34 PM Seth wrote: > 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.
