Optimizing Your Java Code (2)

So as I mentioned earlier, I recently attended the Devoxx Java conference (formerly named Javapolis). At this conference I attended the 'Java Performance' lecture given by Dr. Holly Cummins (I should really use her title, not just Holly but Dr. Holly) and Kirk Pepperdine (not a doctor but an independent consultant).

This is part two of my Java Performance blogs. See the first part here

Today, I will be talking about a subject called Latency.
When you're working on a program or a piece of code you sometimes notice that it isn't running as it should. It seems to be slower than you expect. Or sometimes a customer can come to you and say that the program is doing five transactions per second when it should be doing ten.
In either way, you never quite know what the problem is precisely. All we really know is that the user is experiencing a poor reponse time. The user tries to work with your program but gets annoyed because the system doesn't do everything as quickly as he would like.

Right now, you know next to nothing about what could be causing the problem. It could be that the user's computer just isn't powerful enough to run this application in a responsive manner or it could be that your application just uses too much memory, making the guest's operating system swap like crazy.
Quite generally, we have three possible causes of poor response times
1) Insuffient capacity (hardware-related)
2) Inefficient use of capacity (a dreadful architecture, slow algorithms)
3) combination of the two above

Even if you know that inefficient use of capacity is the bottleneck in this particular case, you will still be hard pressed to find the exact source of the problem. As you will probably know, your hardware has a finite amount of resources available. Every time the processor receives an overflow of information for example, it queues the additional information and processes what it can, then retrieves the data in the queue and processes this. Not only the processor but every piece of hardware works with a queue. The amount of time data has to stay still and wait to be processed is called Latency. Latency is usually expressed by the inability of the application to consume the CPU. This means that if you're running the program at the part where the bottleneck occurs according to the client and you notice that your CPU is getting utilized more but not at its top priority (not 100%), then this should be a reasonable indicator that you're experiencing inflated latency times.

It works the other way around as well. If you're having a fully-utilized CPU, while still getting inflated response times, then one piece of code is dominating the CPU and isn't doing what it should. In this case, you can probably have an infinite loop (even though that shouldn't have gotten through the final testing phase) or maybe you're even doing the String concatenation I warned you about earlier.

There are four kinds of latency that are important to the performance of your Java application. These are:
1) Hardware Induced Latency
2) OS Induced Latency
3) VM Induced Latency
4) Application Induced Latency

Hardware Induced Latency is the form you'll probably understand best. Your computer has definite capacities that cannot be exceeded. You cannot ask more of your hardware than the absolute maximum. Everything you ask of it that does exceed this maximum is queued in memory until the hardware has time to execute these particular commands. The time that these instructions are kept waiting is what we refer to as Latency.

Operating System (OS) Induced Latency is a bit harder to understand, but not really. The OS provides an interface for hardware management. It takes the work out of the programmer's hands. The OS provides in memory management, I/O and other provisions. It's much harder to tell that you're dealing with OS induced latency but symptoms include a relatively high CPU-utilization or a large strain on your hard drive.
You can't really change your Operating System (unless you're running an open source one, of course). I have never found the problem to be lying with the Operating System itself. I just want you to understand that the Operating System is just another layer that queues your requests before it can handle them, thus increasing the complete latency.

The VM Induced Latency, on the other hand, is something you can do something about. The Java Virtual Machine (JVM) provides Garbage Collection (GC) as you know. It removes those objects that are no longer needed from memory. A lot of people don't really realize what the Garbage Collector does precisely. Does it work alongside your application, or does it interrupt your application? I believe, if I remember Dr. Cummins correctly, that it depends on the strategy your JVM follows. The default strategy for the JVM is to interrupt your program, remove those objects from memory and then allow your program to proceed. Think back to my String concatenation example. You create a String object and then concatenate some characters to this String. The result is a new String object. The JVM now interrupts your application, realising that the first String object is no longer needed and removes it from memory. Then it allows your application to proceed again. This is a vicious circle that makes your application run so much slower. The symptoms for diagnosing whether or not the problem lies with the JVM include high object creation rate and a high CPU utilization.
I think the only real thing you can do about this problem is check your object creation and disposal rates. There are easy light-weight monitoring tools out there like starting the JVM with the -verbose:gc switch. This will keep a log of your Garbage Collector. There are other tools out there (from IBM, for instance) that can present the information in this log in a visual way.

