So the very reason for google’s voice attractiveness (existence?), to save me the pain of having to update people with new phone numbers, appears to have backfired gloriously.

So up first, my current job. As you may or may not know, I work at a startup face recognition company in Pittsburgh. Our decision to relocate was largely for personal reasons, and choosing to leave my job wasn’t easy. It’s an awesome place to work. If you are interested, we are still hiring.

Interviewing

The job market in California seems quite good for software engineers right now. If you are thinking about heading west, I would wager a guess that now is a great time to do it. The whole process was extremely quick (once I was in contact with a recruiter). I ended up with a handful of offers from several really awesome places (names ranging from the biggest, to awesome little places you’ve only maybe heard of).  Having spent quite a bit of time the last 5 years being the interviewer, it was quite enlightening to be on the other side of it, for once. To be sure, there’s another blog post hiding behind that last sentence.

Though the vast majority of my interviews ended up with offers, it wasn’t all good news. I actually got phone-screened by one startup company. I have tons of opinions about the quality of my interviewers throughout this process (and it’s not all good, by any means), but I can’t blame that phone screener. I bumblefucked my way through a fairly easy question (I was unprepared, more on that in a bit) and knew I was blowing it. My wife tried to make me feel better after the call but I told her, having done a ton phone screens myself, that was a definite ‘no’. In fact, if he wanted to interview me after that phone screen, I’d have questioned his whole interview philosophy to begin with! There’s probably another blog post hiding there, too.

In the end, the blown phone screen was a nice wake-up call that I needed to do some more review. I did, and the rest of my interviews went extremely well. Had that phone screen been later in the process, I’m certain it would have turned out much better for me, but c’est la vie.

Facebook

In the end, the decision to choose Facebook was fairly difficult (and somewhat personal) because I had such a fantastic group of offers. All of them had huge upsides, and the thought of saying “no” to any one elicited this “are you crazy?” feeling in me. The reasons Facebook stood out, for me, was because 1) they have tons of the types of problems I want to learn about, and solve, 2) they are one of the few places in the world where you can learn about things at that scale, and 3) over the next few years, Facebook is almost certainly going to be a fascinating place to be.

This post was mainly an update to anyone who frequently reads. In the next few posts, I’ll go back to the more general style, probably talking a bit more about the interview and the interviewing process. I feel like I could write a book, at this point.

For this example, consider a very large list of strings (and their lengths) that we need to persist to disk. Or, a very large array of these:

typedef struct {
  char *data;
  int len;
} data_t;

To make the problem non-trivial, we will consider the case of different length strings (in my tests I was using a million strings around 150 bytes in length — plus or minus a few to keep them from all being the same size).

Let’s get started

Here is a naive read/write for this data structure:

void naive_write(char* filename, data_t* data, int n)
{
  FILE *f;
  int i;
  f = fopen (filename, "wb" );
  fwrite(&n, sizeof(n), 1, f);
  for (i=0;i<n;i++)
  {
    fwrite(&data[i].len, sizeof(data[i].len), 1, f);
    fwrite(data[i].data, sizeof(char), data[i].len, f);
  }
  fclose(f);
}

data_t* naive_read(char* filename)
{
  data_t* answer;
  FILE *f;
  int i, n;
  f = fopen (filename, "rb");
  fread(&n, sizeof(n), 1, f);
  answer = malloc(n * sizeof(data_t));
  for (i=0;i<n;i++)
  {
    fread(&answer[i].len, sizeof(answer[i].len), 1, f);
    answer[i].data = malloc(sizeof(char) * answer[i].len);
    fread(answer[i].data, sizeof(char), answer[i].len, f);
  }
  return answer;
}

We first write the number of strings, and then for each string we write its length followed by the string data. When reading, we read the number of strings (and malloc the array of strings) and then for each string we read its length (to malloc the string data itself) and then read the string. This implementation does many mallocs() and it does many freads(). It is, consequently, fairly slow.

With this data format on disk, though, this would be difficult to (easily) optimize much more. So, let’s change the layout.

A better file format

void flat_write(char* filename, data_t* data, int n)
{
  FILE *f;
  int i;
  f = fopen (filename, "wb" );
  fwrite(&n, sizeof(n), 1, f);
  for (i=0;i<n;i++)
    fwrite(&data[i].len, sizeof(data[i].len), 1, f);

  for (i=0;i<n;i++)
    fwrite(data[i].data, sizeof(char), data[i].len, f);

  fclose(f);
}

We made a very minor change to how we write the data structure to disk. This time, we put all of the lengths up front, and then all of the strings after that. This is going to allow us two rather large simplifications: 1) we can malloc() once for all of the data strings, 2) we can read them all with a single fread(). This is a pretty big change because it effectively removes all malloc() pressure and puts everything into fread(). The read function does, though, become slightly more complicated:

data_t* onecopy_read(char* filename)
{
  data_t* answer;
  FILE *f;
  int i, n, total;

  f = fopen (filename, "rb");
  fread(&n, sizeof(n), 1, f);
  answer = malloc(n * sizeof(data_t));

  total = 0;
  for (i=0;i<n;i++)
  {
    fread(&answer[i].len, sizeof(answer[i].len), 1, f);
    total += answer[i].len;
  }

  answer[0].data = malloc(sizeof(char)*total);
  fread(answer[0].data, sizeof(char), total, f);  /* one giant fread */

   /* set all the ptrs */
  total=0;
  for (i=0;i<n;i++)
  {
    answer[i].data = answer[0].data + sizeof(char)*total;
    total += answer[i].len;
  }

  return answer;
}

This is a decent optimization but not ideal. fread, still, involves a copy (copying from disk into our program’s address space). The only way around this problem is to not use fread.

Towards zero-copy

Using the exact same file, we can open it using mmap() (windows users see: MappedViewOfFile). This maps the file directly into our address space without having to do any copying whatsoever. We can then just setup all the data pointers to point to the memory mapped file, and we’ve initialized our data structure with zero copies.

data_t* zerocopy_read(char* filename)
{
  data_t* answer;
  int f;
  int i, n, total;
  char *data_ptr;
  int* hdr_ptr;
  struct stat sb;

  f = open (filename, O_RDONLY);
  fstat(f, &sb);
  hdr_ptr = mmap(0, sb.st_size, PROT_READ, MAP_PRIVATE, f, 0);

  n = *hdr_ptr++;
  answer = malloc(n*sizeof(data_t));

  for (i=0;i<n;i++)
    answer[i].len = *hdr_ptr++;

  data_ptr = (char*) hdr_ptr;

  total=0;
  for (i=0;i<n;i++)
  {
    answer[i].data = data_ptr + sizeof(char)*total;
    total += answer[i].len;
  }

  return answer;
}

Timings

So the moral of the story, then, is how much faster are the various versions. Here’s some timings:

(for num_strings=1,000,000 and str_len= ~150 bytes)
naive_read time: 0.373289
1copy_read time: 0.202408
0copy_read time: 0.011233

It’s important to understand what we are actually measuring here. I ran this test on Linux (Windows isn’t much different) which has a file cache. The actual disk wasn’t ever really involved in this program or these timings. We are really testing the summed speed of our processing, malloc() (in the first case), fread(), and the kernel’s handling of cached files. (note: if you modified this program to only read the files, and then reboot your machine to clear the file-cache, the first run would be much slower as the file was read in from disk and cached).

Benefits

Having these large static data structures persist using memory mapped files has some rather significant advantages beyond just initializing extremely fast. We’ve shifted the entire burden of managing this memory onto the operating system. If multiple processes are being run, this memory will be shared amongst them. This is not true of the fread() solution. The OS’s file cache will effectively keep the file in memory and ready to go whenever it’s been recently run. If there are portions of your data you aren’t using (in face recognition imagine a scenario where you only do face detection), the rest will never get loaded (or will eventually be swapped out). And last, but not least, the flattening process puts all of the bits contiguous in memory (compare with the naive approach), allowing for the OS to handle the pages of data much more efficiently.

I need people to follow as well, so if you read this site, you should send me your twitter name so I can follow you. You can do this in comments, in email, or, if you are feeling brave, on twitter. That last one will presume I can figure out how to “receive” such messages.

I did tons of work on my sites this weekend, so I’m not really writing a serious post. I upgraded the server (so if you see any badness, please let me know). I also switched on google ads, not because I think you guys will click on any ads, but because I wanted to play around with adsense and learn a bit about it.

Back to normal posting next week.

UPDATE: Just to make this explicitly clear: I did not write this program. The fourth sentence makes this fairly clear, but some comments indicate that some people are a bit lazy . I also added a video of the rush to the bottom.

I’ve been on a bit of starcraft kick recently (see my replay aggregator: replayspider). I also work in computer vision, and general AI has always been an interest (see this post on “evolving” faces). Sometimes strange interests collide. Over on a forum called teamliquid, a user by the name of Lomilar posted a fairly long thread about a program he had written that optimized build orders for the zerg race in starcraft. He eventually cleaned up his code and posted the code to googlecode. The program is called EvolutionChamber (a clever name, as it’s the name of one of the buildings in the game), and it uses genetic algorithms to find build orders.

