Java：微优化数组操作

Question

我正在尝试制作一个简单的前馈神经网络的 Java 端口。
这显然涉及大量的数值计算，因此我正在尝试尽可能优化我的中央循环。结果在 float 数据类型的限制内应该是正确的。

我当前的代码如下所示（已删除错误处理和初始化）：

/**
 * Simple implementation of a feedforward neural network. The network supports
 * including a bias neuron with a constant output of 1.0 and weighted synapses
 * to hidden and output layers.
 * 
 * @author Martin Wiboe
 */
public class FeedForwardNetwork {
private final int outputNeurons;    // No of neurons in output layer
private final int inputNeurons;     // No of neurons in input layer
private int largestLayerNeurons;    // No of neurons in largest layer
private final int numberLayers;     // No of layers
private final int[] neuronCounts;   // Neuron count in each layer, 0 is input
                                // layer.
private final float[][][] fWeights; // Weights between neurons.
                                    // fWeight[fromLayer][fromNeuron][toNeuron]
                                    // is the weight from fromNeuron in
                                    // fromLayer to toNeuron in layer
                                    // fromLayer+1.
private float[][] neuronOutput;     // Temporary storage of output from previous layer


public float[] compute(float[] input) {
    // Copy input values to input layer output
    for (int i = 0; i < inputNeurons; i++) {
        neuronOutput[0][i] = input[i];
    }

    // Loop through layers
    for (int layer = 1; layer < numberLayers; layer++) {

        // Loop over neurons in the layer and determine weighted input sum
        for (int neuron = 0; neuron < neuronCounts[layer]; neuron++) {
            // Bias neuron is the last neuron in the previous layer
            int biasNeuron = neuronCounts[layer - 1];

            // Get weighted input from bias neuron - output is always 1.0
            float activation = 1.0F * fWeights[layer - 1][biasNeuron][neuron];

            // Get weighted inputs from rest of neurons in previous layer
            for (int inputNeuron = 0; inputNeuron < biasNeuron; inputNeuron++) {
                activation += neuronOutput[layer-1][inputNeuron] * fWeights[layer - 1][inputNeuron][neuron];
            }

            // Store neuron output for next round of computation
            neuronOutput[layer][neuron] = sigmoid(activation);
        }
    }

    // Return output from network = output from last layer
    float[] result = new float[outputNeurons];
    for (int i = 0; i < outputNeurons; i++)
        result[i] = neuronOutput[numberLayers - 1][i];

    return result;
}

private final static float sigmoid(final float input) {
    return (float) (1.0F / (1.0F + Math.exp(-1.0F * input)));
}
}

我正在使用 -server 选项运行 JVM，到目前为止，我的代码比类似的 C 代码慢 25% 到 50%。我可以做些什么来改善这种情况？

谢谢

Martin Wiboe

编辑#1：在看到大量回复后，我可能应该澄清我们场景中的数字。在典型的运行过程中，该方法将使用不同的输入被调用大约 50.000 次。典型的网络有 numberLayers = 3 层，分别有 190、2 和 1 个神经元。因此，最里面的循环将有大约 2*191+3=385 次迭代（当计算第 0 层和第 1 层中添加的偏置神经元时）

编辑#1：在实现本线程中的各种建议后，我们的实现实际上与 C 版本一样快（大约 2% 以内）。感谢您的帮助！所有建议都有帮助，但由于我只能将一个答案标记为正确答案，因此我会将其交给@Durandal，以提供数组优化建议并成为唯一预先计算 for 循环的答案标头。

Answer 1

一些提示。

• 在最里面的循环中，考虑如何遍历 CPU 缓存并重新排列矩阵，以便按顺序访问最外面的数组。这将导致您按顺序访问缓存，而不是到处跳转。高速缓存命中可以比高速缓存未命中快两个数量级。
  例如，重构 fWeights，使其作为

激活 += NeuronOutput[layer-1][inputNeuron] * fWeights[layer - 1][neuron][inputNeuron] 进行访问；

• 不要在循环内（每次）执行可以在循环外完成（一次）的工作。当您可以将其放入局部变量时，不要每次都执行 [layer -1] 查找。您的 IDE 应该能够轻松地重构它。

• Java中的多维数组不如C中的高效。它们实际上是单维数组的多层。您可以重构代码，以便仅使用一维数组。

• 当您可以将结果数组作为参数传递时，不要返回新数组。 （节省了每次调用时创建新对象的麻烦）。

