Skip to content

Instantly share code, notes, and snippets.

@ExpandingMan
Created August 29, 2022 23:48
Show Gist options
  • Save ExpandingMan/4d51436701f61046ff4016d568427748 to your computer and use it in GitHub Desktop.
Save ExpandingMan/4d51436701f61046ff4016d568427748 to your computer and use it in GitHub Desktop.
basic benchmarks for best-case AbstractTrees iteration
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.
====================================================================================================#
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment