Looping through 2d array. Performance question

Question

Why is below uncommented code much faster than the commented out code? Leetcode beginner here, and I honestly don't see the difference between the two.

class Solution {
    //public int maximumWealth(int[][] accounts) {
    //    int max = 0;
    //    for (int i = 0; i < accounts.length; i++) {
    //        int sum = 0;
    //        for (int j = 0; j < accounts[i].length; j++) {
    //            sum += accounts[i][j];
    //        }
    //        max = Integer.max(max, sum);
    //    }
    //    return max;
    //}
    public int maximumWealth(int[][] accounts) {
        int max = 0;
        for (int[] account : accounts) {
            int sum = 0;
            for (int j = 0; j < account.length; j++) {
                sum += account[j];
            }
            max = Integer.max(max, sum);
        }
        return max;
    }
}

Why do you think it is faster? (It probably isn't, but it's easy to measure it in an incorrect way that makes you think it is.) — Louis Wasserman, Jan 03 '21 at 06:22
To the people trying to turn ^^^ into a credible benchmark ... use JMH or Caliper: https://stackoverflow.com/a/15199328/139985 — Stephen C, Jan 04 '21 at 06:16

Aalexander · Answer 1 · 2021-01-08T09:43:37.810

Difference

In your first method maximumWealth(int[][] acounts you use in the inner and in the outer loop a traditional for-loop while against in the second method you use in the outer loop an enhanced for-loop

 for (int[] account : accounts)

Experiment

Experiment to measure the runtime.

Created 21 arrays inside of the accounts array
loop through it with the two distinct maximumWealth(int[][] acounts)

in the first we use the enhanced for-loop
in the second we use the traditional for-loop

stop the time beeing passed for executing in nanoseconds.
do step 3 ten times and calculate the average
compare the averages in nanoseconds

Which loop is faster?

Enhanced for-loop

public class Tryout {
    public static void main(String[] args) {
        int[][] accounts = {{3, 3, 5, 5, 4, 2, 2, 3, 1, 31, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2},
                {2, 3, 3, 3, 33, 3, 3, 3, 3, 3, 3, 3, 33, 32, 2, 21, 1, 1, 22, 3, 3, 3, 4, 4, 4, 4, 9, 8, 2, 3, 4},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {5, 0, 2, 92, 31},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5}};
        long startTime = System.nanoTime();
        int result = Tryout.maximumWealthEnhanced(accounts);
        long endTime = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.println(totalTime);
    }

    public static int maximumWealthEnhanced(int[][] accounts) {
        int max = 0;
        for (int[] account : accounts) {
            int sum = 0;
            for (int j = 0; j < account.length; j++) {
                sum += account[j];
            }
            max = Integer.max(max, sum);
        }
        return max;
    }
}

Runtime AVG

1. 37085 NS
2. 41154 NS
3. 47630 NS
4. 37348 NS
5. 39489 NS
6. 37107 NS
7. 37605 NS
8. 37096 NS
9. 37609 NS
10. 39255 NS

AVG = 39137,0 Nanoseconds

Traditional for loop

public class Tryout {
    public static void main(String[] args) {
        int[][] accounts = {{3, 3, 5, 5, 4, 2, 2, 3, 1, 31, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2},
                {2, 3, 3, 3, 33, 3, 3, 3, 3, 3, 3, 3, 33, 32, 2, 21, 1, 1, 22, 3, 3, 3, 4, 4, 4, 4, 9, 8, 2, 3, 4},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {5, 0, 2, 92, 31},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5},
                {92, 92, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 3, 4, 5}};
        long startTime = System.nanoTime();
        int result = Tryout.maximumWealth(accounts);
        long endTime = System.nanoTime();
        long totalTime = endTime - startTime;
        System.out.println(totalTime);
    }

    public static int maximumWealth(int[][] accounts) {
        int max = 0;
        for (int i = 0; i < accounts.length; i++) {
            int sum = 0;
            for (int j = 0; j < accounts[i].length; j++) {
                sum += accounts[i][j];
            }
            max = Integer.max(max, sum);
        }
        return max;
    }
}

