Brian Gordon blog

Optimizations performed by javac

programming 12 January 2014

I’ve been a full-time Java developer for about a year now, and in that time I’ve seen a lot of incorrect information out there about the behavior of the Java compiler (javac). With this post I hope to clear up some misconceptions about compile-time optimization in Java. Note that this information is correct for my version of javac but is not necessarily true for all JDKs.

brian@mint ~ $ java -version
java version "1.7.0_45"
Java(TM) SE Runtime Environment (build 1.7.0_45-b18)
Java HotSpot(TM) 64-Bit Server VM (build 24.45-b08, mixed mode)

Boolean expressions

Let’s start with an easy case. Is the compiler smart enough to spot a redundant logical NOT in a boolean condition? Let’s compile the following blocks of code:

if(!booleanExpression) {
    doSomething(1);
} else {
    doSomething(0);
}
if(booleanExpression) {
    doSomething(0);
} else {
    doSomething(1);
}

The compiler produces pretty much identical bytecode for both of these. Of course, the cost of an added logical NOT operation would be insignificantly small. But in fact there is no extra operation. Let’s examine the bytecode:

13: ifne          23
16: iconst_1      
17: invokestatic  #5                  // doSomething(1)
20: goto          27
23: iconst_0      
24: invokestatic  #5                  // doSomething(0)
27: return
13: ifeq          23
16: iconst_0      
17: invokestatic  #5                  // doSomething(0)
20: goto          27
23: iconst_1      
24: invokestatic  #5                  // doSomething(1)
27: return

The only difference is an ifeq instead of an ifne as the condition for the jump, so you can feel free to use either of the two forms depending on which makes more intuitive sense in context.

Now for a more complex case. You might be tempted to apply your knowledge of boolean algebra to transform the former of these blocks into the latter in order to improve performance in a tight loop:

if(!a || !b) {
    doSomething();
}
if(!(a && b)) {
    doSomething();
}

Would you be justified in doing so?

19: iload_2       
20: ifeq          27
23: iload_3       
24: ifne          33
30: invokevirtual #6
19: iload_2       
20: ifeq          27
23: iload_3       
24: ifne          33
30: invokevirtual #6

Nope! Once again, the compiler is smarter than you are. In fact, in this case the compiler literally generates the exact same bytecode for the two functions.

Constant arithmetic

private static int SECONDS_IN_30_DAYS = 60*60*24*30;

This is clearly more readable than embedding the magic constant 2592000 in the source code. But does it incur a runtime performance cost? Here is the bytecode for the class’s static initializer:

0: ldc           #5                  // int 2592000
2: putstatic     #3                  // Field SECONDS_IN_30_DAYS:I
5: return

The ldc instruction indicates that the compiler has precomputed the value 2592000 and stored it in the class’s constant pool. No multiplication occurs at run-time.

OK, so that works for integer arithmetic. How about constant boolean expressions?

private static boolean troo = true && (false || false || (true && true));
0: iconst_1      
1: putstatic     #3                  // Field troo:Z
4: return

This one is even leaner! Since there’s a special bytecode instruction for loading the integer 1, you don’t even have to go to the constant pool.

Note that in the two previous examples we have forced the compiler to create a static field within the class, and to create code which initializes the field. Creating a field is unnecessary for constant expressions. If we add the final keyword, we can get the compiler to inline these values wherever they’re actually used within the class.

Without final:

private static int SECONDS_IN_30_DAYS = 60*60*24*30;

public static void main(String[] args) {
    System.out.println(SECONDS_IN_30_DAYS);
}
public static void main(java.lang.String[]);
  Code:
     0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
     3: getstatic     #3                  // Field SECONDS_IN_30_DAYS:I
     6: invokevirtual #4                  // Method java/io/PrintStream.println:(I)V
     9: return        

static {};
  Code:
     0: ldc           #5                  // int 2592000
     2: putstatic     #3                  // Field SECONDS_IN_30_DAYS:I
     5: return

With final there is no separate static initializer section, and instead of getstatic we can simply ldc to get the constant value:

