javac 是否无法优化我的代码？

Question

我一直在测试 cpu 缓存优化，我做的一个简单测试是对嵌套循环内的 2048x2048 整数矩阵求和，首先我尝试使用顺序索引（总是跳转到下一个内存整数）然后使用长宽度内存访问（跳到下一个整数 2048），我运行这些代码每一个 1000 次然后我得到每一个的平均执行时间，测试是在 Intel Core 2 上执行的Duo E4600 2.4 GHz，没有其他可能影响后台执行时间的进程，结果为：

Sequential index: average: 8ms.

Long width memory access: average: 43.

这里是源代码：

import java.util.Arrays;
import java.util.Random;

public class Main {

    public static void main(String[] args) {
        int [][] matrix = new int[2048][2048];
        
        long tInitial = 0;
        long tFinal = 0;
        
        long [] avgExecTime = new long[1000];
        
        for (int i = 0; i < avgExecTime.length; i++) {
            fillWithRandomNumbers(matrix);
            
            tInitial = System.currentTimeMillis();
            
            sumSequentially(matrix);
            
            tFinal = System.currentTimeMillis();
            
            avgExecTime[i] = tFinal - tInitial;
        }
        
        System.out.println(Arrays.stream(avgExecTime).sum() / avgExecTime.length);
        
        for (int i = 0; i < avgExecTime.length; i++) {
            fillWithRandomNumbers(matrix);
            
            tInitial = System.currentTimeMillis();
            
            sumRandomly(matrix);
            
            tFinal = System.currentTimeMillis();
            
            avgExecTime[i] = tFinal - tInitial;
        }
        
        System.out.println(Arrays.stream(avgExecTime).sum() / avgExecTime.length);
    }
    
    public static void fillWithRandomNumbers(int [][] matrix) {
        Random r = new Random();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = r.nextInt();
            }
        }
    }
    
    public static long sumSequentially(int [][] matrix) {
        long total = 0;
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                total += matrix[i][j];
            }
        }
        
        return total;
    }
    
    public static long sumRandomly(int [][] matrix) {
        long total = 0;
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                total += matrix[j][i];
            }
        }
        
        return total;
    }
}

我的问题是：

考虑到 sumRandomly 和 sumSequentially 的最终结果相同，为什么 java 编译器没有优化 sumRandomly 方法？
java 编译器是否会考虑可能存在一个线程在求和时更改我的矩阵参数值，这可能会改变结果？

我已经尝试过不使用方法并在 main 方法上进行所有操作，结果几乎相同。

Answer 1

javac 不会优化接近这个程度的任何地方，而 JIT 可能。这在某些方面为 JVM 提供了优势，因为可以根据运行时观察到的特定行为以及 JVM 所在处理器的特定功能和怪癖来定制优化运行.

您还假设了 Java 虚拟机及其对数组（尤其是嵌套数组）的处理。虽然诸如 C and/or Fortran 之类的语言可以处理具有矩形数据结构的多维数组，但 Java 不会（因此允许 "ragged arrays"，即对于 int[][]，arr[0].length 不必等于 arr[1].length.

这是使用 对象引用数组 实现的，其中每个对象引用都指向一个 int[]。显然，Java 进行边界检查，如果在紧密循环中访问单个数组，这似乎更容易检测和优化，而不是在多个数组上访问相同的索引。

Answer 2

正如您在 hexafraction 的回答中看到的，您需要的优化类型不可行。无论如何，我相信 java 编译器可能会进行微小的优化，那是因为时代不同了。

我发布这个答案只是为了让这些术语变得更加明显，因为我认为它们很重要。

数组访问函数

在Java语言中，所有被调用的非原始变量都是引用，这意味着数据不能直接访问，并且可能不是顺序存储的。

您的数据类型是长数据类型，即原始数据，但您将它们存储到数组中，这不是原始数据。当您尝试像 matrix[i][j] 那样访问数组的值时，JVM 将必须执行至少三个操作。找到 matrix 对象的引用，找到对 [i] 项目的引用，最后找到对你的值 [j].

的引用

正如我所说，这些值可能不会按顺序存储，因此在大多数情况下，缓存不会有太大帮助。查看您的代码，我们可以看到两种不同形式的对象访问，matrix[i][j] 和 matrix[j][i] 总是 i 与外循环索引和 j 内部循环的索引.在这种情况下，我们可以对第一种情况进行简单的优化，因为第一个数组访问的值将 return 在所有 j 循环中相同，因此编译器可以看到这一点并说，“等等！我不需要在每个循环中都找到相同的结果。我会缓存这个！”，因此您的代码将计算为类似：

public static long sumSequentially(int [][] matrix) {
    long total = 0;

    for (int i = 0; i < matrix.length; i++) {
        long[matrix[i].length] matrixi = matrix[i];
        for (int j = 0; j < matrixi.length; j++) {
            total += matrixi[j];
        }
    }

    return total;
}

关于第二种方法，这不是真的。 j索引每次内部循环都会改变，所有循环中第一个和第二个数组访问结果都会随着他改变。

cpu缓存

我用 C 编写了这个示例，因为 C 是 CPU 缓存的有效方案，我相信这是您的主要疑问。

结果是：

Sequential sum average: 2ms.

Random sum average: 39ms.

所以，我们有几乎相同的场景。 C 将数据按顺序存储在数组中，在我们拥有的多维矩阵中（考虑 char[2][2] 作为类型）：

+--------------+------------+
| Ram address  | Item index | 
+--------------+------------+
| 00000120000  | [0][0]     | 
+--------------+------------+
| 00000120001  | [0][1]     | 
+--------------+------------+
| 00000120002  | [1][0]     | 
+--------------+------------+
| 00000120003  | [1][1]     | 
+--------------+------------+

CPU 缓存数据和指令，无需返回 RAM 即可拥有它们。当我们顺序访问数据时， CPU 将我们获取的数据的下一个数据填充到缓存中，然后当我们访问一个时，他将缓存下一个 N 个值，问题是当我们必须访问N + 1 个值，所以缓存需要得到验证，并且会有一批数据从 RAM 中移动。

第二种方式访问数据时，会跳转各个RAM地址，然后返回。几乎每次跳转都会使缓存失效，并且缓存会再次被填满，因此您需要更多的操作并且过程会变慢。如果你想知道更多，我前段时间看到一个Gallery of Processor cache effects

这两种语言具有相似的行为，但出于不同的原因，我想那是因为您感到困惑。

javac 是否无法优化我的代码？

Is javac failing on optimize my code?

java

jit

javac

cpu-cache

数组访问函数

cpu缓存