views:

195

answers:

7

Hello all,

I am trying to make a Java port of a simple feed-forward neural network.
This obviously involves lots of numeric calculations, so I am trying to optimize my central loop as much as possible. The results should be correct within the limits of the float data type.

My current code looks as follows (error handling & initialization removed):

/**
 * 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)));
}
}

I am running the JVM with the -server option, and as of now my code is between 25% and 50% slower than similar C code. What can I do to improve this situation?

Thank you,

Martin Wiboe

Edit #1: After seeing the vast amount of responses, I should probably clarify the numbers in our scenario. During a typical run, the method will be called about 50.000 times with different inputs. A typical network would have numberLayers = 3 layers with 190, 2 and 1 neuron, respectively. The innermost loop will therefore have about 2*191+3=385 iterations (when counting the added bias neuron in layers 0 and 1)

Edit #1: After implementing the various suggestions in this thread, our implementation is practically as fast as the C version (within ~2 %). Thanks for all the help! All of the suggestions have been helpful, but since I can only mark one answer as the correct one, I will give it to @Durandal for both suggesting array optimizations and being the only one to precalculate the for loop header.

+3  A: 

First thing I would look into is seeing if Math.exp is slowing you down. See this post on a Math.exp approximation for a native alternative.

nivekastoreth
I was thinking a lookup table for the entire `sigmoid()` function might be worthwhile, but it's hard to say without knowing how much time is spend in that function.
Brendan Long
It's almost certain a lookup table would greatly increase speed of that function, and possibly help you regain the 25% loss from C to Java. If you doubt how much time is spent there, use some profiling tools to determine what is taking so long. But since it's at least being calculated layer*neuron times, there's a good chance this is one bottleneck that can be easily eliminated.
drharris
I have tried using that approximation, but unfortunately the results are too inaccurate. Do you know any way to increase the accuracy by trading off some [email protected] Long and drharris Lookup table could very well be an option - I will be doing millions of calculations. How would one go about implementing a thread-safe lookup table that uses floating-point numbers as the key?
Martin Wiboe
Well, check this older post out, for many examples on how to improve the typical Sigmoid function: http://stackoverflow.com/questions/412019/math-optimization-in-c
drharris
If your questions is "how do I make this code run faster", before going much deeper on optimizing the trade off between speed and accuracy, I'm curious if the inaccurate (yet faster) method pushed you closer to an acceptable run time? If not, perhaps we're looking in the wrong area.
nivekastoreth
+4  A: 

For a start, don't do this:

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

But this:

System.arraycopy( input, 0, neuronOutput[0], 0, inputNeurons );
Webinator
+1 Aye, it's a lot faster.
Vuntic
Sure, but aren't there only two arrays copied in this algorithm, one to copy the inputs in, and one to copy the results out? The real costs are more likely inside the nested for loops.
Jim Ferrans
@W and V - True, but that's not where the bottleneck would be.
CurtainDog
Good suggestion - will do that :) But the running time of the method is determined by the inner loops, so it won't save the day, unfortunately. (inputNeurons is ~ 200, so it shouldn't make that big a difference)
Martin Wiboe
+1  A: 

Purely based upon code inspection, your inner most loop has to compute references to a three-dimensional parameter and its being done a lot. Depending upon your array dimensions could you possibly be having cache issues due to have to jump around memory with each loop iteration. Maybe you could rearrange the dimensions so the inner loop tries to access memory elements that are closer to one another than they are now?

In any case, profile your code before making any changes and see where the real bottleneck is.

sizzzzlerz
Profiling will definitely help. I'll try and switch the last two indices in fWeights[layer - 1][inputNeuron][neuron], so that inputNeuron, which varies, is the 3rd index.
Martin Wiboe
A: 

I suggest using a fixed point system rather than a floating point system. On almost all processors using int is faster than float. The simplest way to do this is simply shift everything left by a certain amount (4 or 5 are good starting points) and treat the bottom 4 bits as the decimal.

Your innermost loop is doing floating point maths so this may give you quite a boost.

Daniel
In general, a good point (in fact many systems which actually do require fixed precision are wrong because they naively use FP). However in this case I don't think the sigmoid function lends itself well to this technique.
CurtainDog
A: 

The key to optimization is to first measure where the time is spent. Surround various parts of your algorithm with calls to System.nanoTime():

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

I'd guess that while using System.arraycopy() would help a bit, you'll find your real costs in the inner loop.

Depending on what you find, you might consider replacing the float arithmetic with integer arithmetic.

Jim Ferrans
+3  A: 

Some tips.

  • in your inner most loop, think about how you are traversing your CPU cache and re-arrange your matrix so you are accessing the outer most array sequentially. This will result in you accessing your cache in order rather than jumping all over the place. A cache hit can be two orders of magniture faster than a cache miss. e.g restructure fWeights so it is accessed as

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

  • don't perform work inside the loop (every time) which can be done outside the loop (once). Don't perform the [layer -1] lookup every time when you can place this in a local variable. Your IDE should be able to refactor this easily.

  • multi-dimensional arrays in Java are not as efficient as they are in C. They are actually multiple layers of single dimensional arrays. You can restructure the code so you're only using a single dimensional array.

  • don't return a new array when you can pass the result array as an argument. (Saves creating a new object on each call).

  • rather than peforming layer-1 all over the place, why not use layer1 as layer-1 and using layer1+1 instead of layer.

Peter Lawrey
Wow - optimizing array access reduced running time by 20 %. Thanks.
Martin Wiboe
+1  A: 

Disregarding the actual math, the array indexing in Java can be a performance hog in itself. Consider that Java has no real multidimensional arrays, but rather implements them as array of arrays. In your innermost loop, you access over multiple indices, some of which are in fact constant in that loop. Part of the array access can be move outside of the loop:

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];
}

It is possible that the server JIT performs a similar code invariant movement, the only way to find out is change and profile it. On the client JIT this should improve performance no matter what. Another thing you can try is to precalculate the for-loop exit conditions, like this:

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++) { ... }

Again the JIT may already do this for you, so profile if it helps.

Is there a point to multiplying with 1.0F that eludes me here?:

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

Other things that could potentially improve speed at cost of readability: inline sigmoid() function manually (the JIT has a very tight limit for inlining and the function might be larger). It can be slightly faster to run a loop backwards (where it doesnt change the outcome of course), since testing the loop index against zero is a little cheaper than checking against a local variable (the innermost loop is a potentical candidate again, but dont expect the output to be 100% identical in all cases, since adding floats a + b + c is potentially not the same as a + c + b).

Durandal
Arrays and precalculation seemed to improve the overall running time by 25 % :) Thanks.
Martin Wiboe