Optimization: Don't do it... The compiler will!

The Two Rules of Program Optimization

I've seen some bad code lately which was designed in an effort to improve performance. For instance, there was a long method (80 lines) that was not split into several methods for a single reason: to avoid the method call overhead (around 15 nanoseconds!). The result was code that was just hard to read.

This reminded me of the rules of program optimization (coined by Michael A. Jackson, a British computer scientist) we were teached back on university:
The First Rule of Program Optimization: Don't do it.
The Second Rule of Program Optimization (for experts only!): Don't do it yet.

Well, this is true for mainly two reasons:

1. Optimization can reduce readability and add code that is used only to improve the performance. This may complicate programs or systems, making them harder to maintain and debug.
2. Doing optimizations most of the time means we think to be smarter than the compiler, which is just plain wrong more often than not.

Cleaner Code

Donald Knuth said "Premature optimization is the root of all evil". Whereas "Premature optimization" means that a programmer lets performance considerations drive the design of his code. This can result in a design that is not as clean as it could have been, because the code is complicated by the optimization and the programmer is distracted by optimizing.

Therefore, if performance tests reveal that optimization or performance tuning really have to be done, they usually should be done at the end of the development stage.

Wrong Intuitions

This is what Sun Microsystem's Technology Evangelist Brian Goetz thinks: "Most performance problems these days are consequences of architecture, not coding – making too many database calls or serializing everything to XML back and forth a million times. These processes are usually going on outside the code you wrote and look at every day, but they are really the source of performance problems. So if you just go by what you're familiar with, you're on the wrong track. This is a mistake that developers have always been subject to, and the more complex the application, the more it depends on code you didn't write. Hence, the more likely it is that the problem is outside of your code." Right he is!

Smarter Compiler

Often, the best way to write fast code in Java applications is to write dumb code – code that is straightforward, clean, and follows the most obvious object-oriented principles in order to get the best compiler optimization. Compilers are big pattern-matching engines, written by humans who have schedules and time budgets, so they focus their efforts on the most common code patterns, in order to get the most leverage. Usually hacked-up, bit-banging code that looks really clever will get poorer results because the compiler can't optimize effectively.

A good example is string concatenation in Java (see this conversation with Java Champion Heinz Kabutz where he gives some measures)...

1. Back in the early days, we all used the String addition (+ operator) to concatenate Strings:
   return s1 + s2 + s3;
   However, since Strings are immutable, the compiled code will create many temporary String objects, which can strain the garbage collector.
2. That's why we were told to use StringBuffer instead:
   return new StringBuffer().append(s1).append(s2).append(s3).toString();
   That was around 3-5 times faster those days, but the code became less readable. Was it worth it? Is your code doing enough String concatenation to make you really feel a difference after you (for instance) made that execute three times faster?
3. Is that still the recommended way? A main downside of StringBuffer is its thread safety that is usually not required (since they are not shared between threads), but slows things down. Hence, the StringBuilder class was introduced in Java 5, which is almost the same as StringBuffer, except it's not thread-safe. So, using StringBuilder is expected to be significantly faster, and know what? When Strings are added using the + operator, the compiler in Java 5 and 6 will automatically use StringBuilder:
   return s1 + s2 + s3;
   Clean, easy to understand, and quick. Note that this optimization will not occur if StringBuffer is hard-coded!

That was just one example.... All in all, it's quite simple: today's Java JIT Compilers are highly optimized and clever in optimizing your code. Trust them. Don't try to be even more clever. You aren't!

How big is BigDecimal?

Lately, there was a debate in our company about rounding of numbers, more specific on how, when and where to do that.

One of the questions was if a calculation method should return a rounded value, or if the result should be precise and rounded by the caller. Another question was how to represent the values and which functionality to use to actually do the rounding.

There was a suggestion to use BigDecimal objects everywhere instead of simple double types because this class provides convenient methods for doing rounding.

Of course, when you need the higher precision, this might be a great choice. However, when you don't need that and are just using the class for being able to easily use it's rounding capabilities, the solution is probably over-engineered. Well, I voted against that mainly for two reasons: performance and object size.

1) Performance

It's obvious that calculations with primitive data types are faster than with BigDecimals (or BigInteger). But... how much?

A small Java code snippet helps to estimate the performance penalty:

final long iterations = 1000000;
long t = System.currentTimeMillis();
double d = 123.456;
for (int i = 0; i < iterations; i++) {
    final double b = d * (
                       (double)System.currentTimeMillis() 
                     + (double)System.currentTimeMillis());
}
System.out.println("double: "+(System.currentTimeMillis() - t));

