Brian Gordon blog

MagicalTux's EVE Online pathfinder

programming 05 March 2014

The personal blog of Mark Karpeles, aka MagicalTux, CEO of the recently-bankrupt Bitcoin exchange Mt. Gox, received attention on Hacker News recently. Given that Gox’s spectacular $473 million downfall was supposedly caused by a bug in Karpeles’s custom implementation of the Bitcoin protocol, people were understandably interested in checking the quality of his public source code.

What we saw was not reassuring. In one post, Karpeles describes a custom implementation of SSH2 which he wrote for production use at his web hosting company.

With PHP I could write a fully working SSH server in only 3 days. … My goal when writing this was to provide a replacement for the FTP protocol for the customers of my hosting service.

As I was missing some functions to properly handle the initial Diffie-Hellman key exchange (and later to implement publickey authentication) I had to re-implement those in PHP.

This is horrifying to see from the guy who wrote the server which once handled 70 percent of all Bitcoin trades. If I had seen this post before Mt. Gox’s failure, I would never have deposited my Bitcoin with them. The SSH server source code has since been taken down, but one HN user remembers it:

The code for the sshd does not seem to be there anymore, but from memory: it did not check if the number sent by Bob was 0, 1, or any any other groups that would make it easy solve the discrete logarithm problem. I don’t think it bothered to check the primes either. [1] I think there was also something wrong with the signature checking (padding not checked maybe?).

Altogether it seemed like you could easily MITM connections made to the server, but I don’t think I ever tried. It was a perfect example–to me at least–of why you should not spend a trivial amount of time reading about crypto on Wikipedia and then writing crypto code.

I absolutely agree. The main lesson that you should take away from the crypto class is that you should be afraid of rolling your own crypto code. There are a thousand ways to screw up, and it only takes one mistake for your cryptosystem to fall apart. The recent Apple and GnuTLS vulns show that even the serious players get this wrong.

So best practices were apparently not followed at Mt. Gox. In fact, later it was alleged that developers at Mt. Gox would push changes directly to production, and didn’t even use version control for the site’s source code.

Another of his blog posts is about a tool which he wrote - in PHP of course - to compute routes between star systems in the MMORPG EVE Online. In EVE, solar systems are connected to each other with portals called Stargates. The result is a big graph. Savvy players will try to take the shortest possible path to get from point A to point B by using a shortest-path algorithm to automate navigation.

Systems map in EVE Online

I thought I’d hop on the bandwagon by criticizing his EVE pathfinder. Although I could nitpick on matters of style, I’d rather focus on the core- that is, the all-pairs shortest path solver which is the basis of his algorithm. The general idea is to generate an index which contains, for each system, the next hop to take in order to reach any given system. This uses O(n^2) space but allows efficient pathfinding between any two arbitrary systems in the universe. All of this is perfectly fine so far. The problem is how he goes about constructing this index.

Based on my reading of his code, this appears to be his algorithm:

  1. Inform each system how to reach its adjacent systems.
  2. From each system s, collect the best known paths to systems 1 hop away and advertise them to s’s adjacent systems.
  3. From each system s, collect the best known paths to systems 2 hops away and advertise them to s’s adjacent systems.
  4. From each system s, collect the best known paths to systems 3 hops away and advertise them to s’s adjacent systems.
  5. From each system s, collect the best known paths to systems 4 hops away and advertise them to s’s adjacent systems.

This continues for 256 steps, by which point MagicalTux hopes all systems have been informed of the shortest path to all other systems. Judging by a cusory search of the EVE forums, this appears to be a valid assumption.

Although his solution seems asymptotically optimal (maybe off by a factor of the number of edges?), in real life it will perform poorly compared to a real all-pairs shortest path algorithm. I thought it would be interesting to see how badly I could beat his code’s performance. MagicalTux claims that it takes about 3 hours to construct the index using his PHP code. I’m going to see how much faster I can do it, by doing these things differently:

I downloaded the jump connection data helpfully provided by MagicalTux - the official data comes in an unusable binary MSSQL format - and put it in a CSV file for easy parsing.

My complete EVE pathfinder implementation can be found here. It doesn’t require any extra space (asymptotically) to construct the index, which is nice. This is the core of the code where almost 100% of the running time is spent:

// Floyd's algorithm
for(uint32_t k=0; k<NUM_SYSTEMS; k++) {
    #pragma omp parallel for shared(k, cost, next) schedule(dynamic)
    for(uint32_t i=0; i<NUM_SYSTEMS; i++) {
        if(i == k) {
            continue;
        }
        for(uint32_t j=0; j<NUM_SYSTEMS; j++) {
            uint32_t prev = cost[(NUM_SYSTEMS * i) + j];
            uint32_t candidate = cost[(NUM_SYSTEMS * i) + k] + cost[(NUM_SYSTEMS * k) + j];
            if(candidate < prev) {
                cost[(NUM_SYSTEMS * i) + j] = candidate;
                next[(NUM_SYSTEMS * i) + j] = next[(NUM_SYSTEMS * i) + k];
            }
        }
    }
}

I picked two random system IDs (30000029 and 30000050) for a pathfinding demo. My test program constructed the all-pairs index and then used it to find the shortest path between the two systems. You can see the output of the test below:

brian@mint ~/eve $ ./eve 
Indexing... done. Elapsed time 38.99 seconds.
Calculating the quickest route from 30000029 to 30000050... done.
Built a 14 hop route in 0.002 ms.

Note that, indeed, the shortest route between those two systems according to DOTLAN is 14 hops! And the index was built in less than 40 seconds- about 0.4% of the time that it took MagicalTux’s PHP version.

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

riddles 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);
}