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

Answer 2

So I have tested your code and checked how long it runs. Whith the following results (the time in millisecond for loop 1 and 2):

 time1   time2 
 175.2   171.0
 189.6   187.1
 162.1   164.2
 162.3   162.1
 162.3   166.0

Both loops run in the same time.

Here is the code

private static void test()
  {
    long b;

    float time1=0;
    float time2=0;

    int x=0;
    for(int l=0;l<10;l++) {
        b=System.currentTimeMillis();
        for(int i=0;i<20001;i++) {
          int t=0;
          while (i!=t++)
            {
            x++;
            }
        }


        time1+=System.currentTimeMillis()-b;

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


        }

    time2+=System.currentTimeMillis()-b;

    }

    time1/=10;
    time2/=10 ;   
    System.out.println(time1);  
    System.out.println(time2);
}

I am not sure why you think that the statements would chance the situations. But I think that your program ran out of time on your online compiler (which has an end time). After wich you changed the arguments and thought that it worked now. This could probably be caused by that your code was warmed up, wich may decrease the rune time slightly of a program. But this is just guessing....And should not work as an answer.

Pleas test the above code for yourself.

To answer youre question both logical epressions are the same. Although there is a slight difference in the post-fix i++ (copy the value, increment the current value, yields the copy) and the prefix ++i (increment the current value and yields the result). Where the second does have one less operation. But this should not result in a different computation time.

Look at this post Why is "while (i++ < n) {}" significantly slower than "while (++i < n) {}" for an explanation why youre IDE give some strange results.

Answer 3

My best guess here is that it's a quirk of how the bytecode is being generated and/or executed.

Computer processors have a limited number of registers they can use to store the values they are working on at any given time. It's possible that the variables are being placed in different registers based on which one appears first. And if the variables are in different registers to start out, that might impact which one is removed to make room for something else.

If a value is not in a register when it is later needed, the processor will have to go get it from the computer's memory (or the processor's cache), which takes more time than if it was already in a register.

There's also things where the processor can try to begin to execute one statement before another is finished. But this can be interrupted if a value changes. If the t++ happens very soon before it tries to load t again, perhaps the processor is being interrupted and has to start the instruction from scratch. (However, I don't think this is the main reason for what's happening; it wouldn't have such a large effect.)

Maybe it's just a matter of some optimization that the Java compiler sees it can do in one instance and not the other.