Things Learned, Enjoyed

  1. Do not by mints or gum in metal or plastic containers if you intend to put them in a bag. They may look cute, but the constant clanking is beyond irritating, especially in the realm of the big, grey cubicles where no one breathes.
  2. I wasn’t aware of this, but furniture shopping is a lot like buying a car. To put it lightly, it is a very high-stress situation, and that’s not where I like buying things. Ikea is not like that at all, in fact, it’s very close to being the type that I consider perfect for a store. This is why I shop there, and why I continue shopping there. It’s very low stress.
  3. I used to consider Perl an old-man’s language. Ignoring the fact that it came out the year before I was born, I’ve discovered this summer, that it indeed is. That doesn’t mean that I don’t enjoy it. Its ability to touch and process text quickly is so amazing, I’ll probably be turning to it again in the future. And there’s the fact that I rewrote all of my blog’s backup scripts in it.
  4. I won’t be trying to reinvent the building-software wheel again. Build systems are very hard to get right, especially when you’re not sure what you need to support. Let’s go shopping; may I suggest SCons?
  5. (500) Days of summer was a really good movie. There’s a scene with Tom laying in his bed, and outside its raining. There’s those super ugly, low power sodium lights outside, that I usually hate. With the rain and the windows, the light comes through in a great Old Hollywood sort of way. I consider that few seconds one of my favorite scenes in all of my movie-going history.
  6. I can go to grad-school, and it’s going to be amazing.

Starting Fresh

Last night marked the first complete wipe and reinstall of Mac OS X I’ve ever performed because I had to. I was that irritated with it. Everything seems to be work better now- knock on wood.

The Way Up

I figure a small Casper update is in order. Since we last spoke, I’ve been spending a lot of time bringing performance up on the demo fib program. Let’s start with the last example, fib(20), which executed in a little over 600 milliseconds and took a whopping 70 MB of memory to run over the course of the program lifetime. To execute fib(20), Casper run 229990 instructions, and I wasn’t sure how good or bad that number was. It was bad.

Today Casper runs the same code with only 182640 instructions executed. This is largely due to the fact that my instruction emitter for if statements was woefully inefficient. I spent a lot of time in the bytecode emitter making sure to optimize all outputs; after all, the fastest Casper will ever run is when it’s not running anything. Fixing up the bytecode output dropped execution time roughly in half, but didn’t help the memory usage. I fixed that by opting out of stack copying the running code blocks in and out of the execution stack for every function call and return. This cut the total memory usage down to something a little under 10 MB. It’s an impressive reduction, but we can do better in the future. This optimization saved us a little over 150 milliseconds in execution time. Other optimizations (e.g., direct dispatch when using GCC, switching to a frame model for call and returns to avoid copying the whole block, and a few new data structures) bring us down around 60 milliseconds, leaving us around a total of 90 milliseconds of execution time. Overall, it’s a huge win, but we can do better.

Perl, for sake of argument, performs the same computation in just under 30 milliseconds. Perl is fast, but arguably not the fastest language out there and I think getting closer to where Perl is performing is a good goal. I’m sure the bytecode emitter is running some interesting optimizations on the recursive algorithm, and I’d like to emulate some of those. Recursive calls (i.e., function calls and returns) are the most expensive type of operation you can make in Casper right now, so optimizing them away would be an obvious win. I haven’t had a ton of time to work, and I probably won’t for a while; I’m ending my internship and moving at the end of the week. Progress in my mind, though, is quite good.

Isn’t it Neat?

I’ve just accomplished something of a personal milestone: Casper is capable of running a program that generates a Fibonacci sequence. Correctly. Let me take a moment to dance.

I had to work through a number of problems to get to this stage. I had to implement new syntax for function calls, for personal taste as much as technical requirement of the stack-based interpreter. If/then/else blocks are no longer generated as separate blocks, but instead generated linearly, with the add benefit of skipping the repeated condition test if true. I fixed a couple of bugs that were related to storing variables, which is required now that functions can have parameters. All this led up to the exciting moment where fib actually ran, correctly!

It’s not all love and roses though. Casper right now is quite a bit slower than every other interpreted language I’ve tested. It executes about 230,000 instructions to generate the answer for fib(20), but I’m not sure how good or bad that number is. At the moment, I can really only see only place where instructions could easily be cut down. An unconditional jump would be useful when generating if/then/else blocks. It gets worse. Casper takes around 70 MB of memory (amazingly none of that is leaked) to execute fib(20). Now I haven’t done any comparisons yet, but that number is unacceptable for me regardless. I think both or memory and speed issues will be greatly reduced when I figure out a better way to pass variables into functions; there’s a lot of unnecessary copying going on in there. We’ll see. You can track my progress through commits (I make a lot of them) at github.

For those of you who came here for the show:

# fib.cas
def fib(x)
	if x < 3 then
		fib(x: x-1) + fib(x: x-2)

fib(x: 20)

(instructions omitted)
Instructions executed: 229990
Yielding stack...
0: 6765