Benchmark game binary-trees

binarytrees.jl

using BenchmarkTools

struct Node
    l::Union{Node,Nothing}
    r::Union{Node,Nothing}
end

function make(n)
    n === 0 ? Node(nothing, nothing) : Node(make(n - 1), make(n - 1))
end

function check(node)
    node.l === nothing ? 1 : 1 + check(node.l) + check(node.r)
end

function binary_trees_serial(io, n)
    write(io, "stretch tree of depth $(n+1)\t check: $(check(make(n+1)))\n")

    long_tree::Node = make(n)

    d = 4
    while d <= n
        niter = 1 << (n - d + 4)
        c = 0
        for _ = 1:niter
            c += check(make(d))
        end
        write(io, "$niter\t trees of depth $d\t check: $c\n")
        d += 2
    end

    write(io, "long lived tree of depth $n\t check: $(check(long_tree))\n")
end#function

function binary_trees_parallel(io, n)
    write(io, "stretch tree of depth $(n+1)\t check: $(check(make(n+1)))\n")

    long_tree::Node = make(n)

    d = 4
    while d <= n
        niter = 1 << (n - d + 4)
        ct = Vector{Int}(undef, niter)
        let d = d
            Threads.@threads for i = 1:niter
                ct[i] = check(make(d))
            end
        end
        c = sum(ct)
        write(io, "$niter\t trees of depth $d\t check: $c\n")
        d += 2
    end

    write(io, "long lived tree of depth $n\t check: $(check(long_tree))\n")
end#function

function binary_trees_parallel_gc(io, n)
    write(io, "stretch tree of depth $(n+1)\t check: $(check(make(n+1)))\n")

    long_tree::Node = make(n)

    d = 4
    while d <= n
        niter = 1 << (n - d + 4)
        ct = Vector{Int}(undef, niter)
        GC.enable(false)
        let d = d
            Threads.@threads for i = 1:niter
                ct[i] = check(make(d))
            end
        end
        GC.enable(true)
        GC.gc(false)
        c = sum(ct)
        write(io, "$niter\t trees of depth $d\t check: $c\n")
        d += 2
    end

    write(io, "long lived tree of depth $n\t check: $(check(long_tree))\n")
end#function

isinteractive() || @time binary_trees_parallel_gc(stdout, parse(Int, ARGS[1]))

#= @btime binary_trees_serial(devnull, 21) samples=3
@btime binary_trees_parallel(devnull, 21) samples=3
@btime binary_trees_parallel_gc(devnull, 21) samples=3 =#