Java 8 Lambda overhead

Intro

This is a follow-up to an earlier post where I was speculating that Java's Just In Time compilation may have been causing significant performance differences when some code was being exercised more than one or two times.

Here is a snippet of the code which I would like to focus on:

int anIndex = Collections.binarySearch(sorted, target, 

(o1, o2) -> o1.compareTo(o2)
);

The title of this post should have given away that the lambda expression made the performance take a hit until something kicked in and probably replace the lambda setup in each loop iteration with a single instance.

Alternatives

Comparator intComparator = Integer::compareTo;

int anIndex = Collections.binarySearch(sorted, target, intComparator);

Also uses some Java 8 magic and performs slowly.

Comparator intComparator = new Comparator() {
    @Override    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);    }
};int anIndex = Collections.binarySearch(sorted, target, intComparator);

Doesn't use any lambda expressions and performs quickly.

The final, slightly embarrassing example:

int anIndex = Collections.binarySearch(sorted, target);

So, I didn't even need to define the method for the comparison.

The micro benchmarking trap

JVM Compilation Magic

(Updated - corrected code sample to include actual call to indexOf, which I only noticed after tweeting about this.)

A better indexOf for a sorted ArrayList

I'm in the process of brushing up on my knowledge of the Java Collections API at the moment.  When I came across indexOf(Object object) in ArrayList I decided to see how it works.

Although Lists in Java preserve order they cannot assume their contents will be in a particular order.  So in indexOf(myObject) on a List the safest way to guarantee that the index of the first match that exists will be returned is by starting from the head of the list and iterating through the tail.

As an exercise for myself, I decided to compare the performance of indexOf against a slightly tweaked binary search for when the elements of the list are known to be in a sorted order.

The Collections class provides a binarySearch static method which returns the index of an Object in a List - so the majority of the work has already been done for us.

The tweak that I mentioned earlier is that my List can contain duplicates.  So, once the binarySearch has found a match, we still need to check earlier in the List until we can confirm that we have the very first match.

private static void indexOfSortedList() {
    // indexOf is a bit naive, so let's see if a sorted list     // can be made to behave better with binarySearch    ArrayList sorted = new ArrayList<>(50000000);    // Pre-loading randoms    Random random = new Random();    random.setSeed(1337L);    boolean[] randoms = new boolean[20000000];
    for (int b = 0; b < 20000000; b++) {
        randoms[b] = random.nextBoolean();    }

    for (int i = 0; i < 20000000; i++) {
        sorted.add(i);
        // Introducing duplicates at random points        if (randoms[i]) {
            sorted.add(i);        }
    }

    final Integer target = Integer.valueOf(1700000);
    long timeBefore = System.currentTimeMillis();    int anIndex = Collections.binarySearch(sorted, target,            (o1, o2) -> o1.compareTo(o2)
    );
    // We treat anIndex as starting position and move backwards    // until we establish the first instance    while (anIndex > 0 && sorted.get(anIndex - 1).equals(target)) {
        anIndex--;    }
    System.out.println("Duration binary approach " + 
            (System.currentTimeMillis() - timeBefore));    System.out.println("binarySearch value: " + anIndex);
    long timeBeforeIndexOf = System.currentTimeMillis();    int indexOfValue = sorted.indexOf(target);    System.out.println("Duration indexOf " + 
            (System.currentTimeMillis() - timeBeforeIndexOf));    System.out.println("Index of value: " + indexOfValue);}

The computer scientists amongst you should appreciate how a binary search will involve far fewer operations than the linear search that indexOf is based on.

Would it surprise you to find that the indexOf implementation consistently showed a much faster performance?

That was until I scaled up the search space to have 10s of millions of elements to search through, and shifted the match to be quite high in the search space - biasing towards the binarySearch in a very unfair way.

Slightly surprised at this counterintuitive outcome, I went away for lunch and picked up a book: Java Performance : The definitive guide

A section about the JIT compiler gave me a theory to try out - perhaps this code wasn't being compiled beyond byte code because it was only being run once.

