为什么减少循环次数不会加速程序？

Question

我有一个程序需要执行大量矩阵乘法操作。为了提高效率，我尝试通过减少代码中的循环次数来加速它（稍后我会尝试使用矩阵数学库）。结果发现并没有加快速度。我用一些示例代码复制了这个问题。我的猜测是testOne()比testTwo()更快，因为它不会创建任何新的数组，并且循环次数只有testTwo()的三分之一。但在我的电脑上，它运行起来需要两倍的时间：

5000个epoch的testOne持续时间: 657, 循环次数: 64000000

5000个epoch的testTwo持续时间: 365, 循环次数: 192000000

我的猜测是multOne()比multTwo()慢，因为在multOne()中，CPU不能像在multTwo()中那样写入顺序内存地址。这听起来合理吗？如果有任何解释，请告诉我。

import java.util.Random;

public class ArrayTest {

    double[] arrayOne;
    double[] arrayTwo;
    double[] arrayThree;

    double[][] matrix;

    double[] input;
    int loopCount;

    int rows;
    int columns;

    public ArrayTest(int rows, int columns) {
        this.rows = rows;
        this.columns = columns;
        this.loopCount = 0;
        arrayOne = new double[rows];
        arrayTwo = new double[rows];
        arrayThree = new double[rows];
        matrix = new double[rows][columns];
        Random random = new Random();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                matrix[i][j] = random.nextDouble();
            }
        }
    }

    public void testOne(double[] input, int epochs) {
        this.input = input;
        this.loopCount = 0;
        long start = System.currentTimeMillis();
        long duration;
        for (int i = 0; i < epochs; i++) {
            multOne();
        }
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration for testOne with " + epochs + " epochs: " + duration + ", loopCount: " + loopCount);
    }

    public void multOne() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                arrayOne[i] += matrix[i][j] * arrayOne[i] * input[j];
                arrayTwo[i] += matrix[i][j] * arrayTwo[i] * input[j];
                arrayThree[i] += matrix[i][j] * arrayThree[i] * input[j];
                loopCount++;
            }
        }
    }

    public void testTwo(double[] input, int epochs) {

        this.loopCount = 0;
        long start = System.currentTimeMillis();
        long duration;
        for (int i = 0; i < epochs; i++) {
            arrayOne = multTwo(matrix, arrayOne, input);
            arrayTwo = multTwo(matrix, arrayTwo, input);
            arrayThree = multTwo(matrix, arrayThree, input);
        }
        duration = System.currentTimeMillis() - start;
        System.out.println("Duration for testTwo with " + epochs + " epochs: " + duration + ", loopCount: " + loopCount);
    }

    public double[] multTwo(double[][] matrix, double[] array, double[] input) {
        double[] newArray = new double[rows];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                newArray[i] += matrix[i][j] * array[i] * input[j];
                loopCount++;
            }
        }
        return newArray;
    }

    public static void main(String[] args) {
        int rows = 100;
        int columns = 128;
        ArrayTest arrayTest = new ArrayTest(rows, columns);
        Random random = new Random();
        double[] input = new double[columns];
        for (int i = 0; i < columns; i++) {
            input[i] = random.nextDouble();
        }
        arrayTest.testOne(input, 5000);
        arrayTest.testTwo(input, 5000);
    }
}

- KrakathorOfTheLavaPeople

---

在Java中进行基准测试确实非常困难。我不会相信你的测量结果——编写欺骗性基准测试非常容易。如果您希望获得可靠的数据，请使用JMH或类似工具。 - Louis Wasserman

这里有一个提示，可以帮助你开始自己回答它（尽管看到一个良好的问题很好）：将mult1更改为使用新数组而不是arrayOne +=，arrayTwo +=和arrayThree +=，然后在方法末尾分配arrayOne，arrayTwo和arrayThree。 - Chill

那可能是真的。 - Jean-Baptiste Yunès

是的，以纳秒计算时间。 - Pavan

在Java中，每个循环指令需要近1个CPU周期的计算时间，约为0.1纳秒。因此，通过减少循环次数，肯定可以加快总共所需的时间。难以获得毫秒级别的变化。因此，请尝试获取以纳秒为单位的所需时间。 - Pavan

Answer 1

你的测试用例所花费的时间不同，这是因为它们并不做相同的事情。由于你比较的两个循环在功能上并不相同，迭代次数并不是一个好的指标。

testOne 比 testTwo 花费更长的时间是因为：

1. 在 multOne 中，你在每次 j 循环的迭代中原地更新 arrayOne[i]。这意味着对于内部循环 j 的每次迭代，你都使用了 arrayOne[i] 的新值，该值是在前一次迭代中计算出来的。这会创建一个循环依赖关系，这对编译器来说更难以优化，因为你需要在下一个 CPU 时钟周期上要求操作 matrix[i][j] * arrayOne[i] * input[j] 的输出结果。这在浮点运算中通常具有几个时钟周期的延迟，因此会导致停顿，从而降低性能。

2. 在 testTwo 中，你只在每个 epoch 迭代中一次更新 arrayOne，由于没有存在循环依赖关系，因此循环可以高效地进行向量化处理，这会产生更好的缓存和算术性能。

- paul-g