Runtime AVG

1. 43645 NS
2. 42052 NS
3. 40661 NS
4. 40936 NS
5. 46346 NS
6. 46916 NS
7. 42064 NS
8. 39406 NS
9. 39572 NS
10. 40945 NS

AVG = 42254,3 Nanoseconds

Conclusion

So I wouldn't say the enhanced is much faster. I would say it is a tiny nano seconds bit faster.

An important thing to note here is the enhanced for loop uses an Iterator, so if you manually iterate over a collection using an Iterator then you should have pretty much the same performance.

Benefits of the enhanced for loop are it's convenient and less error-prone, but if you want more control over iteration process then use traditional for loop.

Resources:

score 0 · Answer 2 · 2021-01-03T15:39:13.520

Conduct an experiment

Take a 2d array of 30000x30000 random elements. Prepare three methods for benchmarking and call each of them 20 times, measure the time and calculate the average.

Results: an enhanced for loop is faster then a regular for loop, and a parallel stream is two times faster.

   enhanced for: avg 750 ms
       for loop: avg 1013 ms
parallel stream: avg 385 ms

Best result: parallel stream

public static int maximumWealthPStream(int[][] accounts) {
    return Arrays.stream(accounts).parallel()
            .mapToInt(arr -> Arrays.stream(arr).sum())
            .max().orElse(0);
}

Full results:

   enhanced for: 1281 | 1286 |  701 |  710 |  690 |  691 |  702 |  688 |  689 |  676 |  673 |  705 |  698 |  686 |  686 |  688 |  684 |  683 |  690 |  696 || avg 750 ms
       for loop:  669 |  667 | 1252 |  677 |  670 |  659 |  669 |  652 |  657 | 1226 | 1240 | 1244 | 1279 | 1230 | 1218 | 1224 | 1260 | 1233 | 1289 | 1260 || avg 1013 ms
parallel stream:  455 |  378 |  376 |  380 |  377 |  372 |  376 |  371 |  374 |  376 |  369 |  372 |  382 |  379 |  375 |  370 |  369 |  376 |  516 |  376 || avg 385 ms

Code of experiment:

public static void main(String[] args) {
    int size = 30000;
    int count = 20;

    // random array
    int[][] arr = IntStream.range(0, size)
            .mapToObj(i -> IntStream.range(0, size)
                    .map(j -> (int) (1 + Math.random() * 10))
                    .toArray())
            .toArray(int[][]::new);

    benchmark("enhanced for", count, () -> maximumWealthEnhanced(arr));
    benchmark("for loop", count, () -> maximumWealthFor(arr));
    benchmark("parallel stream", count, () -> maximumWealthPStream(arr));
}

public static void benchmark(String name, int count, Runnable runnable) {
    int average = 0;
    System.out.print(String.format("%16s", name + ":"));
    for (int i = 0; i < count; i++) {
        long time = System.currentTimeMillis();
        runnable.run();
        time = System.currentTimeMillis() - time;
        System.out.print(" " + String.format("%4d", time) + " |");
        average += time;
    }
    average /= count;
    System.out.println("| avg " + average + " ms");
}

public static int maximumWealthEnhanced(int[][] accounts) {
    int max = 0;
    for (int[] account : accounts) {
        int sum = 0;
        for (int j = 0; j < account.length; j++) {
            sum += account[j];
        }
        max = Integer.max(max, sum);
    }
    return max;
}

public static int maximumWealthFor(int[][] accounts) {
    int max = 0;
    for (int i = 0; i < accounts.length; i++) {
        int sum = 0;
        for (int j = 0; j < accounts[i].length; j++) {
            sum += accounts[i][j];
        }
        max = Integer.max(max, sum);
    }
    return max;
}

public static int maximumWealthPStream(int[][] accounts) {
    return Arrays.stream(accounts).parallel()
            .mapToInt(arr -> Arrays.stream(arr).sum())
            .max().orElse(0);
}