• 与其到处执行layer-1，为什么不使用layer1作为layer-1并使用layer1+1代替layer。

Answer 2

抛开实际的数学计算不谈，Java 中的数组索引本身就是一个性能消耗者。考虑一下 Java 没有真正的多维数组，而是将它们实现为数组的数组。在最里面的循环中，您可以访问多个索引，其中一些索引实际上在该循环中是恒定的。部分数组访问可以移到循环之外：

final int[] neuronOutputSlice = neuronOutput[layer - 1];
final int[][] fWeightSlice = fWeights[layer - 1];
for (int inputNeuron = 0; inputNeuron < biasNeuron; inputNeuron++) {
    activation += neuronOutputSlice[inputNeuron] * fWeightsSlice[inputNeuron][neuron];
}

服务器 JIT 可能会执行类似的代码不变移动，找出答案的唯一方法是更改​​并分析它。在客户端 JIT 上，无论如何这都会提高性能。
您可以尝试的另一件事是预先计算 for 循环退出条件，如下所示：

for (int neuron = 0; neuron < neuronCounts[layer]; neuron++) { ... }
// transform to precalculated exit condition (move invariant array access outside loop)
for (int neuron = 0, neuronCount = neuronCounts[layer]; neuron < neuronCount; neuron++) { ... }

JIT 可能已经为您执行此操作，因此请分析是否有帮助。

与 1.0F 相乘是否有让我困惑的地方？：

float activation = 1.0F * fWeights[layer - 1][biasNeuron][neuron];

其他可能以牺牲可读性为代价提高速度的东西：手动内联 sigmoid() 函数（JIT 对内联有非常严格的限制，并且函数可能更大） 。
向后运行循环可能会稍微快一些（当然它不会改变结果），因为针对零测试循环索引比检查局部变量要便宜一些（最里面的循环又是一个潜在的候选者，但不要期望输出在所有情况下都 100% 相同，因为添加浮点数 a + b + c 可能与 a + c + b 不同）。

Answer 3

首先，不要这样做：

// Copy input values to input layer output
for (int i = 0; i < inputNeurons; i++) {
    neuronOutput[0][i] = input[i];
}

但是这样：

System.arraycopy( input, 0, neuronOutput[0], 0, inputNeurons );

Answer 4

我要调查的第一件事是查看 Math.exp 是否会减慢您的速度。请参阅这篇关于 Math.exp 近似的文章了解本机替代方案。

Answer 5

用整数步长传递函数替换昂贵的浮点 sigmoid 传递函数。

sigmoid 传递函数是有机模拟突触学习的模型，而它又似乎是阶跃函数的模型。

历史上的先例是，Hinton 直接根据关于真实突触的认知科学理论的第一原理设计了反向传播算法，而这些理论又基于真实的模拟测量，结果是 S 型曲线。

但sigmoid传递函数似乎是数字阶跃函数的有机模型，当然不能直接有机实现。

不要对模型进行建模，而是用阶跃函数的直接数字实现（小于零 = -1，大于零 = +1）替换有机 sigmoid 传递函数的昂贵浮点实现。

大脑做不到这一点，但反向传播可以！

这不仅可以线性且显着地提高单次学习迭代的性能，还可以减少训练网络所需的学习迭代次数：支持学习本质上是数字化的证据。

也支持了计算机科学本质上很酷的论点。

Answer 6

纯粹基于代码检查，最内部的循环必须计算对三维参数的引用并进行大量操作。根据您的数组尺寸，您可能会遇到缓存问题，因为每次循环迭代都必须在内存中跳转。也许您可以重新排列维度，以便内部循环尝试访问比现在更接近的内存元素？

无论如何，在进行任何更改之前，请分析您的代码并查看真正的瓶颈在哪里。

Answer 7

我建议使用定点系统而不是浮点系统。在几乎所有处理器上，使用 int 都比 float 更快。最简单的方法是将所有内容向左移动一定量（4 或 5 是很好的起点）并将底部 4 位视为小数。

你最里面的循环正在做浮点数学，所以这可能会给你带来很大的提升。

Answer 8

优化的关键是首先衡量时间花在哪里。通过调用 System.nanoTime() 包围算法的各个部分：

long start_time = System.nanoTime();
doStuff();
long time_taken = System.nanoTime() - start_time;

我猜想虽然使用 System.arraycopy() 会有所帮助，但您会在内部循环中找到真正的成本。

根据您发现的内容，您可能会考虑用整数算术替换浮点算术。