java - 为什么更新/更快的 Java 8 排序方式更糟糕？

Question

List<Point> pixels = new ArrayList<>(width * height); // 1280*960

for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++)
        pixels.add(new Point(x, y));

// Java 7 sorting
Collections.sort(pixels, comparator);

// Java 8 sorting
pixels = pixels.stream().parallel().sorted(comparator).collect(Collectors.toList());

使用任何排序方法时，一开始我的性能都很慢，后来会有所改善。我期待这一点，因为 JIT 编译器需要时间来优化高使用率的代码。

奇怪的是，旧的分拣机一开始有点慢，而新的分拣机慢得多，慢了 60% 以上。过了一会儿，新的分拣机变得更快了，正如预期的那样。但是前两/三次执行如此缓慢的方式简直令人无法接受。

Java 7 collection sorter
0.258992413
0.265509443
0.536536068
0.117830618
0.136303916
0.111004611
0.134771877
0.108078261

Java 8 stream sorter
0.631757108
0.868032669
0.076455248
0.087101852
0.070401965
0.056989645
0.072018371
0.078908912
0.074237648

眼镜:
CPU:Intel I7 3770(8核8M/1M/128K缓存)
cmd: javaw -server -cp bin Myclass

有没有其他人经历过较新的(流)操作性能更差的情况？

有没有办法解决这种缓慢的问题？ (不引起启动延迟)

Answer 1

看来你关心的是预热阶段的性能(即JVM启动后的第一次和第二次排序)。所以可能标准的 JMH 基准不适合你。没关系，让我们手动编写基准测试。正如我们所说的几十毫秒，使用 System.nanoTime() 的简单基准测试将提供足够的精度。

您没有在问题中提供您的 Comparator。简单的比较器(如 Comparator.comparingInt(p -> p.x) )可以更快地对数据进行排序，因此我假设您有更复杂的比较器:

final Comparator<Point> comparator = Comparator.comparingInt(p -> p.x*p.x + p.y*p.y);

它通过与 (0, 0) 的欧几里得距离来比较点(不需要取平方根，因为它是单调函数，所以顺序不会改变)。

另外让我们将数据准备与排序分开来仅衡量排序性能:

private Point[] prepareData() {
    Point[] pixels = new Point[width*height];
    int idx = 0;
    for (int y = 0; y < height; y++)
        for (int x = 0; x < width; x++)
            pixels[idx++] = new Point(x, y);
    return pixels;
}

我使用数组而不是 List 来直接测试 Arrays.parallelSort。普通的旧排序是这样的:

public List<Point> sortPlain(Point[] data) {
    List<Point> list = Arrays.asList(data);
    Collections.sort(list, comparator);
    return list;
}

基于 Parallel Stream API 的排序将是

public List<Point> sortParallelStream(Point[] data) {
    return Stream.of(data).parallel().sorted(comparator).collect(Collectors.toList());
}

让我们还添加顺序流 API 版本:

public List<Point> sortStream(Point[] data) {
    return Stream.of(data).sorted(comparator).collect(Collectors.toList());
}

并直接使用 parallelSort:

public List<Point> sortParallel(Point[] data) {
    Arrays.parallelSort(data, comparator);
    return Arrays.asList(data);
}

测量代码不是很困难。 Here 的完整实现。请注意，每个测试都应该独立启动，因此我们在 JVM 启动期间只测试一种模式。这是我机器上的典型结果(i7-4702MQ 2.20GHz，4 核 HT = 8 个硬件线程，Win7 64 位，java 1.8.0_71)。

Iter  Plain      Parallel   Stream     ParallelStream
#01:  0.38362s   0.37364s   0.28255s   0.47821s
#02:  0.23021s   0.25754s   0.18533s   0.72231s
#03:  0.18862s   0.08887s   0.21329s   0.18024s
#04:  0.19810s   0.06158s   0.68004s   0.12166s
#05:  0.19671s   0.06461s   0.17066s   0.08380s
#06:  0.14796s   0.05484s   0.18283s   0.12931s
#07:  0.16588s   0.04920s   0.21481s   0.13379s
#08:  0.21988s   0.05932s   0.19111s   0.12903s
#09:  0.14434s   0.05123s   0.14191s   0.11674s
#10:  0.18771s   0.06174s   0.14977s   0.07237s
#11:  0.15674s   0.05105s   0.21275s   0.06975s
#12:  0.17634s   0.06353s   0.14343s   0.07882s
#13:  0.15085s   0.05318s   0.16004s   0.11029s
#14:  0.18555s   0.05278s   0.19105s   0.12123s
#15:  0.14728s   0.05916s   0.14426s   0.07235s
#16:  0.18781s   0.05708s   0.21455s   0.07884s
#17:  0.14493s   0.12377s   0.14415s   0.11170s
#18:  0.14395s   0.05100s   0.18201s   0.07878s
#19:  0.14849s   0.05437s   0.14484s   0.08364s
#20:  0.14143s   0.12073s   0.18542s   0.11257s

