code optimization results in slower execution - need explanation

Question

public class Zigzag{
    public static void zigzag_optimizated(int n, int m) {
        int length = 2*m;
        int localIndex[] = new int[n];
        for(int i = 0; i<n; i++){
            localIndex[i] = i % length;
        }
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                if (localIndex[j]==i || localIndex[j] == length-i)
                   assert true;
                    //  System.out.print('*');
                else
                    assert true;
                    //System.out.print('-');
            }
            //System.out.println();
            assert true;
        }
    }
    public static void zigzag(int n, int m) {
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j < n; j++) {
                int k = j % (2*m);
                char c = '-';
                if (k==i || k == 2*m-i) c = '*';
                assert true;
                //System.out.print(c);
            }
            assert true;
            //System.out.println();
        }
    }
    public static void main(String args[]){
        final int n = 5000000;
        long start =  System.nanoTime();
        zigzag(n, n);
        long time = System.nanoTime() - start;
        long start2 =  System.nanoTime();
        zigzag_optimizated(n, n);
        long time2 = System.nanoTime() - start2;
        System.out.println();
        System.out.println("Time1:" + time);
        System.out.println("Time2:" + time2);

}
}

Two functions have same algorithm, it print a zigzag board to screen. In optimizated version, k is saved in array to avoid recalculate, 2*m is extracted. I changed System.out.println() to assert true; for faster and more accurate benchmark, but when i do the benchmark, the original version is always run faster (with n large enough)

Answer 1

How big is n to see the difference?

If n is big enough array is too big to keep it in CPU cache - it's faster to calculate j % (2*m) then access it from RAM (60-100 nanosec).

See Scott Mayers - How CPU Cache works and why you care -