Consider the following two functions, which construct an undirected graph from a collection of edges.
using BenchmarkTools
using Catlab
using Graphs
function make_graph_1(n, edges)
graph = Catlab.Graphs.SymmetricGraph(n)
for (v₁, v₂) in edges
if !Catlab.Graphs.has_edge(graph, v₁, v₂)
Catlab.Graphs.add_edge!(graph, v₁, v₂)
end
end
graph
end
function make_graph_2(n, edges)
graph = Graphs.Graph(n)
for (v₁, v₂) in edges
if !Graphs.has_edge(graph, v₁, v₂)
Graphs.add_edge!(graph, v₁, v₂)
end
end
graph
end
n = 1000
edges = zip(1:n-1, 2:n)
Then @benchmark make_graph_1(n, edges) outputs
BenchmarkTools.Trial: 427 samples with 1 evaluation.
Range (min … max): 10.694 ms … 16.823 ms ┊ GC (min … max): 0.00% … 10.04%
Time (median): 11.526 ms ┊ GC (median): 0.00%
Time (mean ± σ): 11.708 ms ± 790.291 μs ┊ GC (mean ± σ): 3.23% ± 5.15%
▁ ▃▆▁ ▁ ▇█▅▂
▂▂▄▃█████▆█▆▆▅▅▅▅▆████▇▃▄▄▁▃▁▁▁▁▁▁▁▃▁▂▂▃▅▄▅▄▂▄▃▄▂▃▂▃▃▄▅▅▆▅▄▅ ▄
10.7 ms Histogram: frequency by time 13.3 ms <
Memory estimate: 10.71 MiB, allocs estimate: 131834.
whereas @benchmark make_graph_2(n, edges) outputs
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
Range (min … max): 48.125 μs … 1.879 ms ┊ GC (min … max): 0.00% … 95.21%
Time (median): 59.875 μs ┊ GC (median): 0.00%
Time (mean ± σ): 65.047 μs ± 93.556 μs ┊ GC (mean ± σ): 8.12% ± 5.44%
▁▃▅▂ ▁▅█▇▄
▂▂▁▁▂▂▁▁▂▂▂▂▂▃▅▆▅▅██████▇███████▆▅▄▄▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂ ▄
48.1 μs Histogram: frequency by time 74.2 μs <
Memory estimate: 148.59 KiB, allocs estimate: 2002.
Consider the following two functions, which construct an undirected graph from a collection of edges.
Then
@benchmark make_graph_1(n, edges)
outputswhereas
@benchmark make_graph_2(n, edges)
outputs