The Java JIT Compiler is Darn Good at Optimization

“Challenge accepted” said Tagir Valeev when I recently asked the readers of the jOOQ blog to show if the Java JIT (Just-In-Time compilation) can optimise away a for loop.

Tagir is the author of StreamEx, very useful Java 8 Stream extension library that adds additional parallelism features on top of standard streams. He’s a speaker at conferences, and has contributed a dozen of patches into OpenJDK Stream API (including bug fixes, performance optimizations and new features). He’s interested in static code analysis and works on a new Java bytecode analyzer.

I’m very happy to publish Tagir’s guest post here on the jOOQ blog.

tagir-valeev

The Java JIT Compiler

In recent article Lukas wondered whether JIT could optimize a code like this to remove an unnecessary iteration:

// ... than this, where we "know" the list
// only contains one value
for (Object object : Collections.singletonList("abc")) {
    doSomethingWith(object);
}

Here’s my answer: JIT can do even better. Let’s consider this simple method which calculates total length of all the strings of supplied list:

static int testIterator(List<String> list) {
    int sum = 0;
    for (String s : list) {
        sum += s.length();
    }
    return sum;
}

As you might know this code is equivalent to the following:

static int testIterator(List<String> list) {
    int sum = 0;
    Iterator<String> it = list.iterator();
    while(it.hasNext()) {
        String s = it.next();
        sum += s.length();
    }
    return sum;
}

Of course in general case the list could be anything, so when creating an iterator, calling hasNext and next methods JIT must emit honest virtual calls which is not very fast. However what will happen if you always supply the singletonList here? Let’s create some simple test:

public class Test {
    static int res = 0;

    public static void main(String[] args) {
        for (int i = 0; i < 100000; i++) {
            res += testIterator(Collections.singletonList("x"));
        }
        System.out.println(res);
    }
}

We are calling our testIterator in a loop so it’s called enough times to be JIT-compiled with C2 JIT compiler. As you might know, in HotSpot JVM there are two JIT-compilers, namely C1 (client) compiler and C2 (server) compiler. In 64-bit Java 8 they work together. First method is compiled with C1 and special instructions are added to gather some statistics (which is called profiling). Among it there is type statistics. JVM will carefully check which exact types our list variable has. And in our case it will discover that in 100% of cases it’s singleton list and nothing else. When method is called quite often, it gets recompiled by better C2 compiler which can use this information. Thus when C2 compiles it can assume that in future singleton list will also appear quite often.

You may ask JIT compiler to output the assembly generated for methods. To do this you should install hsdis on your system. After that you may use convenient tools like JITWatch or write a JMH benchmark and use -perfasm option. Here we will not use third-party tools and simply launch the JVM with the following command line options:

$ java -XX:+UnlockDiagnosticVMOptions -XX:+PrintCompilation -XX:+PrintAssembly Test >output.txt

This will generate quite huge output which may scare the children. The assembly generated by C2 compiler for ourtestIterator method looks like this (on Intel x64 platform):

  # {method} {0x0000000055120518} 
  # 'testIterator' '(Ljava/util/List;)I' in 'Test'
  # parm0:    rdx:rdx   = 'java/util/List'
  #           [sp+0x20]  (sp of caller)
  0x00000000028e7560: mov    %eax,-0x6000(%rsp)
  0x00000000028e7567: push   %rbp

  ;*synchronization entry
  ; - Test::testIterator@-1 (line 15)
  0x00000000028e7568: sub    $0x10,%rsp         
                                                
  ; implicit exception: dispatches to 0x00000000028e75bd
  0x00000000028e756c: mov    0x8(%rdx),%r10d    

  ;   {metadata('java/util/Collections$SingletonList')}
  0x00000000028e7570: cmp    $0x14d66a20,%r10d  

  ;*synchronization entry
  ; - java.util.Collections::singletonIterator@-1
  ; - java.util.Collections$SingletonList::iterator@4
  ; - Test::testIterator@3 (line 16)
  0x00000000028e7577: jne    0x00000000028e75a0 

  ;*getfield element
  ; - java.util.Collections$SingletonList::iterator@1
  ; - Test::testIterator@3 (line 16)
  0x00000000028e7579: mov    0x10(%rdx),%ebp    

  ; implicit exception: dispatches to 0x00000000028e75c9
  0x00000000028e757c: mov    0x8(%rbp),%r11d    

  ;   {metadata('java/lang/String')}
  0x00000000028e7580: cmp    $0x14d216d0,%r11d  
  0x00000000028e7587: jne    0x00000000028e75b1

  ;*checkcast
  ; - Test::testIterator@24 (line 16)
  0x00000000028e7589: mov    %rbp,%r10          
                                                
  ;*getfield value
  ; - java.lang.String::length@1
  ; - Test::testIterator@30 (line 17)
  0x00000000028e758c: mov    0xc(%r10),%r10d    

  ;*synchronization entry
  ; - Test::testIterator@-1 (line 15)
  ; implicit exception: dispatches to 0x00000000028e75d5
  0x00000000028e7590: mov    0xc(%r10),%eax     
                                                
                                               
  0x00000000028e7594: add    $0x10,%rsp
  0x00000000028e7598: pop    %rbp

  # 0x0000000000130000
  0x00000000028e7599: test   %eax,-0x27b759f(%rip)        
         
  ;   {poll_return}                                       
  0x00000000028e759f: retq   
  ... // slow paths follow