This I had to see.

A quick Starcraft 2 primer: setting up the rules

Since this is primarily a programming blog, I’m going to assume you know a fair bit about video games. Feel free to skip this section if  you know anything about starcraft 2, in particular. Essentially, SC2 is a real-time strategy game that starts you with a simple base, some workers, and some resources, and asks you to put those workers to work collecting resources that you can use to build things (including other workers), eventually building up an army and killing your opponent. A build order refers to the exact opening steps you take early in the game that best supports the strategy you are trying to conduct. These early games are all about balancing spending money on your economic foundation (making more workers), making units (rush!), or building new buildings or getting new upgrades (tech!).

Build orders generally only cover the very early game because once you’ve scouted the enemy, you have to begin to react to what he’s doing and modifying it as you go. In other words, and a perfect aphorism, no battle plan survives first contact with the enemy. In this way, build orders in real-time strategy are very much akin to openings in chess. They set up the soul of the entire game about to be played, and some players prefer to force certain types of games, depending on what kind of opening they choose to do.

One of the reasons build-order optimization is so important is that you can discover openings that “hard-counter” other openings. If I can get an army of N size into your base when you do opening X, you will always lose.

Enough with the abstract, here’s what you need to know:

1. The program in question optimizes Zerg build orders (which is one race in starcraft), this is a rather significant choice because the mechanics of the zerg race are arguably the most difficult to manage (esp. for build order optimization).
2. Of most interest are “rush” build orders. This means “how quickly can I get N of this type of unit?”.
3. There are two primary resources that workers collect in starcraft: gas and minerals.
4. Zerg also have a third de factor resource: larva. Larva are used to create ALL zerg units, including workers.  So long as you have less than three,  they regenerate at a fixed rate (note: this means any time spent at three larva delays all future larva production — very bad).
5. Most units require some building to be constructed in order to be “unlocked” (and many of these buildings require others as prerequisites – this is the so-called tech tree)
6. Creating a building causes you to lose the worker who creates it (so the longer you can wait, the more resources that worker can collect before building the building)

These “rules” provide for an extremely complicated search space to find optimal build orders. Essentially, you want to make the exact number of workers you need as quickly as possible (and then no more). Losing a worker when you make a building, and delaying all future larva when at three larva make the dynamics extremely complicated.

How EvolutionChamber works

At its core, the program is a genetic algorithm. For those of you who don’t know, a genetic algorithm is a type of optimization algorithm that tries to find optimal solutions using a method analogous to biologic evolution (to be specific: descent with modification & natural selection). Put simply, you take a “population” of initial build orders, evaluate them for fitness, and modify the population according to each element’s fitness. In other words, have the most successful reproduce.

The program’s input is simply the desired game state. In practice, this means “make N units” to determine some rush build order (but it also allows for other types of builds, like make N workers with some defensive structures and a small army). Here are some of the highlights:

1. It’s written in Java using JGAP.
2. A ‘chromosome’, in this case, is an array of ‘actions’ that can be done in game. (e.g, 1) Build a drone. 2) Build a drone. 3) Build a spawning pool. 4) Build an overlord. And so on.)
3. Invalid actions (ie, trying to build a unit you cannot build because you do not have the tech necessary) are ignored (this allows for “junk dna”).
4. An action that can’t be done YET (not enough minerals!) causes the simulation to wait until it can be done.
5. It uses some fairly standard mutation types (deletion, insertion, and one strange one called “overlording” — heh)
6. It uses the “many villages” approach where there are several separate populations evolving independently.
7. Populations that are deemed to be stagnant are annihilated and replaced by a variant of the most successful.
8. The fitness function is really a measure of distance from the “desired” state and the current state (this is measured by the difference in resources required to get there), taking into account the time required (less time is always better).

The 7-roach rush

For the starcraft nerds among you, here’s one of the very first builds constructed by the program:

10 extractor-trick to 11
11 overlord
11 spawning pool
15 extractor
16 queen (stop drones here)
18 overlord
18 roach warren
17 overlord (yes, two)
spawn-larva on queen when she pops
roach x7

This is a fairly fascinating build order in a number of respects.

First, from a starcraft perspective: it is incredibly strong. To be clear, I am certain virtually anyone who practiced this build and went onto the ladder and used it in every game would very easily rise to diamond level (currently the highest league). The seven roaches at that time in the game will destroy all but the most well-executed counter-builds. It caused an almost immediete stir on the starcraft forums, and had one player proclaiming that an all-in variant (“all-in” coming from poker and to mean that you win or lose right now, in this case it means attacking with all your workers as well as your army) was completely unstoppable in a certain matchup.

