Sum the difference of two arrays

I have a function in App Engine Java where I compare two patterns stored in an int array:

public static int patternMatch(int [] pattern1, int [] pattern2, int range) {

    int max = range * pattern1.length;

    int match = (pattern1.length - pattern2.length) * range;

    for(int i = 0; i < pattern2.length; i++) {
        match += Math.abs(pattern1[i] - pattern2[i]);
    }

    return (max - match) * 100 / max;
}

I am facing very weird problems with respect to performance of this function between the development server and deployment on app engine as listed below:

• This function is called in a loop with the intention of finding best match(es).

• Performance for a single iteration is critical as there are lot of iterations.

• If I were to not have any logic in this code and directly return any integer, my overall code takes 100 ms to complete on an average.

• The above code takes anywhere between 200 - 600 ms.

-
On the development server, if I replace

int match = (pattern1.length - pattern2.length) * range;

by

int match = Math.abs(pattern1.length - pattern2.length) * range;

somehow the performance improves bringing the time taken down to 200 - 300 ms only. No impact on deployment server.

• If I remove Math.abs, the performance improves, bringing the average to 150 ms.

• I tried replacing Math.abs with bit operations to derive absolute value. I see huge performance improvement on development server ~160 ms. On deployment server it makes things worse ~700 ms.

What I would like to know here is:

• Why and how differently do Development server (Windows 7/eclipse/JDK6) and Deployment server behave in terms of performance tweaks?

• Is there any better algorithm to the match?

It's hard to say anything without profiling the whole application. Two possible scenarios about this point:


If I were to not have any logic in this code and directly return any integer, my overall code takes 100 ms to complete on an average.

#1

I guess the application processes the output of patternMatch, so maybe it handles different results differently which varies in time. Consider the following example:

public static int patternMatch(int [] pattern1, int [] pattern2, int range) {
    return 5;
}

int result = patternMatch( [] pattern1, int [] pattern2, int range) {
if (result < 10) {
    // do nothing
} else {
    // do something complicated and slow
}

Of course, it might not be so obvious. Profile it!

#2

JMV is smart about optimizations. If you put the simple return 5 statement into the method (as above) the JVM might have fooled you and did not even call the patternMatch method and probably eliminated or optimized other codes too which call patternMatch.


For example, reconsider the code in Listing 4: note
that main not only computes result but also uses result
in the output that it prints. Suppose that I make just
one tiny change and remove result from the println. In
this case, an aggressive compiler might conclude that it
does not need to compute result at all.

Source: Robust Java benchmarking, Part 1: Issues

I've created a test class for testing the runtime. It takes only 8,766 ms on my machine.

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.junit.Test;

import com.google.common.base.Stopwatch;

public class AppEngineCompareTest {

    private final Random random = new Random();

    @Test
    public void test() {
        final Stopwatch stopwatch = Stopwatch.createStarted();
        final int count = 20000;
        final int[] ranges = createRandomIntegerArray(count);
        final List patternOneList = createPatterns(count);
        final List patternTwoList = createPatterns(count);
        System.out.println("gen: " + stopwatch);
        stopwatch.reset();
        stopwatch.start();
        int result = 0;
        for (int index = 0; index  createPatterns(final int count) {
        final List result = new ArrayList<>(count);
        for (int index = 0; index < count; index++) {
            final int[] patterns = createRandomIntegerArray(60);
            result.add(patterns);
        }
        return result;
    }
}

StackExchange Code Review Q#18653, answer score: 2