The last form of latency is Application Induced Latency. This is your program itself queuing data before processing it. Think of a deadlock happening. Thread A is waiting to gain access to resource R1 (having just used R2), while Thread B is waiting for resource R2 to be released by Thread A (having just used, and still locking R1). This prevents your application from making forward progress. The symptom for diagnosing whether or not the problem lies with your Application itself is an inability to fully utilize the CPU. You notice the response times aren't too good, but the CPU isn't being used all that intensively anyway. That means that some problem is occurring somewhere in your application, causing threads to be parked. For instance, one thread is waiting for an external system (connected e.g. across the Internet) to respond to a request and no threads can proceed without the answer from the external system. Your CPU doesn't have any work, but your application (or a part of) is halted anyway.
When this problem occurs, I think it's safe to say you may need to do some redesigning of your application, to make it less dependent of external systems. If, on the other hand, it is one of those programs that just needs that one web service to perform its task accordingly, this is not an option.

So those are the four forms of latency that are important to understand. It's important that you realize that sometimes the problem does not lie exactly with your code. Your JVM may be intrusive by halting your application all the time as well. You should check out all four forms of latency and
Hopefully you'll have a better understanding of latency now and realize how the different forms of Latency can affect your application.

Optimizing your Java code

I recently attended the Devoxx Java conference, held at Antwerp (Belgium) from Monday, 8th of Decembre 'till Friday,12th of Decembre. Unfortunately, I could only go the first two days but I managed to attend some interesting lectures about Java performance. There seem to be a lot of techniques you can apply to your Java code to make it run faster.
In the following days/weeks, I will discuss quite a few of these.

---

A lot of the people I talk to daily often complain about the speed, or lack thereof, of the Java programming language. Java is not one of the fastest programming languages out there and to understand why, you should dig into the basic structure of Java. Below is included a short explanation of how Java works. If you require more information, feel free to examine the links given at the end of this article. If you already know how Java works, feel free to skip the first part.

The basic structure of Java

Java works on every operating system, provided there is a Java Virtual Machine (JVM) available for this operating system. This is usually the case. If it's not the case, you should probably be wondering why you're working on such a system anyway.

Every instruction you program in the Java programming language gets translated into some intermediary language that only the JVM understands. This JVM (specific to the operating system it is installed on) then translates this to something the operating system can understand. The OS then ensures that these instructions are being executed by the hardware.

So every line of code you write in the Java programming language is translated not once, but thrice. Once, so the JVM understands what you want to make happen. These instructions are then translated again by the JVM so the operating system knows what you want done. The operating system then translates this into machine-code that the hardware can understand. The result (if any) is then calculated by the hardware, sent to the operating system, who gives it to the JVM who sents it to you.

That's a long way for data to travel and this is the first reason why people are quick to say that Java is slow. Sure, Java has its drawbacks when it comes to speedy execution of code and probably shouldn't be used for Grid Computing, for instance. But Java also has advantages. Like I said before, Java is platform-independent. Program once, and run it anywhere. You wrote your program on Windows but it will also work on Linux or Mac OS X without you having to invest extra time in porting your application. Also, Java has automatic memory management, thus removing those objects you no longer need to free up memory while your program is running (see Java Garbage collection) and on top of all of this, Java is also a very secure programming language.

When you write your Java code, there are certain aspects you should be aware of. Some of them will affect the performance of your Java code dramatically (either positively or negatively).

The first problem – String concatenation

One of the lectures I attended concerned itself entirely with testing for performance. The lecture was given by Holly Cummins (noted IBM garbage collection tuning specialist) and Kirk Pepperdine (a primary contributer to javaperformancetuning.com). The very first problem they tackled was that of String concatenation. They demonstrated a little program that was supposed to output the information of various stocks in HTML-form. This was accomplished by a method quite like the one below:

Table 1.1 The method getStockInfo

public String getStockInfo() { String result; result += "<html>"; result += "<head>"; result += "</head>"; result += "<body>"; result += "<table>"; for (Stock s : allStocks) { result += "<tr>"; result += "<td>Name: </td>"; result += "<td>" + s.getStockName() + "</td>"; result += "<td>" + s.getStockDate() + "</td>"; result += "<td>" + s.getStockRating() + "</td>"; result += "</tr>"; } result += "</table></body></html>"; return result; }

So as you can see, we make a String-object, append it using the '+=' operator with tags like <html> and then we get into a ForEach loop, iterating over the allStocks-collection. For every Stock, we append the result object with all data contained in the Stock, surrounded with HTML tags.

What do you think, will this code run smoothly? There is an easy way to find out.

