but it is the amalgamation of several posts, which I am told is preferable.
We’re at the point, I think, where it might be better to use Github issues for this discussion, as it’s probably not of general interest.
You have one allocation per vertex because we’re creating a vector of (different) empty vectors. What would you do otherwise that would be more efficient? Here’s an alternative:
function sg(n::T) where T <: Integer
fadjlist = Vector{Vector{T}}()
sizehint!(fadjlist, n)
@inbounds for _ = one(T):n
push!(fadjlist, Vector{T}())
end
return SimpleGraph{T}(0, fadjlist)
end
Which doesn’t perform as well:
julia> @benchmark SimpleGraphsCore.sg(2_000_000)
BenchmarkTools.Trial:
memory estimate: 167.85 MiB
allocs estimate: 2000003
--------------
minimum time: 92.165 ms (0.00% GC)
median time: 105.792 ms (19.77% GC)
mean time: 116.216 ms (27.17% GC)
maximum time: 226.732 ms (63.25% GC)
--------------
samples: 44
evals/sample: 1
julia> @benchmark SimpleGraphsCore.SimpleGraph(2_000_000)
BenchmarkTools.Trial:
memory estimate: 167.85 MiB
allocs estimate: 2000003
--------------
minimum time: 78.624 ms (0.00% GC)
median time: 90.569 ms (24.84% GC)
mean time: 99.989 ms (31.70% GC)
maximum time: 212.482 ms (67.59% GC)
--------------
samples: 50
evals/sample: 1
Perhaps you are allowing for the adding of vertices?
Yes. Both SimpleGraph and SimpleWeightedGraph allow graph modification (adding/removing of vertices), though each has its own performance profile/tradeoffs.
But then why not define a DynamicSimpleGraph type for that case?
That’s what these graph types are. If you want an unmodifiable graph, use StaticGraphs.
SimpleWeightedGraph allocates nothing, which I find logical.
Sparse matrices don’t allocate anything except for colptr until you start adding to them. An empty sparse matrix is three pointers and 2 integers big, plus m values of some integer size that represents the column type.
So why 400,000 allocations when the constructor of SimpleWeightedGraph is a SimpleGraph ?
Because with SimpleGraphs you’re simply paying the cost of allocation up front instead of repeatedly during edge insertion. Give it a try: create two empty 200k-vertex graphs (SG, and SWG), and then time adding 2 million random edges to each.
I would have expected at most 200,000 allocations
and that’s what you get:
julia> @btime SimpleGraph(200_000)
4.137 ms (200003 allocations: 16.78 MiB)
Directed graphs have to store the backward adjacencies, so that doubles the allocations:
julia> @btime SimpleDiGraph(200_000)
8.546 ms (400005 allocations: 33.57 MiB)
What you’re doing in the third case is converting into a sparse-matrix-backed graph type from a adjacency-list-backed graph type. This will necessarily be less efficient than creating it directly.
Finally, the construction time cost of SimpleWeightedGraph is three times that of SimpleGraph
I don’t see this for empty graphs:
julia> @btime SimpleGraph(200_000)
4.166 ms (200003 allocations: 16.78 MiB)
{200000, 0} undirected simple Int64 graph
julia> @btime SimpleWeightedGraph(200_000)
287.023 ÎĽs (9 allocations: 3.05 MiB)
{200000, 0} undirected simple Int64 graph with Float64 weights
It’s ~20x faster to create an empty SWG than an empty SG. Again, you’re saving time up front at the cost of worse-performing edge inserts, which is why if you’re adding edges one at a time, you’ll get better performance in the long run with SimpleGraphs.
One question is: why not use a reference to this adjacency matrix since it has already been constructed?
I don’t understand this. Where has it been constructed outside of the adjacency_matrix function?
Why not copy the adjacency matrix rather than have 200,000 allocations
So again, why would getting the adj_matrix from sg produce 200,000 allocations.
For SimpleGraphs, there’s no adjacency matrix to copy until we create it, which is where the allocations are coming from. SimpleGraphs do not store a sparse matrix: they store adjacency lists, and we have to convert the adjacency lists to a sparse matrix in order to provide an adjacency matrix. This involves allocation: specifically, nv(g) ints to put into the colptr vector for the sparse matrix.
In my estimation, it should produce no allocations whatsoever!!
You have to allocate nv(g) memory for the colptr vector in every case. Are you looking at the number of allocations as opposed to the size of the allocs? In that case, it’s because we hand-roll the creation of the adjacency matrix in SimpleGraphs for efficiency, and this requires a bunch of small allocations but it’s the fastest way we’ve found to do it for the general (non-empty) case. If you can find a faster way, please open a PR.
More surprising, is that I checked that the statement
adj_matrix = adjacency_matrix(sg)
is not a copy.
It’s not a copy of anything, because it doesn’t exist anywhere until you create it. There is no sparse matrix just hanging around waiting for you to call adjacency_matrix. The sparse matrix is created when you call the function. Because we don’t want modifications to the adjacency matrix to change the graph from which the AM was created, and because we don’t want to store the graph data twice, we return a separate data structure. This necessarily allocates.
So I am not clear why the copy is made when initializing a variable of type SimpleWeightedGraph
There is no copy, as you’re showing in your aaa = adj_matrix benchmark.
You told me that you store weights separately from the adjacency_matrix because many people preferred it that way.
For SimpleGraphs, we do not store weights at all. For SimpleWeightedGraphs, the weights are stored in the sparse matrix that represents the graph. Unsurprisingly, perhaps, this data structure is called weights.
Why should have fadjlist::Array{Array{T,1},1} for the adacency matrix and a sparse array structure for the weight matrix? Both structures are not equally efficient are they?
We don’t have that. You may be confusing the data structure for SimpleGraph, which is an adjacency list: Vector{Vector{T}} and is called fadjlist, with that of SimpleWeightedGraph, which is a sparse matrix that holds weight information as well, and is called weights.
If you’re asking why we require folks who use SimpleGraphs to store their weight data separately, it’s because we have (deliberately) created no place in the data structure used by SimpleGraph (that is, an adjacency list) to store the weights. SimpleGraphs are weightless.
I think I have overstayed my welcome. 
It’s probably best to continue this via Github issues.