private static final int SECONDS_IN_30_DAYS = 60*60*24*30;

public static void main(String[] args) {
    System.out.println(SECONDS_IN_30_DAYS);
}
public static void main(java.lang.String[]);
  Code:
     0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
     3: ldc           #3                  // int 2592000
     5: invokevirtual #4                  // Method java/io/PrintStream.println:(I)V
     8: return

String concatenation

Some people will tell you that String concatenation with + is a performance killer on Java. They’ll tell you to use StringBuilder instead. But javac is actually pretty smart about converting + into StringBuilder appends.

return str1 + " : " + str2;
11: new           #3                  // class java/lang/StringBuilder
14: dup           
15: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
18: aload_1       
19: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
22: ldc           #6                  // String  : 
24: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
27: aload_2       
28: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
31: invokevirtual #7                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;

However, it’s not perfect. In cases like this you need to construct a StringBuilder yourself, because the automatic StringBuilder won’t be reused for the second line:

String cat = str1 + " : " + str2;
return cat + " 123";
 8: new           #2                  // class java/lang/StringBuilder
11: dup           
12: invokespecial #3                  // Method java/lang/StringBuilder."<init>":()V
15: aload_1       
16: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
19: ldc           #5                  // String  : 
21: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
24: aload_2       
25: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
28: invokevirtual #6                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
31: astore_3      
35: new           #2                  // class java/lang/StringBuilder
38: dup           
39: invokespecial #3                  // Method java/lang/StringBuilder."<init>":()V
42: aload_3       
43: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
46: ldc           #8                  // String  123
48: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
51: invokevirtual #6                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;

Note that the StringBuilder constructor is called twice (lines 8 and 35).

Constant String concatenation

IntelliJ IDEA breaks lengthy String constants into multiple lines:

return "We the People of the United States, in Order to form a more perfect "
     + "Union, establish Justice, insure domestic Tranquility, provide for the "
     + "common defence, promote the general Welfare, and secure the Blessings "
     + "of Liberty to ourselves and our Posterity, do ordain and establish this "
     + "Constitution for the United States of America.";

As you might expect, the compiler deals:

0: ldc           #2                  // String We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America.

Dead code elimination

If code is unreachable, it will be eliminated from the class file:

public static void main(String[] args) {
    if(false) {
        System.out.println("The universe is broken.");
    }
}
public static void main(java.lang.String[]);
  Code:
     0: return

Advanced optimizations

Believe it or not, that’s about all of the optimizations that are performed at compile time. The really advanced optimizations are going to be deferred until the code is just-in-time compiled at runtime. This allows the JIT to write machine code which is optimized for your specific processor architecture.

Something you need to be aware of, though, is that in order to employ certain optimizations the JIT cannot compile loaded bytecode immediately:

A warm-up period provides the HotSpot VM’s JIT compiler the opportunity to collect information about a running program and make intelligent dynamic optimization decisions based on the “hot” code paths taken by the executing program. By default, the HotSpot Server VM executes a block of Java byte code 10,000 times before the HotSpot Server JIT compiler produces native machine code for that block of Java bytecode.

Java Performance, by Charlie Hunt and Binu John.

This can really play hell with your efforts to profile code, because the performance profile of your application is constantly changing as more methods are JIT compiled. One thing you can try is setting the runtime flag -XX:CompileThreshold to a lower value, for example 1. This will cause the JIT to run immediately; however, its optimizations will be less effective and this will subvert the Java code cache mechanism if you don’t have enough memory available.

A brain teaser

puzzle 28 December 2012

These two brain teasers posted on /r/math impressed me greatly, so I decided to present them here.

You have been abducted by terrorists and blindfolded. They sit you down at a table and tell you that if you can solve two puzzles then they will let you go.

There is a deck of 52 cards on the table in front of you. Ten of them are face-up and the rest are face-down. Split the deck such that each new stack has an equal number of face-up cards.

You sit thinking in darkness for a few minutes. The terrorists are growing impatient around you when you finally smile: you’ve got the solution! You count out 10 cards from the deck and flip them over. Then you push the two stacks across the table.

