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

The 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);

  508.635 μs (458 allocations: 744.16 KiB)

@btime build_bulk_metagraphsnext(100);

  272.271 μs (274 allocations: 998.67 KiB)

@btime build_metagraphs(100);

  1.145 ms (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
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);

  190.668 μs (0 allocations: 0 bytes)

mg2 = build_metagraphs(100);
@btime sum_active_edges_metagraphs($mg2);

  490.360 μs (1540 allocations: 24.06 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::UNION{NOTHING, TUPLE{TUPLE{INT64, INT64}, TUPLE{INT64, INT64}}}
│   %6  = (%5 === nothing)::Bool
│   %7  = Base.not_int(%6)::Bool
└──       goto #7 if not %7
2 ┄ %9  = @_3::Tuple{Tuple{Int64, Int64}, Tuple{Int64, Int64}}
│   %10 = Core.getfield(%9, 1)::Tuple{Int64, Int64}
│   %11 = Base.indexed_iterate(%10, 1)::Core.PartialStruct(Tuple{Int64, Int64}, Any[Int64, Core.Const(2)])
│         (li = Core.getfield(%11, 1))
│         (@_5 = Core.getfield(%11, 2))
│   %14 = @_5::Core.Const(2)
│   %15 = Base.indexed_iterate(%10, 2, %14)::Core.PartialStruct(Tuple{Int64, Int64}, Any[Int64, Core.Const(3)])
│         (lj = Core.getfield(%15, 1))
│   %17 = Core.getfield(%9, 2)::Tuple{Int64, Int64}
│   %18 = li::Int64
│         (active_i = Base.getindex(mg, %18))
│   %20 = lj::Int64
│         (active_j = Base.getindex(mg, %20))
│   %22 = li::Int64
│   %23 = lj::Int64
│         (distance_ij = Base.getindex(mg, %22, %23))
│   %25 = active_i::Bool
└──       goto #5 if not %25
3 ─ %27 = active_j::Bool
└──       goto #5 if not %27
4 ─ %29 = S::Float64
│   %30 = distance_ij::Float64
└──       (S = %29 + %30)
5 ┄       (@_3 = Base.iterate(%3, %17))
│   %33 = @_3::UNION{NOTHING, TUPLE{TUPLE{INT64, INT64}, TUPLE{INT64, INT64}}}
│   %34 = (%33 === nothing)::Bool
│   %35 = Base.not_int(%34)::Bool
└──       goto #7 if not %35
6 ─       goto #2
7 ┄ %38 = S::Float64
└──       return %38

@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 = MetaGraphs.get_prop::Core.Const(MetaGraphs.get_prop)
│   %21 = i::Int64
│         (active_i = (%20)(mg, %21, :active))
│   %23 = MetaGraphs.get_prop::Core.Const(MetaGraphs.get_prop)
│   %24 = j::Int64
│         (active_j = (%23)(mg, %24, :active))
│   %26 = MetaGraphs.get_prop::Core.Const(MetaGraphs.get_prop)
│   %27 = i::Int64
│   %28 = j::Int64
│         (distance_ij = (%26)(mg, %27, %28, :distance))
│   %30 = active_i::ANY
└──       goto #5 if not %30
3 ─ %32 = active_j::ANY
└──       goto #5 if not %32
4 ─ %34 = S::ANY
│   %35 = distance_ij::ANY
└──       (S = %34 + %35)
5 ┄       (@_3 = Base.iterate(%3, %11))
│   %38 = @_3::UNION{NOTHING, TUPLE{GRAPHS.SIMPLEGRAPHS.SIMPLEEDGE{INT64}, TUPLE{INT64, INT64}}}
│   %39 = (%38 === nothing)::Bool
│   %40 = Base.not_int(%39)::Bool
└──       goto #7 if not %40
6 ─       goto #2
7 ┄ %43 = S::ANY
└──       return %43

This page was generated using Literate.jl.