JAVA-多线程合并排序的排序速度

Question

我已经在JAVA中实现了多线程MergeSort，并用不同数量的线程测试了算法的运行时间。我在双核处理器上运行代码，该算法以4或8个线程运行最快。这对我来说没有意义-我有两个核心。这是我的源代码。

public static void parallelMergeSort(int[] a, int NUM_THREADS)
{
    if(NUM_THREADS <= 1)
    {
        mergeSort(a);
        return;
    }

    int mid = a.length / 2;

    int[] left = Arrays.copyOfRange(a, 0, mid);
    int[] right = Arrays.copyOfRange(a, mid, a.length);

    Thread leftSorter = mergeSortThread(left, NUM_THREADS);
    Thread rightSorter = mergeSortThread(right, NUM_THREADS);

    leftSorter.start();
    rightSorter.start();

    try {
        leftSorter.join();
        rightSorter.join();
    } catch (InterruptedException e) {
        e.printStackTrace();
    }

    merge(left, right, a);
}

private static Thread mergeSortThread(int[] a, int NUM_THREADS)
{
    return new Thread()
    {
        @Override
        public void run()
        {
            parallelMergeSort(a, NUM_THREADS / 2);
        }
    };
}

public static void mergeSort(int[] a)
{
    if(a.length <= 1) return;

    int mid = a.length / 2;

    int[] left = Arrays.copyOfRange(a, 0, mid);
    int[] right = Arrays.copyOfRange(a, mid, a.length);

    mergeSort(left);
    mergeSort(right);

    merge(left, right, a);
}


private static void merge(int[] a, int[] b, int[] r)
{
    int i = 0, j = 0, k = 0;
    while(i < a.length && j < b.length)
    {
        if(a[i] < b[j])
            r[k++] = a[i++];
        else
            r[k++] = b[j++];
    }

    while(i < a.length)
        r[k++] = a[i++];

    while(j < b.length)
        r[k++] = b[j++];
}

我测试了使用不同数量的线程运行它，并在毫秒内得到以下结果：

Serial Sort Run Time: 5368.
Parallel Sort Run Time with 2 Threads: 3202.
Parallel Sort Run Time with 4 Threads: 2408.
Parallel Sort Run Time with 8 Threads: 2544.
Parallel Sort Run Time with 16 Threads: 2738.
Parallel Sort Run Time with 32 Threads: 2909.
Parallel Sort Run Time with 64 Threads: 3078.
Parallel Sort Run Time with 128 Threads: 3777.

为什么该算法在双核CPU上以4个线程运行最快？

Answer 1

为什么该算法在双核CPU上以4个线程运行最快？

这可能只是基准测试不佳的产物。例如，如果您的基准测试未适当考虑JVM预热的影响，则结果将不可靠。

除此之外，“超线程”解释是合理的：

酷睿i3，i5和i7

Core i3，i5和i7型号于2008年首次推出，构成了英特尔当前的台式PC处理器产品线。它们涵盖了广泛的时钟速度，从i3 Mobile的1.2 GHz到最快的i7处理器的3.6 GHz。该系列中的所有处理器均为64位设计，每个处理器至少具有两个内核。除了四核i5型号，它们都受益于超线程技术。

资料来源：“哪些英特尔处理器具有超线程？

但是，HT（显然）在处理器上可用的事实并不意味着它实际上已启用。这将取决于BIOS设置等。

• https://unix.stackexchange.com/questions/33450/checking-if-hyperthreading-is-enabled-or-not