t = System.currentTimeMillis();
BigDecimal bd = new BigDecimal("123.456");
for (int i = 0; i < iterations; i++) {
    final BigDecimal b = bd.multiply(
      BigDecimal.valueOf(System.currentTimeMillis()).add(
      BigDecimal.valueOf(System.currentTimeMillis())));
}
System.out.println("java.math.BigDecimal: "+(System.currentTimeMillis() - t));

We are not interested in absolute numbers here, but only in the comparison between double's and BigDecimal's. It turns out that one million operations (each is one multiplication and one addition of a double value) takes approximately 3-4 times longer with BigDecimal than with doubles (on my poor old laptop with Java 5).

Interestingly, when trying the same for BigInteger and long, the factor is approximately 5, i.e. the performance difference is even higher.

With Java 6, the method runs faster for all types, but calculation with primitives has a greater improvement so that the performance penalty for using Big* is even higher: 4-5 for BigDecimal, 6 for BigInteger.

2) Object Size

Everybody would expect that a BigDecimal would need more memory than a primitive double, right? But, how much is it? We are going to have big objects with up to hundreds of decimal values, so the bigger BigDecimal's might sum up to a critical value when thinking of transporting those objects between processes (web service calls) or holding them in the session (for web applications).

It happended that I have blogged about how to determine an object's size in my last post ;-) Hence, we can just move on to the actual figures:

• double: 8 bytes


• Double: 16 bytes (8 bytes overhead for the class, 8 bytes for the contained double)


• BigDecimal: 32 bytes


• long: 8 bytes


• Long: 16 bytes (8 bytes overhead for the class, 8 bytes for the contained long)


• BigInteger: 56 bytes

Wow. It seems that BigDecimal is 4 times as big than double and twice the size of Double – which is not that bad. As before, BigInteger has a bigger penalty with respect to object size as well.

3) Conclusion

All in all, when using BigDecimal instead of double, this means factor 4 for both memory footprint as well as performance penalty. A good reason to not use BigDecimal's just for using the rounding functionality...!

Size of Java Objects

I'm sure you know that measuring the size of objects in Java is not so easy since there is no C style sizeof() functionality. Additionally, the actual size used to store an object on the Java heap depends on several variables: the JVM implementation, operation system (32/64 Bit) etc. Hence, a particular value for the amount of storage consumed by an object can be compared to the size of another object, but not between different runtime environments.

So... how can the size of an object (i.e. it's memory usage) be determined? There are actually two possibilities. Both are well-known and not invented by me, so I only provide some basic information and links.

1) Use Runtime.freeMemory()

The usual (old-fashioned) way to estimate the size of an object is like this: call garbage collector (GC) to ensure all unused memory is freed, then count current memory consumption (M1), construct the object, GC once again and count memory (M2). The difference M2-M1 indicates the amount of memory used for the created object.

There are a few things to note:

• A single call to GC is more or less only a suggestion to the Java Virtual Machine to reclaim space from all discarded objects – it's no guarantee that GC has been finished (method is not blocking) and all old objects have been removed. To be a bit more aggressive, GC should be used a couple of times.


• To make sure that supplementary memory (for static data etc.) is already allocated before starting memory count, you should construct an object and set the handle to null before starting the estimation cycle described above.


• The precision might increase when creating not a single object, but a large amount of them.

JavaWorld's Java Tip 130 described this approach, and Heinz Kabutz published two JavaSpecialists newsletters (Issue 29, 78) about determining memory usage in Java.

Addtionally, there is an open source project java.sizeOf at SourceForge using this approach.

2) Use Instrumentation.getObjectSize()

Starting with Java 5 there is a new method to determine object size: the instrumentation interface. It's getObjectSize() method is still an estimate, but seems to provide more accurate results, albeit a bit slower than counting free memory.

In short, you have to implement an instrumentation agent that contains a premain(String, Instrumentation) method that will be called by the JVM on startup. The given instrumentation can be used to call methods on it later on. The agent has to be packaged into a JAR file that requires a Premain-Class specification in it's manifest file. To use the instrumentation agent, call java with the -javaagent option. For more information, see here and this blog post.

Guess what, Heinz Kabutz has published another JavaSpecialists newsletter 142 describing this approach (you see, it's really worth subscribing!). Refer to this java.net article for another example of how to use Java instrumentation.


That's it for today... One more remark: note that both described ways are not able to provide exact figures, but only estimates of memory consumption. This is not really an issue because these estimates are typically exact for small objects, and size of complex data structures can be calculated using the known size of basic types and data structures.