Mar*_*mus 4 java sorting performance java-8 java-stream
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
似乎您关心预热阶段的性能(即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());
}
我们还添加顺序Stream 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);
}
测量代码并不是很困难.这是完整的实施.请注意,每个测试都应该独立启动,因此我们在JVM启动期间只测试一种模式.这是我机器上的典型结果(i7-4702MQ 2.20GHz,4核心HT = 8个HW线程,Win7 64bit,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
此后不再有完整的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,花费的时间要少得多,因为垃圾明显少了.
让我们将初始堆大小设置为1Gb,-Xms1G以降低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事件
总结如下:
Arrays.parallelSort直接使用,因为它可以就地排序.特别是如果您事先知道数据集的大小.最后应该注意的是,当您Collections.sort(list, comparator)在Java-7下启动时调用"Java 7集合分类器"时,它的工作速度要慢8-10%,因为Collections.sort实现已更改.
| 归档时间： |
|
| 查看次数： |
3944 次 |
| 最近记录： |