The terrorists count the face-up cards in each stack suspiciously. When they find that the number of face-up cards is identical, they’re impressed, but you have a yet harder challenge to face before they will let you go.

On one side of the table there are five dice which add up to 15. On the other side of the table there are another five dice which add up to 13. Move some dice around so that the two sides of the table have equal sums.

You furrow your brow and sit thinking in darkness for over an hour. The terrorists’ new respect for you is wearing off quickly, and they won’t wait much longer. Finally, you get it. You take one die from the group on the right and move it to the group on the left. Then you flip the remaining 4 dice of the right group upside-down. “You see,” you explain carefully. “If the left group sums to , then the right group sums to ; this was given in the problem. If you take a die from the right group and move it to the left, then the new sums are and . Now, because the opposite sides of a single die always add to 7, any time you flip a set of 4 dice summing to , you end up with a set of 4 dice summing to . Therefore, if we flip all of the dice in the right group, we now have:” “which is the same value that we have on the left side.”

Looping a YouTube video

tips 30 November 2012

Last night I was trying to figure out a balisong trick by watching 15 seconds of a YouTube video over and over while trying to duplicate the movements. Switching back and forth between my mouse and the knife was getting annoying, so I took a few minutes to figure out how to control the player with JavaScript. This is how I did it.

First, get the <embed> DOM object. The best way to do this is by using the DOM inspector in your favorite browser to find the ID string of the element. Right now that ID is movie_player, but YouTube mught change it in the future.

A screenshot of Firefox's DOM inspector

Once you have the ID string you can get the DOM object using getElementById in your browser’s JavaScript console.

var ytplayer = document.getElementById("movie_player");

Now you can use any of the functions of the YouTube player API, which are properties of the DOM object we just found. For example, seekTo will take you to a given point in the video. So if you want to go back to 1:01 in the video every ten seconds then you can use setInterval:

setInterval(function () { ytplayer.seekTo(61, true); }, 10000);

A tricky JavaScript closure problem

programming 21 November 2012

Say you have ten images on a page, with IDs img0 to img9. You’d like the number of the image to pop up when you click on one. You might be tempted to write the following JQuery code:

for(var i=0; i<10; i++) {
    $("#img" + i).click(
        function () { alert(i); }
    );
}

The event handlers will successfully bind to every image’s onClick event. You may be surprised, however, to find that when you click on any of the images, 10 always pops up! You can try it for yourself at this jsfiddle.

The problem, of course, is that a reference to the i object is being stored in the click handler closure, rather than the actual value of i. Since there’s only one counter object, every single click handler will refer to the same object, which has the value 10 by the time the user gets a chance to trigger the handler.

Here’s a workaround:

for(var i=0; i<10; i++) {
    (function (i) {
        $("#img" + i).click(
            function () { alert(i); }
        );
    })(i);
}

So what happened? Lest you think that the extra execution context has something to do with it, observe that this version without a function argument doesn’t work:

for(var i=0; i<10; i++) {
    (function () {
        $("#img" + i).click(
            function () { alert(i); }
        );
    })();
}

This demonstrates that the function argument preserves the passed value. Indeed, primitives are copied by value in function calls:

function toFive(in) {
	in = 5;
}
var a = 4;
toFive(a);
a == 4 // true

What about the case where we’re dealing with real objects? Here’s an alternative example, which toggles each image to a different image on click. This version doesn’t work (the last image is always toggled):

for(var i=0; i<5; i++) {
    var toggler = $("<img/>", { "src": "http://www.famfamfam.com/lab/icons/silk/icons/cross.png" });
    toggler.click(function () { toggler.attr("src", "http://www.famfamfam.com/lab/icons/silk/icons/tick.png"); });
    $("#container").append(toggler);
}

First of all, it’s important to note that variable and function declarations are hoisted to the top of their scope, so the above code is equivalent to:

