The Computer Language
22.05 Benchmarks Game

binary-trees Julia #3 program

source code

# The Computer Language Benchmarks Game
# https://salsa.debian.org/benchmarksgame-team/benchmarksgame/
#
# Contributed by Joonas Muhonen. Based on code by Adam Beckmeyer, Jarret Revels, Alex
# Arslan, Michal Stransky, Jens Adam.

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

mutable struct Latch
    count::Int
    cond::Threads.Condition
end

function Latch(n::Int)::Latch
    Latch(n,Threads.Condition())
end

function countDown(latch::Latch)
    lock(latch.cond) do
        latch.count -= 1
        notify(latch.cond)
    end
end

function await(latch::Latch)
    lock(latch.cond)
    try
        while latch.count != 0
            wait(latch.cond)
        end
    finally
        unlock(latch.cond)
    end
end

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

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

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

    long_tree::Node = make(n)

    minDepth::Int = 4
    resultSize::Int = trunc(Int,(n - minDepth) / 2 ) + 1
    results = Vector{String}(undef,resultSize)
    latch::Latch = Latch(resultSize)
    Threads.@threads for depth::Int = minDepth:2:n
        c::Int = 0
        niter::Int = 1 << (n - depth + minDepth)
        lk::ReentrantLock = ReentrantLock()
        Threads.@threads for _ = 1:niter
            lock(lk) do
                c+=check(make(depth))
            end
        end#for
        index::Int = trunc(Int,(depth - minDepth)/2) + 1
        results[index] = "$niter\t trees of depth $depth\t check: $c\n"
        countDown(latch)
    end
    await(latch)
    for i in results
        write(io,i)
    end

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

isinteractive() || binary_trees(stdout, parse(Int, ARGS[1])) 
    

notes, command-line, and program output

NOTES:
64-bit Ubuntu quad core
julia version 1.7.2


Wed, 04 May 2022 20:49:37 GMT

MAKE:
printenv JULIA_NUM_THREADS
4

0.12s to complete and log all make actions

COMMAND LINE:
/opt/src/julia-1.7.2/bin/julia -O3 --cpu-target=ivybridge --math-mode=ieee -p4 -- binarytrees.julia-3.julia 21

PROGRAM OUTPUT:
stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303