basic benchmarks for best-case AbstractTrees iteration

tree_benchmarks.jl

using AbstractTrees, BenchmarkTools, Random
using AbstractTrees: PreOrderState, next

using Base: @kwdef


@kwdef struct RandTreeParams
    max_generations::Int = 5
    max_children::Int = 3
end


struct Node
    value::Float64
    children::Vector{Node}
end

AbstractTrees.children(n::Node) = n.children
AbstractTrees.nodevalue(n::Node) = n.value
AbstractTrees.NodeType(::Type{<:Node}) = HasNodeType()
AbstractTrees.nodetype(::Type{<:Node}) = Node


function randnode(rng::AbstractRNG=Xoshiro(999), g::Integer=1, params::RandTreeParams=RandTreeParams())
    x = randn(rng)
    if g < params.max_generations
        ch = [randnode(rng, g+1, params) for i ∈ 1:rand(rng, 1:params.max_children)]
        Node(x, ch)
    else
        Node(x, [])
    end
end

function bench1(arg=PreOrderDFS, seed::Integer=999)
    @benchmark iterate(itr) setup=begin
        itr = $seed |> Xoshiro |> randnode |> $arg
    end
end

function bench2(arg=PreOrderDFS, seed::Integer=999)
    @benchmark sum(nodevalue, itr) setup=begin
        itr = $seed |> Xoshiro |> randnode |> $arg
    end
end


#====================================================================================================
       Results - latest

◖◗ bench1()
BenchmarkTools.Trial: 10000 samples with 985 evaluations.
 Range (min … max):  54.102 ns …   3.816 μs  ┊ GC (min … max):  0.00% … 97.68%
 Time  (median):     57.752 ns               ┊ GC (median):     0.00%
 Time  (mean ± σ):   69.270 ns ± 196.199 ns  ┊ GC (mean ± σ):  15.41% ±  5.34%

      ▅█▆▅▃
  ▂▂▄██████▇▅▄▃▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▁▂▂▁▂▂▂▂▂▁▂▂▂▂▂▂▂▂▂▂▂ ▃
  54.1 ns         Histogram: frequency by time           87 ns <

 Memory estimate: 144 bytes, allocs estimate: 3.

◖◗ bench2()
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  13.926 μs …  3.165 ms  ┊ GC (min … max):  0.00% … 98.38%
 Time  (median):     15.249 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   17.811 μs ± 76.740 μs  ┊ GC (mean ± σ):  10.38% ±  2.40%

      ▂▅▇██▅▃
  ▁▂▃▆████████▆▅▃▃▂▂▁▁▁▁▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  13.9 μs         Histogram: frequency by time        22.9 μs <

 Memory estimate: 26.52 KiB, allocs estimate: 413.

◖◗ bench1(PostOrderDFS)
BenchmarkTools.Trial: 10000 samples with 222 evaluations.
 Range (min … max):  336.077 ns …  11.857 μs  ┊ GC (min … max):  0.00% … 95.37%
 Time  (median):     352.284 ns               ┊ GC (median):     0.00%
 Time  (mean ± σ):   414.037 ns ± 763.620 ns  ┊ GC (mean ± σ):  13.52% ±  7.05%

   ▄▇██▇▅▄▃▃▂▂▁▁▁                                               ▂
  ███████████████▇▆▆▅▅▃▅▁▅▁▃▃▁▁▄▁▁▄▁▁▁▃▄▅▄▃▃▃▄▅▅▁▅▅▅▅▅▆▆▅▆▇▆▆▅▅ █
  336 ns        Histogram: log(frequency) by time        569 ns <

 Memory estimate: 1.12 KiB, allocs estimate: 14.

