Parallel merge in Cilk+ vs Julia

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:

// 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:

# 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.

@spawn builds a closure for the thunk which it passes to the task. This can indeed make variable references tricky.