c - 并行 QuickSort C 实现

Question

我在 C 中使用 pthreads 实现了并行快速排序。开始时似乎工作正常，但将输入增加到 10'000'000 个数字时，我遇到了一个我无法检测和解决的意外段错误。

这是我的代码

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>

#define SIZE 3000000
#define MAXTHREAD 10

_Atomic int count = MAXTHREAD;
_Atomic int threadid = 0;

pthread_mutex_t mutex;

void swap(int *lhs, int *rhs){
    if (lhs == rhs)
        return;

    int tmp = *lhs;
    *lhs = *rhs;
    *rhs = tmp;
}

int do_pivot(int *data, int len) {
    int i, pvt=0;
    swap(data + (rand() % len), data+(len-1));
    for (i=0; i<len; ++i)
    {
        if (data[i] < data[len-1])
            swap(data + i, data + pvt++);
    }

    // swap the pivot value into position
    swap(data+pvt, data+(len-1));
    return pvt;
}


typedef struct {
    int *data;
    int len;
} array_t;

void quick_sort(int *data, int len);

void *quick_sort_thread_wrapper(void *thread_arg) {
    array_t *pArray = (array_t *) thread_arg;

    int *data = pArray->data;
    int len = pArray->len;

    quick_sort(data, len);
    count ++;
    free(pArray);

    //printf("Count : %d\n", count);
    //pthread_exit(NULL);
}

void create_quick_sort_thread(pthread_t *thread, int *data, int len) {
    count--;
    array_t *pArray = malloc(sizeof(array_t));
    pArray->data = data;
    pArray->len = len;
    //printf("len %d\n", len);
    pthread_create(thread, NULL, quick_sort_thread_wrapper, (void *) pArray);
    //printf("ciao\n");
}

void print_array(int * data, int len){
    for (int i=0; i < len; i++){
        printf("%d ", data[i]);
    }
    printf("\n");
}
void quick_sort(int *data, int len) {
    //printf("start quicksort\n");
    //printf("len %d", len);
    //print_array(data,len);
    switch (len) {
        case 2:
            if (data[0] > data[1]) {
                int temp = data[0];
                data[0] = data[1];
                data[1] = temp;
            }
            /* return; */
        case 1:
            return;
        case 0:
            return;
    }

    int pivot_pos = do_pivot(data, len);

    //printf("pivot idx: %d\n", pivot_pos);

    pthread_t right_thread;

    int thread_started = 0;

    /* pthread_mutex_lock(&mutex); */
    if(count > 0){
        //printf("thread_started %d\n", pivot_pos);
        thread_started = 1;
        create_quick_sort_thread(&right_thread, data + pivot_pos + 1, len - pivot_pos - 1);
    }else{
        //printf("no thread %d\n", pivot_pos);
        quick_sort(data + pivot_pos + 1, len - pivot_pos -1);
    }
    /* pthread_mutex_unlock(&mutex); */
    quick_sort(data, pivot_pos);
    if (thread_started == 1){
        //print_array(data,len);
        //printf("waiting\n");
        pthread_join(right_thread, NULL);
    }

}

int main(int argc, char *argv[]) {
    //int data[]= {31, 39, 59, 73, 47, 100, 57, 45, 84, 57, 35, 16, 24, 66, 92, 55, 66, 10, 65, -2, 31, 39, 59, 73, 47, 100, 57, 45, 84, 57, 35, 16, 24, 66, 92, 55, 66, 10, 65, -2};
    /* int * data  = malloc(sizeof(10000 * sizeof(int))); */
    int p,n;
    int data[SIZE];
    for(int i = 0; i < SIZE; i++){
        data[i]=rand() % 10000 + 1;
    }
    /* while(scanf(data,"%d%n", &n, &p)==1){ */
    /*     data[p]=n; */
    /*     printf("%d", data[p]); */
    /*     data+=p; */
    /* } */
    const int count = sizeof(data) / sizeof(int);

    pthread_t thread;
    /* printf("count %d\n", count); */
    create_quick_sort_thread(&thread, data, count);

    pthread_join(thread, NULL);
    print_array(data,count);
    //pthread_exit(NULL);

    return 0;
}

Answer 1

for ( ; data[l] <= pivot; ++l)
    ;

什么？这不会根据 size 检查 l，那么是什么阻止它遍历整个内存呢？未定义的行为......