So I'm working on an implementation of parallel quicksort in C using Cilk, and I'm running into an odd problem. The relevant portions of my code, for reference (and apologies in advance for length):
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <cilk/cilk.h>
#include <cilk/cilk_api.h>
void prefixSum(int* input,int* output, int length){
if(length == 1){
output[0] = input[0];
return;
}
int i;
int nPairs = (int) floor(((double)length)/2);
int pairs = (int) ceil(((double)length)/2);
int z[pairs];
int w[pairs];
cilk_for(i=0;i<nPairs;i++){
z[i] = input[2*i]+input[2*i+1];
}
if(pairs>nPairs){
z[pairs-1] = input[length-1];
}
prefixSum(z,w,pairs);
cilk_for(i=0;i<length;i++){
if(i==0){
output[i] = input[i];
}
else if((i-1)%2==0){
output[i] = w[(i-1)/2];
}
else{
output[i] = w[(i-2)/2] + input[i];
}
}
return;
}
void prefixScan(int* input, int length){
int i;
for(i=length-1;i>0;i--){
input[i] = input[i-1];
}
input[0] = 0;
}
void paraSort(double* array, int length){
if(length==1){
return;
}
int pivot = rand() % length;
int lowSet[length];
int highSet[length];
int equalSet[length];
int i;
cilk_for(i=0;i<length;i++){
if(array[i]==array[pivot]){
lowSet[i] = 0;
highSet[i] = 0;
equalSet[i] = 1;
} else if(array[i]<array[pivot]){
lowSet[i] = 1;
highSet[i] = 0;
equalSet[i] = 0;
} else {
lowSet[i] = 0;
highSet[i] = 1;
equalSet[i] = 0;
}
}
int lowIndex[length];
int highIndex[length];
int equalIndex[length];
prefixSum(lowSet,lowIndex,length);
int numLow = lowIndex[length-1];
prefixScan(lowIndex,length);
prefixSum(highSet,highIndex,length);
int numHigh = highIndex[length-1];
prefixScan(highIndex,length);
prefixSum(equalSet,equalIndex,length);
int numEqual = equalIndex[length-1];
prefixScan(equalIndex,length);
double lowList[imin(numLow,1)];
double highList[imin(numHigh,1)];
double equalList[numEqual];
cilk_for(i=0;i<length;i++){
if(lowSet[i]==1){
lowList[lowIndex[i]] = array[i];
} else if(highSet[i]==1){
highList[highIndex[i]] = array[i];
} else if(equalSet[i]==1){
equalList[equalIndex[i]] = array[i];
}
}
if(numLow>0 && numHigh>0){
cilk_spawn paraSort(lowList,numLow);
paraSort(highList,numHigh);
cilk_sync;
} else if(numLow==0 && numHigh>0){
paraSort(highList,numHigh);
} else if(numLow>0 && numHigh==0){
paraSort(lowList,numLow);
}
cilk_for(i=0;i<length;i++){
if(i<numLow){
array[i] = lowList[i];
} else if(i<numLow+numEqual){
array[i] = equalList[i-numLow];
} else {
array[i] = highList[i-(numLow+numEqual)];
}
}
return;
}
Now, when I run this on a test case of 50 elements (sequentially, for ease of debugging), I get one layer deep into the recursion and then encounter a segmentation fault that seems to be caused by an out-of-bounds index in the line equalList[equalIndex[i]] = array[i];.
Checking further, immediately after allocating equalIndex, the values in it are completely arbitrary. This is to be expected; I haven't assigned anything yet. prefixSum is called on a list of elements which is all zero except for the second-to-last element, which is one. (This is a bitmap marking the elements equal to the pivot.) It puts the results of a prefix sum operation into equalIndex, which I pass in as a pointer to the array so that the results persist outside the call.
After doing this, debug printf commands show that equalIndex is now all zeroes save for the last two elements, which are both one. This is the expected prefix sum result; so far so good. prefixScan is a simple helper function to help me tackle indexing from zero; it moves all the elements in the given array one space to the right, filling in the first element with zero. After passing equalIndex to this, debug statements show that equalIndex is all zeroes except for the last element, which is one.
Where the problem arises is immediately following, in the cilk_for loop that copies each element into its proper array. In the body of this loop, printf statements now display values that don't match the previous ones in the slightest - some are properly zero, others wildly large positive or negative integers of the sort I saw earlier before I had initialized this array with prefixSum. Once it hits one of these extreme values and tries to use it as an array index, the program rightly crashes.
My best guess is that somehow the values in equalIndex aren't being assigned properly (hence the odd behavior as though I hadn't initialized the array), but I'm having a lot of trouble figuring out exactly what's going wrong and where.
You contradict yourself. At one point you say
equalIndex is all zeroes except for the last element, which is one
but later you speculate that
somehow the values in equalIndex aren't being assigned properly
. You can't have it both ways.
I don't know Cilk, but extrapolating from C, I'm inclined to think you are trashing your own data. Consider in particular this code, which seems to be the locus of the trouble:
double lowList[imin(numLow,1)];
double highList[imin(numHigh,1)];
double equalList[numEqual];
cilk_for(i=0;i<length;i++){
if(lowSet[i]==1){
lowList[lowIndex[i]] = array[i];
} else if(highSet[i]==1){
highList[highIndex[i]] = array[i];
} else if(equalSet[i]==1){
equalList[equalIndex[i]] = array[i];
}
}
How long are arrays lowList and highList? Study their declarations before you answer. Now what do you suppose might happen if you attempted to assign values to elements of those arrays outside their bounds?