Modifying the setup to loop around calling the method showed numbers that would reinforce that theory.  After the first iteration the tweaked binarySearch performed faster than the indexOf call.

Pre-allocating for capacity

Within the same code you may have noticed that I chose to pre-initialise the capacity of the ArrayList.  This is a habit that I got into when want to reduce waste in memory allocation.

Some code that I have deleted from the example above was measuring the performance of the calls to populate the ArrayList.

I observed that specifying the capacity in advance resulted in slower insertion - even though the code for setting up the capacity was not included in the calls to be measured.

When I changed the code to have multiple calls to the method I observed that the first pass through had poor performance around 11s, but the next few calls dropped down around 4s, and subsequent passes went as low as a few hundred millis but fluctuated back up to around 4s.

Summary

My future approaches to trying some minor performance tweaking change out will not involve single runs, but will take into account how the JVM will actually massage the code into its final working state.

Software Library Dependency Iceberg

A while ago I wrote some Java code as a plugin for the Go Continuous Delivery server software.  It works quite nicely and won a contest - but that's not the topic for today.

Out of curiosity I have considered changing the way that dependencies have been managed.  So far the application just has three direct runtime dependencies and relies on Gradle to pull in any transitive dependencies.  I want to explicitly declare the dependencies and let Gradle only take care of downloading them, compilation, and assembling the jar.

A quick look at the tree of transitive dependencies shows common libraries but different versions.

+--- cd.go.plugin:go-plugin-api:14.4.0

+--- com.google.code.gson:gson:2.3.1

