这是一个创建于 1796 天前的主题，其中的信息可能已经有所发展或是发生改变。
楼主写了两个排序方法，一个是选择排序，一个是插入排序，代码肯定是没有任何问题的
在 macOS 下的 jdk 15.1，跑出来是这样的： 
在虚拟机 ubuntu 的 openjdk 8 中，跑出来是这样的： 
为什么会这样呢？同样一份代码，在 jdk 15.1 下，插入排序的 random array 怎么比选择排序慢了这么多？
第 1 条附言 2020-11-19 20:43:23 +08:00
第 2 条附言 2020-11-20 08:06:35 +08:00
新发现，如果添加上 -XX:+UseParallelOldGC 这个参数，这个问题就会得到极大的缓解。
 | 1 nguoidiqua 2020-11-19 19:30:15 +08:00 Ubuntu 上用 openJDK15 跑呢？ |
 | 2 GTD OP 另附一个 jdk 15.1 在 macOS 终端跑的截图，因为试了很多次，应该不存在随机性  |
 | 3 jedrek 2020-11-19 19:38:33 +08:00 楼主什么虚拟机软件？ |
| 4 GTD OP @nguoidiqua #1 试了一下，用了 openjdk 11，神奇的事情出现了 竟然跟 macOS 的 15.1 一样，插入排序慢很多  |
| 6 GTD OP 这是我插入排序的源代码： public static <E extends Comparable<E>> void sort(E[] arr){ for(int i= 0; i < arr.length; i ++){ E t = arr[i]; int j; for(j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j --){ arr[j] = arr[j - 1]; } arr[j] = t; } } |
 | 7 40EaE5uJO3Xt1VVa 2020-11-19 19:53:52 +08:00  1 虽然不知道为什么，我感觉你需要 www.injdk.cn |
 | 8 oldshensheep 2020-11-19 20:23:11 +08:00 看代码运行结果，可以看出来代码的随机数种子应该是固定的。所以可以排除随机数种子的问题。 那就可能是 jdk 版本不同，生成的随机数不同？但是这感觉不太可能，根据结果看生成的随机数应该是一样的。 那就是虚拟机的问题？ 还是什么…… 可以把全部代码贴上来，测试测试。推荐在这个网站粘贴 https://paste.ubuntu.com/ |
| 9 GTD OP @oldshensheep #8 多谢 应该不是随机数的问题，也不是 ubuntu 的问题，因为在 ubuntu 不同的 jdk，最后时间也不一样 代码： https://paste.ubuntu.com/p/NFcDMsvNdH/ |
 | 10 jasonkayzk 2020-11-19 20:39:13 +08:00 难道是 GC 的问题？ 说实话，只有 JDK11 刚出的时候，研究了一下 ZGC ；后面，因为 JDK 11 目前不支持 Android，后面又用回 8 了； 之后再也没研究过 JDK 新版本…… |
 | 11 secondwtq 2020-11-19 21:17:12 +08:00 你这代码根本就没法用来做 benchmark 我记得 Java 做性能测试要用一个专门的库。JVM 会有一个 JIT 的策略，决定什么时候优化哪里的代码，不同的 JVM 版本这个可能会变。要测试性能，你得把这个拉平了。 如果最后在同样的优化等级下还是有 regression 的话，那恭喜楼主可以给 JVM 贡献代码了。 |
 | 12 Cbdy 2020-11-19 21:21:11 +08:00 刚刚简单了写了一个 https://gist.github.com/cbdyzj/00bf90ae5def3609c3831b107ec89c21 macOS Big Sur 11.0.1 openjdk 15 2020-09-15 OpenJDK Runtime Environment AdoptOpenJDK (build 15+36) OpenJDK 64-Bit Server VM AdoptOpenJDK (build 15+36, mixed mode, sharing) --- n = 1000 --- Random Array InsertionSort: 0.004 s SelectionSort: 0.004 s Ordered Array InsertionSort: 0.0 s SelectionSort: 0.001 s --- n = 10000 --- Random Array InsertionSort: 0.042 s SelectionSort: 0.05 s Ordered Array InsrtionSort: 0.0 s SelectionSort: 0.03 s --- n = 100000 --- Random Array InsertionSort: 1.367 s SelectionSort: 2.803 s Ordered Array InsertionSort: 0.0 s SelectionSort: 2.793 s |
