Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use threads instead of distributed for binarytrees #47

Open
KristofferC opened this issue Apr 22, 2021 · 2 comments
Open

Use threads instead of distributed for binarytrees #47

KristofferC opened this issue Apr 22, 2021 · 2 comments

Comments

@KristofferC
Copy link
Collaborator

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
Copy link
Contributor

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
Copy link
Collaborator Author

It was faster for me with 4 threads at least.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants