# Parallel quicksort openmp

**URL:** <https://discourse.julialang.org/t/parallel-quicksort-openmp/88499>\
**Category:** New to Julia\
**Tags:** parallel, multithreading, sort, sortperm, quicksort\
**Created:** [October 9, 2022, 9:11pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499 "2022-10-09T21:11:20Z")\
**Posts on this page:** 11\
**Page:** 2

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [October 11, 2022, 4:51pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/22 "2022-10-11T16:51:40Z")

</div>

Ok. In this case one may randomize the order of silver application to make sure that the branch prediction plays no role.

---

<div class="post-metadata">

**Author:** ![blackeneth](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/blackeneth/32/10353_2.png) [@blackeneth](https://discourse.julialang.org/u/blackeneth)\
**Post date:** [October 11, 2022, 9:25pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/23 "2022-10-11T21:25:33Z")

</div>

Likely that m is “mid”

---

<div class="post-metadata">

**Author:** ![gitboy16](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gitboy16/32/24906_2.png) [@gitboy16](https://discourse.julialang.org/u/gitboy16)\
**Post date:** [October 12, 2022, 2:36am UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/24 "2022-10-12T02:36:06Z")

</div>

When you do the changes described in that section, does it run ok for you? It does not for me. I have a large memory allocation, and the code is actually slower. I am probably doing something wrong. Showing the full code in that blog would have maybe been better for new people like me who are trying to learn and reproduce their “experiment”.

---

<div class="post-metadata">

**Author:** ![GeoKou](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/geokou/32/43505_2.png) [@GeoKou](https://discourse.julialang.org/u/GeoKou)\
**Post date:** [October 12, 2022, 4:18pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/25 "2022-10-12T16:18:11Z")

</div>

Hello @gitboy16,

To chime in on your issue that your code provides no speedup VS the code provided as a solution.

I found this thread to be helpful: [For loops run SUPER slow in Julia when outside a function - Stack Overflow](https://stackoverflow.com/questions/51990527/for-loops-run-super-slow-in-julia-when-outside-a-function)  
and I believe it provides hints as to why you did not see the expected results in your code.

---

<div class="post-metadata">

**Author:** ![gitboy16](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gitboy16/32/24906_2.png) [@gitboy16](https://discourse.julialang.org/u/gitboy16)\
**Post date:** [October 12, 2022, 5:13pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/26 "2022-10-12T17:13:32Z")

</div>

Hi @GeoKou , thank you for the link but I don’t get it. All my loops are inside functions.

---

<div class="post-metadata">

**Author:** ![GeoKou](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/geokou/32/43505_2.png) [@GeoKou](https://discourse.julialang.org/u/GeoKou)\
**Post date:** [October 12, 2022, 5:30pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/27 "2022-10-12T17:30:50Z")

</div>

It seems, after testing it myself, that the difference that enables the desired behavior is having the “partition” part of the code in its own function.

I think it is not exactly the issue in the thread I sent, but a similar one; by having the while loops in a function that is called on each thread, julia must be putting up “safety” mechanics to prevent any issues (even though the code is written in a way that no such issues should arise), and this slowdown is removed by having the while loops (the partition function) in their own function.

---

<div class="post-metadata">

**Author:** ![gitboy16](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gitboy16/32/24906_2.png) [@gitboy16](https://discourse.julialang.org/u/gitboy16)\
**Post date:** [October 12, 2022, 6:12pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/28 "2022-10-12T18:12:16Z")

</div>

Ok let’s assume you are right, then if you look at the blog sent by @blackeneth you can see that the parallel mergesort has a loop in function body and the code is running perfectly fine in parallel. So how do you explain this?

---

<div class="post-metadata">

**Author:** ![gitboy16](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gitboy16/32/24906_2.png) [@gitboy16](https://discourse.julialang.org/u/gitboy16)\
**Post date:** [October 12, 2022, 6:19pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/29 "2022-10-12T18:19:45Z")

</div>

Also, interestingly if we move the 2 while loops in mergesort to a function and call that function inside parallel merge sort then it slows down the function. So we have here the opposite effect 🤔

---

<div class="post-metadata">

**Author:** ![pitsianis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pitsianis/32/26588_2.png) [@pitsianis](https://discourse.julialang.org/u/pitsianis)\
**Post date:** [October 13, 2022, 9:16pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/30 "2022-10-13T21:16:47Z")

</div>

I spawned a new thread, with the two codes in one, here:

> [@@spawn large memory allocation reduced when some code abstracted out in a function](https://discourse.julialang.org/t/spawn-large-memory-allocation-reduced-when-some-code-abstracted-out-in-a-function/88691):
>
> In another discussion, [https://discourse.julialang.org/t/parallel-quicksort-openmp/88499](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499) bizarre behavior that requires further attention and explanation came up. A recursive textbook implementation of quicksort makes no memory allocations as it modifies its argument input vector. However, the straightforward parallelization by @spawning the first recursive call results in a large number and volume of memory allocations. As a result, the parallel code is slower than the sequential. The above …

@gitboy16 or anybody else, please post there the mergesort with the opposite behavior.

---

<div class="post-metadata">

**Author:** ![PetrKryslUCSD](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/petrkryslucsd/32/215825_2.png) [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)\
**Post date:** [March 24, 2023, 5:26pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/31 "2023-03-24T17:26:14Z")

</div>

This is a nice piece of code. I hope I have your permission to borrow it? Thanks.

---

<div class="post-metadata">

**Author:** ![pitsianis](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pitsianis/32/26588_2.png) [@pitsianis](https://discourse.julialang.org/u/pitsianis)\
**Post date:** [March 24, 2023, 8:26pm UTC](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499/32 "2023-03-24T20:26:47Z")

</div>

Absolutely!

I teach for 25 years a Parallel Computing class to advanced engineering students. I’ve been toying with the idea of using Julia as a common “algorithmic notation” to describe parallel algorithms and ideas, --executable pseudocode-- as I call it 🙂

Since Julia 1.8, I think I got all I need.

[Previous page](https://discourse.julialang.org/t/parallel-quicksort-openmp/88499.md?page=1)