Gfrktyl

I am new to java, and was running some code last night, and this really bothered me. I was building a simple program to display every X outputs in a for loop, and I noticed a MASSIVE decrease in performance, when I used modulus as variable % variable vs variable % 5000 or whatnot. Can someone explain to me why this is and what is causing it? So I can be better...

Here is the "efficient" code (sorry if I get a bit of syntax wrong I'm not on the computer with the code right now)

long startNum = 0;

long stopNum = 1000000000L;



for (long i = startNum; i <= stopNum; i++){

    if (i % 50000 == 0) {

        System.out.println(i);

    }

}

Here is the "inefficient code"

long startNum = 0;

long stopNum = 1000000000L;

long progressCheck = 50000;



for (long i = startNum; i <= stopNum; i++){

    if (i % progressCheck == 0) {

        System.out.println(i);

    }

}

Mind you I had a date variable to measure the differences, and once it became long enough, the first one took 50ms while the other took 12 seconds or something like that. You may have to increase the stopNum or decrease the progressCheck if your PC is more efficient than mine or what not.

I looked for this question around the web, but I can't find an answer, maybe I'm just not asking it right.

EDIT:
I did not expect my question to be so popular, I appreciate all the answers. I did perform a benchmark on each half in time taken, and the inefficient code took considerably longer, 1/4 of a second vs 10 seconds give or take. Granted they are using println, but they are both doing the same amount, so I wouldn't imagine that would skew it much, especially since the discrepancy is repeatable. As for the answers, since I am new to Java, I will let votes decide for now which answer is best. I will try to pick one by Wednesday.

EDIT2:
I am going to make another test tonight, where instead of modulus, it just increments a variable, and when it reaches progressCheck, it will perform one, and then reset that variable to 0. for a 3rd option.

EDIT3:

I used this code, and below I'll show my results.. Thank you ALL for the wonderful help!

public class Main {



    public static void main(String args) {



        long startNum = 0;

        long stopNum = 1000000000L;

        long progressCheck = 50000;

        final long finalProgressCheck = 50000;

        long date;



        // using a fixed value

        date = System.currentTimeMillis();

        for (long i = startNum; i <= stopNum; i++) {

            if (i % 50000 == 0) {

                System.out.println(i);

            }

        }

        long final1 = System.currentTimeMillis() - date;

        date = System.currentTimeMillis();

        //using a variable

        for (long i = startNum; i <= stopNum; i++) {

            if (i % progressCheck == 0) {

                System.out.println(i);

            }

        }

        long final2 = System.currentTimeMillis() - date;

        date = System.currentTimeMillis();

        // using a final declared variable

        for (long i = startNum; i <= stopNum; i++) {

            if (i % finalProgressCheck == 0) {

                System.out.println(i);

            }

        }

        long final3 = System.currentTimeMillis() - date;

        date = System.currentTimeMillis();

        // using increments to determine progressCheck

        int increment = 0;

        for (long i = startNum; i <= stopNum; i++) {

            if (increment == 50000) {

                System.out.println(i);

                increment = 0;

            }

            increment++;



        }



        long final4 = System.currentTimeMillis() - date;

        System.out.println(

                "/nfixed = " + final1 + " ms " + "/nvariable = " + final2 + " ms " + "/nfinal variable = " + final3 + " ms " + "/nincrement = " + final4 + " ms");

    }

}

Results:

• fixed = 1067 ms


• variable = 8406 ms


• final variable = 1045 ms


• increment = 1894 ms

You are measuring the OSR (on-stack replacement) stub.

OSR stub is a special version of compiled method intended specifically for transferring execution from interpreted mode to compiled code while the method is running.

OSR stubs are not as optimized as regular methods, because they need a frame layout compatible with interpreted frame. I showed this already in the following answers: 1, 2, 3.

A similar thing happens here, too. While "inneficient code" is running a long loop, the method is compiled specially for the on-stack replacement right inside the loop. The state is transferred from the interpreted frame to OSR-compiled method, and this state includes progressCheck local variable. At this point JIT cannot replace the variable with the constant, and thus cannot apply certain optimizations like strength reduction.

In particular this means JIT does not replace integer division with multiplication. (See Why does GCC use multiplication by a strange number in implementing integer division? for the asm trick from an ahead-of-time compiler, when the value is a compile-time constant after inlining / constant-propagation, if those optimizations are enabled. An integer literal right in the % expression also gets optimized by gcc -O0, similar to here where it's optimized by the JITer even in an OSR stub.)

However, if you run the same method several times, the second and the subsequent runs will execute the regular (non-OSR) code, which is fully optimized. Here is a benchmark to prove the theory:

@State(Scope.Benchmark)

public class Div {



    @Benchmark

    public void divConst(Blackhole blackhole) {

        long startNum = 0;

        long stopNum = 100000000L;



        for (long i = startNum; i <= stopNum; i++) {

            if (i % 50000 == 0) {

                blackhole.consume(i);

            }

        }

    }



    @Benchmark

    public void divVar(Blackhole blackhole) {

        long startNum = 0;

        long stopNum = 100000000L;

        long progressCheck = 50000;



        for (long i = startNum; i <= stopNum; i++) {

            if (i % progressCheck == 0) {

                blackhole.consume(i);

            }

        }

    }

}

And the results:

# Benchmark: bench.Div.divConst



# Run progress: 0,00% complete, ETA 00:00:16

# Fork: 1 of 1

# Warmup Iteration   1: 126,967 ms/op

# Warmup Iteration   2: 105,660 ms/op

# Warmup Iteration   3: 106,205 ms/op

Iteration   1: 105,620 ms/op

Iteration   2: 105,789 ms/op

Iteration   3: 105,915 ms/op

Iteration   4: 105,629 ms/op

Iteration   5: 105,632 ms/op





# Benchmark: bench.Div.divVar



# Run progress: 50,00% complete, ETA 00:00:09

# Fork: 1 of 1

# Warmup Iteration   1: 844,708 ms/op          <-- much slower!

# Warmup Iteration   2: 105,893 ms/op          <-- as fast as divConst

# Warmup Iteration   3: 105,601 ms/op

Iteration   1: 105,570 ms/op

Iteration   2: 105,475 ms/op

Iteration   3: 105,702 ms/op

Iteration   4: 105,535 ms/op

Iteration   5: 105,766 ms/op

The very first iteration of divVar is indeed much slower, because of inefficiently compiled OSR stub. But as soon as the method reruns from the beginning, the new unconstrained version is executed which leverages all the available compiler optimizations.

As others have noted, the general modulus operation requires a division to be done. In some cases, the division can be replaced (by the compiler) by a multiplication. But both can be slow compared to addition/subtraction. Hence, the best performance can be expected by something along these lines:

long progressCheck = 50000;



long counter = progressCheck;



for (long i = startNum; i <= stopNum; i++){

    if (--counter == 0) {

        System.out.println(i);

        counter = progressCheck;

    }

}

Notice that often you don't really want/need modulus, because you know that your loop counter (i) or whatever is only ever incremented by 1, and you really don't care about the actual remainder the modulus will give you, just see if the incrementing-by-one counter hits some value.

Another 'trick' is to use power-of-two values/limits, e.g. progressCheck = 1024;. Modulus a power of two can be quickly calculated via bitwise and, i.e. if ( (i & (1024-1)) == 0 ) {...}. This should be pretty fast too, and may on some architectures outperform the explicit counter above.

In follow-up to @phuclv comment, I checked the code generated by JIT¹, the results are as follows:

for variable % 5000 (division by constant):

mov     rax,29f16b11c6d1e109h

imul    rbx

mov     r10,rbx

sar     r10,3fh

sar     rdx,0dh

sub     rdx,r10

imul    r10,rdx,0c350h    ; <-- imul

mov     r11,rbx

sub     r11,r10

test    r11,r11

jne     1d707ad14a0h

for variable % variable (by variable):

mov     rax,r14

mov     rdx,8000000000000000h

cmp     rax,rdx

jne     22ccce218edh

xor     edx,edx

cmp     rbx,0ffffffffffffffffh

je      22ccce218f2h

cqo

idiv    rax,rbx           ; <-- idiv

test    rdx,rdx

jne     22ccce218c0h

Because division always takes longer than multiplication, the last code snippet is less performant.

Java version:

java version "11" 2018-09-25

Java(TM) SE Runtime Environment 18.9 (build 11+28)

Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

^{1 - VM options used: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main}

I also surprised by seeing the performance of the above codes. Its all about the time taken by the compiler for executing the program as per the declared variable. In the second code i.e. inefficient one :

for (long i = startNum; i <= stopNum; i++){

if (i % progressCheck == 0) {

    System.out.println(i)

}

}

you are performing the modulus operation between two variable. Here compiler have to check the value of stopNum and progressCheck to go to the specific memory block located for these variable every time after each iteration because it is a variable and its value might be change. Thats why after each iteration compiler went to the memory location to check the latest value of the variables. Therefore at the compile time compiler not able to create efficient byte code. In the first code , you are performing modulus operator between a variable and a constant numeric value which is not going to change within execution and compiler no need to check the value of that numeric value from the memory location. Thats why compiler able to create efficient byte code. If you declare progressCheck as a final/final static variable then at the time of run-time/compile-time compiler know that its a final variable and its value not going to change then compiler replace the progressCheck with 50000 in code :

for (long i = startNum; i <= stopNum; i++){

if (i % 50000== 0) {

    System.out.println(i)

}

}

Now you can notice that this code is also look like the first code i.e. efficient one. The performance of first code and as we mentioned above both code will work efficiently. There will not be much difference in execution time of both code.