Huge performance gain in Java data processing by not using branches/conditions

1

Ran the following Java snippet which showed a big performance difference. Java 11.0.9.1 on Ubuntu 18.04.

With condition, like c = (res[i][j] >= 64)? 1 : 0;, I got time in ms: 1216

With no condition, like c = ((((res[i][j] - 64) & 0x80000000)>>31)+1); I got time in ms: 438

Questions:

  1. why is there such a big difference in performance
  2. Is c = ((((res[i][j] - 64) & 0x80000000)>>31)+1); the best option?

Thanks in advance.

public class FastCompare {
    static final int ITEMS = 1000000;
    static final int ATTRS = 1000;
    public static void main(String args[]) {
        byte[][] res = new byte[ITEMS][ATTRS];
        int i;
        int j;
        for (i=0; i<ITEMS; i++) {
            for (j=0; j<ATTRS; j++) {
                res[i][j] = (byte)(i+j);
            }
        }
        long start = System.currentTimeMillis();
        long a = 1;
        int c;
        for (i = 0; i < ITEMS; i++) {
            for (j=0; j<ATTRS; j++) {
                c = (res[i][j] >= 64)? 1 : 0;
                //c = ((((res[i][j] - 64) & 0x80000000)>>31)+1);
                a += c;
            }
        }
        System.out.println("time in ms: " + (System.currentTimeMillis() - start));
        System.out.println("a="+a);
    }
};
java
performance
optimization
asked on Stack Overflow Dec 19, 2020 by pktCoder • edited Dec 19, 2020 by akuzminykh

2 Answers

0

Use JMH for perfomance testing. Don't trust naive currentTimeMillis() measures.

answered on Stack Overflow Dec 20, 2020 by user882813
0

I got the same result as you (though I used System.nanotime() instead as that's more reliable). It's probably because branching can cause problems with modern processor pipelining. See https://software.intel.com/content/www/us/en/develop/articles/branch-and-loop-reorganization-to-prevent-mispredicts.html

answered on Stack Overflow Dec 20, 2020 by k314159

User contributions licensed under CC BY-SA 3.0