var toggler;
for(var i=0; i<5; i++) {
    toggler = $("<img/>", { "src": "http://www.famfamfam.com/lab/icons/silk/icons/cross.png" });
    toggler.click(function () { toggler.attr("src", "http://www.famfamfam.com/lab/icons/silk/icons/tick.png"); });
    $("#container").append(toggler);
}

When you assign a new <img> to toggler, the reference is updated to point to the new object. And it’s the reference, not the value, which is bound into the click closure. So the same reference is being updated over and over, and the same reference is being bound into the click closure each time. If we want to fix this problem, we can create a new reference each time by using a self-executing function declaration like before:

for(var i=0; i<5; i++) {
    var toggler = $("<img/>", { "src": "http://www.famfamfam.com/lab/icons/silk/icons/cross.png" });
    (function (t) {
        t.click(function () { t.attr("src", "http://www.famfamfam.com/lab/icons/silk/icons/tick.png"); });
        $("#container").append(t);
    })(toggler);
}

Counter-Strike: Source ladder climbing

gaming 24 August 2012

I have been playing Counter-Strike: Source off and on since its release in late 2004. Gameplay largely consists of playing the same short scenarios over and over against different opponents. Over the course of hundreds of hours of gameplay, everything from tiny obstructions in the game levels to the feel of the recoil of each weapon is inevitably memorized and incorporated into players’ muscle memory. Players continually search out better tactics, tune their game client configurations, and generally try to develop a better feel for the Source engine.

I say all of that in the hope that with the above introduction, the next sentence won’t seem overly bizarre: I’ve been wondering for years about the most efficient way to climb a ladder.

Typically to climb a ladder in a first-person shooter, the player (1) walks forward into the ladder while looking up. But what happens if you (2) back into the ladder while looking down? What happens if you (3) strafe sideways into a ladder while facing off to the side? What happens if you (4) face 45 degrees to the right of the ladder and then walk diagonally forward and left? In the case of the Source engine, 2 produces the same upward movement as 1, 3 produces no movement, and - I found - 4 produces up to 142% of the upward movement of 1 and 2 depending on where you’re looking vertically.

To get exact times for each possibility, I created this test map (screenshot) with the Source SDK. The idea was to climb the ladders with each technique, record the climbs, and examine the video to get the exact time for each climb.

A screenshot of the Hammer editor.

Unfortunately, the second variable in play - the vertical angle that the player is facing when they climb the ladder- has a huge influence on the speed of the climb. What I really want is to rank the times using the optimal vertical angle for each technique. It would be extremely difficult to determine the optimal angle and control it experimentally, so I cheated!

Because of the game’s physics model, if the player gets up to speed and reaches the top of the ladder, then he or she will sail upward a short distance past the top before falling back down. By trial and error, I determined that it’s impossible to clear more than 53 units using techniques 1 and 2, and it’s imposible to clear more than 105 units using technique 4. Those maximum distances can only be cleared at very close to top speed. So I jump around trying to find the optimal vertical angle which will clear the first height at the bottom of the track. Then I let go of the mouse and record a climb the rest of the way up at top speed!

Here are some recordings of the forward and diagonal methods. It takes about a minute to find the exact angle where it works, but I cut that part out.

The final results: technique 1 and its variant 2 climb at about 281 ups (units per second), and technique 3 and its variants climb at about 399 ups. That’s 42% faster!

A Fibonacci mnemonic

math 24 May 2012

The Fibonacci sequence is:

Each term is the sum of the previous two terms in the sequence. Terms in the Fibonacci sequence are pretty easy to spot. An interesting property of this sequence is that it works as a mnemonic for converting miles to kilometers. For example, 21 is followed by 34 in the Fibonacci sequence, and 21 miles is about 34 kilometers. Likewise, 34 is followed by 55 in the Fibonacci sequence, and 34 miles is about 55 kilometers.

Why does this work? The short answer is that the Fibonacci numbers grow with , and is approximately the conversion constant from miles to kilometers. More exactly,

The value of is about 1.62, and 1 mile is about 1.61 kilometers. So successive terms in the Fibonacci sequence are approximately converting miles to kilometers! And, of course, to convert in the other direction you simply look at predecessive terms.

