Processing an array of overridden methods depends if it is arbitrary or in alternance

Question

I have this piece of code and I want to know the cause of the difference between the time of execution of the first input and the second. I think it should take the same time because I am calling the same method which do nothing in 2 objects. but input1 (which is an alternation of 2 instances) takes on my computer 5 seconds. and input2 (which is an arbitrary choosing between 2 instances) takes on my computer 17 seconds.

public class Program {


    private static final Runnable FIRST_INSTANCE = () -> {};
    private static final Runnable SECOND_INSTANCE = () -> {};

    private static Runnable[] input1() {
        Runnable[] array = new Runnable[10000];
        for (int i = 0; i < array.length; i++) {
            array[i] = i % 2 == 0 ? FIRST_INSTANCE : SECOND_INSTANCE;
        }
        return array;
    }


    private static Runnable[] input2() {
        Random rnd = new Random(0);
        Runnable[] array = new Runnable[10000];
        for (int i = 0; i < array.length; i++) {
            array[i] = rnd.nextBoolean() ? FIRST_INSTANCE : SECOND_INSTANCE;
        }
        return array;
    }


    public static void main(String[] args) {
        Runnable[] input1 = input1();
        Runnable[] input2 = input2();

        solve(input1);
        solve(input2);

    }

    private static void solve(Runnable[] array) {
        long start = System.nanoTime();
        for (int j = 0; j < 500000; j++) {
            for (Runnable r : array) {
                r.run();
            }
        }
        System.out.println((System.nanoTime() - start) / 1000000000.0);
    }
}

I think it is not related to cache because they use the same instances, and it is not a problem of which is called first because I try to call input2 before input1 and I get the same results (input2 is always slower).

I start to calculate time after creating the arrays. rnd.nextBoolean() and i % 2 times is not calculated here. — Khaled Baklouti, Sep 19 '19 at 00:08
I wrote already in the question. I try to call input2 before input1 and I get the same results (input2 is always slower). @ErwinBolwidt — Khaled Baklouti, Sep 19 '19 at 00:19
Hmm, strange even if doing array2 first, the results are just as bad. — Scary Wombat, Sep 19 '19 at 00:25
It could be related to branch prediction - perhaps a predictable alternating pattern is caught by the CPU but not a random pattern. But I'm just guessing. See also https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array — Erwin Bolwidt, Sep 19 '19 at 00:59
Scary Wombat, that's not even the strange part. The strange part is the update to my answer I'm about to write :) — iluxa, Sep 19 '19 at 01:01

score 2 · Answer 1 · edited May 20 '21 at 09:58

Some kind of compiler optimization is at play.

I've tried your code with 50000 iterations instead of 500000, because life is short. My times are roughly 10 times better than yours.

First, I've ran your code

0.502928476
1.68480928

Then I tried to run the same with -Djava.compiler=NONE (disables JIT):

25.267888581
24.742234792

Note how awful the timing became. JIT is definitely a suspect here.

Then I tried to make input1 less uniform:

array[i] = i % 21 == 0 ? FIRST_INSTANCE : SECOND_INSTANCE;

and that hasn't made a difference. Then I tried to remove the pattern from input1:

array[i] = (int)(Math.sqrt(i) * Math.sqrt(i)) == i ? FIRST_INSTANCE : SECOND_INSTANCE;

0.973357599
1.82497641

Performance of input1 became almost twice worse.

So my conclusion is as follows: uniformity of the array matter to JIT for some reason :)

Looking at it a bit further:

If we don't run input at all, and run input2 5 times instead of twice, we get this:

1.826676411
1.835746098
1.566231165
1.531194014
1.551068832

So it seems that JIT fully kicked in by the third loop. Note the times are ~1.5s.

Now, if we start off running input1 twice, then proceed to input2:

input1: 2 times
0.507165973
0.509543633
input2: 5 times
1.270496255        <------ WAT?
1.817742481
1.804664757
1.845583904
1.846861045

It looks like JIT set up for input1 actually helped input2 a bunch, but then got thrown away and never quite recovered

JIT watches the code execution, and when it sees a sequence that repeats and can be optimized, it does that. It doesn't care about the content of the array, it cares about the instructions order that JCM performs — iluxa, Sep 19 '19 at 00:34
Is that sure or just an opinion?? because I don't think that it can know that there is a sequence — Khaled Baklouti, Sep 19 '19 at 00:41
It's an opinion, of course, I have no idea how JIT actually works internally — iluxa, Sep 19 '19 at 00:58
Yes I really want to know what is happening exactly there. I am reading about branch prediction like @Erwin Bolwidt said. Maybe I can find a reason — Khaled Baklouti, Sep 19 '19 at 01:23

Processing an array of overridden methods depends if it is arbitrary or in alternance

1 Answers1