JuliaPerf / BenchmarksGame.jl

Other
43 stars 13 forks source link

Use threads instead of distributed for binarytrees #47

Open KristofferC opened 3 years ago

KristofferC commented 3 years ago

Something like:

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

make(n) = n === 0 ? Node(nothing, nothing) : Node(make(n-1), make(n-1))
check(node) = node.l === nothing ? 1 : 1 + check(node.l) + check(node.r)

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

    long_tree = make(n)

    results = zeros(Int, Threads.nthreads())
    d = 4
    while d <= n
        niter = 1 << (n - d + 4)
        Threads.@threads for _ in 1:niter
            tid = Threads.threadid()
            results[tid] += check(make(d))
        end
        c = sum(results)
        print(io, "$niter\t trees of depth $d\t check: $c\n")
        d += 2
    end

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

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

performs quite a bit better than the submitted benchmark since it avoids spawning a bunch of workers.

non-Jedi commented 3 years ago

I'll check your version's perf out, but in past versions of Julia, multithreading binary-trees was slower than non-parallel code much less the distributed version; something to do with how the allocator behaves with multi-threading afaicr.

KristofferC commented 3 years ago

It was faster for me with 4 threads at least.