Which code runs faster?

Question

I have two piece of code, and I want to know which is faster when they run and why it's faster. I learn less about JVM and CPU, but I'm hard working on them. Every tip will help.

int[] a=new int[1000];
int[] b=new int[10000000];
long start = System.currentTimeMillis();
//method 1
for(int i=0;i<1000;i++){
    for(int j=0;j<10000000;j++){
        a[i]++;
    }
}
long end = System.currentTimeMillis();
System.out.println(end-start);

start=System.currentTimeMillis();
//method 2
for(int i=0 ;i<10000000;i++){
    for(int j=0;j<1000;j++){
        b[i]++;
    }
}
end = System.currentTimeMillis();
System.out.println(end-start);

Answer 1

Modern architectures are complex, so answering this kind of question is never easy.

The run time could be same or the first could be faster.

Things to consider in this case is mostly memory access and optimization.

A good optimizer will realize that the values are never read, so the loops can be skipped entirely, which gives a run time of 0 in both cases. Such optimization can take place at compile time or at run-time.

If it isn't optimized away, then there is memory access to consider. a[] is much smaller than b[], so it will more readily fit in faster cache memory resulting in fewer cache misses.

Another thing to consider is memory interleaving.

Answer 2

The first loop runs faster on my system (median: 333 ms vs. 596 ms)
(Edit: I made a wrong assumption on number of array accesses in my first response, see comments)

Subsequent incremental (index++) accesses to the same array seem to be faster than random accesses or decremental (index--) accesses. I assume the Java Hotspot compiler can optimize the array bound checks if it recognizes that the array will be incrementally traversed.

When reversing the loops, it actually runs slower:

//incremental array index
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 10000000; j++) {
        a[i]++;
    }
}

//decremental array index
for (int i = 1000 - 1; i >= 0; i--) {
    for (int j = 10000000 - 1; j >= 0; j--) {
        a[i]++;
    }
}

Incremental: 349ms, decremental: 485ms. Without bounds checks, decremental loops usually are faster, especially on old processors (comparing to zero).

If my assumption is right, this makes 1000 optimized bounds checks versus 10000000 checks, so the first method is faster.

By the way, when benchmarking:

• Do multiple rounds and compare the averages/mediums instead of the first sample
• In Java: give your benchmark a warmup-phase (execute it a few times before measuring). On the first run, classes have to be loaded, and code might be interpreted before the HotSpot VM feature kicks in and does a native compilation
• Measure time deltas with System.nanoTime(). This gives more accurate timestamps. System.currentTimeMillis() is not that precise (depends on the VM), and usually 'hops' in junks of a dozen or more milliseconds, rendering your result times more volatile than they actually are. Btw: 1 milliseconds = 1'000'000 nano second.

Answer 3

Complexity

In terms of asymptotic complexity (e.g. big-O notation), they have the same running time.

Data localization

Ignoring any optimization for the moment...

b is larger and is thus more likely to be split across multiple (or more) pages. Because of this, the first is likely faster.

The difference here is likely to be rather small, unless not all of these pages fit into RAM and need to be written to disk (which is unlikely here since b is only 10000000*4 = 40000000 bytes = 38 MB).

Optimization

The first method involves "execute a[i]++ 10000000 times" (for a fixed i), which can theoretically rather easily be converted to a[i] += 10000000 by the optimizer.

A similar optimization can occur for b, but only to b[i] += 1000, which still has to run 10000000 times.

The optimizer is free to do this or not do this. As far as I know, the Java language specification doesn't say much about what should and shouldn't be optimized, as long as it doesn't change the end result.

As an extreme result, the optimizer could, in theory, see that you're not doing anything with a or b after the loops and thus get rid of both loops.

Answer 4

First will be fuster. Because of initialization of first a and i cell much more less times.

Answer 5

I'll throw my answer in there, in theory they will be exactly the same but in practice there will be a small, but negligible, difference. Too small to really matter, actually.

The basic idea is how array b is stored in memory. Because it is a lot larger, depending on your platform/implementation it might be stored in chunks, aka non-contiguously. That is likely since an array of 10 million ints is 40 million bytes = 40 MB!

EDIT: I get 572 and 593, respectively.

Answer 6

Time should be equal, the result will obviously be different since a will contain 1000 entries with value 10000 and b will contain 10000000 entries with value 1000. I don't really get your question. What's the result for end-start? It might be that the JVM will optimize the forloops, if it understands what the end results will be in the array than the smallest array will be much easier to calculate, since it requires only 1000 assignments, while the other one needs 10 000 times more.

Answer 7

Check out big-oh notation

A nested for loop is O(n^2) - They will run the same in theory.

The numbers 1000 or 100000 are a constant k O(n^2 + k)

They won't be exactly identical in practise because of various other things at play but it will be close.

Answer 8

My guess would be that the they are both pretty much the same. One of them has a smaller array to handle, but that wouldn't make much difference except for the initial allocation of memory, which is outside your measuring anyway.

The time to execute each iteration should be the same (writing a value into an array). incrementing larger numbers shouldn't take the JVM longer than incrementing smaller numbers, nor should addressing a smaller or larger array index.

But why the question if you already know how to measure yourself?