| 13 oldshensheep 2020-11-19 21:53:51 +08:00 1 测试了一下，用的 jdk11，13，14，结果和楼主的一样。jdk8 的结果也和楼主一样。 jdk8 的排序速度都差不多，jdk11，13，14 的插入和选择排序速度比是 1:2 。  这可以说是负优化吗……，是由什么引起的呢？ 另外我上面的回复说的随机数种子的问题是我想错了…… |
| 14 GTD OP @Cbdy 诶对啊，你这个差不多也是 1:2，这两个算法时间复杂度都是 o （ n ） 2 才对，不应该差距这么大 |
| 15 Cbdy 2020-11-19 22:59:56 +08:00 via Android @GTD 时间复杂度 O(n^2)的意思是，随着 n 的增长，时间复杂度呈 n^2 增长，并不是两个相同时间复杂度的算法花费的时间是一样的 比如两个算法，一个算法花的时间是 n，另一个是 10000n，他们的时间复杂度都是 O(n)，但他们花费的时间相差一万倍 另外，现代计算机其实对于交换和比较的耗时其实是有差别的，另外，不同排序算法对 CPU 缓存的命中率也会影响排序的速度 我稍微看了一下你的代码，有个点注意一下，Java 数组本身就是协变的，没必要加那个协变泛型标注 |
| 16 GTD OP |
| 17 GTD OP @Cbdy #15 不过谢谢你的回复，就很灵异，jdk 8 下两个算法不论跑多少遍，都约等于 1：1，到了 jdk 11 以上，两个算法不论跑多少遍，都约等于 1：2 。这个解释不通啊 |
 | 18 liuhuan475 2020-11-19 23:10:57 +08:00 等一手大佬回复 |
 | 19 Jooooooooo 2020-11-19 23:11:35 +08:00 看下 GC 日志 不同版本默认 GC 参数会有差异 |
 | 20 socket1q1 2020-11-20 09:27:35 +08:00 等一手大佬回复 |
 | 21 acmore 2020-11-20 09:57:08 +08:00 1 从 Java 9 开始默认 GC Collector 从 Parallel GC 切换为了 G1 。再根据你切换垃圾回收策略对结果的影响来看，GC 应该是主要问题，可以找找看不同策略的侧重和注意事项。 |
 | 22 securityCoding 2020-11-20 11:56:37 +08:00 @secondwtq jmh,压测一定要用这个 |
 | 23 sagaxu 2020-11-20 12:48:44 +08:00 via Android 1 就是 gc 不同，试试 zgc 和 epsilongc |
| 24 secondwtq 2020-11-24 01:51:59 +08:00 1 分代 GC 需要加 Write Barrier 跟踪不同代对象之间的相互引用，G1 GC 相比 Parallel GC，Write Barrier 涉及的指令更多（实际并没有触发 GC，而是多执行了 10%-20% 的指令）。 Epsilon GC 作为 placeholder，并不需要 Write Barrier 。但是直接用 Epsilon GC 效果并不会更好，原因应该是 C2 犯了傻逼，在 JIT 时把一个判断子类型的检查提到了外面，正常情况这个检查不会被触发，但是只要被触发很有可能失败，所以 JIT 的函数没法用，只能用 OSR 的。OSR 的循环并没有 JIT 更优化，特别是 CompressedOops 这时又占了很多指令，用 -XX:-UseProfiledLoopPredicate 可以把这个行为纠正回来（ JDK 8 好像没有这个参数）。再加 -XX:-UseCompressedClassPointers 可以进一步减少指令数。 （或者可以不用 -XX:-UseProfiledLoopPredicate，换成 -XX:-UseCompressedOops，但是这样还是会跑 OSR 循环，效果不如 JIT 好，尤其是变量 t 的访问没有优化） 至于为啥倒霉的是插入排序，因为只有插入排序才需要在 inner loop 里面折腾引用值的赋值。别问，问就是天灭 Type Erasure，退 Java 保平安。祝楼主早日获得新生。 |
Select Language