Strange branching performance

by

It looks like a minor JIT bug. For a small branch probability, it generates something like the following, just much more complicated due to unrolling (I’m simplifying a lot):

movzwl 0x16(%r8,%r10,2),%r9d

Get the char: int r9d = queries[r10]

imul   $0x8acbf29,%r9d,%ebx

Multiply: ebx = 145538857 * r9d

shr    $0x1b,%ebx

Shift: ebx >>>= 27

cmp    %edx,%ebx
jae    somewhere

Check bounds: if (ebx > edx || ebx < 0) goto somewhere (and throw there an IndexOutOfBoundsException.

cmp    %r9d,%ebx
jne    back

Jump back to loop beginning if not equal: if (r9d != ebx) goto back

inc    %eax

Increment the result: eax++

jne    back

Simply goto back

We can see one smart and one dumb thing:

  • The bound check gets done optimally with a single unsigned comparison.
  • It’s completely redundant as x >>> 27 is always positive and less than the table length (32).

For a branch probability above 20%, these three instructions

cmp    %r9d,%ebx
jne    back
inc    %eax

get replaced by something like

mov    %eax,%ecx   // ecx = result
inc    %ecx        // ecx++
cmp    %r9d,%ebx   // if (r9b == index)
cmoveq %ecx,%ebx   //    result = ecx

using a conditional move instruction. This is one instruction more, but no branching and thus no branch misprediction penalty.

This explains the very constant time in the 20-80% range. The ramping below 20% is clearly due to branch mispredictions.

So it looks like a JIT failure to use the proper threshold of about 0.04 rather than 0.18.

thr

More Related Contents:

  1. What is the fastest search algorithm for a list with names and numbers
  2. Difference between declaring variables before or in loop?
  3. Does use of final keyword in Java improve the performance?
  4. Why is creating a Thread said to be expensive?
  5. Is there a performance difference between a for loop and a for-each loop?
  6. .toArray(new MyClass[0]) or .toArray(new MyClass[myList.size()])?
  7. Swing animation running extremely slow
  8. Java lambdas 20 times slower than anonymous classes
  9. What would be the fastest method to test for primality in Java?
  10. Compile-time constants and variables
  11. System.currentTimeMillis() vs. new Date() vs. Calendar.getInstance().getTime()
  12. Faster alternatives to Java’s reflection [closed]
  13. Java: what’s the big-O time of declaring an array of size n?
  14. Java local vs instance variable access speed
  15. Performance difference between Java 8 lambdas and anonymous inner classes
  16. Best practice for passing many arguments to method?
  17. Speed up Spring Boot startup time
  18. What is the time complexity of HashMap.containsKey() in java?
  19. Most efficient Java primitive collections library [closed]
  20. Know of any Java garbage collection log analysis tools? [closed]
  21. What is the fastest Java collection with the basic functionality of a Queue?
  22. Writing image to servlet response with best performance
  23. What is the quantitative overhead of making a JNI call?
  24. Java split String performances
  25. What is the Metadata GC Threshold and how do I tune it?
  26. ArrayList vs. Vectors in Java if thread safety isn’t a concern
  27. Java’s varargs performance
  28. Fastest way of reading relatively huge byte-files in Java
  29. Which one to use, int or Integer
  30. Is Hibernate an overkill for an Android application? [duplicate]

Leave a Comment