\--- org.cloudfoundry:cloudfoundry-client-lib:1.1.3

     +--- org.springframework:spring-webmvc:4.0.5.RELEASE -> 4.0.8.RELEASE

     |    +--- org.springframework:spring-beans:4.0.8.RELEASE

     |    |    \--- org.springframework:spring-core:4.0.8.RELEASE

     |    |         \--- commons-logging:commons-logging:1.1.3

     |    +--- org.springframework:spring-context:4.0.8.RELEASE

     |    |    +--- org.springframework:spring-aop:4.0.8.RELEASE

     |    |    |    +--- aopalliance:aopalliance:1.0

     |    |    |    +--- org.springframework:spring-beans:4.0.8.RELEASE (*)

     |    |    |    \--- org.springframework:spring-core:4.0.8.RELEASE (*)

     |    |    +--- org.springframework:spring-beans:4.0.8.RELEASE (*)

     |    |    +--- org.springframework:spring-core:4.0.8.RELEASE (*)

     |    |    \--- org.springframework:spring-expression:4.0.8.RELEASE

     |    |         \--- org.springframework:spring-core:4.0.8.RELEASE (*)

     |    +--- org.springframework:spring-core:4.0.8.RELEASE (*)

     |    +--- org.springframework:spring-expression:4.0.8.RELEASE (*)

     |    \--- org.springframework:spring-web:4.0.8.RELEASE

     |         +--- org.springframework:spring-aop:4.0.8.RELEASE (*)

     |         +--- org.springframework:spring-beans:4.0.8.RELEASE (*)

     |         +--- org.springframework:spring-context:4.0.8.RELEASE (*)

     |         \--- org.springframework:spring-core:4.0.8.RELEASE (*)

     +--- org.springframework.security.oauth:spring-security-oauth2:2.0.4.RELEASE

     |    +--- org.springframework:spring-beans:4.0.8.RELEASE (*)

     |    +--- org.springframework:spring-core:4.0.8.RELEASE (*)

     |    +--- org.springframework:spring-context:4.0.8.RELEASE (*)

     |    +--- org.springframework:spring-webmvc:4.0.8.RELEASE (*)

     |    +--- org.springframework.security:spring-security-core:3.2.5.RELEASE

     |    |    +--- aopalliance:aopalliance:1.0

     |    |    +--- org.springframework:spring-aop:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                               (*)

     |    |    +--- org.springframework:spring-beans:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                             (*)

     |    |    +--- org.springframework:spring-context:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                           (*)

     |    |    +--- org.springframework:spring-core:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                              (*)

     |    |    \--- org.springframework:spring-expression:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                        (*)

     |    +--- org.springframework.security:spring-security-config:3.2.5.RELEASE

     |    |    +--- aopalliance:aopalliance:1.0

     |    |    +--- org.springframework.security:spring-security-core:3.2.5.RELEASE                                                                             (*)

     |    |    +--- org.springframework:spring-aop:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                               (*)

     |    |    +--- org.springframework:spring-beans:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                             (*)

     |    |    +--- org.springframework:spring-context:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                           (*)

     |    |    \--- org.springframework:spring-core:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                              (*)

     |    +--- org.springframework.security:spring-security-web:3.2.5.RELEASE

     |    |    +--- aopalliance:aopalliance:1.0

     |    |    +--- org.springframework.security:spring-security-core:3.2.5.RELEASE                                                                             (*)

     |    |    +--- org.springframework:spring-beans:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                             (*)

     |    |    +--- org.springframework:spring-context:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                           (*)

     |    |    +--- org.springframework:spring-core:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                              (*)

     |    |    +--- org.springframework:spring-expression:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                        (*)

     |    |    \--- org.springframework:spring-web:3.2.8.RELEASE -> 4.0.8.RELEASE                                                                               (*)

     |    +--- commons-codec:commons-codec:1.6

     |    \--- org.codehaus.jackson:jackson-mapper-asl:1.9.13

     |         \--- org.codehaus.jackson:jackson-core-asl:1.9.13

     +--- org.apache.httpcomponents:httpclient:4.3.6

     |    +--- org.apache.httpcomponents:httpcore:4.3.3

     |    +--- commons-logging:commons-logging:1.1.3

     |    \--- commons-codec:commons-codec:1.6

     +--- commons-io:commons-io:2.1

     +--- com.esotericsoftware.yamlbeans:yamlbeans:1.06

     +--- com.fasterxml.jackson.core:jackson-core:2.3.3

     +--- com.fasterxml.jackson.core:jackson-databind:2.3.3

     |    +--- com.fasterxml.jackson.core:jackson-annotations:2.3.0

     |    \--- com.fasterxml.jackson.core:jackson-core:2.3.3

     +--- org.apache.tomcat.embed:tomcat-embed-websocket:8.0.15

     |    \--- org.apache.tomcat.embed:tomcat-embed-core:8.0.15

     +--- org.apache.tomcat:tomcat-juli:8.0.15

     \--- com.google.protobuf:protobuf-java:2.6.1

Just look at the number of times a Spring library version 3.2.8 is specified, but overridden to 4.0.8 - that's a jump in major version number, which may have introduced incompatible code changes, such as removing a method from the API.

I wonder if there are any tools out there that could analyse the caller / callee relationships to offer developers some reassurance or warnings when jars get replaced by different versions in a situation like this.

Service lifecycle

Just some notes about the lifecycle of an instance of a service application from deployment through to shutdown.

In a continuous delivery environment this cycle might happen multiple times per day, where each instance represents a new version of working software that has passed through a deployment pipeline.

Start up

Initialisation
 - locate and parse configuration
 - validate configuration
 - establish connectivity to downstream services
 - log success or failure details

PASS/FAIL

Ready to accept requests, but no routing in place to receive live traffic.

Smoke tests
 - final readiness checks before setting live
 - accept and process incoming requests, produce responses

PASS/FAIL

Load balancer updated to direct live traffic

Routine business of processing incoming requests

Requests come in via load balancer, get processed by service - potentially with calls to downstream services - and responses are returned.

Depending on demand, the number of instances of the service may be scaled up and down to service the volume of requests.

Shut down

Load balancer updated to exclude instance from receiving live traffic requests (connection draining to allow existing requests to each receive a response - check how well this is supported).

Log the fact that shutdown has been initiated.

Finish processing existing requests

Close all connections to downstream services.

Terminate all threads.

Process terminates.