# Parallel merge in Cilk+ vs Julia
**URL:** https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903
**Category:** Julia at Scale
**Created:** [February 20, 2020, 1:31pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903 "2020-02-20T13:31:25Z")
**Posts on this page:** 19
**Page:** 1
### Author:  [@eaubanel](https://discourse.julialang.org/u/eaubanel)
#### Post date: [February 20, 2020, 1:31pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/1 "2020-02-20T13:31:25Z")
As my first Julia program, I had some fun debugging a Julia implementation of a parallel merge, which I had already developed in Cilk+. I thought I’d make my first post by pointing the following out to warn others developing divide and conquer algorithms with `@spawn`.
Here’s my Cilk+ function:
```julia
// parallel merge of sorted sub-arrays i ∈ [low1..up1) and i ∈ [low2..up2) of a into b
// starting at index start
void parMerge(int *a, int low1, int up1, int low2, int up2, int *b, int start){
int k1 = up1 - low1;
int k2 = up2 - low2;
int mid1, mid2;
// Sequential cutoff
if(k1+k2 < 100000)
// usual sequential non-recursive merge
sequentialMerge(a, low1, up1, low2, up2, b, start);
else{
if(k1 >= k2){
mid1 = (low1+up1-1)/2;
mid2 = binarySearch(a, low2, up2, mid1);
} else{
mid2 = (low2+up2-1)/2;
mid1 = binarySearch(a, low1, up1, mid2)-1;
mid2++;
}
cilk_spawn parMerge(a, low1, mid1+1, low2, mid2, b, start);
start = start + mid1 - low1 + 1 + mid2 - low2;
parMerge(a, mid1+1, up1, mid2, up2, b, start);
cilk_sync;
}
}
```
Note that I’ve updated `start` after the first recursive call to `parMerge`, which works fine since the value of `start` has already been used in that recursive call.
Here’s my Julia version, modified to deal with 1-based indexing:
```julia
# Merge a[lo1:hi1] and a[lo2:hi2] into b starting at start
function parMerge!(b, a, lo1, hi1, lo2, hi2, start)
k1 = hi1 - lo1 + 1
k2 = hi2 - lo2 + 1
mid1, mid2 = 0, 0
# sequential cutoff
if k1+k2 < 100000
sequentialMerge!(b, a, lo1, hi1, lo2, hi2, start)
return
end
if k1 >= k2
mid1 = (lo1+hi1)>>> 1
mid2 = binarySearch(a, lo2, hi2, mid1)
else
mid2 = (lo2+hi2)>>>1
mid1 = binarySearch(a, lo1, hi1, mid2)-1
mid2 += 1
end
first = @spawn parMerge!(b, a, lo1, mid1, lo2, mid2-1, start)
parMerge!(b, a, mid1+1, hi1, mid2, hi2, start + mid1 - lo1 + 1 + mid2 - lo2)
wait(first)
end
```
Note that here I didn’t update `start` before the second recursive call, but instead put the expression into the last parameter.
I had initially updated `start` before the second recursive call (as in the Cilk+ program). What happened was that the first recursive call used the value of `start` that was updated in the following line, leading to out of bound array accesses. From my limited understanding of Julia, I take it that this is because the expression in the `@spawn` macro is “escaped” (`esc`), which results in variables referring back to the scope where the macro is called.
---
### Author:  [@Ralph\_Smith](https://discourse.julialang.org/u/Ralph_Smith)
#### Post date: [February 20, 2020, 2:25pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/2 "2020-02-20T14:25:00Z")
`@spawn` builds a closure for the thunk which it passes to the task. This can indeed make variable references tricky.
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 25, 2023, 4:43am UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/3 "2023-03-25T04:43:05Z")
Can this allocation overhead be avoided? This makes divide and conquer algorithms
allocate way too much…
---
### Author:  [@sgaure](https://discourse.julialang.org/u/sgaure)
#### Post date: [March 25, 2023, 9:30am UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/4 "2023-03-25T09:30:41Z")
> [@PetrKryslUCSD](#):
>
> Can this allocation overhead be avoided?
You can interpolate values into `@spawn`.
```julia
a = b+c
a += 1
task = @spawn myfun($a)
```
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 26, 2023, 5:45pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/5 "2023-03-26T17:45:14Z")
That has a nil effect, I am afraid.
---
### Author:  [@eaubanel](https://discourse.julialang.org/u/eaubanel)
#### Post date: [March 27, 2023, 12:52pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/6 "2023-03-27T12:52:38Z")
I agree that divide and conquer implementations can allocate too much memory, only I don’t see how that applies in this example. Could you elaborate?
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 27, 2023, 3:06pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/7 "2023-03-27T15:06:53Z")
Take for instance this sorting algorithm (credit @pitsianis ):
```julia
- const SEQ_THRESH = 1 << 9
-
- @inline function partition!(A, pivot, left,right)
- @inbounds while left <= right
- while A[left] < pivot
- left += 1
- end
- while A[right] > pivot
- right -= 1
- end
- if left <= right
- A[left], A[right] = A[right], A[left]
- left += 1
- right -= 1
- end
- end
-
- return (left,right)
- end
-
- function quicksort!(A, i=1, j=length(A))
0 if j > i
0 left, right = partition!(A, A[(j+i) >>> 1], i, j)
0 quicksort!(A,i,right)
0 quicksort!(A,left,j)
- end
0 return
- end
-
- function parallel_quicksort!(A,i=1,j=length(A))
0 if j-i <= SEQ_THRESH
0 quicksort!(A, i, j)
0 return
- end
0 left, right = partition!(A, A[(j+i) >>> 1], i, j)
12327200 t = Threads.@spawn parallel_quicksort!(A,i,right)
0 parallel_quicksort!(A,left,j)
18542720 wait(t)
-
0 return
- end
-
- function test(n)
8388656 b = rand(n)
-
0 for i = 1:5
240 print("Parallel : ")
41943280 a1 = copy(b); @time parallel_quicksort!(a1);
240 print("Sequential: ")
41943280 a2 = copy(b); @time quicksort!(a2);
720 println("")
41943280 @assert a1 == sort(a1)
0 @assert a1 == a2
0 end
-
- end
-
- test(2^20)
```
Notice the huge allocations where the task is spawned and where it is waited on.
---
### Author:  [@eaubanel](https://discourse.julialang.org/u/eaubanel)
#### Post date: [March 27, 2023, 7:00pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/8 "2023-03-27T19:00:15Z")
That is ugly. So even if the implementation is good in theory, these allocations couldn’t be avoided. BTW how is this profile generated? I’ve only used totals given by @time and @btime
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 27, 2023, 7:12pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/9 "2023-03-27T19:12:19Z")
julia --track-allocation=user
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 27, 2023, 7:55pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/10 "2023-03-27T19:55:28Z")
Sorry, i think it was =all
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [March 27, 2023, 7:57pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/11 "2023-03-27T19:57:35Z")
`--track-allocation` inserts allocations that don’t exist. What happens if you use the allocation profiler instead?
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 27, 2023, 8:55pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/12 "2023-03-27T20:55:13Z")
That sounds promising. Alas, output is anything but easy to interpret. I’ve been looking at it least ten minutes without being able to figure out whether my code allocated anything or not.
This is a sample of the graph:
Is there a trick to it?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [March 27, 2023, 9:02pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/13 "2023-03-27T21:02:08Z")
That looks like a lot of allocations in compilation. One thing to be aware of is that you probably need to set the `sample_rate` higher. It defaults to only capturing 1/1000 allocations (I want to change that default but haven’t yet).
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 27, 2023, 9:20pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/14 "2023-03-27T21:20:45Z")
Thanks! With ten thousand samples, there is a mention of my own code:
Does this mean it does not allocate?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [March 27, 2023, 9:25pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/15 "2023-03-27T21:25:50Z")
No. that 8316 means that there are 8316 allocations that it recorded.
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 27, 2023, 9:30pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/16 "2023-03-27T21:30:36Z")
I do long for the old memory-allocation way of display: simply show the source code with the numbers on the left. Is that possible?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [March 27, 2023, 9:35pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/17 "2023-03-27T21:35:34Z")
The problem with that display is that it forces the compiler to lie to you. In order to get that display you have to turn off most inlining (since once you inline code it’s very hard to attribute it to a line number), and a number of other unfortunate things happen that reduce the ability of the compiler to optimize your code. The fundamental problem is that Julia’s compiler works on an “as if” basis. This means that it is only allowed to make optimizations if it can prove that you can’t tell the difference. This has the unfortunate effect that when trying to do something like correspond allocations wiht line numbers, you are inherently preventing the compiler from optimizing your code.
---
### Author:  [@PetrKryslUCSD](https://discourse.julialang.org/u/PetrKryslUCSD)
#### Post date: [March 27, 2023, 9:58pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/18 "2023-03-27T21:58:39Z")
How do I find out _where_ the memory was allocated?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [March 27, 2023, 10:02pm UTC](https://discourse.julialang.org/t/parallel-merge-in-cilk-vs-julia/34903/19 "2023-03-27T22:02:55Z")
The boxes give you the function names. following the arrows down gives you the call stack that leads to them.