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); 450.439 μs (561 allocations: 711.19 KiB)@btime build_bulk_metagraphsnext(100); 217.395 μs (275 allocations: 908.51 KiB)@btime build_metagraphs(100); 999.743 μs (45901 allocations: 5.08 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); 150.700 μs (0 allocations: 0 bytes)mg2 = build_metagraphs(100);
@btime sum_active_edges_metagraphs($mg2); 442.956 μs (1081 allocations: 16.89 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"#MetaGraph##10#MetaGraph##11", 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"#MetaGraph##10#MetaGraph##11", 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 = Main.MetaGraphsNext::Core.Const(MetaGraphsNext)
│ %3 = Base.getproperty(%2, :edge_labels)::Core.Const(MetaGraphsNext.edge_labels)
│ %4 = (%3)(mg)::Base.Generator{Graphs.SimpleGraphs.SimpleEdgeIter{SimpleGraph{Int64}}, MetaGraphsNext.var"#edge_labels##0#edge_labels##1"{MetaGraph{Int64, SimpleGraph{Int64}, Int64, Bool, Float64, Nothing, MetaGraphsNext.var"#MetaGraph##10#MetaGraph##11", Float64}}}
│ (@_3 = Base.iterate(%4))
│ %6 = @_3::UNION{NOTHING, TUPLE{TUPLE{INT64, INT64}, TUPLE{INT64, INT64}}}
│ %7 = (%6 === nothing)::Bool
│ %8 = Base.not_int(%7)::Bool
└── goto #7 if not %8
2 ┄ %10 = @_3::Tuple{Tuple{Int64, Int64}, Tuple{Int64, Int64}}
│ %11 = Core.getfield(%10, 1)::Tuple{Int64, Int64}
│ %12 = Base.indexed_iterate(%11, 1)::Core.PartialStruct(Tuple{Int64, Int64}, Any[Int64, Core.Const(2)])
│ (li = Core.getfield(%12, 1))
│ (@_5 = Core.getfield(%12, 2))
│ %15 = @_5::Core.Const(2)
│ %16 = Base.indexed_iterate(%11, 2, %15)::Core.PartialStruct(Tuple{Int64, Int64}, Any[Int64, Core.Const(3)])
│ (lj = Core.getfield(%16, 1))
│ %18 = Core.getfield(%10, 2)::Tuple{Int64, Int64}
│ %19 = li::Int64
│ (active_i = Base.getindex(mg, %19))
│ %21 = lj::Int64
│ (active_j = Base.getindex(mg, %21))
│ %23 = li::Int64
│ %24 = lj::Int64
│ (distance_ij = Base.getindex(mg, %23, %24))
│ %26 = active_i::Bool
└── goto #5 if not %26
3 ─ %28 = active_j::Bool
└── goto #5 if not %28
4 ─ %30 = Main.:+::Core.Const(+)
│ %31 = S::Float64
│ %32 = distance_ij::Float64
└── (S = (%30)(%31, %32))
5 ┄ (@_3 = Base.iterate(%4, %18))
│ %35 = @_3::UNION{NOTHING, TUPLE{TUPLE{INT64, INT64}, TUPLE{INT64, INT64}}}
│ %36 = (%35 === nothing)::Bool
│ %37 = Base.not_int(%36)::Bool
└── goto #7 if not %37
6 ─ goto #2
7 ┄ %40 = S::Float64
└── return %40@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::Core.Const(Graphs.edges)
│ %3 = (%2)(mg)::Graphs.SimpleGraphs.SimpleEdgeIter{SimpleGraph{Int64}}
│ (@_3 = Base.iterate(%3))
│ %5 = @_3::UNION{NOTHING, TUPLE{GRAPHS.SIMPLEGRAPHS.SIMPLEEDGE{INT64}, TUPLE{INT64, INT64}}}
│ %6 = (%5 === nothing)::Bool
│ %7 = Base.not_int(%6)::Bool
└── goto #7 if not %7
2 ┄ %9 = @_3::Tuple{Graphs.SimpleGraphs.SimpleEdge{Int64}, Tuple{Int64, Int64}}
│ (e = Core.getfield(%9, 1))
│ %11 = Core.getfield(%9, 2)::Tuple{Int64, Int64}
│ %12 = Main.src::Core.Const(Graphs.src)
│ %13 = e::Graphs.SimpleGraphs.SimpleEdge{Int64}
│ %14 = (%12)(%13)::Int64
│ %15 = Main.dst::Core.Const(Graphs.dst)
│ %16 = e::Graphs.SimpleGraphs.SimpleEdge{Int64}
│ %17 = (%15)(%16)::Int64
│ (i = %14)
│ (j = %17)
│ %20 = Main.MetaGraphs::Core.Const(MetaGraphs)
│ %21 = Base.getproperty(%20, :get_prop)::Core.Const(MetaGraphs.get_prop)
│ %22 = i::Int64
│ (active_i = (%21)(mg, %22, :active))
│ %24 = Main.MetaGraphs::Core.Const(MetaGraphs)
│ %25 = Base.getproperty(%24, :get_prop)::Core.Const(MetaGraphs.get_prop)
│ %26 = j::Int64
│ (active_j = (%25)(mg, %26, :active))
│ %28 = Main.MetaGraphs::Core.Const(MetaGraphs)
│ %29 = Base.getproperty(%28, :get_prop)::Core.Const(MetaGraphs.get_prop)
│ %30 = i::Int64
│ %31 = j::Int64
│ (distance_ij = (%29)(mg, %30, %31, :distance))
│ %33 = active_i::ANY
└── goto #5 if not %33
3 ─ %35 = active_j::ANY
└── goto #5 if not %35
4 ─ %37 = Main.:+::Core.Const(+)
│ %38 = S::ANY
│ %39 = distance_ij::ANY
└── (S = (%37)(%38, %39))
5 ┄ (@_3 = Base.iterate(%3, %11))
│ %42 = @_3::UNION{NOTHING, TUPLE{GRAPHS.SIMPLEGRAPHS.SIMPLEEDGE{INT64}, TUPLE{INT64, INT64}}}
│ %43 = (%42 === nothing)::Bool
│ %44 = Base.not_int(%43)::Bool
└── goto #7 if not %44
6 ─ goto #2
7 ┄ %47 = S::ANY
└── return %47This page was generated using Literate.jl.