Plain 和 ParallelStream 测试的结果与您的有些相似:ParallelStream 的前两次迭代(尤其是第二次)要慢得多。您还可以注意到，直接执行 Arrays.parallelSort 没有这种效果。最后，非并行流是最慢的。那是因为 Stream API 总是使用中间缓冲区进行排序，因此需要更多的空间和时间对缓冲区执行额外的复制、排序，然后执行复制到结果列表。

为什么 ParallelStream 的前两次迭代如此之慢(尤其是第二次)？仅仅因为你有相当小的起始堆来方便地放置所有的中间缓冲区，所以在前两次迭代期间发生了几个 full-gc 事件，最终会出现明显的延迟。如果您使用 -verbose:gc 运行测试，您将看到 ParallelStream :

[GC (Allocation Failure)  16384K->14368K(62976K), 0.0172833 secs]
[GC (Allocation Failure)  30752K->30776K(79360K), 0.0800204 secs]
[Full GC (Ergonomics)  30776K->30629K(111104K), 0.4487876 secs]
[GC (Allocation Failure)  63394K->74300K(111104K), 0.0215347 secs]
[Full GC (Ergonomics)  74300K->45460K(167936K), 0.1536388 secs]
[GC (Allocation Failure)  76592K->57710K(179712K), 0.0064693 secs]
#01: 0.41506s
[GC (Allocation Failure)  101713K->103534K(180224K), 0.0567087 secs]
[Full GC (Ergonomics)  103534K->39365K(203776K), 0.5636835 secs]
[GC (Allocation Failure)  84021K->53689K(266752K), 0.0103750 secs]
#02: 0.71832s

在此之后不再有 Full GC 事件，因为现在堆已经足够大了。与 Plain 启动比较:

[GC (Allocation Failure)  16384K->14400K(62976K), 0.0162299 secs]
[GC (Allocation Failure)  30784K->30784K(79360K), 0.0762906 secs]
[Full GC (Ergonomics)  30784K->30629K(111616K), 0.4548198 secs]
#01: 0.43610s
[GC (Allocation Failure)  63397K->58989K(111616K), 0.0330308 secs]
[Full GC (Ergonomics)  58989K->25278K(133120K), 0.2479148 secs]
#02: 0.20753s

只有两次 Full GC 花费的时间显着减少，因为垃圾显着减少。

让我们使用 -Xms1G 将初始堆大小设置为 1Gb 以降低 GC 压力。现在我们得到了完全不同的结果:

Iter  Plain      Parallel   Stream     ParallelStream
#01:  0.38349s   0.33331s   0.23834s   0.24078s      
#02:  0.18514s   0.20530s   0.16650s   0.07802s      
#03:  0.16642s   0.10417s   0.16267s   0.11826s      
#04:  0.16409s   0.05015s   0.19890s   0.06926s      
#05:  0.14475s   0.05241s   0.15041s   0.06932s      
#06:  0.14358s   0.05584s   0.14611s   0.06684s      
#07:  0.17644s   0.04913s   0.14619s   0.06716s      
#08:  0.14252s   0.04642s   0.19333s   0.10813s      
#09:  0.14427s   0.04547s   0.14673s   0.06900s      
#10:  0.14696s   0.04634s   0.14927s   0.06712s      
#11:  0.14254s   0.04682s   0.15107s   0.07874s      
#12:  0.15455s   0.09560s   0.19370s   0.06663s      
#13:  0.15544s   0.05133s   0.15110s   0.13052s      
#14:  0.18636s   0.04788s   0.15928s   0.06688s      
#15:  0.14824s   0.04833s   0.15218s   0.06624s      
#16:  0.15068s   0.04949s   0.19183s   0.13925s      
#17:  0.14605s   0.04695s   0.14770s   0.12714s      
#18:  0.14130s   0.04660s   0.14903s   0.15428s      
#19:  0.14695s   0.05491s   0.14389s   0.07467s      
#20:  0.15050s   0.04700s   0.18919s   0.07662s      

现在，即使是 Plain 的结果也更加稳定(因为我们的 GC 暂停更少)并且 ParallelStream 现在总是比 Plain 更好(尽管它仍然产生更多的对象，但当你有更大的堆时更容易分配它们并收集垃圾)。对于所有四个测试，-Xms1G 没有观察到完整的 gc 事件

所以总结一下:

ParallelStream 会产生更多垃圾并进行额外的复制，这会减慢操作速度。

JVM 启动后默认堆设置太小，所以垃圾收集器需要相当多的时间，直到它决定充分增加整体堆大小。

如果您想要最大并行速度，请直接使用 Arrays.parallelSort，因为它就地排序。特别是如果您事先知道数据集的大小。

最后应该注意的是，当您在 Java-7 下启动时将 Collections.sort(list, comparator) 称为“Java 7 集合排序器”时，它的运行速度要慢 8-10%，因为 Collections.sort 实现已更改。