# 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: MetaGraphsNext

1. Build a complete graph with random boolean metadata on the vertices (active) and float metadata on the edges (distance)
2. 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
end
sum_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
end
sum_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 S