A couple of techniques are useful for when the number you want to convert isn’t exactly a Fibonacci number. If you want to convert 17 miles to kilometers, you could look at the conversions for Fibonacci numbers 13 and 21 and try to interpolate the answer. However, since 34 is a Fibonacci number you can get a much better answer by converting 34 miles to 55 kilometers and dividing by 2.

You could also change the initial conditions of the recurrence. A Fibonacci sequence with general starting conditions is called a Lucas sequence. Because when solving a linear homogeneous recurrence relation the starting conditions don’t affect the relation’s characteristic equation, a Lucas sequence also grows with , and the mnemonic applies. So you have more data points to work with if you also memorize, for example, the sequence:

For more mathematical coincidences, see the Wikipedia article.

The pipe optimization problem

puzzle 03 February 2012

GitHub provides a great service called GitHub pages, which allows you to host static web sites from GitHub servers by simply pushing a repository containing the content. GitHub founder Tom Preston-Werner wrote a fantastic blog platform called Jekyll to fit this hosting model. Blog authors can write their posts in Markdown and Jekyll will render the posts to HTML and generate an entire site structure of static pages suitable for hosting with GitHub Pages. It makes sense as an architecture- if not for user comments there would be no reason at all for having a whole scripting lanugage and database engine behind an otherwise static blog. Of course you’ve probably guessed that this post is published through that system. The complete source code and some comments about setting up your own blog are available here.

Besides playing with GitHub, I’ve also been working on my reading list over the break. Other than fiction, I’ve been reading through some textbooks which I have been fortunate enough to recieve for free thanks to financial aid. One of these books is Introduction to Algorithms (in my classes we used Manber and Kleinberg & Tardos instead), which I have discovered has some excellent exercises- perfect little puzzlers for a blog format! Today’s puzzle is based on exercise 9.3-9 in the 3rd edition.

The problem

A number of well pumps have been built in arbitrary positions throughout a region. An east-west pipeline is to be built through the area. Connections will run north-south from each pump to the nearest point on the main pipeline. Your task is to decide where to place the pipeline so that the total length of connections that need to be laid is minimized. An example region map is below; click the image to expand it.

An overhead map showing four pump stations. A pipe runs east-west through the center of the area. Shorter pipes running north-south connect each pump station to its closest point on the main east-west pipe.

The example above is, in fact, a solution- you cannot find a better place to put the east-west pipeline. So how do you find an optimal position in general, given the coordinates of each pump?

You might be tempted to suggest that the pipeline be placed along the mean y-coordinate of all of the pump stations. It seems to be clear that the pipeline should be laid roughly through the center of the constellation of pumps, since we’re trying to minimize the distance to each pump. This geometrical intuition turns out to be wrong in rather the same way that our as-the-crow-flies pathfinding intuition is wrong in cities- the unusual way of accounting for distance foils the obvious solution. I hope that examining an example of using the mean will convince you that the mean doesn’t work; click the image to expand it.

An overhead map showing five pump stations. A pipe runs east-west through approximately the mean of the y-coordinates of the pumps. Shorter pipes running north-south connect each pump station to its closest point on the main east-west pipe.

The correct answer is to use the median of the y-coordinates. The easiest way to see why this works is by considering the case where there are an odd number of pumps, for example 5. The median, then, is the latitude line through the third pump sorted by y-coordinate. Say we move the pipeline from the median to just one meter north of the median. Then the lengths of two vertical connectors (to pumps 4 and 5) will decrease by one meter, and the lengths of three vertical connectors (to pumps 1, 2, and 3) will increase by one meter. In sum, the total length of pipe will increase. The same thing will happen if you move the pipeline just one meter south.

If we have an even number of pumps, say 6, the solution is that the pipeline can go anywhere vertically between pumps 3 and 4. It should be clear that you can move the pipeline up and down within that range without changing the overall total length, because three vertical connectors increase and three decrease in lockstep. It’s only when you move outside of that range that an asymmetry appears.