并行排序比串行排序慢

Question

我正在阅读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.你知道我为什么会得到这样的结果吗？

Answer 1

这个基准几乎没有告诉你什么.微基准测试最重要的事情是

• 通过多次运行测试,让JIT有机会优化代码
• 使用不同的输入尺寸
• 打印一些结果,以防止JIT优化掉整个调用

还有一些要考虑的要点 - 实际上还有更多要点.您应该参考如何在Java中编写正确的微基准测试？了解更多信息.

对于真正"深刻"的信息,您应该使用Caliper或JMH等工具.但即使付出很少的努力,人们也可以创建一个微基准,显示实际性能的粗略指示.因此,最简单的microbenchmark形式之一可能如下所示:

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

显示并行排序应该更快,至少.