Queens, growing pains

Part II. Blind alleys

Not everything goes smoothly in the passage of life. One of the numerous false starts I ran into stemmed in a false assumption. First off, my program is written in Java.¹ I had reached the performance level of the current record holder, which was also written in Java, and I was ready to move on. Beating a Java program in terms of speed is kind of like winning the Special Olympics. I mean, it's kind of an accomplishment, but you know you're not facing off against the best the world has to offer. My point is that no matter what Sun tries to tell you, Java is slow. Slower than the guy who offed himself in Full Metal Jacket. So in order to face off against the fastest program in the world, my next target would have to be the C program that is now the second runner-up for the Queens record.²

Which as easier said than done. Where the Java world-record holder took 70 seconds to solve the 16-queens problem, the C program took 8 seconds.³ That's almost ten times faster. Ain't that a peach? Or maybe "peach" isn't the right word.

I decided to try something completely new with my approach, and here was my reasoning for this experiment. In C, recursion is about ten times slower than iteration.⁴ Which is why that fast runner-up program used iteration. And why I decided to use it too. Here's my code. Be warned, it's ugly. I'll explain the ugliness further down.

  private static void findSolutions(
      int index,
      int row, 
      long down,
      long ld,
      long rd,
      int maxRowIndex,
      SolutionResult res) {
    
    int startIndex = index;
    int startRow = row;
    int[] indexStack = new int[maxRowIndex];
    long mask;
    long tries = res.tries;
    long solutionCount = res.solutionCount;
    
    // Main (critical) loop.
    main_loop:
    for (;;) {
      mask = index;
      if ((down & mask) == 0L &&
          (ld & (mask << row)) == 0L &&
          (rd & (mask << (32 - row))) == 0L) {
        tries += 1;
        if (row == maxRowIndex) {
          solutionCount += 1;
          // This optimization disables rectangular boards.
          index = 1; // Triggers exit condition below.
        } else {
          down |= mask;
          ld |= mask << row;
          rd |= mask << (32 - row);
          indexStack[row] = index;
          ++row;
          index = startIndex;
          continue;
        }
      }
      while (index == 1) {
        if (row == startRow) {
          break main_loop;
        }
        --row;
        index = indexStack[row];
        mask = index;
        down &= ~mask;
        ld &= ~(mask << row);
        rd &= ~(mask << (32 - row));
      }
      index >>= 1;
    } // End critical for loop
    
    res.tries = tries;
    res.solutionCount = solutionCount;
  }

Why is it ugly? Well, the problem we're trying to solve is inherently recursive. Transforming it into an iterative solution forced us to make certain concessions. These concessions are twofold. First, size: there's a lot more code. More code means more chance for bugs and should always be avoided if possible. Secondly, we have to maintain a custom stack in an array since we can't take advantage of the function stack.⁵ These two problems jam together to make this snippet awkward.

So right now, I should take a moment to explain exactly why I chose to try something ugly and awkward. It's the mentality that the ends justify the means. Just ask the Chinese: what's the childhood of one little girl compared to winning a gold medal in gymnastics? Well worth it, they'll tell you. In terms of cars, this solution is totally the pimped-out Civic that can do 300 HP. It may look like ass, but it goes fast. And that's worth it, right?

Right, if it went fast. But unfortunately, it didn't. What? That's kind of like going out with a girl who's both ugly and dumb. There's just no point. A total waste of effort. This solution wound up taking over 80 seconds. The assumption that an iterative solution would be fast in Java just because it's fast in C was wrong.

The only thing we can do is learn from our mistake. This thing was supposed to save our necks, but instead it totally bombed. How could that have happened? The mystery deepens.

The answer lies in the loops.⁶ Loops in Java are very slow. Kind of like the rest of Java, but inordinately so. The presence of a loop seems to incur much more overhead than a method invocation. That's an important clue as to where we should go next. Loops are slow, so if we want to go fast, we should avoid loops as much as possible.

This experiment failed, but from this failure we have obtained a critical hint about our goal. I kind of liken it to dating. Sometimes it's only through trials and failures that we learn what doesn't work. And the lesson is best learned through experience. It can be painful, even heartbreaking, to do your best and not be good enough. But instead of giving up and succumbing to the life of a spinster, we can take away nuggets of wisdom that leave us better equipped in the future. And I think that's the lesson learned here: our failures are much more valuable than our successes. Maybe I'm making too much a deal out of something so small, but then again programming makes me philosophize.

Footnotes

(1) Java 1.5 on Mac OS X, client VM.

(2) Solution for the 24 x 24 case by Jeff Somers. His site has several links to other Queens sites. And yes, this program is significantly faster than the current world record holder.

(3) Somers' site has some timings that give 23 seconds for the solution of the 16 x 16 case. These were taken on an older machine. All of my timings are taken on the same computer, a 2.6GHz Mac Pro. I compiled Somers' code with gcc 4.0 with -O3 optimization (the fastest). The resulting program solved the 16 x 16 case in 8 seconds.

(4) Recursion and iteration are two differnt ways of approaching a problem that can be broken down into smaller problems. For a classic example of recursion, see the Towers of Hanoi problem, a personal favorite interview question of mine. Iteration is somewhat simpler. If you've ever taken a programming class, a simple "for" loop is an example of iteration. It allows you to step sequentially through a range of values.
    Although both approaches are powerful tools for the programmer, there are certain classes of problems that lend themselves naturally to one approach over the other. Binary search, for example, can be implemented using either method but most computer science courses teach it using recursion because it's easier to understand that way.

