Beyond Java

As you can see, there's an array and an ArrayList, both containing the same set of numbers. In Java, streams always operate on a Collection, so I implemented the two algorithms using an ArrayList in order to compare similar things. However, I also was interested in how much the algorithm can be optimized by using a simple array.

Now for the first two attempts to calculate the sum. The first method uses the procedural style, the second method employs a fancy functional reduce method:

Subsonic speed

Whow. On my 2015 MacBook running JDK 1.8.0_151, the procedural method completes within merely 20 nanoseconds. The functional algorithm takes 120 nanoseconds.

That's six times slower - more or less what I expected to see. However, I was puzzled about the 20 nanoseconds. A quick (and very inaccurate) calculation revealed that the algorithm takes at least 100 instructions in total. That'd mean the CPU runs at the theoretical optimum of more than 1 instruction per cycle. Not impossible, given that the algorithm and the data is small enough to fit into the L1 cache, but extremely fast.

Mind you: the first three computers I owned operated at a megahertz. The fasted instruction they performed took two milliseconds. That's roughly 100 times slower than the procedural sum algorithm, and even 20 times slower than taking the sum using functional programming.

I became suspicious. Granted, a computer manufactured in 2014 is a lot faster than a computer dating back to the early 80s, but that seems a bit too much to be true.

But it is. I'll spare you the gory details, but I went to great lengths to examine the machine code the JVM executes after optimizing the code as much as it can. Both methods are really executed. The JVM doesn't detect they always return the same result.

So it seems to be true. Converting a good old for loop to a fancy functional stream makes it six times slower. Adding insult to injury, operating the procedural algorithm on a simple array doubles the performance again, making the functional approach a full magnitude slower.

Converting to streams is like running a computer four years old

If Moore's law was still true with respect to performance, the performance penalty was equivalent to running the algorithm on hardware that's four years old. In the IT world, that's ages.

On the other side, that's a trade-off that makes perfect sense in many situations. For example, if your feel streams improve the maintainability of your program, go for it. A rationalization frequently heard is testing. It's easy to test a function. No side effects, no hassles.

There are worse things than using a computer that four years old. The MacBook I'm using to write this text is three years old, and it doesn't feel like updating anytime soon.

But surely it's gonna improve over time!

I ran the performance test on JDK 1.8U151. Basically, that's the first version of Java supporting Java. So when I researched for this article, I've read many voices claiming "yeah, currently streams are slow, but surely they are going to improve over time!".

So the first thing I did was to run the benchmark again on Java 9. Can you imagine my surprise when I saw it's 15% slower on Java 9?

Actually, performance has already improved a lot over time, if you look at the early prototypes. In the early day, the idea was to convert Lambdas to "SAMs" - anonymous classes implementing a Single Abstract Method. Following this trait, using Lambdas would result in a lot of "...$1.class" files in your classpath, and a major performance penalty because of a plethora of inner classes created each time a Lambda is used.

I was fairly surprised to learn how Lambdas are implemented in the current JDKs. It's a fairly complicated process, involving the invokeDynamic instruction introduced with Java 8, method handles, and even creating classes during runtime. To verify the latter claim, I deliberately caused an exception in the Lambda expression:

The stack trace of the resulting exception looks suspiciously like being caused by an inner class:

Looking from that angle, the performance penalty doesn't come as a surprise. In fact, many resources on the internet indicate there's a huge performance penalty if Lambdas are only used a few times. The JVM generates a new class on the fly when the Lambda is called for the first time. After that, this class can be reused. That's why so many resources on the internet report a giant performance penalty. Using a Lambda once is expensive, indeed.

As soon as the JIT compiler kicks in, the performance penalty caused by Lambda themselves mostly vanishes.

Examining what really happens

As it turns out, Lambdas themselves only contribute a small part to the performance penalty. It's the surprisingly complex stream API making the difference. Running the benchmark with some JVM parameters show which methods are compiled during runtime. Add these parameters to the start command:

-Xbatch switches off a great feature of the JVM. By default, the JVM starts the JIT compiler in a new thread. Unfortunately, this causes log messages to arrive in parallel, making the output hard to read.

-XX:-TieredCompilation forces the JIT compiler to optimize the assembly code as much as possible from start. Usually, it prefers to optimize the code no less than five times. In general, this is a great compromise between quick startup time of your application and maximum performance of the parts of the application that are really used frequently. However, in this article, we're happy to see the final result of all the optimizations, so we opt to use the C5 compiler directly.

Finally, -XX:+PrintCompilation prints a line each time a method is compiled to assembly code. I've also examined the assembly code itself, but I'll spare you that because it's surprisingly long. Suffice it to say that the functional approach roughly takes roughly 900 lines of Assembly code, the procedure algorithm using the ArrayList takes roughly 333 lines of code, and the algorithm using a simple array takes less than 120 lines of code.

Inlining "hot" methods

How can so few lines of Java code translate to so many lines of machine code?

First, the JVM adds a lot of stuff you're not aware of. There are safepoints, there's code to correct optimizations that were just too optimistic, and there's much more. There's also a lot of extra lines to align the memory addresses of the code and the data with the CPU architecture. Your CPU reads stuff faster if it's at an "even" address. In 2018, "even" usually means that it divides to 16. Sometimes, it pays to waste 15 bytes. You trade memory for performance.

But all that doesn't explain the difference between the two procedural approaches. The clue is that the JVM inlines methods that are called often enough. Inlining means that the body of the method is copied to the caller. So you get rid of the overhead of calling a method. As a result, the Assembly code is kind of bloated, but it's a lot faster.

Complex implementation of the stream API

Back to the initial approach starting the application with the JVM parameters -Xbatch -XX:-TieredCompilation -XX:+PrintCompilation.

Among other things, this reveals which methods are used frequently. Omitting the methods compiled before our method under test is compiled, the functional approach compiles these methods: