# Multithreading shuffle

**URL:** <https://discourse.julialang.org/t/multithreading-shuffle/42699>\
**Category:** General Usage\
**Created:** [July 8, 2020, 12:29am UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699 "2020-07-08T00:29:27Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![hros](https://avatars.discourse-cdn.com/v4/letter/h/97f17d/32.png) [@hros](https://discourse.julialang.org/u/hros)\
**Post date:** [July 8, 2020, 12:29am UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/1 "2020-07-08T00:29:27Z")

</div>

I wanted to port a parallel in-place shuffle algorithm, mergeshuffle:  
[paper](https://arxiv.org/pdf/1508.03167.pdf), [repo](https://github.com/axel-bacher/mergeshuffle)  
it basically works by splitting the array into `k` subarrays, shuffling them in parallel. Followed by merging neighboring subarrays (in a parallel tree like fashion) in such a way that creates a global random permutation.  
The C code is very straightforward, consisting of two routines:  
[shuffle.c](https://github.com/axel-bacher/mergeshuffle/blob/master/merge_omp.c), [merge.c](https://github.com/axel-bacher/mergeshuffle/blob/master/merge.c) (optionally an optimized assembly version [merge.s](https://github.com/axel-bacher/mergeshuffle/blob/master/merge.s))

I’ve created a Julia port of these functions replacing the openmp pragmas (`#pragma omp parallel for`) with Julia’s `Threads.@threads` (hoping that Julia’s macro will be just as simple and effective as openmp’s).  
Following the [docs](https://docs.julialang.org/en/v1/manual/parallel-computing/index.html#Side-effects-and-mutable-function-arguments-1) I created an array of random number generators using a different one in each thread.  
My code: [mergeshuffle.jl](https://gist.github.com/hros/b5703fa2da2c1cca25dfc2a0c54ab65a)

However, this version was slower than the sequential `shuffle!` (and even from a naive sequential implementation)  
The results of shuffling a 10,000,000 array using 16 threads on a powerful server:

```julia
nthreads = 16
  0.453090 seconds (135.32 k allocations: 6.736 MiB)
  1.117024 seconds (936.77 k allocations: 45.491 MiB, 0.95% gc time)
  0.254580 seconds (61.56 k allocations: 3.357 MiB)

```

where the first line is a naive Fisher-Yates shuffle, the second line corresponds to the mergeshuffle (the C implementation is much faster than the serial Fisher-Yates), and the 3rd line is Julia’s sequential but optimized shuffle!

It should be noted that varying the number of threads did have a (relative) impact:

| nthreads | time |
| --- | --- |
| 1 | 2.574 |
| 2 | 1.652 |
| 4 | 1.242 |
| 8 | 1.195 |
| 16 | 1.117 |
| 32 | 1.121 |
| 64 | 1.045 |

What can I do to improve the absolute performance of the parallel random permutation algorithm?  
Additionally, is the RNG threading hack still necessary in version 1.5?

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [July 8, 2020, 1:49am UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/2 "2020-07-08T01:49:00Z")

</div>

instead of @time, use BenchmarkTools

`@benchmark`

Which will run the code several times. It might be that you’re mostly measuring the first-call compile time, and the benchmark tools does a good job of getting more reliable stats.

---

<div class="post-metadata">

**Author:** ![hros](https://avatars.discourse-cdn.com/v4/letter/h/97f17d/32.png) [@hros](https://discourse.julialang.org/u/hros)\
**Post date:** [July 8, 2020, 1:48pm UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/3 "2020-07-08T13:48:42Z")

</div>

Thanks for your comment  
Unfortunately, the problem in this experiment is not due to the “measurement device”.  
You can see that my file has a `using BenchmarkTools` at the top, and initially I used `@btime`.  
I switched to using `@time` because it runs much faster and the fluctuations are not significant.  
I’d appreciate any ideas of how to get the code to run faster.  
I profiled the routine, and it seems that most of the time is dedicated to indexing which is reasonable.

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [July 8, 2020, 2:16pm UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/4 "2020-07-08T14:16:32Z")

</div>

My guess is that this is memory bandwidth limited and so a sequential algorithm can be as fast as anything. the fact that it spends most of its time indexing suggests that’s true. parallel may be pointless or even cache harmful here.

---

<div class="post-metadata">

**Author:** ![mikkoku](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikkoku/32/16274_2.png) [@mikkoku](https://discourse.julialang.org/u/mikkoku)\
**Post date:** [July 8, 2020, 5:41pm UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/5 "2020-07-08T17:41:47Z")

</div>

I tried your code and glanced at the paper.  
Looking more closely at the profiler output tells me that ~70% of time is spent on line 40

```julia
@views shuffle!(r, v[1:i])

```

which according to the paper should be negligible.

---

<div class="post-metadata">

**Author:** ![stillyslalom](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stillyslalom/32/45687_2.png) [@stillyslalom](https://discourse.julialang.org/u/stillyslalom)\
**Post date:** [July 8, 2020, 6:28pm UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/6 "2020-07-08T18:28:59Z")

</div>

Have you tried this on v1.5? This may have been fixed by [https://github.com/JuliaLang/julia/pull/34126](https://github.com/JuliaLang/julia/pull/34126)

\*\*edit: for v1.4 vs. v1.5, I see the following results on my machine (with four threads):

```julia
julia> @time mergeshuffle!(PAR_RNG, v)
  1.274356 seconds (1.27 k allocations: 75.406 KiB) # v1.4

```

```julia
julia> @time mergeshuffle!(PAR_RNG, v)
  1.419680 seconds (485 allocations: 40.422 KiB) # v1.5

```

So the number of allocations is indeed reduced, but performance actually decreases in v1.5.

---

<div class="post-metadata">

**Author:** ![hros](https://avatars.discourse-cdn.com/v4/letter/h/97f17d/32.png) [@hros](https://discourse.julialang.org/u/hros)\
**Post date:** [July 9, 2020, 10:06pm UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/7 "2020-07-09T22:06:00Z")

</div>

thanks!  
I had a typo when converting from C, the corrected line reads:  
`@views shuffle!(r, v[i:n])` (I’ve updated the gist)  
The run times have improved…  
but it is almost as fast as the sequential Fisher Yates version when using 16 threads, and much slower than the builtin sequential `shuffle!`

looking at the profiler output it seems most of the time is spent on `rand(::MersenneTwister, ::Rando...` calls

Any suggestions how to speed up the random bit generation?

---

<div class="post-metadata">

**Author:** ![mikkoku](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mikkoku/32/16274_2.png) [@mikkoku](https://discourse.julialang.org/u/mikkoku)\
**Post date:** [July 10, 2020, 6:31am UTC](https://discourse.julialang.org/t/multithreading-shuffle/42699/8 "2020-07-10T06:31:32Z")

</div>

I think rand(Bool) would be a bit faster than rand(0:1), but it still uses atleast 32 random bits.

```julia
bitrand

```

sounds promising.