并行排序比串行排序慢

Question

并行排序比串行排序慢

5

我正在阅读有关Java 8新功能的内容，其中之一是新的Arrays.parallelSort()方法。我对双精度数组和字符串数组进行了排序测试，发现对于字符串数组，parallelSort速度较慢。

下面是一个字符串排序测试方法的内容：

    final int size = 10000;
    final String[] values1 = new String[size];
    final String[] values2 = new String[size];
    for (int i = 0; i < size; i++) {
        values1[i] = Integer.toString(i);
        values2[i] = values1[i];
    }
    Collections.shuffle(Arrays.asList(values1));
    Collections.shuffle(Arrays.asList(values2));
    final Comparator<String> comparator = (o1, o2) -> o2.compareTo(o1);

    long startTimeInNano = System.nanoTime();
    Arrays.sort(values1, comparator);
    long endTimeInNano = System.nanoTime();
    System.out.println("Arrays.sort: totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000));

    //parallel sort with java 8
    startTimeInNano = System.nanoTime();
    Arrays.parallelSort(values2,comparator);
    endTimeInNano = System.nanoTime();
    System.out.println("Arrays.parallelSort: totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000));

结果如下：

结果为：

Arrays.sort：totalTimeInMicro= 11993

Arrays.parallelSort：totalTimeInMicro= 89823

我还在另一台计算机上尝试了这段代码，结果是一样的（25608 vs 808660）。我运行测试的计算机使用的是i5-2500 CPU。您有任何想法为什么会得到这种结果吗？

- Slimu

1

可能是由于线程创建开销导致的。尝试对更大的数组进行排序：可能存在一种数组大小，使得并行排序更快。 - juhist

3

单次执行的时间（即使没有逐渐升高）并不能告诉你太多信息。 - biziclop

在进行任何微基准测试之前，您应该进行热身运动。
Arrays.parallelSort() 使用 fork-join 框架。因此它直接与系统上的核心数相关（因此它是架构相关的）。i-5 有4个内核，所以理论上 parallel sort 应该更快。

- TheLostMind

@Elemental 列表的顺序不正确，因为元素被视为字符串进行比较，所以 "1000" < "2"。 - biziclop

这可能有助于编写更具信息性的基准测试。 - biziclop

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marco13 · Accepted Answer

这个基准测试并不能告诉你太多东西。一个微基准测试最重要的是：

多次运行测试，给JIT编译器优化代码的机会
使用不同的输入大小进行测试
输出部分结果，以防止JIT优化掉整个调用过程

当然还有其他需要考虑的点 - 实际上还有许多其它点。你可以参考如何正确编写Java微基准测试？获取更多信息。

如果您需要真正“深奥”的信息，则应使用像Caliper或JMH这样的工具。但是即使花费很少的精力，也可以创建一项微基准测试，显示实际性能的大致指示。因此，一个简单的微基准测试可以看起来像这样：

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class ParallelSortSpeedTest
{
    public static void main(String[] args)
    {
        for (int size=100000; size<=1000000; size+=100000)
        {
            final String[] values1 = new String[size];
            final String[] values2 = new String[size];
            for (int i = 0; i < size; i++) {
                values1[i] = Integer.toString(i);
                values2[i] = values1[i];
            }
            Collections.shuffle(Arrays.asList(values1));
            Collections.shuffle(Arrays.asList(values2));
            final Comparator<String> comparator = (o1, o2) -> o2.compareTo(o1);

            testSort(values1, comparator);
            testParallelSort(values2, comparator);
        }
    }

    private static void testSort(
        String array[], final Comparator<String> comparator)
    {
        long startTimeInNano = System.nanoTime();
        Arrays.sort(array, comparator);
        long endTimeInNano = System.nanoTime();
        System.out.println("Arrays.sort        : totalTimeInMicro= " + 
            ((endTimeInNano - startTimeInNano)/1000)+", first "+array[0]);
    }

    private static void testParallelSort(
        String array[], final Comparator<String> comparator)
    {
        long startTimeInNano = System.nanoTime();
        Arrays.parallelSort(array, comparator);
        long endTimeInNano = System.nanoTime();
        System.out.println("Arrays.parallelSort: totalTimeInMicro= " + 
            ((endTimeInNano - startTimeInNano)/1000)+", first "+array[0]);
    }

}

考虑到启动JMH基准测试的工作量和结果的可靠性之间的权衡，这是一个合理的选择。此测试将打印类似于以下内容：

...
Arrays.sort        : totalTimeInMicro= 530669, first 999999
Arrays.parallelSort: totalTimeInMicro= 158227, first 999999

至少表明并行排序应该更快。