What you can notice is that it’s surpisingly short. I’ll took the liberty to annotate what happens here:

// Standard stack frame: every method has such prolog
mov    %eax,-0x6000(%rsp)
push   %rbp
sub    $0x10,%rsp         
// Load class identificator from list argument (which is stored in rdx 
// register) like list.getClass() This also does implicit null-check: if 
// null is supplied, CPU will trigger a hardware exception. The exception
// will be caught by JVM and translated into NullPointerException
mov    0x8(%rdx),%r10d
// Compare list.getClass() with class ID of Collections$SingletonList class 
// which is constant and known to JIT
cmp    $0x14d66a20,%r10d
// If list is not singleton list, jump out to the slow path
jne    0x00000000028e75a0
// Read Collections$SingletonList.element private field into rbp register
mov    0x10(%rdx),%ebp
// Read its class identificator and check whether it's actually String
mov    0x8(%rbp),%r11d
cmp    $0x14d216d0,%r11d
// Jump out to the exceptional path if not (this will create and throw
// ClassCastException)
jne    0x00000000028e75b1
// Read private field String.value into r10 which is char[] array containing
//  String content
mov    %rbp,%r10
mov    0xc(%r10),%r10d
// Read the array length field into eax register (by default method returns
// its value via eax/rax)
mov    0xc(%r10),%eax
// Standard method epilog
add    $0x10,%rsp
pop    %rbp
// Safe-point check (so JVM can take the control if necessary, for example,
// to perform garbage collection)
test   %eax,-0x27b759f(%rip)
// Return
retq   

If it’s still hard to understand, let’s rewrite it via pseudo-code:

if (list.class != Collections$SingletonList) {
  goto SLOW_PATH;
}
str = ((Collections$SingletonList)list).element;
if (str.class != String) {
  goto EXCEPTIONAL_PATH;
}
return ((String)str).value.length;

So for the hot path we have no iterator allocated and no loop, just several dereferences and two quick checks (which are always false, so CPU branch predictor will predict them nicely). Iterator object is evaporated completely, though originally it has additional bookkeeping like tracking whether it was already called and throwing NoSuchElementException in this case. JIT-compiler statically proved that these parts of code are unnecessary and removed them. The sum variable is also evaporated. Nevertheless the method is correct: if it happens in future that it will be called with something different from singleton list, it will handle this situation on the SLOW_PATH (which is of course much longer). Other cases like list == null or list element is not String are also handled.

What will occur if your program pattern changes? Imagine that at some point you are no longer using singleton lists and pass different list implementations here. When JIT discovers that SLOW_PATH is hit too often, it will recompile the method to remove special handling of singleton list. This is different from pre-compiled applications: JIT can change your code following the behavioral changes of your program.

10 Java Articles Everyone Must Read

One month ago, we’ve published a list of 10 SQL Articles Everyone Must Read. A list of articles that we believe would add exceptional value to our readers on the jOOQ blog. The jOOQ blog is a blog focusing on both Java and SQL, so it is only natural that today, one month later, we’re publishing an equally exciting list of 10 Java articles everyone must read.

Note that by “must read”, we may not specifically mean the particular linked article only, but also other works from the same authors, who have been regular bloggers over the past years and never failed to produce new interesting content!

Here goes…

1. Brian Goetz: “Stewardship: the Sobering Parts”

The first blog post is actually not a blog post but a recording of a very interesting talk by Brian Goetz on Oracle’s stewardship of Java. On the jOOQ blog, we’ve been slightly critical about 1-2 features of the Java language in the past, e.g. when comparing it to Scala, or Ceylon.