Second, as far as I know, this build was “discovered” by the program (or at least, it’s never been well known). There is a similar build that’s been well known called the 5-roach-rush (the 5-roach-rush comes later, and is a bit more economical). When comparing the two, the 5RR has certain situational advantages, but the 7RR build, above, has two staggeringly obvious advantages: 1) you get two more roaches, 2) you get them almost 45 seconds sooner. I’m not 100% certain this build was “discovered” by the program, but I do know it’s not been extremely popular or considered standard play so my guess is that it’s not been studied in too much detail.

The most interesting part of this build, however, is how counter-intuitive it is. It violates several well-known (and well-adhered-to) heuristics used by Starcraft players when creating builds. Some of this may be lost on you non-starcraft players, but I’ll do my best to explain.

Extractor trick.

The extractor trick is using a drone to build an extractor (remember this removes the drone), then build a replacement drone, then cancel the extractor, giving you the original drone back — this allows you to build one more worker than your supply would allow. The extractor trick, as used above, has been tested and seen to be economically inferior to a more standard play of buying an overlord on 9 supply. The extractor trick + very early spawning pool do some economic damage and induce a small larva delay, so they are almost never seen. In this case, however, the extractor trick + early pool end up speeding up the entire tech path (this is the primary reason why the 7RR produces roaches much sooner than the 5RR).

Double Overlord at 18/17.

First, a quick discussion about supply. Each unit you create costs supply. So long as you have supply, you can make units. Most RTS games have a similar concept. Overlords, for the zerg, are the unit that provides this supply. So for zerg, you have to spend 100 minerals to unlock additional supply. In general, it  is considered “optimal” for you to have just enough supply to not be supply-blocked. It’s generally considered wasteful to buy supply when you don’t need it (since you could spend that money, instead, on units or workers now, and buy the supply later, when you need it).

In almost all cases, it would be extremely wasteful to purchase supply twice in a row. I’m not sure any starcraft player would look at such a build and consider that a good idea. In this case though, it ends up  working out so perfectly that you’d actually have to try it any other way to understand how and why. Because your desired goal is 7 roaches, you will need to construct 2 more overlords at some point, but doing them both so early is certainly surprising. During that particular period of the build (around 18 supply), you end up waiting for your roach warren to finish so you can begin creating roaches.  This causes you to max out on larva, stopping regeneration. By moving the second overlord so far up into the build, this larva ends up being “free” — you’d lose it anyway because the regeneration would stop. So the only penalty to making the second overlord early is minerals, and during this portion of the build, you are not mineral-bound. The net result is that moving that overlord so far up into the build costs nothing and frees up larva regeneration to produce quicker roaches.

This is the type of non-obvious optimization that genetic algorithms excel at.

As for the 7-roach-rush, I’m certain if you are playing starcraft2, you’ll see this build quite a bit. As for whatever hidden and game-breaking builds remain undiscovered, that remains to be seen.

UPDATE:

Here’s a video of someone doing the ‘all-in’ variant of this build against a real player:

Thanks to rockpapershotgun.com for the writeup and pointing me to this video.

2. Negative Information Theory

It’s a little appreciated fact that being frequently wrong is (adjusted for a prioris) as difficult as being frequently right. For work, I once wrote a pixel classifier that, given an eye region of an image, would identify red-eye pixels. My classifier worked exactly as I intended it (ie, it was debugged) and yet it was wrong about 80% of the time. It was simultaneously a terrible and terribly effective algorithm.

3. A Trick for Sales Projections

For internal use, halve it. For external use, double it. Twice.

4. The web is such a friggin hack

Imagine if I told you we were going to build a system to run our company. We’d use a domain specific language for the data-store, a second language for the back-end code which is run on a server written in a third language, a fourth xml-based approach to explain the documents, a fifth DSL to explain the styling of said document, a sixth language to write the front-end code, and a seventh “language” that is actually a library that makes the sixth language usable for our purposes. Would anyone think I was crazy?

Not that the web can easily be “fixed” but the existence of things like “reset.css” or tables vs css are not just excellent examples of the huge pile of sand people have built castles on, but more precisely, are a testament to a slaughtered paradigm.

5. The “one-page resume is a myth” myth

I’ve looked at so many resumes. I try not to be biased but I’ll be honest. Long resumes are not as good as focused resumes. There isn’t some rule where over a certain length goes into the trash, it’s just that everyone gets about the same amount of time, and if yours is long, I’m more likely to miss something good.

6. All my best work is done in the shower…

Programming work, that is. This is why I never feel guilty if I leave 15 minutes early. I traded 15 terribly unproductive minutes for 15 terribly productive ones.