c++ - 多线程合并排序的奇怪结果

Question

我正在使用 C++ 进行多线程合并排序。结果很奇怪，即使要排序的数字非常大(500万)，添加更多线程也会减少运行时间。我希望添加更多线程会减少运行时间。我认为我的代码中有一些错误。谁能帮帮我？

    #include <iostream>
    #include <pthread.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <time.h>

    // number of elements in array
    // number of threads

    int MAX;
    int THREAD_MAX;
    // array bellow is to store the right edge of a divided array
    int index[20] = {0};
    int p_i = 0;


    using namespace std;


    //int *a;
    int part = 0;


    void fillData(int a[], int len)
    {
        // Create random arrays
        int i;
        for (i = 0; i<len; i++)
            a[i] = rand();
        return;
    }


    // merge function for merging two parts
    void merge(int *a, int low, int mid, int high)
    {
        // We have low to mid and mid+1 to high already sorted.
        int i, j, k;
        int * temp = new int[high - low + 1];
        i = low;
        k = 0;
        j = mid + 1;

        // Merge the two parts into temp[].
        while (i <= mid && j <= high)
        {
            if (a[i] < a[j])
            {
                temp[k] = a[i];
                k++;
                i++;
            }
            else
            {
                temp[k] = a[j];
                k++;
                j++;
            }
        }

        // Insert all the remaining values from i to mid into temp[].
        while (i <= mid)
        {
            temp[k] = a[i];
            k++;
            i++;
        }

        // Insert all the remaining values from j to high into temp[].
        while (j <= high)
        {
            temp[k] = a[j];
            k++;
            j++;
        }


        // Assign sorted data stored in temp[] to a[].
        for (i = low; i <= high; i++)
        {
            a[i] = temp[i - low];
        }
    }




    // merge sort function
    void merge_sort(int *a, int low, int high)
    {
        // calculating mid point of array
        int mid = low + (high - low) / 2;
        if (low < high) {

            // calling first half
            merge_sort(a, low, mid);

            // calling second half
            merge_sort(a, mid + 1, high);

            // merging the two halves
            merge(a, low, mid, high);
        }
    }

    // thread function for multi-threading
    void* merge_sort(void* arr)
    {
        int *a = (int *)(arr);
        int thread_part = part++;

        // calculating low and high


        int low = thread_part * (MAX / THREAD_MAX);
        int high = (thread_part + 1) * (MAX / THREAD_MAX) - 1;

        // allocate the rest part of original array to the last thread
        if(thread_part == THREAD_MAX -1){
                high = MAX - 1;
        }
        // store the right edge of each divided array
        index[++p_i] = high;

        // evaluating mid point
        int mid = low + (high - low) / 2;

            merge_sort(a, low, mid);
            merge_sort(a, mid + 1, high);
            merge(a, low, mid, high);

    }


    void isSorted(int *a, int len)
    {
        if (len == 1)
        {
            printf("Sorting Done Successfully\n");
            return;
        }

        int i;
        for (i = 1; i<len; i++)
        {
            if (a[i]<a[i - 1])
            {
                printf("Sorting Not Done\n");
                return;
            }
        }
        printf("Sorting Done Successfully\n");
        return;
    }



    // Driver Code
    int main()
    {


    /*  cout << "Enter No of elements of Array:";
        cin >> MAX;*/
        int length, i;
        cout << "\nEnter the number of data element to be sorted: ";
        cin >> MAX;

        int *a= new int[MAX];
        // Create a random array of given length
        srand(time(NULL));
        fillData(a, MAX);



        cout << "Enter No of Thread:";
        cin >> THREAD_MAX;


    /*  // generating random values in array
        a = new int[MAX];
        srand(time(NULL));
        for (int i = 0; i < MAX; i++)
        {
            a[i] = rand();
        }*/

        // t1 and t2 for calculating time for merge sort

        clock_t t1 = clock();
        pthread_t threads[THREAD_MAX];

// creating threads
for (int i = 0; i < THREAD_MAX; i++)
{
    pthread_create(&threads[i], NULL, merge_sort, (void*)a);
}


    // joining all threads
    for (int i = 0; i < THREAD_MAX; i++)
        {
        pthread_join(threads[i], NULL);
        }
        clock_t t2 = clock();
        // merging the final parts
        int p = 1;
        int mid, high;
        for(int q = 1; q < THREAD_MAX; q++)
        {   

            mid = index[p];
            p++;
            high = index[p];
            merge(a, 0, mid, high);         
        }


        cout << "Time taken: " << (double)(t2 - t1)/ CLOCKS_PER_SEC << endl;
        isSorted(a, MAX);



        // displaying sorted array
        /*cout << "Sorted array: ";
        for (int i = 0; i < MAX; i++)
            cout << a[i] << " ";*/


        return 0;
    }

Answer 1

不要在 merge 中分配内存, 分配一个大数组 MAX提前并在merge_sort内使用.

你的 merge函数被调用了很多次，而且来自多个线程。每个new修改空闲存储(堆)，这通常以某种形式的临界区完成。有可扩展的分配器，例如 malloc为此目的，来自 Intel TBB。但是，在合并排序实现中没有理由进行这样的分配。

而且你不delete[] temp在你的merge功能。您的代码还有更多问题，例如数据竞争(int thread_part = part++;)。你执行最终 merge仅顺序，这阻碍了可扩展性。合并排序(和快速排序)的高效实现通常在递归结束时使用插入排序(例如，低于 10 个元素)，因为它比调用函数更快。等等……