Brian makes good points about why it would not be a good idea for Java to become just as “modern” as quickly as other languages. A must-watch for every Java developer (around 1h)

2. Aleksey Shipilёv: The Black Magic of (Java) Method Dispatch

In recent years, the JVM has seen quite a few improvements, including invokedynamic that arrived in Java 7 as a prerequisite for Java 8 lambdas, as well as a great tool for other, more dynamic languages built on top of the JVM, such as Nashorn.

invokedynamic is only a small, “high level” puzzle piece in the advanced trickery performed by the JVM. What really happens under the hood when you call methods? How are they resolved, optimised by the JIT? Aleksey’s article sub-title reveals what the article is really about:

“Everything you wanted to know about Black Deviously Surreptitious Magic in low-level performance engineering”

Definitely not a simple read, but a great post to learn about the power of the JVM.

Read Aleksey’s “The Black Magic of (Java) Method Dispatch

3. Oliver White: Java Tools and Technologies Landscape for 2014

We’re already in 2015, but this report by Oliver White (at the time head of ZeroTurnaround’s RebelLabs) had been exceptionally well executed and touches pretty much everything related to the Java ecosystem.

Read Oliver’s “Java Tools and Technologies Landscape for 2014

4. Peter Lawrey: Java Lambdas and Low Latency

When Aleksey has introduced us to some performance semantics in the JVM, Peter takes this one step further, talking about low latency in Java 8. We could have picked many other useful little blog posts from Peter’s blog, which is all about low-latency, high performance computing on the JVM, sometimes even doing advanced off-heap trickery.

Read Peter’s “Java Lambdas and Low Latency

5. Nicolai Parlog: Everything You Need To Know About Default Methods

Nicolai is a newcomer in the Java blogosphere, and a very promising one, too. His well-researched articles go in-depth about some interesting facts related to Java 8, digging out old e-mails from the expert group’s mailing list, explaining the decisions they made to conclude with what we call Java 8 today.

Read Nicolai’s “Everything You Need To Know About Default Methods

6. Lukas Eder: 10 Things You Didn’t Know About Java

This list wouldn’t be complete without listing another list that we wrote ourselves on the jOOQ blog. Java is an old beast with 20 years of history this year in 2015. This old beast has a lot of secrets and caveats that many people have forgotten or never thought about. We’ve uncovered them for you:

Read Lukas’s “10 Things You Didn’t Know About Java

7. Edwin Dalorzo: Why There Is Interface Pollution in Java 8

Edwin has been responding to our own blog posts a couple of times in the past with very well researched and thoroughly thought through articles, in particular about Java 8 related features, e.g. comparing Java 8 Streams with LINQ (something that we’ve done ourselves, as well).

This particular article explains why there are so many different and differently named functional interfaces in Java 8.

Read Edwin’s “Why There Is Interface Pollution in Java 8

8. Vlad Mihalcea: How Does PESSIMISTIC_FORCE_INCREMENT Lock Mode Work

When Java talks to databases, many people default to using Hibernate for convenience (see also 3. Oliver White: Java Tools and Technologies Landscape for 2014). Hibernate’s main vision, however, is not to add convenience – you can get that in many other ways as well. Hibernate’s main vision is to provide powerful means of navigating and persisting an object graph representation of your RDBMS’s data model, including various ways of locking.

Vlad is an extremely proficient Hibernate user, who has a whole blog series on how Hibernate works going. We’ve picked a recent, well-researched article about locking, but we strongly suggest you read the other articles as well:

Read Vlad’s “How Does PESSIMISTIC_FORCE_INCREMENT Lock Mode Work

9. Petri Kainulainen: Writing Clean Tests

This isn’t a purely Java-related blog post, although it is written from the perspective of a Java developer. Modern development involves testing – automatic testing – and lots of it. Petri has written an interesting blog series about writing clean tests in Java – you shouldn’t miss his articles!

Read Petri’s “Writing Clean Tests

10. Eugen Paraschiv: Java 8 Resources Collection

If you don’t already have at least 9 open tabs with interesting stuff to read after this list, get ready for a browser tab explosion! Eugen Paraschiv who maintains baeldung.com has been collecting all sorts of very interesting resources related to Java 8 in a single link collection. You should definitely bookmark this collection and check back frequently for interesting changes:

Read Eugen’s “Java 8 Resources Collection

Many other articles

There are, of course, many other very good articles providing deep insight into useful Java tricks. If you find you’ve encountered an article that would nicely complement this list, please leave a link and description in the comments section. Future readers will appreciate the additional insight.