◖◗ bench2(PostOrderDFS)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  10.790 μs …  3.314 ms  ┊ GC (min … max):  0.00% … 98.28%
 Time  (median):     11.602 μs              ┊ GC (median):     0.00%
 Time  (mean ± σ):   14.134 μs ± 80.053 μs  ┊ GC (mean ± σ):  13.70% ±  2.41%

  ▁▄▆████▇▆▅▄▄▂▂▂▁▁▁▁ ▁▂▁▁▂▂▁▁▁▂▁▂▂▂▁▁▂▁ ▁  ▁                 ▃
  ████████████████████████████████████████████▇▇▇█▆▆▅▆▅▅▄▅▄▃▃ █
  10.8 μs      Histogram: log(frequency) by time      18.5 μs <

 Memory estimate: 23.66 KiB, allocs estimate: 386.
====================================================================================================#

#====================================================================================================
       Results - this PR

◖◗ bench1()
BenchmarkTools.Trial: 10000 samples with 982 evaluations.
 Range (min … max):  60.581 ns …   4.202 μs  ┊ GC (min … max):  0.00% … 97.03%
 Time  (median):     64.990 ns               ┊ GC (median):     0.00%
 Time  (mean ± σ):   77.914 ns ± 191.807 ns  ┊ GC (mean ± σ):  14.43% ±  5.74%

  ▁▂▅▇███▆▄▄▃▃▂▁▁▁                                             ▂
  █████████████████▇▆▇▆▅▅▆▁▄▅▆▇█▇▇▇▇▇▇▇▇▇▆▇▅▆▇▇▇▇▇▇▇▇▇▆▅▆▆▅▆▇▇ █
  60.6 ns       Histogram: log(frequency) by time       108 ns <

 Memory estimate: 160 bytes, allocs estimate: 5.

◖◗ bench2()
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  19.526 μs …  3.991 ms  ┊ GC (min … max): 0.00% … 98.35%
 Time  (median):     20.739 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   22.281 μs ± 68.152 μs  ┊ GC (mean ± σ):  5.24% ±  1.70%

    ▁▃▄▅▆▆▇▇███▇▆▅▃▃        ▁▁▁▁   ▁▁▂▂▂▂▂▁▂ ▁▁▁▁             ▃
  ▇▇██████████████████▇█▇▇▇▇█████▇▇█████████████████▇▇▇▆▇▆▅▅▅ █
  19.5 μs      Histogram: log(frequency) by time      25.8 μs <

 Memory estimate: 15.00 KiB, allocs estimate: 545.

◖◗ bench1(PostOrderDFS)
BenchmarkTools.Trial: 10000 samples with 186 evaluations.
 Range (min … max):  556.204 ns … 22.454 μs  ┊ GC (min … max): 0.00% … 96.51%
 Time  (median):     579.849 ns              ┊ GC (median):    0.00%
 Time  (mean ± σ):   640.868 ns ±  1.097 μs  ┊ GC (mean ± σ):  8.81% ±  5.00%

         ▄▇██▆▅▂
  ▂▂▂▃▅▆████████▇▆▄▃▃▃▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂▂▂▂▁▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂ ▃
  556 ns          Histogram: frequency by time          691 ns <

 Memory estimate: 656 bytes, allocs estimate: 19.

◖◗ bench2(PostOrderDFS)
BenchmarkTools.Trial: 10000 samples with 1 evaluation.
 Range (min … max):  19.006 μs …  3.982 ms  ┊ GC (min … max): 0.00% … 98.66%
 Time  (median):     19.988 μs              ┊ GC (median):    0.00%
 Time  (mean ± σ):   20.869 μs ± 39.642 μs  ┊ GC (mean ± σ):  1.88% ±  0.99%

   ▂▅▆▇███▇▆▅▃▁       ▁▁▁▂▁▁▂▂▂▂▁▁▂▁▁ ▁▁                      ▂
  ▅███████████████▇▇█████████████████████▇▇▇▆▆▆▆▅▆▆▄▅▅▅▅▅▄▅▄▄ █
  19 μs        Histogram: log(frequency) by time      27.3 μs <

 Memory estimate: 15.11 KiB, allocs estimate: 549.
====================================================================================================#