c - 多线程合并排序在大型数据集上使用时会错过对某些元素的排序吗？

Question

家庭作业

我将我的数据划分为更小的矩阵，并使用线程来优化递归排序。我的函数在元素数量不超过 2000 的小型数据集上完美运行。但是，一旦数据开始变得比这个大，我就会开始让一些元素乱序，并且在运行地址 sanitizer 时不会出现任何内存错误或 valgrind。我还没弄明白。我确实尝试更改枢轴以使用带有模数的 if 语句对偶数或奇数数量的元素进行分区 n/2对于偶数和 (n+1)/2对于奇怪，但仍然没有用。任何人都可以看到我错过了什么或给我一个提示吗？

// struct used for merge sort threads
typedef struct {
    float* m;
    size_t n;
} thread_arg;

/*
 * Merge matrices together
 */
void merge(float* main_matrix, float* left_matrix, int left_elements, float* right_matrix, int right_elements) {
    // left_matrix index
    int l = 0;
    // right_matrix index
    int r = 0;
    // main_matrix index
    int m = 0;

    while (l < left_elements && r < right_elements) {
        if (left_matrix[l] < right_matrix[r]) {
            main_matrix[m++] = left_matrix[l++];
        } else {
            main_matrix[m++] = right_matrix[r++];
        }
    }

    while (l < left_elements) {
        main_matrix[m++] = left_matrix[l++];
    }

    while (r < right_elements) {
        main_matrix[m++] = right_matrix[r++];
    }
}

/*
 * Threaded merge sort
 */
void* merge_sort(void* arg) {
    thread_arg* t_arg = (thread_arg*) arg;

    // base case
    if (t_arg->n < 2) {
        return NULL;
    }

    size_t pivot = (t_arg->n / 2);

    // left and right sub-matrices
    float* left_matrix = malloc(sizeof(float) * pivot);
    float* right_matrix = malloc(sizeof(float) * (t_arg->n - pivot));

    // fill left_matrix
    for (size_t i = 0; i < pivot; i++) {
        left_matrix[i] = t_arg->m[i];
    }

    // fill right_matrix
    for (size_t i = pivot; i < t_arg->n; i++) {
        right_matrix[(i - pivot)] = t_arg->m[i];
    }

    // create structs for recursive thread call
    thread_arg t_arg1 = (thread_arg) {
        .m = left_matrix,
        .n = pivot
    };
    thread_arg t_arg2 = (thread_arg) {
        .m = right_matrix,
        .n = (t_arg->n - pivot)
    };

    // create threads and send structs to sort recursively
    pthread_t thread1;
    pthread_t thread2;
    pthread_create(&thread1, NULL, merge_sort, &t_arg1);
    pthread_create(&thread2, NULL, merge_sort, &t_arg2);
    // join threads to retrieve sorted sub-matrices
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    // Merge left_matrix and right_matrix into sorted matrix.
    merge(t_arg->m, left_matrix, pivot, right_matrix, (t_arg->n - pivot));

    // free left and right matrices
    free(left_matrix);
    free(right_matrix);

    return NULL;
}

/**
 * Returns sorted matrix.
 */
float* sort(float* matrix) {
    float* result = cloned(matrix);

    // structs for threaded merge sort
    thread_arg t_arg = (thread_arg) {
        .m = result,
        .n = g_elements
    };

    merge_sort(&t_arg);

    return result;
}

Answer 1

问题似乎不是检查 pthread_create 是否失败。通过修改代码进行检查，您可以在所有线程都被使用的情况下进行无线程调用。这是一些伪代码。

// create threads and send structs to recursively sort
pthread_t thread1;
if (pthread_create(&thread1, NULL, merge_sort, &t_arg1) != 0 || t_arg->n_threads == MAX_THREADS) {
    merge_sort(&t_arg1);
} else {
    no. of threads++
}

merge_sort(&t_arg2);

pthread_join(thread1, NULL);
no. of threads--