Debug (i! = T ++) vs (t ++! = I)
I was solving some problem when I need to use (i! = T ++) condition. Unfortunately, using this condition gave TLE. But when I use (t ++! = I) it was sent successfully. I think both conditions are the same compared to the program below. The output of the program on my compiler is 5259 3, the time taken for the first and second loops respectively I cannot find the difference between these two conditions. Surely there is a mistake 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++;
}
}
}
source to share
This is a partial answer and further research is needed. But for now, the answer is the effect of JIT optimization . Also note that micro lenses are not the best performance testing option, especially with dynamically compiled languages like Java (see this guru doc for example ).
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 modified your code as follows and added x
as an external counter to make sure the loops are not optimized:
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 look at the results for a standard call java Test
(no other argument arguments are provided):
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 calls, the running time is 0 in both cases. The same thing happens even if we change the initialization int x = 0
to int x = new Random().nextInt()
to ensure that the results of the second call are not cached or whatever. As a rule, the Java interpreter should be soaked before taking measurements; Measure the performance of the code twice in the same run and discard the first result to make sure the optimization exists. But that's a luxury you don't have when solving online judges' exercises.
Now for the other part. Oracle JDK has a switch -Xint
that completely disables JIT. Let me use it and see what happens. I also used a flag -XX:+PrintCompilation
to ensure that no compilation occurs at all (i.e. the Interpreter was invoked as java -XX:+PrintCompilation -Xint Test
if no additional diagnostics were printed out, which 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 a long time and the results are the same in all calls. More research is needed to figure out why the two codes are JIT-optimized differently.
EDIT: Fun with part 2 JIT
So, I kept trying different compilation options. Generally speaking, there are two types of compilers that JIT uses. The C1 (client) compiler aims to speed up JVM startup times, but not as fast as the C2 (server) compiler. The 64-bit Java 8 JVM I have used seems to make the server accessible just for convenience (see this FAQ , however different compilation levels can be selected with a flag -XX:TieredStopAtLevel=
, for brevity I will not paste the results it gets, but they support the thesis that this is the version of the server compiler that makes the first call test2
faster).
I also have a 32 bit JRE on my machine. It does not support the server compiler and provides the following version information:
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
source to share
So, I checked your code and checked how long it has been running. The results are as follows (time in milliseconds for cycles 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 are executed at 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'm not sure why you think situations can arise in statements. But I think your program ran out of time on your online compiler (which has an end time). After you changed the arguments and thought it worked. This can probably be caused by the fact that your code has been warmed up, which can slightly reduce the rune time of the program. But that's just guessing ... and shouldn't work as an answer.
Please check the above code for yourself.
To answer your question, both boolean presses are the same. Although there is a slight difference in post-fix i ++ (copy value, increase current value, produces a copy) and prefix c ++ i (increase current value and give the result). Where the second has another operation. But this should not lead to a different computation time.
Look at this post Why "while" (i ++ <n) {} "is significantly slower than" while "(++ i <n) {}" for an explanation of why the IDE IDE is giving some strange results.
source to share
My best guess is that this is a quirk of how the bytecode is generated and / or run.
Computer processors have a limited number of registers that they can use to store the values they operate on at any given time. It is possible that the variables are placed in different registers based on which the first one appears. And if the variables are in different registers to start with, it might affect what is removed to make room for something else.
If the value is not in a register when needed later, the processor will have to retrieve it from the computer's memory (or processor cache), which takes longer than if it was already in the register.
Also where the processor might try to start executing one statement before another. But this can be aborted if the value changes. If it t++
happens very soon, before it tries to load again t
, the processor might be interrupted and must start the instruction from scratch. (However, I don't think this is the main reason for what is happening, it won't have that much effect.)
Maybe it's just a matter of some optimization that the Java compiler sees what it can do in one instance and not another.
source to share