# \[ANN\] ThreadsX.jl: Parallelized Base functions

**URL:** <https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666>\
**Category:** Package Announcements\
**Tags:** package, announcement, parallel\
**Created:** [March 29, 2020, 5:40am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666 "2020-03-29T05:40:14Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 30, 2020, 3:01pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/21 "2020-03-30T15:01:16Z")

</div>

This benchmark really runs for a while … 🙂

Here’s an intermediate result, running with `JULIA_NUM_THREADS=64` on a 64-code (128 hyperthreads) Epyc-2.

![sort_agg_plot](https://global.discourse-cdn.com/julialang/original/3X/c/1/c1aa1df497cebad63f29c694764f30df5a23cae8.png)

![fold_agg_plot](https://global.discourse-cdn.com/julialang/original/3X/b/0/b0bd8bfc8a6d6d282f978d987b27160425b7f946.png)

After this is through, I’ll try to run one more time with thread-pinning, to make sure Linux doesn’t assign two Julia threads to the same physical core. Shouldn’t happen, usually, under high load if other cores are free, but …

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 30, 2020, 10:22pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/22 "2020-03-30T22:22:27Z")

</div>

Awesome! Thanks a lot for running the benchmark. It looks a lot better than mine 🙂 It’s especially nice to see many reduce-like benchmarks can follow the scaling “upper bound” `sum_sin` with somewhat large number of threads (~15?).

By the way, I think this is from Julia 1.4 or 1.3, right? I’m having trouble determining the source of deadlock in quicksort [QuickSort hangs · Issue #104 · tkf/ThreadsX.jl · GitHub](https://github.com/tkf/ThreadsX.jl/issues/104) so I’d like to know when the deadlock happens or does not happen.

> [@oschulz](#):
>
> This benchmark really runs for a while …

Sorry, I forgot to remove some very excessive/redundant benchmarks 😅… I should’ve optimized it a bit more.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 30, 2020, 10:27pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/23 "2020-03-30T22:27:34Z")

</div>

Running with Julia v1.4 (almost done).

@tkf, I’d like to re-run this with thread pinning, but with the benchmark running for so long, is there a way to specify (e.g. via an array of number of threads) on how many threads to test? Like, `[1, 2, 3, 4, 6, ...., 20, 25, 30, ...]`?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 30, 2020, 10:32pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/24 "2020-03-30T22:32:25Z")

</div>

You can pass the list of threads to try like `ThreadsXBenchmarks.run_all("OUTDIR", nthreads_range=[1, 2, 3, ...])`. But I think I can speedup each benchmark more.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 30, 2020, 10:35pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/25 "2020-03-30T22:35:58Z")

</div>

I think this `opt` branch reduces benchmark time: [GitHub - tkf/ThreadsXBenchmarks.jl at opt](https://github.com/tkf/ThreadsXBenchmarks.jl/tree/opt) (I haven’t tried it myself yet)

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 30, 2020, 11:36pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/26 "2020-03-30T23:36:50Z")

</div>

Will run overnight with the opt branch.

Have to re-run anyhow, turns out there was some low-priority numerical tasks running in parallel that grabbed time on hyper-threads - after I paused them, performance went up. Here are the plots:

![sort_agg_plot](https://global.discourse-cdn.com/julialang/original/3X/2/a/2ab4b4eb5a1d8bb735a091bb28d31e9d0b671920.png)

![fold_agg_plot](https://global.discourse-cdn.com/julialang/original/3X/e/d/ed4da33053704f889a71d71399a27f85c1db5c7f.png)

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 30, 2020, 11:37pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/27 "2020-03-30T23:37:31Z")

</div>

The jump at the end is due to pausing those other processes.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 30, 2020, 11:41pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/28 "2020-03-30T23:41:25Z")

</div>

> [@oschulz](#):
>
> performance went up

That’s great 😆

By the way, the `opt` branch is not compatible with the plotting script. I’ll fix it later today.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 31, 2020, 12:05am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/29 "2020-03-31T00:05:24Z")

</div>

Ok, started with “opt”, I’ll see if I can run with `1:1:64` threads to get full detail. I pinned the threads now, should ensure one thread on each physical core. Night here now, hope I have results for you tomorrow.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [March 31, 2020, 7:11am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/30 "2020-03-31T07:11:00Z")

</div>

> [@tkf](#):
>
> But I think at this point it’s probably more straight forward to add threading support to LoopVectorization.jl API. @Elrod What do you think?

Yes, I should add an `@avx_threaded` macro that breaks up (what it chooses as) the outer most loop into `Threads.nthreads()` chunks and uses `@spawn`.  
The trickiest part would be having it support reductions. It’d be nice if, for example, we could define a threaded 3-arg dot product like this:

```julia
function mydot(x, A, y)
    s = zero(promote_type(eltype(x), eltype(A), eltype(y)))
    @avx_threaded for m in 1:size(A,1), n in 1:size(A,2)
        s += x[m] * A[m,n] * y[n]
    end
    s
end

```

or maybe

```julia
function mydot(x, A, y)
    s = zero(promote_type(eltype(x), eltype(A), eltype(y)))
    @avx threads=true for m in 1:size(A,1), n in 1:size(A,2)
        s += x[m] * A[m,n] * y[n]
    end
    s
end

```

I’ll try and get around to it in the next few weeks. (If anyone has an API preference, please let me know! I’m leaning towards the `threads=true`)

EDIT:  
If folks are curious about the hangs, it seems to be a problem with Julia master. I could not reproduce on Julia 1.4, nor could I on the master branch from November. I’m running a script by @tkf now to automate bisecting.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 31, 2020, 8:02am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/31 "2020-03-31T08:02:37Z")

</div>

Hey, @tkf, benchmark ran through quite quickly (in comparison to before), took about 2 hours for 1 to 64 threads. Did you have a chance to update the plotting script yet?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 31, 2020, 8:03am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/32 "2020-03-31T08:03:24Z")

