Java: микрооптимизация управления массивом

Я пытаюсь сделать порт 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)));
}
}

Я выполняю JVM с - параметр сервера, и на данный момент мой код между 25% и на 50% медленнее, чем подобный код C. Что я могу сделать для улучшения этой ситуации?

Спасибо,

Martin Wiboe

Редактирование № 1: После наблюдения огромного количества ответов я должен, вероятно, разъяснить числа в нашем сценарии. Во время типичного выполнения методу позвонят по поводу приблизительно 50 000 раз с различными исходными данными. Типичная сеть имела бы numberLayers = 3 слоя с 190, 2 и 1 нейрон, соответственно. Самый внутренний цикл будет поэтому иметь о 2*191+3=385 повторения (при подсчете добавленного нейрона предвзятости в уровнях 0 и 1)

Редактирование № 1: После реализации различных предложений в этом потоке наша реализация практически с такой скоростью, как версия C (в ~2%). Спасибо за всю справку! Все предложения были полезны, но так как я могу только отметить один ответ как корректный, я дам его @Durandal и для предлагающий оптимизацию массива и для являющийся единственной предварительно вычислить for заголовок цикла.

9
задан Martin Wiboe 8 June 2010 в 15:29
поделиться

7 ответов

Не обращая внимания на фактическую математику, индексирование массивов в 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).

5
ответ дан 4 December 2019 в 08:14
поделиться

Несколько советов.

  • в своем внутреннем цикле подумайте о том, как вы обращаетесь к кэшу процессора, и перестройте свою матрицу так, чтобы вы обращались к внешнему массиву последовательно. Это приведет к тому, что вы будете обращаться к кэшу по порядку, а не прыгать по всему циклу. Попадание в кэш может быть на два порядка быстрее, чем промах в кэше. Например, перестройте fWeights так, чтобы доступ к нему был следующим

activation += neuronOutput[layer-1][inputNeuron] * fWeights[layer - 1][neuron][inputNeuron];

  • не выполняйте внутри цикла (каждый раз) работу, которую можно сделать вне цикла (один раз). Не выполняйте поиск [layer -1] каждый раз, когда вы можете поместить его в локальную переменную. Ваша IDE должна быть в состоянии легко рефакторить это.

  • Многомерные массивы в Java не так эффективны, как в C. На самом деле они представляют собой несколько слоев одномерных массивов. Вы можете перестроить код так, чтобы использовать только одномерный массив.

  • не возвращайте новый массив, когда вы можете передать массив результатов в качестве аргумента. (Это экономит создание нового объекта при каждом вызове).

  • вместо того, чтобы повсюду использовать layer-1, почему бы не использовать layer1 как layer-1 и не использовать layer1+1 вместо layer.

8
ответ дан 4 December 2019 в 08:14
поделиться

Первое, на что я бы обратил внимание, это не тормозит ли Math.exp. Смотрите этот пост об аппроксимации Math.exp в качестве альтернативы.

3
ответ дан 4 December 2019 в 08:14
поделиться

Ключ к оптимизации заключается в том, чтобы сначала измерить, на что тратится время. Окружите различные части вашего алгоритма вызовами System.nanoTime():

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

Я бы предположил, что хотя использование System.arraycopy() немного поможет, реальные затраты вы обнаружите во внутреннем цикле.

В зависимости от того, что вы обнаружите, вы можете рассмотреть возможность замены арифметики с плавающей точкой на арифметику с целыми числами.

0
ответ дан 4 December 2019 в 08:14
поделиться

Чисто на основе осмотра кода, ваш внутренний цикл должен вычислять ссылки на трехмерный параметр, и это делается очень часто. В зависимости от размеров вашего массива у вас могут быть проблемы с кэшем из-за того, что вам приходится прыгать по памяти при каждой итерации цикла. Возможно, вы могли бы изменить размеры массива так, чтобы внутренний цикл пытался получить доступ к элементам памяти, которые находятся ближе друг к другу, чем сейчас?

В любом случае, профилируйте свой код перед внесением каких-либо изменений и посмотрите, где действительно узкое место.

1
ответ дан 4 December 2019 в 08:14
поделиться

Для начала, не делайте так:

// 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 );
5
ответ дан 4 December 2019 в 08:14
поделиться

Я предлагаю использовать систему с фиксированной, а не с плавающей точкой. Почти на всех процессорах использование int быстрее, чем float. Самый простой способ сделать это - просто сдвинуть все влево на определенную величину (4 или 5 - хорошие отправные точки) и рассматривать нижние 4 бита как десятичную дробь.

Ваш внутренний цикл выполняет математику с плавающей запятой, так что это может дать вам значительное ускорение.

1
ответ дан 4 December 2019 в 08:14
поделиться
Другие вопросы по тегам:

Похожие вопросы: