排序时非常奇怪的效率怪癖
Very Strange Efficiency Quirks while Sorting
我目前正在学习数据结构 class，正如您所料，我们要做的其中一件事就是编写一些常见的排序。在编写我的插入排序算法时，我注意到 运行 比我导师的算法快得多（对于 400000 个数据点，我的算法用了大约 30 秒，他的算法用了大约 90 秒）。我通过电子邮件将我的代码发给他，当他们 运行 在同一台机器上时，结果相同。我们设法浪费了 40 多分钟，慢慢地将他的排序方法改为我的排序方法，直到完全一样，逐字逐句，除了一个看似随意的事情。首先，这是我的插入排序代码：
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
此时他的代码与我的代码完全相同，除了我们交换 A[j] 和 A[j - 1] 的行。他的代码做了以下事情：
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
我们发现这 3 行是罪魁祸首。因此，我的代码 运行ning 明显更快。困惑的是，我们 运行 javap -c 得到一个简单程序的字节码，该程序只有一个 main，其中包含一个数组声明，一个 int j 的变量声明和 3 行在我写的和他写的时候交换代码。这是我的交换方法的字节码：
Compiled from "me.java"
public class me {
public me();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iaload
12: istore_3
13: aload_1
14: iload_2
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: iaload
20: iastore
21: aload_1
22: iload_2
23: iconst_1
24: isub
25: iload_3
26: iastore
27: return
}
还有我导师方法的字节码：
Compiled from "instructor.java"
public class instructor {
public instructor();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iconst_1
12: isub
13: iaload
14: istore_3
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: aload_1
20: iload_2
21: iaload
22: iastore
23: aload_1
24: iload_2
25: iload_3
26: iastore
27: return
}
我看不出这些字节码之间有什么真正的区别。 什么可能导致这种 st运行ge 行为（我的代码仍然 运行 比他的代码快 ~3 倍，并且正如我们预期的那样，当我们为算法提供更大的数组时，这种差异会变得更加剧烈） ？这只是 Java 的一个 st运行ge 怪癖吗？此外，这是否发生在您的计算机上？ 作为参考，这是 运行 在 2014 年年中的 MacBook Pro 上，我的代码与此处显示的完全一样，他的代码被推断为与它完全相同的代码出现在这里除了那 3 行。
[编辑] 这是我的测试 classes:
public class Tester1 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
insertionSort(A);
System.out.println("My insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
}
第二个文件：
public class Tester2 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
otherInsertion(A);
System.out.println("Other insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] otherInsertion(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
j--;
}
}
return A;
}
}
和输出（没有参数，只有 java Tester1 和 java Tester2）：
My insertion sort took 37680.0 milliseconds.
Other insertion sort took 86358.0 milliseconds.
这些 运行 作为 2 个不同 JVM 中的 2 个独立文件。
TL;DR
您的实验无效，有许多变量可能会影响结果。最好使用微基准测试工具，例如 Caliper 或 JMH。我使用了这样的工具来检查 which method is faster to create indentation
你和你教授的差别可以忽略不计。
实验
对于我的实验，我有 745,038 个数据点。我创建了 3 个测试，你的，你的导师的版本和 Arrays.sort() 是 JDK.
的一部分
https://microbenchmarks.appspot.com/runs/8b8c0554-d3f1-4339-af5a-fdffd18dd053
根据结果，您的运行时间为：1,419,867.808 ns
你的导师是：1,429,798.824 ns
所以我们说的是 0.01 毫秒。
讲师的运行之间的差异较小。
JDK Arrays.sort() 在 1,779,042.513 ns 上慢了一个更大的幅度，比你的慢了 0.300 毫秒。
下面是我用来在 Caliper 中进行微基准测试的代码。
package net.trajano.caliper.test;
import java.io.DataInputStream;
import java.io.EOFException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import com.google.caliper.BeforeExperiment;
import com.google.caliper.Benchmark;
import com.google.caliper.api.VmOptions;
import com.google.caliper.runner.CaliperMain;
@VmOptions("-XX:-TieredCompilation")
public class SortBenchmark {
public static int[] insertionSort(final int[] A) {
// Check for illegal cases
if (A == null || A.length == 0) {
throw new IllegalArgumentException("A is not populated");
}
for (int i = 0; i < A.length; i++) {
int j = i;
while (j > 0 && A[j - 1] > A[j]) {
final int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
j--;
}
}
return A;
}
public static int[] insertionSortInstructor(final int[] A) {
// Check for illegal cases
if (A == null || A.length == 0) {
throw new IllegalArgumentException("A is not populated");
}
for (int i = 0; i < A.length; i++) {
int j = i;
while (j > 0 && A[j - 1] > A[j]) {
final int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
@BeforeExperiment
void setUp() throws IOException {
try (final DataInputStream dis = new DataInputStream(
Files.newInputStream(Paths.get("C:/Program Files/iTunes/iTunes.exe")))) {
final List<Integer> list = new ArrayList<Integer>();
while (true) {
try {
list.add(dis.readInt());
} catch (final EOFException e) {
break;
}
}
data = list.stream().mapToInt(i -> i).toArray();
System.out.println("Data size = " + data.length);
}
}
// data to sort
private static int[] data;
@Benchmark
public void insertionSort(final int reps) {
for (int i = 0; i < reps; i++) {
insertionSort(data);
}
}
@Benchmark
public void insertionSortInstructor(final int reps) {
for (int i = 0; i < reps; i++) {
insertionSortInstructor(data);
}
}
@Benchmark
public void jdkSort(final int reps) {
for (int i = 0; i < reps; i++) {
Arrays.sort(data);
}
}
public static void main(final String[] args) {
CaliperMain.main(SortBenchmark.class, args);
}
}
一边
老实说，我对结果感到惊讶，JDK 速度更慢。所以我看了一下the source code。 JDK 似乎根据阈值使用了三种排序算法（合并排序、少于 286 个元素的快速排序和少于 47 个元素的插入排序）。
由于我的数据集一开始就非常大，合并排序首先进行，它以数组的第二个副本的形式具有 O(n) space 复杂度。因此，可能是额外的堆分配导致了额外的时间。
这是loop unrolling优化和common的效果
子表达式消除。根据数组访问指令的顺序，JIT 在一种情况下可以消除冗余加载，但在另一种情况下则不能。
让我详细解释一下。在这两种情况下，JIT 都会展开内部循环的 4 次迭代。
例如对于你的情况：
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp; \
} A[j - 1] loaded immediately after store
if (A[j - 2] > A[j - 1]) { /
int temp = A[j - 1];
A[j - 1] = A[j - 2];
A[j - 2] = temp; \
} A[j - 2] loaded immediately after store
if (A[j - 3] > A[j - 2]) { /
int temp = A[j - 2];
A[j - 2] = A[j - 3];
A[j - 3] = temp; \
} A[j - 3] loaded immediately after store
if (A[j - 4] > A[j - 3]) { /
int temp = A[j - 3];
A[j - 3] = A[j - 4];
A[j - 4] = temp;
}
j -= 4;
}
然后JIT消除了冗余的数组加载，生成的程序集看起来像
0x0000000002d53a70: movslq %r11d,%r10
0x0000000002d53a73: lea 0x0(%rbp,%r10,4),%r10
0x0000000002d53a78: mov 0x10(%r10),%ebx ; ebx = A[j]
0x0000000002d53a7c: mov 0xc(%r10),%r9d ; r9d = A[j - 1]
0x0000000002d53a80: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a83: jle 0x0000000002d539f3
0x0000000002d53a89: mov %r9d,0x10(%r10) ; A[j] = r9d
0x0000000002d53a8d: mov %ebx,0xc(%r10) ; A[j - 1] = ebx
; }
0x0000000002d53a91: mov 0x8(%r10),%r9d ; r9d = A[j - 2]
0x0000000002d53a95: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a98: jle 0x0000000002d539f3
0x0000000002d53a9e: mov %r9d,0xc(%r10) ; A[j - 1] = r9d
0x0000000002d53aa2: mov %ebx,0x8(%r10) ; A[j - 2] = ebx
; }
0x0000000002d53aa6: mov 0x4(%r10),%r9d ; r9d = A[j - 3]
0x0000000002d53aaa: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53aad: jle 0x0000000002d539f3
0x0000000002d53ab3: mov %r9d,0x8(%r10) ; A[j - 2] = r9d
0x0000000002d53ab7: mov %ebx,0x4(%r10) ; A[j - 3] = ebx
; }
0x0000000002d53abb: mov (%r10),%r8d ; r8d = A[j - 4]
0x0000000002d53abe: cmp %ebx,%r8d ; if (r8d > ebx) {
0x0000000002d53ac1: jle 0x0000000002d539f3
0x0000000002d53ac7: mov %r8d,0x4(%r10) ; A[j - 3] = r8
0x0000000002d53acb: mov %ebx,(%r10) ; A[j - 4] = ebx
; }
0x0000000002d53ace: add [=11=]xfffffffc,%r11d ; j -= 4
0x0000000002d53ad2: cmp [=11=]x3,%r11d ; while (j > 3)
0x0000000002d53ad6: jg 0x0000000002d53a70
您讲师的代码在循环展开后看起来会有所不同：
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp; <-- another store instruction between A[j - 1] access
}
if (A[j - 2] > A[j - 1]) {
int temp = A[j - 2];
A[j - 2] = A[j - 1];
A[j - 1] = temp;
}
...
JVM 不会消除 A[j - 1] 的后续加载，因为在先前的 A[j - 1] 加载之后还有另一个存储指令（尽管在这种特殊情况下这种优化在理论上是可能的）。
所以，汇编代码的加载指令会比较多，性能也会变差：
0x0000000002b53a00: cmp %r8d,%r10d ; if (r10d > r8d) {
0x0000000002b53a03: jle 0x0000000002b53973
0x0000000002b53a09: mov %r8d,0xc(%rbx) ; A[j - 1] = r8d
0x0000000002b53a0d: mov %r10d,0x10(%rbx) ; A[j] = r10d
; }
0x0000000002b53a11: mov 0xc(%rbx),%r10d ; r10d = A[j - 1]
0x0000000002b53a15: mov 0x8(%rbx),%r9d ; r9d = A[j - 2]
0x0000000002b53a19: cmp %r10d,%r9d ; if (r9d > r10d) {
0x0000000002b53a1c: jle 0x0000000002b53973
0x0000000002b53a22: mov %r10d,0x8(%rbx) ; A[j - 2] = r10d
0x0000000002b53a26: mov %r9d,0xc(%rbx) ; A[j - 1] = r9d
; }
0x0000000002b53a2a: mov 0x8(%rbx),%r8d ; r8d = A[j - 2]
0x0000000002b53a2e: mov 0x4(%rbx),%r10d ; r10d = A[j - 3]
请注意，如果您 运行 JVM 禁用了循环展开优化 (-XX:LoopUnrollLimit=0)，则两种情况的性能将相同。
P.S. 两种方法的完全反汇编都可用 here，使用
获得
-XX:CompileOnly=Test -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly
您不会在 Java 字节码中看到任何解释。像这样的事情可能是机器指令（由即时 JIT 编译器创建）或什至是微处理器（特别是其中一个处理器高速缓存的影响）的结果。
这里要注意一点，在这个排序算法中，对于循环的每一次迭代，只需要加载A[j]，因为A[j-1]是在上一次迭代中加载的。所以最近加载的值是 A[j]（假设我刚才陈述的事实在某种程度上被利用了）。因此，在循环中，首先存储 A[j] 的算法可能表现不同，因为该值最近由循环检查加载，因此该值更有可能保留在寄存器或处理器缓存中，或者受制于由于 JIT 生成的机器代码中的优化，只需一次内存加载。
确实（如上述答案所示）很难准确了解正在执行的是哪一系列机器指令（JIT 有几个不同级别的编译，每个都有不同的优化，基于执行频率方法被执行，并且有许多不同的 JIT 优化可能相互作用导致不同的机器代码）。也很难知道哪些内存访问必须进入 RAM，哪些可以通过处理器中的内存缓存命中来避免。毫无疑问，上述效果的某些组合正在影响此处的性能。算法的顺序对性能的影响最大，但除此之外，JIT 和微处理器中的许多优化都会影响性能，但并非所有优化都显而易见。
我的直觉是，这是处理器的内存缓存更好地配合您的操作序列的结果，部分原因是每次循环迭代只需要加载 A[j]。
我目前正在学习数据结构 class，正如您所料，我们要做的其中一件事就是编写一些常见的排序。在编写我的插入排序算法时，我注意到 运行 比我导师的算法快得多（对于 400000 个数据点，我的算法用了大约 30 秒，他的算法用了大约 90 秒）。我通过电子邮件将我的代码发给他，当他们 运行 在同一台机器上时，结果相同。我们设法浪费了 40 多分钟，慢慢地将他的排序方法改为我的排序方法，直到完全一样，逐字逐句，除了一个看似随意的事情。首先，这是我的插入排序代码：
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
此时他的代码与我的代码完全相同，除了我们交换 A[j] 和 A[j - 1] 的行。他的代码做了以下事情：
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
我们发现这 3 行是罪魁祸首。因此，我的代码 运行ning 明显更快。困惑的是，我们 运行 javap -c 得到一个简单程序的字节码，该程序只有一个 main，其中包含一个数组声明，一个 int j 的变量声明和 3 行在我写的和他写的时候交换代码。这是我的交换方法的字节码：
Compiled from "me.java"
public class me {
public me();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iaload
12: istore_3
13: aload_1
14: iload_2
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: iaload
20: iastore
21: aload_1
22: iload_2
23: iconst_1
24: isub
25: iload_3
26: iastore
27: return
}
还有我导师方法的字节码：
Compiled from "instructor.java"
public class instructor {
public instructor();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: sipush 10000
3: newarray int
5: astore_1
6: bipush 10
8: istore_2
9: aload_1
10: iload_2
11: iconst_1
12: isub
13: iaload
14: istore_3
15: aload_1
16: iload_2
17: iconst_1
18: isub
19: aload_1
20: iload_2
21: iaload
22: iastore
23: aload_1
24: iload_2
25: iload_3
26: iastore
27: return
}
我看不出这些字节码之间有什么真正的区别。 什么可能导致这种 st运行ge 行为（我的代码仍然 运行 比他的代码快 ~3 倍，并且正如我们预期的那样，当我们为算法提供更大的数组时，这种差异会变得更加剧烈） ？这只是 Java 的一个 st运行ge 怪癖吗？此外，这是否发生在您的计算机上？ 作为参考，这是 运行 在 2014 年年中的 MacBook Pro 上，我的代码与此处显示的完全一样，他的代码被推断为与它完全相同的代码出现在这里除了那 3 行。
[编辑] 这是我的测试 classes:
public class Tester1 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
insertionSort(A);
System.out.println("My insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] insertionSort(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
}
第二个文件：
public class Tester2 {
public static void main(String[] args){
int[] A = new int[400000];
for(int i = 0; i < A.length; i++){
A[i] = (int) (Math.random() * Integer.MAX_VALUE);
}
double start = System.currentTimeMillis();
otherInsertion(A);
System.out.println("Other insertion sort took " + (System.currentTimeMillis() - start) + " milliseconds.");
}
public static int[] otherInsertion(int[] A){
//Check for illegal cases
if (A == null || A.length == 0){
throw new IllegalArgumentException("A is not populated");
}
for(int i = 0; i < A.length; i++){
int j = i;
while(j > 0 && A[j - 1] > A[j]){
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
j--;
}
}
return A;
}
}
和输出（没有参数，只有 java Tester1 和 java Tester2）：
My insertion sort took 37680.0 milliseconds.
Other insertion sort took 86358.0 milliseconds.
这些 运行 作为 2 个不同 JVM 中的 2 个独立文件。
TL;DR
您的实验无效，有许多变量可能会影响结果。最好使用微基准测试工具，例如 Caliper 或 JMH。我使用了这样的工具来检查 which method is faster to create indentation
你和你教授的差别可以忽略不计。
实验
对于我的实验，我有 745,038 个数据点。我创建了 3 个测试，你的，你的导师的版本和 Arrays.sort() 是 JDK.
https://microbenchmarks.appspot.com/runs/8b8c0554-d3f1-4339-af5a-fdffd18dd053
根据结果，您的运行时间为：1,419,867.808 ns 你的导师是：1,429,798.824 ns
所以我们说的是 0.01 毫秒。
讲师的运行之间的差异较小。
JDK Arrays.sort() 在 1,779,042.513 ns 上慢了一个更大的幅度，比你的慢了 0.300 毫秒。
下面是我用来在 Caliper 中进行微基准测试的代码。
package net.trajano.caliper.test;
import java.io.DataInputStream;
import java.io.EOFException;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import com.google.caliper.BeforeExperiment;
import com.google.caliper.Benchmark;
import com.google.caliper.api.VmOptions;
import com.google.caliper.runner.CaliperMain;
@VmOptions("-XX:-TieredCompilation")
public class SortBenchmark {
public static int[] insertionSort(final int[] A) {
// Check for illegal cases
if (A == null || A.length == 0) {
throw new IllegalArgumentException("A is not populated");
}
for (int i = 0; i < A.length; i++) {
int j = i;
while (j > 0 && A[j - 1] > A[j]) {
final int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp;
j--;
}
}
return A;
}
public static int[] insertionSortInstructor(final int[] A) {
// Check for illegal cases
if (A == null || A.length == 0) {
throw new IllegalArgumentException("A is not populated");
}
for (int i = 0; i < A.length; i++) {
int j = i;
while (j > 0 && A[j - 1] > A[j]) {
final int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp;
j--;
}
}
return A;
}
@BeforeExperiment
void setUp() throws IOException {
try (final DataInputStream dis = new DataInputStream(
Files.newInputStream(Paths.get("C:/Program Files/iTunes/iTunes.exe")))) {
final List<Integer> list = new ArrayList<Integer>();
while (true) {
try {
list.add(dis.readInt());
} catch (final EOFException e) {
break;
}
}
data = list.stream().mapToInt(i -> i).toArray();
System.out.println("Data size = " + data.length);
}
}
// data to sort
private static int[] data;
@Benchmark
public void insertionSort(final int reps) {
for (int i = 0; i < reps; i++) {
insertionSort(data);
}
}
@Benchmark
public void insertionSortInstructor(final int reps) {
for (int i = 0; i < reps; i++) {
insertionSortInstructor(data);
}
}
@Benchmark
public void jdkSort(final int reps) {
for (int i = 0; i < reps; i++) {
Arrays.sort(data);
}
}
public static void main(final String[] args) {
CaliperMain.main(SortBenchmark.class, args);
}
}
一边
老实说，我对结果感到惊讶，JDK 速度更慢。所以我看了一下the source code。 JDK 似乎根据阈值使用了三种排序算法（合并排序、少于 286 个元素的快速排序和少于 47 个元素的插入排序）。
由于我的数据集一开始就非常大，合并排序首先进行，它以数组的第二个副本的形式具有 O(n) space 复杂度。因此，可能是额外的堆分配导致了额外的时间。
这是loop unrolling优化和common的效果 子表达式消除。根据数组访问指令的顺序，JIT 在一种情况下可以消除冗余加载，但在另一种情况下则不能。
让我详细解释一下。在这两种情况下，JIT 都会展开内部循环的 4 次迭代。
例如对于你的情况：
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j];
A[j] = A[j - 1];
A[j - 1] = temp; \
} A[j - 1] loaded immediately after store
if (A[j - 2] > A[j - 1]) { /
int temp = A[j - 1];
A[j - 1] = A[j - 2];
A[j - 2] = temp; \
} A[j - 2] loaded immediately after store
if (A[j - 3] > A[j - 2]) { /
int temp = A[j - 2];
A[j - 2] = A[j - 3];
A[j - 3] = temp; \
} A[j - 3] loaded immediately after store
if (A[j - 4] > A[j - 3]) { /
int temp = A[j - 3];
A[j - 3] = A[j - 4];
A[j - 4] = temp;
}
j -= 4;
}
然后JIT消除了冗余的数组加载，生成的程序集看起来像
0x0000000002d53a70: movslq %r11d,%r10
0x0000000002d53a73: lea 0x0(%rbp,%r10,4),%r10
0x0000000002d53a78: mov 0x10(%r10),%ebx ; ebx = A[j]
0x0000000002d53a7c: mov 0xc(%r10),%r9d ; r9d = A[j - 1]
0x0000000002d53a80: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a83: jle 0x0000000002d539f3
0x0000000002d53a89: mov %r9d,0x10(%r10) ; A[j] = r9d
0x0000000002d53a8d: mov %ebx,0xc(%r10) ; A[j - 1] = ebx
; }
0x0000000002d53a91: mov 0x8(%r10),%r9d ; r9d = A[j - 2]
0x0000000002d53a95: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53a98: jle 0x0000000002d539f3
0x0000000002d53a9e: mov %r9d,0xc(%r10) ; A[j - 1] = r9d
0x0000000002d53aa2: mov %ebx,0x8(%r10) ; A[j - 2] = ebx
; }
0x0000000002d53aa6: mov 0x4(%r10),%r9d ; r9d = A[j - 3]
0x0000000002d53aaa: cmp %ebx,%r9d ; if (r9d > ebx) {
0x0000000002d53aad: jle 0x0000000002d539f3
0x0000000002d53ab3: mov %r9d,0x8(%r10) ; A[j - 2] = r9d
0x0000000002d53ab7: mov %ebx,0x4(%r10) ; A[j - 3] = ebx
; }
0x0000000002d53abb: mov (%r10),%r8d ; r8d = A[j - 4]
0x0000000002d53abe: cmp %ebx,%r8d ; if (r8d > ebx) {
0x0000000002d53ac1: jle 0x0000000002d539f3
0x0000000002d53ac7: mov %r8d,0x4(%r10) ; A[j - 3] = r8
0x0000000002d53acb: mov %ebx,(%r10) ; A[j - 4] = ebx
; }
0x0000000002d53ace: add [=11=]xfffffffc,%r11d ; j -= 4
0x0000000002d53ad2: cmp [=11=]x3,%r11d ; while (j > 3)
0x0000000002d53ad6: jg 0x0000000002d53a70
您讲师的代码在循环展开后看起来会有所不同：
while (j > 3) {
if (A[j - 1] > A[j]) {
int temp = A[j - 1];
A[j - 1] = A[j];
A[j] = temp; <-- another store instruction between A[j - 1] access
}
if (A[j - 2] > A[j - 1]) {
int temp = A[j - 2];
A[j - 2] = A[j - 1];
A[j - 1] = temp;
}
...
JVM 不会消除 A[j - 1] 的后续加载，因为在先前的 A[j - 1] 加载之后还有另一个存储指令（尽管在这种特殊情况下这种优化在理论上是可能的）。
所以，汇编代码的加载指令会比较多，性能也会变差：
0x0000000002b53a00: cmp %r8d,%r10d ; if (r10d > r8d) {
0x0000000002b53a03: jle 0x0000000002b53973
0x0000000002b53a09: mov %r8d,0xc(%rbx) ; A[j - 1] = r8d
0x0000000002b53a0d: mov %r10d,0x10(%rbx) ; A[j] = r10d
; }
0x0000000002b53a11: mov 0xc(%rbx),%r10d ; r10d = A[j - 1]
0x0000000002b53a15: mov 0x8(%rbx),%r9d ; r9d = A[j - 2]
0x0000000002b53a19: cmp %r10d,%r9d ; if (r9d > r10d) {
0x0000000002b53a1c: jle 0x0000000002b53973
0x0000000002b53a22: mov %r10d,0x8(%rbx) ; A[j - 2] = r10d
0x0000000002b53a26: mov %r9d,0xc(%rbx) ; A[j - 1] = r9d
; }
0x0000000002b53a2a: mov 0x8(%rbx),%r8d ; r8d = A[j - 2]
0x0000000002b53a2e: mov 0x4(%rbx),%r10d ; r10d = A[j - 3]
请注意，如果您 运行 JVM 禁用了循环展开优化 (-XX:LoopUnrollLimit=0)，则两种情况的性能将相同。
P.S. 两种方法的完全反汇编都可用 here，使用
获得
-XX:CompileOnly=Test -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly
您不会在 Java 字节码中看到任何解释。像这样的事情可能是机器指令（由即时 JIT 编译器创建）或什至是微处理器（特别是其中一个处理器高速缓存的影响）的结果。
这里要注意一点，在这个排序算法中，对于循环的每一次迭代，只需要加载A[j]，因为A[j-1]是在上一次迭代中加载的。所以最近加载的值是 A[j]（假设我刚才陈述的事实在某种程度上被利用了）。因此，在循环中，首先存储 A[j] 的算法可能表现不同，因为该值最近由循环检查加载，因此该值更有可能保留在寄存器或处理器缓存中，或者受制于由于 JIT 生成的机器代码中的优化，只需一次内存加载。
确实（如上述答案所示）很难准确了解正在执行的是哪一系列机器指令（JIT 有几个不同级别的编译，每个都有不同的优化，基于执行频率方法被执行，并且有许多不同的 JIT 优化可能相互作用导致不同的机器代码）。也很难知道哪些内存访问必须进入 RAM，哪些可以通过处理器中的内存缓存命中来避免。毫无疑问，上述效果的某些组合正在影响此处的性能。算法的顺序对性能的影响最大，但除此之外，JIT 和微处理器中的许多优化都会影响性能，但并非所有优化都显而易见。
我的直觉是，这是处理器的内存缓存更好地配合您的操作序列的结果，部分原因是每次循环迭代只需要加载 A[j]。