debugging (i!=t++) vs ( t++!=i)

Question

I was solving some problem where I have to use (i!=t++) condition. Unfortunately using this condition gave TLE. But when I use (t++!=i) instead it was successfully submitted. I think both conditions are the same wrt to below program. The output of the program on my compiler is 5259 3 which is time taken by by first and second loop respectively I can not find the difference between the two conditions. Of course there is bug somewhere that i cannot find

void test()
{
    long b=System.currentTimeMillis();
    for(int i=0;i<100001;i++) {
        int t=0;
        while (i!=t++)
        {
            int x=34;
            x++;

        }
    }
    System.out.println(System.currentTimeMillis()-b);

    b=System.currentTimeMillis();
    for(int i=0;i<100001;i++) {
        int t=0;
        while (t++!=i)
        {
            int x=34;
            x--;
            x++;
        }
    }
}

Answer 1

It is a partial answer, and future investigations are necessary. But, for the time being, the answer is - it is the effect of JIT optimisation. Also, note that microbenchmarks are not the best option for performance testing, especially with dynamically-compiled languages like Java (see, for example, this guru paper).

I am using Windows 10 Home, java -version prints:

java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.121-b13, mixed mode)

I have restructured your code as follows and added x as external counter to assure the loops are not optimized away:

void test1() {
    int x = 0;
    long b = System.currentTimeMillis();
    for (int i = 0; i < 100_001; i++) {
        int t = 0;
        while (i != t++) {
            x++;
        }
    }
    long b1 = System.currentTimeMillis();
    System.out.println("T(test1) = " + (b1 - b));
    System.out.println("x(test1) = " + x);
}

void test2() {
    int x=0;
    long b = System.currentTimeMillis();
    for (int i = 0; i < 100001; i++) {
        int t = 0;
        while (t++ != i) {
            x++;
        }
    }
    long b1 = System.currentTimeMillis();
    System.out.println("T(test2) = " + (b1 - b));
    System.out.println("x(test2) = " + x);
}

Each function is called twice:

t.test1();
t.test1();
t.test2();
t.test2();

Ok, let's see the results for standard java Test invocation (no other interpeter arguments are supplied):

T(test1) = 3745
x(test1) = 705082704
T(test1) = 0
x(test1) = 705082704
T(test2) = 5
x(test2) = 705082704
T(test2) = 0
x(test2) = 705082704

As you can see, after the second invocations, the running times equal to 0 in both cases. The same happens even if we change int x = 0 initialisation to int x = new Random().nextInt() to assure that the second invocation results are not cached or something. Generally, one should "warmup" the Java interpreter before doing measurements, i.e. measure the code performance twice in the same run and throw-away the first result, so that one assures that optimisations are in place. But that's the luxury you don't have when solving online-judges exercises.

Now for the other part. Oracle's JDK has a -Xint interpreter switch, which turns off JIT completely. Let's use it and see what happens. I've used -XX:+PrintCompilation flag as well to assure that no compilation whatsoever is taking place (i.e. interpreter was invoked as java -XX:+PrintCompilation -Xint Test; if no additional diagnostics are printed that means the code was not compiled):

T(test1) = 56610
x(test1) = 705082704
T(test1) = 55635
x(test1) = 705082704
T(test2) = 60247
x(test2) = 705082704
T(test2) = 58249
x(test2) = 705082704

Two observations: now the task takes ages and the results are similar across all invocations. More investigation has to be done to discover why the two codes are optimised by JIT differently.

EDIT: Fun with JIT part 2

So, I went on trying different compilation options. Generally speaking, there are two types of compilers that JIT uses. C1 (client) compiler is aimed at giving faster JVM startup times but is not as fast as C2 (server) compiler. 64-bit Java 8 JVM I used seems to make server the only easily-available option (see this FAQ; however different compilation levels can still be chosen with -XX:TieredStopAtLevel= flag; for brevity, I won't paste the results I got using it, but they support the thesis that it's the server compiler version that makes the first invocation of test2 faster).

I happen to have 32-bit JRE on my machine as well. It does not support server compiler and gives the following version info:

java version "1.8.0_121"
Java(TM) SE Runtime Environment (build 1.8.0_121-b13)
Java HotSpot(TM) Client VM (build 25.121-b13, mixed mode)

The results for this JVM are as follows:

T(test1) = 3947
x(test1) = 705082704
T(test1) = 3985
x(test1) = 705082704
T(test2) = 4031
x(test2) = 705082704
T(test2) = 4172
x(test2) = 705082704