In the Extra-Material-part at the end, you'll find a link to a generic StopWatch class. It is a light monitoring tool and will only have a very small effect on the performance of the application. This class measures performance from one point to another and outputs its result as a Long value.
Note that it's not important to actually understand this Class. I didn't write it myself, either, but found it on the Web. It's a great lightweight tool for performance monitoring though. Just create a new class and paste the code in there. It should work out of the box.

To test this code in an efficient way, I just use the following Main-class:

Table 1.2 The Main class

public Main() { allStocks = new ArrayList(); for (int i = 0; i<10000; i++) { allStocks.add(new Stock()); } StopWatch stopwatch = new StopWatch(); stopwatch.start(); getStockInfo(); stopwatch.stop(); long result = stopwatch.toValue(); System.out.println(result); }

As you can see, I first make 10 000 Stock-objects. That's not an exaggerated number. If you would put this program into production, it might run into instances of having 10 000 Stock objects to keep track of.

Try running this code. On my computer, it took about 17 minutes to complete. (1.6 Ghz single-core cpu, 1 Gb of RAM). As you can probably understand, when I want to see the current data of all Stocks, I don't want to wait 17 minutes. The execution time of this code is completely unacceptable.

There must be something wrong with it. What might we have overlooked?
Well, it's obvious we didn't read the API closely enough because the API for the class String explicitly states:
Strings are constant; their values cannot be changed after they are created. You read correctly. Once you create a String object, you can never change it again. java.lang.String is defined as an Immutable class.

So what gives? I'm changing my String aren't I? No, you're not. You're creating new String objects, containing the previous String and the next part you're trying to concatenate. That's a bummer for performance because every time you create a new String-object the old one becomes obsolete.

Because of the automatic Java memory management (Garbage collection) this old object is destroyed every time. So the Garbage Collector stops your program, removes the old String object from memory and then allows your program to continue. Your program concatenates again. Garbage collector interrupts and removes the old String, and so on and so forth.

Is there a good way to fix this?

Yes there is, fortunately. The Java API provides us with a StringBuilder object. This object works quite like a String-object but for one subtle difference. Internally, the StringBuilder (and StringBuffer as well) holds an array of Characters (char). When you want to concatenate to this String, it just resizes the array and puts the new characters in one by one. At the end, when you really need the String, you call the method toString() of the StringBuilder and for the first time, a String is constructed.
So remember to do all of your adaptations (concatenations, replacement of letters, etc...) on a StringBuilder object and then asking for a String. This is much faster.

But don't take my word for it. By all means. Adapt the getStockInfo() method like so:

Table 1.3 The getStockInfo method revised

public String getStockInfo() { StringBuilder sbResult = new StringBuilder(); sbResult.append("<html>"); sbResult.append("<head>"); sbResult.append("</head>"); sbResult.append("<body>"); sbResult.append("<table>"); for (Stock s : allStocks) { sbResult.append("<tr>"); sbResult.append("<td>Name</td>"); sbResult.append("<td>"); sbResult.append(s.getStockName()); sbResult.append("</td>"); sbResult.append("<td>"); sbResult.append(s.getStockDate()); sbResult.append("</td>"); sbResult.append("<td>"); sbResult.append(s.getStockRating()); sbResult.append("</td>"); sbResult.append("</tr>"); } sbResult.append("</table></body></html>"); return sbResult.toString(); }

I know, it looks pretty counter-intuitive. By using a StringBuilder you get more lines of code so you automatically think that it must be slower than using String concatenation but it's not. It's actually way faster.
The data on my computer is as follows:

• When running with normal String concatenation, the getStockInfo() method took 17 minutes 37 seconds to complete.


• When running with StringBuilder concatenation, the getStockInfo() method took only 148 milliseconds to complete.

Do you see the huge difference? I just sped up my program by more than 500%! And all I did was change String concatenation to StringBuilder concatenation! How efficient is that!!

Conclusion

So what have we learned exactly?
Not only have we learned to never use String concatenation, but we have also learned that the Java Garbage Collector can have a huge impact on the performance of your application. It frequently interrupts your program to get rid of the variables you no longer need. It's useful to keep this in mind when you're writing your code.

So that was the first of my Java Performance posts.
I hope you enjoyed, please drop me a line if you've read this. Anything at all is always appreciated.

Extra Material

The StopWatch class: http://www.javapractices.com/topic/TopicAction.do?Id=85
Podcasts by Holly Cummins: http://www.theserverside.com/tt/knowledgecenter/
The website of Kirk Pepperdine: http://www.kodewerk.com/