could people give examples of what tricks you can use in Java (besides simple compiler flags).
Other than improvements of algorithms, be sure to consider the memory hierarchy and how the processor makes use of it. There are big benefits in reducing memory access latencies, once you understand how the language in question allocates memory to its data types and objects.
Java example to access an array of 1000x1000 ints
Consider the below sample code - it accesses the same area of memory (a 1000x1000 array of ints), but in a different order. On my mac mini (Core i7, 2.7 GHz) the output is as follows, showing that traversing the array by rows more than doubles the performance (average over 100 rounds each).
Processing columns by rows*** took 4 ms (avg)
Processing rows by columns*** took 10 ms (avg)
This is because the array is stored such that consecutive columns (i.e. int values) are placed adjacent in memory, whereas consecutive rows are not. For the processor to actually use the data, it has to be transferred to its caches. The transfer of memory is by a block of bytes, called a cache line - loading a cache line directly from memory introduces latencies and thus decrease a program's performance.
For the Core i7 (sandy bridge) a cache line holds 64 bytes, thus each memory access retrieves 64 bytes. Because the first test accesses memory in a predictable sequence, the processor will pre-fetch data before it is actually consumed by the program. Overall, this results in less latency on memory accesses and thus improves the performance.
Code of sample:
package test;
import java.lang.*;
public class PerfTest {
public static void main(String[] args) {
int[][] numbers = new int[1000][1000];
long startTime;
long stopTime;
long elapsedAvg;
int tries;
int maxTries = 100;
// process columns by rows
System.out.print("Processing columns by rows");
for(tries = 0, elapsedAvg = 0; tries < maxTries; tries++) {
startTime = System.currentTimeMillis();
for(int r = 0; r < 1000; r++) {
for(int c = 0; c < 1000; c++) {
int v = numbers[r][c];
}
}
stopTime = System.currentTimeMillis();
elapsedAvg += ((stopTime - startTime) - elapsedAvg) / (tries + 1);
}
System.out.format("*** took %d ms (avg)\n", elapsedAvg);
// process rows by columns
System.out.print("Processing rows by columns");
for(tries = 0, elapsedAvg = 0; tries < maxTries; tries++) {
startTime = System.currentTimeMillis();
for(int c = 0; c < 1000; c++) {
for(int r = 0; r < 1000; r++) {
int v = numbers[r][c];
}
}
stopTime = System.currentTimeMillis();
elapsedAvg += ((stopTime - startTime) - elapsedAvg) / (tries + 1);
}
System.out.format("*** took %d ms (avg)\n", elapsedAvg);
}
}