</div>

Yeah, I just pushed to `opt` branch. It worked with a small dataset in my laptop.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 31, 2020, 8:08am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/33 "2020-03-31T08:08:04Z")

</div>

> [@Elrod](#):
>
> breaks up (what it chooses as) the outer most loop into `Threads.nthreads()` chunks and uses `@spawn`

I guess you are assuming that the outer most axis is much longer than `Threads.nthreads()` and the work load per element is more-or-less constant? I suppose that’s reasonable when the user is asking to vectorize the loop. But, if you want to parallelize all but the inner most axis, it may be useful to use `halve` function from [SplittablesBase.jl](https://github.com/tkf/SplittablesBase.jl) (which can handle `IndexCartesian`-style arrays and `zip` of them). This is how I support something like `ThreadsX.foreach(f, A, A')`. I think this approach is flexible enough to handle “non-rectangular” iterations like upper-triangular part of the matrix.

> [@Elrod](#):
>
> The trickiest part would be having it support reductions.

It’s interesting as I thought reduction would be the easiest part as there is no mutation (e.g., it sounds hard to chunk the iteration space appropriately to avoid simultaneously writing to the shared region). Though maybe there are something subtle when mixing with vectorization? Naively, I’d imagine it’d be implemented as a transformation to `mapreduce`:

1. Separate the loop body to the mapping (`(m, n) -> x[m] * A[m,n] * y[n]`) and reduction (`+`) parts and generate functions for them.
2. Determine unroll factor and SIMD vector width.
3. Feed those functions and parameters to parallelized and vectorized `mapreduce`.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 31, 2020, 8:16am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/34 "2020-03-31T08:16:39Z")

</div>

> [@tkf](#):
>
> Yeah, I just pushed to `opt` branch. It worked with a small dataset in my laptop.

Thanks - here we go 🙂

![sort_agg_plot](https://global.discourse-cdn.com/julialang/original/3X/1/1/119edeb99ad43baf31a04ff05d805461fbda0d92.png)

![fold_agg_plot](https://global.discourse-cdn.com/julialang/original/3X/e/f/ef0a5364b74182413155ad71d285e3c25c2da448.png)

System info: Julia v1.4 (official build), AMD EPYC 7702P, 512 GB RAM, 64 Julia threads pinned to 64 physical cores, no VM, running in a Singularity container (should not have a performance impact).

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 31, 2020, 8:25am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/35 "2020-03-31T08:25:13Z")

</div>

I wonder if the CPU is starting to clock down a bit above 40 threads on the sum\_sin benchmark, or if we’re starting to see the Julia thread-scheduler overhead there.

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 31, 2020, 8:26am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/36 "2020-03-31T08:26:13Z")

</div>

The merge sort scaling is also interesting - threads fighting over cache?

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [March 31, 2020, 11:15pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/37 "2020-03-31T23:15:50Z")

</div>

Thanks a lot for doing the benchmarks! I wish I had access to this monster machine so that I can debug the saturation/degradation in the performance.

> [@oschulz](#):
>
> The merge sort scaling is also interesting - threads fighting over cache?

I wonder if you can spot something with `perf stat` (when changing `JULIA_NUM_THREADS`). For digging into single-thread performance it’s useful sometimes. Not sure if it’s the best way to do this but I usually run something like this:

```julia
function perf(f, args)
    pid = getpid()
    cmd = `perf $args --pid=$pid`
    proc = run(pipeline(cmd, stdout=stdout, stderr=stderr); wait=false)
    try
        return f()
    finally
        flush(stdout)
        flush(stderr)
        kill(proc, Base.SIGINT)
        wait(proc)
    end
end

using BenchmarkTools, ThreadsX
b = @benchmarkable ThreadsX.sort($(rand(0:0.01:1, 1_000_000)); alg=MergeSort)
tune!(b)

perf(`stat -ddd`) do
    run(b)
end |> display

```

---

<div class="post-metadata">

**Author:** ![oschulz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oschulz/32/2998_2.png) [@oschulz](https://discourse.julialang.org/u/oschulz)\
**Post date:** [March 31, 2020, 11:51pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/38 "2020-03-31T23:51:49Z")

</div>

Hi @tfk, you’re very welcome, I think really like your work on ThreadsX and Transducers. Also, I guess Julia’s new multit-hreading hasn’t often been torture-tested at that level so far, so maybe we can learn lot’s of interesting things here.

Only problem, looks like I don’t have perf available in my container instance … gimme a day or so, need to add that.

---

<div class="post-metadata">

**Author:** ![tkf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkf/32/17635_2.png) [@tkf](https://discourse.julialang.org/u/tkf)\
**Post date:** [April 1, 2020, 1:54am UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/39 "2020-04-01T01:54:05Z")

</div>

It’s great to hear that you like it!

> [@oschulz](#):
>
> Only problem, looks like I don’t have perf available in my container instance

Please don’t worry about it. (Though it’d be nice if you remember it when you are very board or something.) I guess debugging performance problem is very hard with “asynchronous” dialog like this.

---

<div class="post-metadata">

**Author:** ![cscherrer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cscherrer/32/7631_2.png) [@cscherrer](https://discourse.julialang.org/u/cscherrer)\
**Post date:** [April 1, 2020, 4:28pm UTC](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666/40 "2020-04-01T16:28:58Z")

</div>

This looks great! I wonder… In Python, everyone does `import numpy as np` to load numeric Python. Then an `autograd` package came along. To make it easy to use, they suggest `import autograd.numpy as np`, so you don’t have to change the rest of the file at all.

Could an approach like this work for ThreadsX?

[Previous page](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666.md?page=1)

[Next page](https://discourse.julialang.org/t/ann-threadsx-jl-parallelized-base-functions/36666.md?page=3)