(5) When one function calls another, the data from the new function is pushed onto a part of memory called the function stack or call stack. Think of it like putting a new, blank piece of paper on top of a pile when you start something new. Switching to iteration is like trying to use a whole bunch of Post-Its stuck all over your desk instead of a neat stack of paper.

(6) I determined this by using Apple's Shark profiling tool. It's free with OS X's developer tools and easily beats other profiling software that costs hundreds more. If you develop in Java, Shark alone is worth switching your environment to Mac OS X. It's really that good. And believe me, when a cynic like me says that, it really means something.
    Incidentally, all of my speed analyses in the Queens project are done using Shark.

Queens, finding dry land

Sometimes I think it's a curse to be in high-tech. Not because of the job itself but because it basically ruins movies for me. Any movie that has anything to do with computers. Any time a movie throws some hackery on the screen, it winds up looking incredibly amateurish. Imagine a medical show throwing around dialog about freezing peoples' heads. Utterly ridiculous. And I bet I know why this technobabble is wildly inaccurate: it's boring. Code is boring. And not just kind of boring, it's amazingly boring. Public television-boring.

Which is why I gotta warn you: these Queens entries will have a substantial amount of code. But don't worry, I'll be your tour guide. And all the code will be in snippets and clearly marked, so you can gawk at them like you're looking at animals in a zoo. Or inmates in an insane asylum. And we're walking down a corridor, lit only by bare light bulbs, that leads to Dr. Lecter himself.

But don't worry. I'll make it interesting. When I have a pen and paper in my hands, I can make anything interesting.

Part I. Growing pains, or discovery

Software is really malleable. It doesn't exist anywhere except in the minds of its creators. There's nothing substantial about it. That's both a blessing and a curse, though, as many companies are guilty of releasing things that are half-baked. Kind of like the time I got an egg tart from Pacific Mall that was half-cooked. I tried to return it but only got half my money back. But I digest...

Sorry, hungry. Anyways, the best part of software is how easily you can change your mind about things. There are no parts to assemble, no chemicals to dispose. But all that flexibility comes at a cost. You're basically afloat in a vast ocean of possibilities on a tiny little raft. It's night and you're navigating using a deft combination of your wits and the stars. And each trick you know is another constellation you can use for guidance.

I've solved a few problems like this before, so I knew a few tricks. I essentially took what I knew and applied it cookie-cutter to this problem. The solution was, shall we say, competent but uninspired. In case you're curious:

  private static long findSolutions(
      int index,
      int row, 
      long down,
      long ld,
      long rd) {
    
    int startIndex = index;
    long solutions = 0;
    long mask = 0;
    
    // Main (critical) loop.
    for (;; index >>= 1) {
      mask = index;
      if ((down & mask) == 0L &&
          (ld & (mask << row)) == 0L &&
          (rd & (mask << (32 - row))) == 0L) {
        if (row != 0) {
          solutions += findSolutions(startIndex, row - 1, 
              down | mask,
              ld | mask << row,
              rd | mask << (32 - row));
        } else {
          // This optimization disables rectangular boards.
          return 1L;
        }
      }
      if (index == 1) {
        return solutions;
      }
    } // End critical for loop
    /* NOT REACHED */
  } // end of function

If you're not a programmer, that was kind of a Keanu-"whoa" moment. What does any of it mean? Doesn't matter. All you really need to know is that it's basically the standard, plain-vanilla version of the solution. No one would fault you for a solution like this, but you probably wouldn't garnish much praise either.¹

The only thing really noticeable about this solution is how normal it is. It sets everything up, then goes off into a loop. Ya gotta loop, cuz it's, you know, how you get stuff done on computers. Whenever you use a computer it's essentially in a giant loop waiting for you to do stuff. After the loop you get your "if" statements that check to see if we have a solution. Read one of my other entries for the wacky wigged-out fun that is "if" statements. Then the solution calls itself. Not like a schizophrenic with two cell phones; this kind of "calling yourself" actually makes sense. It's called recursion, and in order to define recursion, we must first define recursion. (If you got that, send me a resume.)

For the programming-minded, I have some basic optimizations in place. I'm using longs as bit fields² and looping backwards to avoid a comparison to a variable through each iteration of the loop.³ Real Mickey Mouse stuff. In fact, in any other project, I probably wouldn't suggest looking into such trivial matters. But in this case, trying to optimize this loop was kind of like squeezing blood from an onion.

So there you go. At this point, we're like a kid out of high school. We know what we're doing and where we want to go. We can accomplish things, but we're neither noteworthy nor especially fast. But we're past the first hurdle.

Timing: For my baseline, I'm using the current Java world-record holder.⁴ It solves the 16-queen problem⁵ in 70 seconds on my computer. This version of my solver does it in 70.48. I actually timed it. Yes, I have no life. But I'm just about as fast as a world-record holder, and that's a good start.

Footnotes.

(1) Actually, my first attempt separated the representation of the chessboard into a separate class. Well, since method invocations on classes are much slower than accessing variables, that approach was initially much slower, taking over 180 seconds to solve the 16 x 16 chessboard case. That was embarrassingly slow to mention, except as footnote material.

(2) This is as opposed to using boolean arrays. Array accesses in Java are automatically bounds-checked. This means that each time an array access occurs, the VM checks to see if the index is in bounds. This incurs a significant overhead.

(3) This is a really esoteric form of optimization, and I'd only use in cases where there's a very frequently-called loop and precious little room to improve elsewhere. Such as a tight loop like this. It essentially involves looping backwards from N to 0 instead of forwards from 0 to N in cases where you don't know what N is beforehand. The normal way of iterating forwards requires a comparison between two variables (the loop index and N), which requires two loads from main memory. Looping backwards requires only a comparison between a variable and a constant (the index and 0), which only requires one load from main memory. Loads from main memory are slow and best avoided if possible.

