# 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:

1. This function is called in a loop with the intention of finding best match(es).
2. Performance for a single iteration is critical as there are lot of iterations.
3. 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.
4. The above code takes anywhere between 200 - 600 ms.
5. 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.

6. If I remove Math.abs, the performance improves, bringing the average to 150 ms.
7. 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:

1. Why and how differently do Development server (Windows 7/eclipse/JDK6) and Deployment server behave in terms of performance tweaks?
2. Is there any better algorithm to the match?
-
Maybe the development server runs in client mode while the deployment runs in client mode. stackoverflow.com/questions/198577/… –  palacsint Nov 15 '12 at 19:05
Didn't get it. Your comment says both running in client mode. Either way if you meant one is running in client mode and another in server, then it should actually run faster on the server. –  0n4li Nov 16 '12 at 5:42
Did you check how much CPU/memory you get from App Engine? developers.google.com/appengine/docs/adminconsole/… –  avip Nov 16 '12 at 6:39
It would help to have more info. How many iterations? What is the range typically? How large are the arrays? Is pattern1 always the same? You might be overflowing an int if the range and iterations are both large for example. You also may be better unrolling the abs ( diff = b - a; match = (diff < 0) ? -diff : diff) if the compiler doesn't. –  Tim Niblett Nov 16 '12 at 14:50
Iterations are close to 20000 in one run. Range is < 100. Arrays are max 60 size. Pattern 1 in one run will be the same. –  0n4li Nov 18 '12 at 14:52

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.

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;

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<int[]> patternOneList = createPatterns(count);
final List<int[]> patternTwoList = createPatterns(count);
System.out.println("gen: " + stopwatch);
stopwatch.reset();
stopwatch.start();
int result = 0;
for (int index = 0; index < count; index++) {
final int[] pattern1 = patternOneList.get(index);
final int[] pattern2 = patternTwoList.get(index);
final int range = ranges[index];
result += AppEngineCompare.patternMatch(pattern1, pattern2, range);
}
System.out.println("run: " + stopwatch);
System.out.println(result);
}

private int[] createRandomIntegerArray(final int count) {
final int[] ranges = new int[count];
for (int index = 0; index < count; index++) {
ranges[index] = random.nextInt();
}
return ranges;
}

private List<int[]> createPatterns(final int count) {
final List<int[]> result = new ArrayList<>(count);
for (int index = 0; index < count; index++) {
final int[] patterns = createRandomIntegerArray(60);