ICFP 09, Post Mortem, Part One
"It would be pointless to observe that the finest volume of all the many hexagons that I myself administer is titled Combed Thunder, while another is titled The Plaster Cramp, and another Axaxaxas mlö."
- "The Library of Babel" Jorge Luis Borges.
Well, as of the point when they froze the scoreboard, my solo effort was ranked in the 24th place with 2763.6783 points. The following is the first half of my post mortem, describing the basics and the lower level parts of my code. I intend to post a second half tomorrow, describing my solutions to the specific problems.
The Basics
I wrote all my code in C++, of course. Don't get me wrong: I definitely enjoy messing around with other program languages and other programming paradigms. It's a fun challenge to work under interesting constraints. But when it comes to actually getting stuff done, C++ is the pragmatic choice for me. I don't want a programming language's ideology getting in my way.
Build-wise, CMake is my preference. It's designed for C/C++ and it's sane but powerful. In this case, the program was simple enough that I just swiped the usual opening lines from another project. I could have simply made a makefile directly, but 4 lines or so of CMake did the job for me.
I also swiped a vector class from one of my projects and hacked it down to being only a 2D vector class. I know some folks dislike operator overloading, but its a godsend for something like vector arithmetic.
The VM
The VM was actually the first place where I started hacking on the code. Given the detailed specification of it, it seemed like low hanging fruit. In a fairly short period of time, I had a VM class whose constructor would read in a file and unpack the instructions. (Swiping some of my portable endian conversion code from a library in another project helped with this and saved some time.) Read and write methods for the ports were fairly straightforward.
I ended up using a simple looped switch-dispatch interpreter for the execution of the VM. Easy to write and nicely portable. At one point, I made a start at changing to indirect threading using gcc's computed goto extension to see if I could get a speed boost. But I changed my mind about this: if I was going to go non-portable to speed it up, why not go all out? I could either use LLVM (which I've employing lately for research purposes) to JIT the VM code. Or, I could just translate the code to C++, invoke g++ to compile it into a shared library, and then dlopen() that to load it in. Either would have been messier and more time consuming to implement, so I defered doing adopting those approaches until I'd actually seen that the VM was the bottleneck. It never was.
Orbital Mechanics
I actually decided to tackle the third problem set, Eccentric Meet & Greet, first. I figured if I could get my program to handle those, I should be able to handle any of the others as variations.
I spent a good bit of time on Friday night studying orbital mechanics and getting confused by things like the relationship between mean anomoly, true anomoly, and eccentric anomoly and how to calculate them from the state vectors that we had. But even if I had all the orbital elements, it wasn't clear to me how to use them to efficiently get to a moving target.
Late on Friday night, I came across something called Lambert's problem. One formulation of the problem is, given two radii from a mass center, and the angle between them (i.e., two satelite positions in polar coordinates relative to the Earth), calculate the instantaneous velocity required to get from one position to the other in a given amount of time.
I found a very nice paper on the topic by R. H. Gooding which included working Fortran-77 code for a numeric solver for this problem. I ended Friday night by porting this to C++ code. To avoid mistakes, I converted it as directly as possible, leaving it as very un-idiomatic C++ code. It takes the parameters of the formulation that I described and gives the absolute instantaneous transverse and radial velocities needed. It actually returns up to two solutions.
On Saturday, I wrote two wrappers around this code. The first would take the current position and velocity of the chaser and target satelites, respectively, as well as an initial and terminal time for the maneuver. It projected out the position of both of satelites to the initial time step, and then continued projecting the position of the target to the terminal time step. These in hand, it converted these positions to polar coordinates, called the port of Gooding's code, and converted the results back to offset velocities in the problem coordinate system. (Returning whichever solution required the smallest delta-v.)
The second wrapper employed the first quite heavily. Since the most fuel-efficient initial and terminal times are unknowns, this routine attempts to solve for them. I used the classic downhill simplex method to try to solve for these values, taking the fuel estimate of the first wrapper as the cost function to minimize. It's not perfect, but it's easy to implement and seemed to work well in practice.
- "The Library of Babel" Jorge Luis Borges.
Well, as of the point when they froze the scoreboard, my solo effort was ranked in the 24th place with 2763.6783 points. The following is the first half of my post mortem, describing the basics and the lower level parts of my code. I intend to post a second half tomorrow, describing my solutions to the specific problems.
The Basics
I wrote all my code in C++, of course. Don't get me wrong: I definitely enjoy messing around with other program languages and other programming paradigms. It's a fun challenge to work under interesting constraints. But when it comes to actually getting stuff done, C++ is the pragmatic choice for me. I don't want a programming language's ideology getting in my way.
Build-wise, CMake is my preference. It's designed for C/C++ and it's sane but powerful. In this case, the program was simple enough that I just swiped the usual opening lines from another project. I could have simply made a makefile directly, but 4 lines or so of CMake did the job for me.
I also swiped a vector class from one of my projects and hacked it down to being only a 2D vector class. I know some folks dislike operator overloading, but its a godsend for something like vector arithmetic.
The VM
The VM was actually the first place where I started hacking on the code. Given the detailed specification of it, it seemed like low hanging fruit. In a fairly short period of time, I had a VM class whose constructor would read in a file and unpack the instructions. (Swiping some of my portable endian conversion code from a library in another project helped with this and saved some time.) Read and write methods for the ports were fairly straightforward.
I ended up using a simple looped switch-dispatch interpreter for the execution of the VM. Easy to write and nicely portable. At one point, I made a start at changing to indirect threading using gcc's computed goto extension to see if I could get a speed boost. But I changed my mind about this: if I was going to go non-portable to speed it up, why not go all out? I could either use LLVM (which I've employing lately for research purposes) to JIT the VM code. Or, I could just translate the code to C++, invoke g++ to compile it into a shared library, and then dlopen() that to load it in. Either would have been messier and more time consuming to implement, so I defered doing adopting those approaches until I'd actually seen that the VM was the bottleneck. It never was.
Orbital Mechanics
I actually decided to tackle the third problem set, Eccentric Meet & Greet, first. I figured if I could get my program to handle those, I should be able to handle any of the others as variations.
I spent a good bit of time on Friday night studying orbital mechanics and getting confused by things like the relationship between mean anomoly, true anomoly, and eccentric anomoly and how to calculate them from the state vectors that we had. But even if I had all the orbital elements, it wasn't clear to me how to use them to efficiently get to a moving target.
Late on Friday night, I came across something called Lambert's problem. One formulation of the problem is, given two radii from a mass center, and the angle between them (i.e., two satelite positions in polar coordinates relative to the Earth), calculate the instantaneous velocity required to get from one position to the other in a given amount of time.
I found a very nice paper on the topic by R. H. Gooding which included working Fortran-77 code for a numeric solver for this problem. I ended Friday night by porting this to C++ code. To avoid mistakes, I converted it as directly as possible, leaving it as very un-idiomatic C++ code. It takes the parameters of the formulation that I described and gives the absolute instantaneous transverse and radial velocities needed. It actually returns up to two solutions.
On Saturday, I wrote two wrappers around this code. The first would take the current position and velocity of the chaser and target satelites, respectively, as well as an initial and terminal time for the maneuver. It projected out the position of both of satelites to the initial time step, and then continued projecting the position of the target to the terminal time step. These in hand, it converted these positions to polar coordinates, called the port of Gooding's code, and converted the results back to offset velocities in the problem coordinate system. (Returning whichever solution required the smallest delta-v.)
The second wrapper employed the first quite heavily. Since the most fuel-efficient initial and terminal times are unknowns, this routine attempts to solve for them. I used the classic downhill simplex method to try to solve for these values, taking the fuel estimate of the first wrapper as the cost function to minimize. It's not perfect, but it's easy to implement and seemed to work well in practice.