(4) Inria's ProActive solver. Info and source code available at http://proactive.inria.fr/nqueen.htm.

(5) This is the problem of finding the total number of solutions on a 16 x 16 chessboard. Incidentally, there are 14,772,512. Timing was done on a single computer.

Queens, at first glance

Sometimes obsession is a good thing. Without the ability to focus our thoughts we'd be nowhere today. Without a Dutchman obsessed with pornography we'd have no auto-focusing lenses on our cameras. Without a Japanese comic book artist steadfastly refusing to take her psychotic medication, we wouldn't have Sailor Moon. And finally, without Microsoft's obsession with copying every innovative high-tech company in the business, we wouldn't have the Xbox, Live Search, Zune, or a bunch of other products that no one uses. Cheap shot, I know.

It was obsession that led me to the subject matter at hand. A while ago I was called to do some interviewing. For this interview I had to think of a question. I was kind of lacking creativity that day so I decided to look at the Eight Queens problem. My introduction to this problem was way back in the ninth grade playing 7th Guest. It's a pretty easy problem to understand, and actually pretty fun to solve by hand. The goal for my interview question would be, obviously, to find a solution by computer. At that time, I decided that if I was going to ask this question, I better be able to solve it myself! So I took a quick lunch break to do so. It wasn't too hard—a fun diversion if you're programming-minded—and my own initial solution was pretty straightforward.

Soon, I wanted to make sure that my program was correct. I designed it to spit out all the solutions that it found and checked the first few by hand. They all looked fine. Then I saw the total number of solutions: on an 8 by 8 chessboard, my program claimed that there were 92.¹ So I cross-checked this against a known list and hey, whaddayaknowit, it matched. To make super-extra sure, I checked the number against some different sizes of chessboards. The numbers were weird, but they matched. Good, I think, it works.

