Benchmark
Here we compare the performance of MetaGraphsNext.jl with its predecessor MetaGraphs.jl.
using BenchmarkTools
using Graphs
using InteractiveUtils
using MetaGraphs: MetaGraphs
using MetaGraphsNext: MetaGraphsNextThe benchmarking task is two-fold:
- Build a complete graph with random boolean metadata on the vertices (
active) and float metadata on the edges (distance) - Compute the sum of distances for all edges whose endpoints are both active.
Graph construction
function build_incremental_metagraphsnext(n)
g = Graph(0)
mg = MetaGraphsNext.MetaGraph(
g;
label_type=Int, # this will throw a warning
vertex_data_type=Bool,
edge_data_type=Float64,
)
for li in 1:n
mg[li] = rand(Bool)
end
for li in 1:n, lj in 1:(li - 1)
mg[li, lj] = rand(Float64)
end
return mg
end;function build_bulk_metagraphsnext(n)
g = complete_graph(n)
vertices_description = [li => rand(Bool) for li in 1:n]
edges_description = [(li, lj) => rand(Float64) for li in 1:n for lj in 1:(li - 1)]
mg = MetaGraphsNext.MetaGraph(g, vertices_description, edges_description;)
return mg
end;function build_metagraphs(n)
g = complete_graph(n)
mg = MetaGraphs.MetaGraph(g)
for i in 1:n
MetaGraphs.set_prop!(mg, i, :active, rand(Bool))
end
for i in 1:n, j in 1:(i - 1)
MetaGraphs.set_prop!(mg, i, j, :distance, rand(Float64))
end
return mg
end;@btime build_incremental_metagraphsnext(100); 570.456 μs (449 allocations: 744.28 KiB)@btime build_bulk_metagraphsnext(100); 270.075 μs (158 allocations: 1005.39 KiB)@btime build_metagraphs(100); 1.510 ms (46001 allocations: 5.81 MiB)Graph exploitation
function sum_active_edges_metagraphsnext(mg)
S = 0.0
for (li, lj) in MetaGraphsNext.edge_labels(mg)
active_i = mg[li]
active_j = mg[lj]
distance_ij = mg[li, lj]
if active_i && active_j
S += distance_ij
end
end
return S
endsum_active_edges_metagraphsnext (generic function with 1 method)function sum_active_edges_metagraphs(mg)
S = 0.0
for e in edges(mg)
i, j = src(e), dst(e)
active_i = MetaGraphs.get_prop(mg, i, :active)
active_j = MetaGraphs.get_prop(mg, j, :active)
distance_ij = MetaGraphs.get_prop(mg, i, j, :distance)
if active_i && active_j
S += distance_ij
end
end
return S
endsum_active_edges_metagraphs (generic function with 1 method)mg1 = build_incremental_metagraphsnext(100);
@btime sum_active_edges_metagraphsnext($mg1); 173.805 μs (0 allocations: 0 bytes)mg2 = build_metagraphs(100);
@btime sum_active_edges_metagraphs($mg2); 459.288 μs (1378 allocations: 21.53 KiB)The difference in performance can be explained by type instability.
@code_warntype sum_active_edges_metagraphsnext(mg1);MethodInstance for Main.sum_active_edges_metagraphsnext(::MetaGraph{Int64, SimpleGraph{Int64}, Int64, Bool, Float64, Nothing, MetaGraphsNext.var"#11#13", Float64})
from sum_active_edges_metagraphsnext(mg) @ Main 5_benchmark.md:87
Arguments
#self#::Core.Const(Main.sum_active_edges_metagraphsnext)
mg::MetaGraph{Int64, SimpleGraph{Int64}, Int64, Bool, Float64, Nothing, MetaGraphsNext.var"#11#13", Float64}
Locals
@_3::UNION{NOTHING, TUPLE{TUPLE{INT64, INT64}, TUPLE{INT64, INT64}}}
S::Float64
@_5::Int64
lj::Int64
li::Int64
distance_ij::Float64
active_j::Bool
active_i::Bool
Body::Float64
1 ─ (S = 0.0)
│ %2 = MetaGraphsNext.edge_labels::Core.Const(MetaGraphsNext.edge_labels)
│ %3 = (%2)(mg)::Base.Generator{Graphs.SimpleGraphs.SimpleEdgeIter{SimpleGraph{Int64}}, MetaGraphsNext.var"#22#23"{MetaGraph{Int64, SimpleGraph{Int64}, Int64, Bool, Float64, Nothing, MetaGraphsNext.var"#11#13", Float64}}}
│ (@_3 = Base.iterate(%3))
│ %5 = (@_3 === nothing)::Bool
│ %6 = Base.not_int(%5)::Bool
└── goto #7 if not %6
2 ┄ %8 = @_3::Tuple{Tuple{Int64, Int64}, Tuple{Int64, Int64}}
│ %9 = Core.getfield(%8, 1)::Tuple{Int64, Int64}
│ %10 = Base.indexed_iterate(%9, 1)::Core.PartialStruct(Tuple{Int64, Int64}, Any[Int64, Core.Const(2)])
│ (li = Core.getfield(%10, 1))
│ (@_5 = Core.getfield(%10, 2))
│ %13 = Base.indexed_iterate(%9, 2, @_5::Core.Const(2))::Core.PartialStruct(Tuple{Int64, Int64}, Any[Int64, Core.Const(3)])
│ (lj = Core.getfield(%13, 1))
│ %15 = Core.getfield(%8, 2)::Tuple{Int64, Int64}
│ (active_i = Base.getindex(mg, li))
│ (active_j = Base.getindex(mg, lj))
│ (distance_ij = Base.getindex(mg, li, lj))
└── goto #5 if not active_i
3 ─ goto #5 if not active_j
4 ─ (S = S + distance_ij)
5 ┄ (@_3 = Base.iterate(%3, %15))
│ %23 = (@_3 === nothing)::Bool
│ %24 = Base.not_int(%23)::Bool
└── goto #7 if not %24
6 ─ goto #2
7 ┄ return S@code_warntype sum_active_edges_metagraphs(mg2);MethodInstance for Main.sum_active_edges_metagraphs(::MetaGraphs.MetaGraph{Int64, Float64})
from sum_active_edges_metagraphs(mg) @ Main 5_benchmark.md:102
Arguments
#self#::Core.Const(Main.sum_active_edges_metagraphs)
mg::MetaGraphs.MetaGraph{Int64, Float64}
Locals
@_3::UNION{NOTHING, TUPLE{GRAPHS.SIMPLEGRAPHS.SIMPLEEDGE{INT64}, TUPLE{INT64, INT64}}}
S::ANY
e::Graphs.SimpleGraphs.SimpleEdge{Int64}
distance_ij::ANY
active_j::ANY
active_i::ANY
j::Int64
i::Int64
Body::ANY
1 ─ (S = 0.0)
│ %2 = Main.edges(mg)::Graphs.SimpleGraphs.SimpleEdgeIter{SimpleGraph{Int64}}
│ (@_3 = Base.iterate(%2))
│ %4 = (@_3 === nothing)::Bool
│ %5 = Base.not_int(%4)::Bool
└── goto #7 if not %5
2 ┄ %7 = @_3::Tuple{Graphs.SimpleGraphs.SimpleEdge{Int64}, Tuple{Int64, Int64}}
│ (e = Core.getfield(%7, 1))
│ %9 = Core.getfield(%7, 2)::Tuple{Int64, Int64}
│ %10 = Main.src(e)::Int64
│ %11 = Main.dst(e)::Int64
│ (i = %10)
│ (j = %11)
│ %14 = MetaGraphs.get_prop::Core.Const(MetaGraphs.get_prop)
│ %15 = i::Int64
│ (active_i = (%14)(mg, %15, :active))
│ %17 = MetaGraphs.get_prop::Core.Const(MetaGraphs.get_prop)
│ %18 = j::Int64
│ (active_j = (%17)(mg, %18, :active))
│ %20 = MetaGraphs.get_prop::Core.Const(MetaGraphs.get_prop)
│ %21 = i::Int64
│ %22 = j::Int64
│ (distance_ij = (%20)(mg, %21, %22, :distance))
└── goto #5 if not active_i
3 ─ goto #5 if not active_j
4 ─ (S = S + distance_ij)
5 ┄ (@_3 = Base.iterate(%2, %9))
│ %28 = (@_3 === nothing)::Bool
│ %29 = Base.not_int(%28)::Bool
└── goto #7 if not %29
6 ─ goto #2
7 ┄ return SThis page was generated using Literate.jl.