The part of me that went through combinatorics (man that's a lot of links... am I really that hard to understand?) decided to think about how these numbers grow and how to count the number of solutions without actually going through the messy legwork of finding them all.² Well, it turns out that no one knows of a better way. In order to find out that there are 2 quadrillion-and-whatever solutions for a 25 by 25 board, you actually need to find each and every one of them. Not only that, you also need to find all the possibilities that could have led to solutions but didn't. That's just about 500 bajillion others.³

Twenty-five, by the way... that's the biggest chessboard anyone has ever solved. It's a world record, as far as I know. So that's when I wonder... what would be involved in conquering lucky number 26? So then I see the web page of the current record holder. The results? Over a period of six months, they used the combined resources of 260 machines. That was for a 25 by 25 board.

For 26, it's estimated that there are ten times as many solutions and that the computation will take ten times as long. That means that we either spend five years waiting for this thing to finish with 260 machines, or we somehow recruit 2600 suckers for a period of six months. I don't know about you, but I have better things to do for five years, and I don't even know 200 suckers, let alone 2000.

So what's a programmer to do? World record, interesting challenge, epic computation. I'm sold. Put it on my Visa. I'll pay in installments. I'm gonna take my shot at finding the twenty-something-quadrillion magic number.

But wait, you say, hold it a sec. What about the kabillion-jillion computations and the mind-numbing years it will take to solve this? You really don't know me, do you? Insert smilie here. I'm going to work smarter, not harder. That means, if I have ten times as much work to do, using the same amount of resources as you have, then I've got to pump out my solutions ten times faster than you. But that's okay. Won't be the first time I've done something like this.

And I'm going to need help. Lots of help.

(1) This count is for unique solutions. There are actually 12 solutions unique up to symmetry. Two solutions are considered the same up to symmertry if you can rotate the chessboard 90 degrees in either direction or flip it horizontally or vertically to transform one solution into the other. I'm only interested in counting solutions without symmetry.

(2) The best conjecture right now is that the number c(n) of solutions for an n by n chessboard is asymptotic to n! / (2.54^n). That means that c(26) is about 10 times greater than c(25). So the number of solutions we're expecting for c(26) is in the range of 22 quadrillion, or 22,000,000,000,000,000, give or take a few hundred trillion.

(3) My current algorithm appears to make around 38 times more steps than the total number of solutions. For example, on a 16 by 16 board, there are 14,772,512 solutions. The algorithm takes 570,595,151 steps to find all these solutions, giving a factor of almost 38. This trend appears to continue. I haven't found any references about calculating the number of guesses taken by various solutions. This also means that the solution to 26 will require about 836 quadrillion steps to make sure we've found them all. Now you see why we've no time to dawdle?

References.

ProActive NQueens World Record [http://proactive.inria.fr/nqueens25.htm]. Current world record holder. Used a distributed computing solution to solve the 25 by 25 case. The figures for the amount of computation required is taken from their web site. Their computation was later repeated and confirmed independently by a team in Taiwan.

Online Encyclopedia of Integer Sequences [http://www.research.att.com/~njas/sequences/A000170]. All known values of this sequence are here. So are links to existing record holders and the conjecture for the asymptotic growth of the solution count.

Wikipedia [http://en.wikipedia.org/wiki/Eight_queens]. Solution counts and a list of all solutions for an 8 by 8 board up to symmetry. Also includes a number of interesting links and variations of the puzzle. Note that the section "The eight queens puzzle as an exercise in algorithm design" seems to (confusingly) discuss two forms of the puzzle without explicitly stating which form is under discussion. The form I propose to undertake counts the total number of solutions for a given board size. The latter half of that Wikipedia section talks about finding a single solution on a large board, which is a much simpler problem.

Like a rat in a cage

Tonight we went to Endfest, which featured music to go deaf by. Don't get me wrong, the bands were amazing, but now I'm left with a blaring fire alarm in my head. After surviving mosh pits, bouncers, and drunken brawls, our reward was a surprisingly good Paramore (I might even download their music), the me-too Social Distortion, the we're-too-good-to-say-hello-Seattle Smashing Pumpkins (who rocked anyways), and finally MXPX at some local dive.

Paramore

Social D

Pumpkins

MXPX

At MXPX. I'm slightly tenderized by the mosh pit.

So now the only thing I have to do is wash the smell of pot and tobacco out of my clothes.

Endfest was awesome!

September rain

Every so often we find ourselves at a crossroad. When we realize that among the vast ocean of our dreams, the best we can hope for is to scoop a precious handful to be with us the rest of our lives. And it seems, for me at least, that each scoop is smaller and smaller, containing only the most urgent and precious of ambitions. That's not to say that we lose our dreams throughout the course of our lives. On the contrary—if we didn't let go of some of our goals in life then none of them would come true. Instead, I see it as a refinement. When a diamond is cut, it increases in value and decreases in quantity, and this process of sifting through our ambitions in life is similar. It is only by consciously choosing what to focus on, and realizing what we give up in the decision, that we truly discover what matters to us most.

Have you met my friend Billy? Billy's a great guy, really smart, really cool, but he doesn't get things done. Sure, he's a Microsoft, but that's not his ultimate goal in life. He has a multitude of projects: media browsers, building a motorcycle game, yoga. His variety of interest is great, boggling even. He'd be the start of a true renaissance man—if he ever followed through. I've seen his repertoire. It feels like reading through a thousand post-it notes, and scrawled on the back of each one is an excuse:

"I need to find more people to collaborate with."
"I don't want to start building something now and end up using obsolete technology by the time I finish it."
"I think it's a great idea, but I just haven't found the audience for it."

Not each one is an excuse in the pejorative sense. Some of these projects were refined (to use my own terminology) for obvious reasons: the dot-com bust. Some startup stole his idea. But others do seem like they might fly, and yet poor Billy holds them back. And every time Billy tells me about one of these things, I have to resist the urge to kick him in the butt. It's almost like he's afraid that he'll actually succeed.

Billy's an extreme. He's a shotgun artist. He throws a thousand blind darts and hopes that they stick. He doesn't see that sometimes, you have to stop waiting for that ideal point in your life to finally pick up and do that thing you always wanted to do, go that place you always wanted to go, or talk to that girl you always had a crush on. I see in this idealism a lot of naivete. And eventually his dreams lose their romantic energy and they peter out. And at the end of the day, always, gargantuan plans, always. But nothing accomplished. It turns out that Billy doesn't refine. He just gets bored.

Meet my other friend, Walt. Walt is my age (whatever that means to you). He works at a government job where he can't get fired and he lives with his parents. He sits in his room and downloads gigabytes and gigabytes of anime. I have the feeling that, if you looked really hard, you could find some stains in his carpet that are ten years old. Or twenty. I don't have much to say about Walt, other than his goals in life amount to nothing more than to inherit the house that he lives in. I've never heard him talk about his goals. I don't think he has any. This paragraph is probably the most that anyone will ever write about him. And he's perfectly happy with that.

As for me, I'm trying to stay somewhere in the reality between these two. I can see elements of both of these people in my own psyche, and that's scary. In order not to turn into either one, something's gotta give. It's difficult to live with too many hopes and aspirations; it's impossible to live with too few. The more thought I pour into what I want to do with my life that's truly mine, I come up with one answer. It's an answer that I've often visited, but only now do I make the commitment.

That long-winded intro is basically padding for my announcement.

I'm writing a book. That's it. I said it. Now it's out there, and I'm accountable. I might post some snippets on this blog from time to time. And if you care, if you really do care, then you'll bug me about it incessantly, to make sure I don't give up. Believe me, if you do, you'll earn a special place in my heart (and potentially dust jacket).

Any questions?

I felt the sudden urge to snap a few pictures tonight. Also being in my pyjamas, I thought I'd limit the pictures to my own apartment. So this is my place.

This is my place on drugs.*

This is my place on better drugs.*

All three pictures came from the same camera in the same position and from the same source. The only difference is the presence (or absence) of a few minute corrections in luminosity, white point, and gamma. If a few fractions of a percent can make such a huge difference in our perception of reality in something as simple as a photograph, what does that say about the trillions of connections and chemical bridges in our brains?

Reality is malleable! Don't accept what you see, hear, or feel. You could be a victim of your own senses.

Next time you're mad, count to ten. Next time you're depressed, call up a friend who makes you laugh. Then you'll start making your own reality.

* Not condoning drug use.

Nananananananana Fishing

Genesis went to Tanwax for fishing this year. I took the opportunity to practice some HDR shots. I got up at 6 AM for the photo below. And I also caught three fish, which quite surprised me. But not as much as Uncle Ed's delicious campsite 炒飯. Who knew that a wok would be so useful in the great outdoors?

Tomorrow: Vancouver!

Why programming sucks

This is a screenshot of something hideously funny we did to Razvan (not his real name) during fourth year. This is how geeks get their kicks. And now that it's about five years later, the statute of limitations has expired so I can freely admit to having done this. One day Razvan asks me for a hashtable implementation. Sure, I said. Have this hashtable, I said. While I was preparing this hashtable for Razvan, Brad (a friend in CS with a decent sense of humor) and I hit upon a brilliant idea. This picture is kind of blurry but it shows what we did. Look very closely at the second line. Can you make it out? It says:

#define if while

This clandestine directive, inserted into the code we gave Razvan, was the source (pun not intended) of a huge amount of grief. Programmers will immediately recognize the nightmare world into which we have plunged this unwitting little hashtable. But the rest of you must be wondering, what does this mean?

Well, let's start with the basics of programming. Flow control is how you get the computer to do things conditionally. This is what the if keyword does. Think of it like this.

if (raining) {
  bring(umbrella);
}

Unless you're abysmally retarded you probably got the gist of that. Loops are similar to flow control and work like this.

while (money > 0) {
  spend(money);
}

Easy, right? Now the #define keyword. This is the same as doing a find-and-replace in a word processor. Check it out, y'all. If I put the lines

#define if while
if (raining) {
  bring(umbrella);
}

in a program, the #define line tells the computer, "any time you see 'if,' replace it with a 'while.' " And the computer will do that because computers are stupid. So what you've essentially written above is

while (raining) {
  bring(umbrella);
}

which is utter nonsense: you're going to keep bringing more and more umbrellas with you until die of umbrella poisoning. You're just going to keep stocking up on umbrellas until it stops raining and accomplish nothing else.

Well basically, this kind of logical fallacy is exactly what we introduced in Razvan's shiny new hashtable. Any time the program we gave him tried to do an if statement, it would spin off into an infinite loop that would just keep chewing up processor power until you had to restart Windows 2000. And all because of that one line. If you were to remove that one line, it would work perfectly. Absolutely perfectly. And that is why it was so funny. It's also incredibly hard to detect, because when you debug you never expect anyone to put in a bug intentionally. Poor Razvan.

Of course, this implementation, as it is, doesn't work completely. Anything with an else clause won't compile (although it will throw up some very confusing error messages). You'd have to add the line

#define else if(0)

or something in order to cover all your bases and get all programs to compile. Or you could do

#define if(x) if(!(x))

(the expansion is not recursive). I'll leave it up to you to determine what kind of havoc that wreaks. Non-programmers:

!x

means “not x,” or the boolean negation of x.

This is just one example of things geeks do instead of talking to girls.

HDR and Mount Rainier

I'm really tired from hiking this weekend guys, so those photos will have to wait until tomorrow. Sorry!

In the meantime, check out these HDR pics from our trip. HDR stand for high dynamic range, and it's a technique that creates some pretty surreal-looking photographs. I tried it for the first time at Rainier and got mixed results. Partly due to my own unfamiliarity with the technique and partly because I didn't have a tripod. Nevertheless, here are the best HDR pics from that weekend!

Sunshine Visitor Center

Shadow Lake

I promise to have the rest of the photos up soon. Boy am I tired.

EDIT: The photos are up. See below. And I'm still tired.

Mount Rainier

Old school

One of the most amazing Zangief players you'll ever meet.

Reflection

Summer was such a busy season! Taking the time to recap everything would require many blog posts. So instead I'll squeeze everything into a photoessay so as to keep you entertained with thousands of virtual words. Don't worry, I'll still have some real words so that you're not too entertained.

Vancouver: The final frontier. Despite Adrian's insistence on showing me the intersection of Main and Hastings, Vancouver is a great, relaxing city with a lot of natural beauty, when it's sunny. It's also full of the tastiest Chinese food (and girls!) I've ever seen.

San Francisco: Under the guise of an Apple conference, I went in June. What a refreshing perspective it gave me! Must have been the sea breeze.

Calgary: Despite the, um, colorful wildlife (see picture), it was a fun, quaint town with a lot of natural beauty. Good friends, good food, great steak!

Around Washington: The pic is from Snoquamie Falls. There are so many places to explore. This was one of the first things we did. And the most unexpected part: fresh oysters, $10 for two dozen!

ECC/Genesis: A walk on the spiritual side of life. I felt like we learned a lot about God and faith and gained a deeper understanding of Christianity. Or maybe I just had a lot to learn.

Safeco Field: What summer would be complete without seeing the Jays lose? At least the hot dogs were good.

Boeing: The launch of the 787, which was apparently completely hollow inside. Thanks to Mark for the invitation. I managed to get some great shots because they mistook me for a press photographer and waved me to the front of the line. Asian guy with a camera? Let him through!

Ontario: We went to the beach, hung out, played some Wii. Just like old times. What can I say? Absence really does make the heart go yonder.

Skydiving: Yeah, I know I just posted about it, but I jumped out of a plane so I think I deserve to post about it twice!

And just last weekend, Tiger Mountain. Not as steep or as long as Banff. When we got to the top, the birds ate out of our hands like a nerdy white guy picking up in Tokyo.

Flying without a plane

I only have one thing to say about it: if you haven't been skydiving, you suck!

Picures available for downloading here.

Toronto video up!

I know you can't really make things out but hey, it's the only slideshow that isn't as boring as hanging around Microsoft people.* Originals here and here.

* You know we're kidding. Google loves ya!

馬と鹿の物語

Background for my non-Japanese-speaking friends: Lately I've been taking a Japanese course which involves the occasional essay. I've decided to post these essays here for everyone's enjoyment and ridicule. The first one, called "The tale of the horse and deer," is an exploration into the origins of the word "baka," which any greasy anime fan will tell you is Japanese for "foolish." The story itself is actually rooted in ancient Chinese history, and comes from 司馬遷's famous 史記.

「バカ」は、日本語でよく使われている言葉の一つであり、漢字では「馬鹿」と書く。それは何故だろうか。僕は北京で発見した「日本語の不思議な常識」という本を読んで、面白い話を見つけ出した。この話には中国の歴史にでてくる有名な人物が登場する。

皆様は中国を統一した秦の始皇帝をご存知でしょう。司馬遷の『史記』によると、始皇帝が亡くなったとき、中東府の長官の趙高と丞相の李斯が共謀した。この共謀者は初生の王子の扶蘇を自殺させて弟の胡亥を跡継ぎにするために始皇帝の遺書を偽造した。それだけではなく、二世皇帝にも混乱を起こすことも企てた。

しかし、この謀議を実行する前に皇帝の群臣が反対するかどうかを諮る必要があった。

共謀者の二人が皇帝の前に鹿を連れてきて、「これは馬です」と宣言した。二世皇帝が笑い出し、「馬と鹿の区別すらできないのか。なんで鹿を馬と言うんだ」と答えた。

丞相が周りの群臣を問いただした。ある者が正直に「鹿です」と答え、ある者が黙り、大勢の者が「馬に間違えない」と賛成した。周囲の群臣の反応を見て、趙高は共謀者の計画を進めた。正直に鹿を鹿と言った群臣達は全員処刑してしまったそうだ。

この話は「正直者は馬鹿を見る」の由来のように思える。これを短くして「馬鹿」になったそうだ。「馬鹿」の起源については、サンスクリット語の「愚癡（ぐち）」を表す言葉の音訳から来たという話もある。

The iPhone detail you didn't notice

So for my Canadian friends back home, who failed to live through the iPhone launch, there is an interesting detail about the phone that is not apparent at all from the webcasts or Steve's presentations. Personally I would never have thought that such an important aspect of the device would go un-noticed for so long. It seems like such a fundamental part of the design that it's hard to believe that they would gloss over it like that. And it's impossible to ignore once you actually pick up and use an iPhone. And that detail is:

The iPhone is made almost entirely out of chocolate.

Yes, the back is a delicious Swiss light metallic chocolate with an extra-dark milk chocolate plate at the bottom for the antenna. The screen has a honey glaze that gives it a shiny, reflective look. And the whole thing is powered by pure sugar. As fun as it was to play with, and as great a phone and iPod and internet device as it was, it was clear that the REAL killer feature of the iPhone was its taste. And behind it all is super-secret "melts in the mouth, not in the hand" technology licenced from Mars, Incorporated, makers of M&Ms, and the silent third partner in the Apple-AT&T-Mars triumvirate.

It was hard to find any iPhones on display in the Apple store that didn't have bite marks or that weren't half-eaten. (Eating the whole thing would set off the alarm.) Now I see why Apple was limiting patrons to two delicious iPhones apiece. Not for the sake of availability but for the sake of their customers' waistlines. Forget Verizon -- this thing is going to put Godiva out of business.

This does bring up the unbelievable fact that the iPhone will continue to operate without impairment even if 70% of it is eaten. It automatically scales the display to account for any parts bitten off by the user. Now THAT's a remarkable piece of engineering.

So go ahead my Canadian friends, make a trip south of the border and lick an iPhone. You won't believe what's in the creamery center.

Incidentally, Microsoft has stated that the next-generation Zune will be made out of dried onion meal. Ballmer asserts that by offering customers a grim, flavorless alternative to Apple's product, they will appeal to consumers who want to make "a different choice."

Ire

Q: How do you get your Apple-loving friends to envy and despise you?

A: Change your email signature to "Sent from my iPhone".

The view at night

This view is from my friends' place on the sixth floor. They face the little village that we live in. It looks every bit as spectacular in person.

San Francisco (Part 2: Nostalgic)

WWDC always drizzles out to a close. The grand halls of Moscone, which teemed with energy and possibilities at the beginning of the week, now echo vacant. The deafening hum of the air conditioning. Metallic footfalls on the escalator. Someone coughs. Even the mighty Presidio suite, once overflowing for the keynote, is full of empty seats dotted like islands with only the most determined of developers. Sunlight hangs in the air while people recline on the big leather couches out in the common room. Walking around Moscone feels like being in a house with the children gone.

Tomorrow is the last day of the conference and we are getting ready to head back to our lives. Away from this fairy-tale land where market share is meaningless and viruses are nonexistent. A veritable fruitopia that lasts for just a week. After that, back. Back to reality.

This ending, which I dramatize quite a bit, reminds me of many aspects of life. Let me tell you what I mean. This year at the conference I didn't play the ostrich and decided to meet some people. Among the folks I met were some students from my own alma mater, the University of Waterloo in Ontario. They were here on student scholarships.

It was nice meeting people who had so much to look forward to in the field of software. They still had co-op terms to look forward to. Safe, compartmentalized looks into the real world where politics don't matter and you were gone in four months. Then the slate would be wiped clean. For them, it was only the beginning. There would be many more conferences to attend, many more companies who would fly them to all sorts of places. And around every corner lurked new faces, and rays of opportunity made silhouettes from behind every door.

Again with the drama. But this is perhaps the best way I can describe the contrast. The longer you stay in software, the more colleagues you see getting out of software. Which is natural, given the odds, but the thing is that these people don't just kind of switch out. They do a full 180 (or 540, depending on how long it takes them to decide). They move as far away from programming as they can and then salt the earth so that no trees can ever sprout again. The list of professions runs long. Author. Lawyer. Teacher. Artist. Sportscaster. Gambler. Even incomprehensible dead languages. Point is, whatever they end up doing, they make it a point stay the hell away from computers. And with good reason.

Sixty hours a week. Seventy. Ninety. Sitting in front of a screen, watching their backs hump and their wrists lock up before snapping like breadsticks. Their glasses getting thicker, tummies getting bigger and everything getting greasier. There comes a point when they just say enough! and this is not the life for me!

And so they switch. They take odd jobs. They go back to school, for years more. They become interns again. Long is the path, and hard, that out of hell leads up to the light. And every one of them? Happy as a San Franciscan clam. Not a single regret. They don't miss any of it. The tedious debugging. The silent horror of undefined symbols. The purgatory at the center of the Motif event loop. They don't even miss the good parts. Being assigned a bug that only repros on an 8-core Mac Pro (because you know what you'll need to fix one of those). The silent thrill of seeing your cubic spline intersection code work for the first time. Writing your own java.awt.LayoutManager and getting your font panel to look just perfect. Leaving your competitors wondering, how did they do that?

We all teem with life at the beginning. The beginning of the week, the beginning of the conference. People so excited that they get up before 5:30 AM to line up. They talk shop the entire time with anyone in line who will listen. The four-and-a-half hours pass with conversation and laughter and speculation on what lies behind the curtain. And the students? For some of them, it's their first conference. First time in San Fran. First time out of the country. And I can't help but think about how their adventure is only beginning.

Then I look at myself. Especially at the end of the week. By then, I wax philosophical and think things like, was I ever that young? Where has my passion gone? How am I going to change the world? And I feel like Moscone. Empty. The band has played. The stage hands are slowly taking things apart. Everyone is looking for their jacket and heading for the door. This party is over.

There have been times when I look back and think about how happy my friends who switched out of computers are. And sometimes I imagine their existence sitting on a tropical island, in the shade, with some kind of sweet drink full of ice cubes in a glass dotted on the outside with beads of water. We are, all of us, victims of our own petty jealousies. The grass is always greener. The other guy's job is so much easier. How I envy their career! They get to meet new people! Or read philosophy. Or travel to China.

That's when I remember that I have a lot to be thankful for. I love being with Google, and I intend to be here for a long time. But still, I'm that much older than when I graduated. I know that the world doesn't change so easily. We don't all end up millionaires, or VPs, or CEOs. And the world, my world of possibilities, is a little bit smaller. I meet the bright-eyed youth who could be my archived double from a Time Machine backup. He has so many years on me that I'll never catch up. He's going to change the world. He's going to be different. Just watch him.

Now come the jealousy and the thoughts of straying. So many others have found happiness elsewhere that I wonder if I should consider their footsteps. But then I remember that our hearts and minds can wander, but in the end these journeys can reaffirm our original resolve. The other pasture has led me far from home, and though it may be sweet, I still have work to do back where I came from. I lift my head up and think, it's not so bad. I'm not so old. The world isn't smaller, it's just clearer. The many paths have converged into fewer. And eventually, into one.

So thanks, WWDC. You've tested me, and made me more certain of my path. I still have a world to change.

San Francisco (Part 1: Quick)

So it's time once again for Apple's WWDC, held as always in beautiful San Francisco. This is my fourth time in the city, all four times for conferences, and my third WWDC. The city is starting to feel like home. There's even a Mel's Diner nearby that I frequent.

The city itself is very warm and sunny right now. The theme this year is "seafood." I've already been up to the wharf three times this week for some truly amazing seafood. The best lesson learned from all of this? Don't wear white shirts. The pictures are in my San Francisco album.

Since I'm actually at the conference right now, it's time to sign off. More later!

By the waterfront.

Steve, up to his old tricks.

You can kind of see him. It's difficult to photograph in a Reality Distortion Field.

Pics from Calgary

Last weekend Adrian and I climbed a mountain in Banff. I was a bit worried being out of breath after the first five minutes, but it seems that it's only natural for that to happen when you come to such a high altitude. The foot of the mountain was 5200 feet above sea level, and the peak was 7400. In comparison, I'm used to... 0. We made it in 1:29, much faster than expected. But maybe that's just because Adrian promised there would be hookers there. 

On top of that (pun!), we hung out with the Kalgary Krew and had some amazing beef. Compared to the beef in Kalgary, all other beef tastes like overcooked hamburger. You'd spit it out, you would! When Adrian first started going on about the beef, I thought he was kidding. Boy was I in for a pleasant surprise. Also, being Chinese as we were, we also opted for some late night Chinese cuisine.

Oh, and the airport workers all wore cowboy hats. Seriously.

We worked hard for this spectacular view.

On top of the mountain, an instant of sunshine, in a distant valley.

Proof that we made it up!

The gang at night.

A freakish Calgarian sunset, at 10 PM!

Visit my album for more for more photos.

Welcome Lori to the fold

Just as it's bad luck to have a ship without a name, I've found it useful and creepy to name my cars. My first car, a black 2000 Acura EL, was Chloe. My second car, a 2005 grey Acura TSX, was Rachel. Most recently, during her maiden voyage to Vancouver, we christened the third car, a 2007 bronze Acura (spot the trend here?) TL. The name is Lori, short for Lorraine, as in Marty McFly's mother from Back to the Future. And I must say that the maiden voyage was very much a success! The ride was smooth and quiet, and I was able to pwn all the souped-up Civics that challenged us along the way as well as in Richmond.

Without further ado, here are the pictures that I promised so long ago.

The controversial Type-S rims aren't bad with this color.

This is before I had to put on the front license plate.
Stupid state of Washington. :)

Lori in Vancouver, the day after her maiden voyage.

A lot of pros on this car.

• Drives great.
• Very comfortable and quiet.
  
• GPS works quite well.
• Computer is faster than the one in the TSX.
• Interior controls are a lot more logical as well. Sunroof controls next to the sunroof? Who'd have thunk it?
• Much improved sound system.
  

Some quirks so far include:

• Rattling noises from the driver's side door that only the driver seems to notice.
• The steering was quite stiff when I first got the car but it's loosened up quite a bit, though I still remember the TSX being more agile. Not a big deal on the road, but the feel of the car can be quite different in an enclosed parking lot.
  
• Lack of folding rear seats mean that the car is less useful for making Ikea runs.
  
• The audio system is top-notch, but DVD audio discs (DVD-A) are few, expensive, and far between. That's not a fault of the car but a fact that I still lament.
  
• I have no clue why they still include a tape deck in this day and age. They might as well include the address for the Prussian consulate in Siam.
• The MP3 disc support doesn't support Chinese or Japanese in ID3 tags.

Yes, yes, I know. I'll quit my bitching.

Out with the old...

A while ago I went to a job fair in Boston with a few people from Waterloo. During this time we shot some footage. It has been about a year and a half, but I have finally found the time and tenacity to piece together the snippets we shot into something remotely watchable.

If you're wondering about some of the weird edits, they were to remove shots of an ex-girlfriend. This was really too bad. All the best footage featured her.

May: the flowers bloom

So it's been a while. A long while. Well, I'm not going to split hairs, so let's just jump right in to why I haven't posted for so long: I forgot the URL of my own blog. Yes, even though it's run by the company I work for and it has my name in the address, I forgot it.

Here's an idea of what I've been up to.

• Gone up to Vancouver, twice. Which helped me break in the new car. Whee!
• Met some people from Microsoft, Amazon, Boeing, and many other places. Both new friends and old.
  
• Started going to church.
• Joined a self-defense class. Yellow belt test on Friday.
• After months of inactivity, started writing a new book.

This is just a summary of everything that has happened lately. I'll get into more detail in subsequent posts. But I thought I'd let everyone know that I'm still alive.

Cheers!

New car!

I got a new car!! The 2007 Acura TL Type S. This car features a 3.5 liter, 286 horsepower engine, navigation system, some sweet quad exhaust ports, satellite XM radio, cup holders, leather seats, and Star Trek computer voice. And for those of you who remember my old car (the TSX), this new car totally kicks the old car's ass in every aspect.

After a long time debating, I figured that getting a new car was a good choice for a couple of reasons.

1. Walking is for losers.*
2. Public transit is for losers.*
3. Having a car will help me establish the all-important credit.
4. The car will keep its resale value quite well relative to others in the same segment.
5. The car cost roughly $8000 less in the US than in Canada. (Before you bring it up, yes, that takes exchange rate into account.)
6. It's going to be really funny when I show up for a road test in a brand-new Acura TL-S.
   

* Applies only to people living in Seattle and surrounding areas.

And the best part? The new car cost the same as the old car did! Take the price of this new car and convert it into Canadian, and you'll get the price of my old car in Canada. It would have been cheaper even, if those bastards had let me lease.

Wait, that reminds me. "You want to lease a car? Well, never mind the fact that you've owned one car and leased another one before. We're going to pretend that you're some kind of high school dropout with no money and no prospects and not let you lease a car. Also, never mind the fact that we actually leased you a car in Canada. Here, in America, the rules are different. First you get the sugar. Then you get the money. Then you get the lease." - Acura.

I'm sure I'll have more to say about this soon. For now I just want to get the news out!

Why credit is important

So the United States is really stupid. Wait, there's more. One of the funny things you really never stop to think about when you have it is credit. It's kind of like sex. When you have it, you take it for granted. For example, in Canada, I could sign up for any old cell phone plan within 20 minutes and get a decent phone. I could also get cable. I could also buy a car. That was relatively painless as far as large purchases go. I walked into the dealership at 7:00 and I had a car by 10:00.

Not so here. See, when you move to the US from Canada, you essentially move to a whole other empire where your history is wiped clean. This could potentially be advantageous, but only if you were screwed in Canada to begin with. Which I was not. So starting over was basically not advantageous at all. Which means that it pretty much screwed me over.

The following took place between February 20 and March 9.

"You want insurance? Well, since you don't already have insurance, we can't sell you insurance. You need to have had insurance for six consecutive months before we'll sell you insurance. Never mind the fact that we've been insuring you for seven years in Canada. Here, we just assume that you're going to forget how to drive." - Allstate.

"You want a cell phone? Well, you have no history of having had a cell phone, so we're going to have to assume that you're a bum who won't pay your bills and we'll have to charge you the bum tax up front." (Note: bum tax is $500.) - Cingular.

"You want to live here? Well, never mind that you own your own house in Canada. As far as we're concerned, you've never lived anywhere in your life. So we're going to charge you the vagrant tax." (Note: vagrant tax is $700.) - Avalon Apartments.

"You want a license? Well, since you crossed the border, we're going to assume that you forgot how to drive." (Gee, you must know the insurance people.) "Never mind the fact that you've been driving for 11 years, or that you already own a car." (More on that later.) "We're going to make you waste your time on the written test (2.5 hours) and driving test. This is because Canadians forget how to drive when they come to the US. Never mind the fact that you're allowed to drive here for 30 days legally with a Canadian license, or that you haven't had a single ticket for over 5 years." - Washington State DMV.

"You want coffee? That will be $1.49." (Okay, that one wasn't just for Canadians, but it's still damn expensive coffee.) - Starbucks.

Fortunately, as with any obstacle in this country, one can get by this problem with money. But it's a hell of a lot of money, which makes me understand why relocation bonuses exist. And thank God they do. Now that that's out of the way, here's my main news.

Time for the big move

Tomorrow I'm moving into the new apartment. Moving is one of the few things that I can do without a social security card in this country. I finally get to pick up my stuff, which has been in storage all month. It is possibly a mixed blessing. I actually moved a lot of it because I couldn't sell it before the move and "the company" is picking up the tab. I'll probably end up Craigslisting a lot of it, particularly the home theater stuff, so I don't wind up a couch potato (although I'm starting to resemble an eggplant in silhouette).