Hexar-Decimal

Internetizing My Ethernet-wired Townhouse

Sweet Panels

When I first moved into a new townhouse, one thing I was very excited about was that nearly every room in the house had a panel with not only a cable port and a phone jack, but an RJ-45 jack as well. In other words, it’s wired with Ethernet ports all over the ‘house.

So the first thing I did, naturally, after connecting my cablemodem on the main floor to my wireless router, was make sure my wireless internet was working. It was, but the signal wasn’t so great on the bottom floor, where my desktop is located. In fact it was a bit flaky, giving me a hard time connecting initially and also having random disconnects. Not so great. In order for me to get reliable internet, I’d have to either run my 50-foot ethernet cable from the main floor to the basement, or I could get these ports to work.

Maybe it will just work?

Ever optimistic, I plugged in my desktop into the wall, and then I plugged in an ethernet cable between my wireless router and the wall. Maybe there’s a switch or something somewhere! Maybe it will just work!

Well, it didn’t. My computer was complaining about a network cable being disconnected. I assured my computer that I really did connect an ethernet cable from it to the wall but it still wasn’t happy.

Internets to the rescue

I did a quick search, and I can’t remember what I searched for, but the forum responses mentioned something about opening up the patch panel in the master closet. After removing the panel with the help of my trusty screwdriver, I found this inside:

At first I was a little confused. It looked to me like all these ethernet wires were already connected in that circuit thing. But what were the ports for then? That’s when I realized, these ports are just wired up to the cables, and are not connected to each other in any way. They just happen to be in the same junction box. To connect them, I’d need my own separate switch; ideally the internet connection from the wireless router would be able to connect via the switch to all other clients and give them IP addresses and internet access. That was my theory. So I rounded up my switch and as many cables as I could find and here’s what it looked like:

The Test

Anyway, I went back down to my computer, disabled/enabled my ethernet card, and prayed for mercy (and an IP address). Sure enough, I got 192.168.34.5. Good news! Now for the real test:

It works! Yay! And just in case you were confused, here’s a diagram:

Hope this helps anyone else who found themselves in possession or rental of a home with pre-wired Ethernet ports.

Musings on PAX 2009

Having recently moved to Seattle, this year was the first time I was able to attend the Penny Arcade Expo, despite having heard quite a bit about it during my frequent trips to penny-arcade.com. Unfortunately I only managed to secure tickets for Friday and Sunday, because the 3-day and Saturday passes sold out before I finally got around to buying tickets.

Panels – Friday

Game Design 101: I attended this panel thinking it might have some insight on some basics on how to design a game that would be interesting and fun. But the panel focused more on giving advice to aspiring game designers, some discussion on the difference between game writers and designers, and anecdotes from the game designers’ careers. I was a bit disappointed with this one.

Breaking into the Game Industry the Educated Way: I really enjoyed this panel; several panelists from gaming universities and businesses offered their opinions on the value of pursuing a degree in a games program, such as the ones offered by Digipen and Guildhall SMU. For one, attending a multi-year game development program shows that the student is willing and able to make a commitment to making games, and offers the opportunity to make lots of games and develop lots of contacts. But of course you have to weigh that against the tuition and opportunity cost as well. Ultimately, the consensus opinion was that a successful applicant to the highly competitive games industry needs to demonstrate their experience with game programming with as many high-quality game projects as possible, whether created in an academic setting or on your off-hours.

Penny Arcade Q&A #1: I don’t remember too much from this Q&A panel where Gabe and Tycho fielded questions from the audience, but I do remember that I was laughing almost the entire time.

Panels – Sunday

Penny Arcade Q&A #2: Also hilarious. This was the first panel I attended on Sunday.

Retronauts – The Secret Best History of Gaming: This was a humorous and interesting panel where the members of 1Up’s Retronauts Podcast showed their favorite old-school Penny Arcade comics and how they demonstrate a historical perspective of gamer sentiment over the years, including topics such as Dreamcast and Daikatana. Very amusing.

I also missed several panels that I would have liked to see, including Wil Wheaton’s Awesome Hour, The Guild Season 2 Screening, and of course all of the panels on Saturday.

Expo Hall

It took me a while to find the expo hall, because it was so far away and hidden from the rest of PAX. However, this was definitely the most interesting way to waste time between panels and events. I got to play 20 minutes of Starcraft 2 and 10 minutes of the new WoW: Cataclysm starting zones, played a quick team battle of Global Agenda, and got lots of swag. I also watched some other players play Diablo3, and saw a demo / Q&A of the new DotA “killer”, League of Legends.

PC Freeplay

This was the other main way that I wasted time inbetween panels and events. It was strangely fun playing Team Fortress 2 and Counter-Strike: Source with some other random PAX attendees on the LAN. I also had enough time to check out the game that Tycho and Gabe produced, On The Rain Slick Precipice of Darkness. It was actually pretty fun. The free play area was sectioned off from the Bring Your Own Computer area, and during all three days there were game contests going on for various games.

Game Rooms and Console Freeplay

I was blown away by what was going on in the Console Freeplay room, where basically you get assigned a TV and a console, and can borrow games to play as if it was a library. They also had high score contests on some classic games like Mike Tyson’s Punch Out and Mega Man 2, but unfortunately I didn’t get to spend much time in there. They also had a number of game rooms for Magic the Gathering and various board games, such as Settlers of Catan, which I also missed out on.

Concerts

I missed the Friday night concert because I had some friends who were hanging out in the bar at GameWorks. I heard it was pretty good, but so is grabbing a pint with some friends.

Signatures

I waited in a strangely short line to get Jeff Lewis and Sandeep Parikh’s autographs. You know, those hilarious guys from The Guild? I also spotted a short line of people standing in front of Tycho as I was finishing up my Taco del Mar, and got him to sign my Instruction Book. He seemed like a real nice guy and I only had to wait like ten minutes.

Summary

All in all, it was a very fun event, and I only wish I had had more time and more friends who had come. Next year I will probably get my ticket much earlier and convince my friends to come with me.

Various Optimization Strategies

I’ve been a bit busy lately, and my blogging has suffered because of it. That’s really too bad, because I have a big list of topics / code that I’d like to post about, but most of them require at least a few hours of work to clean up and flesh out. It’s a bit overwhelming.

In the meantime, I wanted to do a quick post on a couple of interesting optimization strategies, especially ones I’ve come across here at Microsoft. These strategies are well-known but some are used quite often in Visual Studio to help speed up performance, so I thought I’d write about them, just for fun. Maybe you’ll learn something, or maybe you’ll already know all of these.

Copy-On-Write

Copy-on-write is an optimization strategy which delays the copying of two or more initially identical resources until a user of the resource attempts to modify it. When a resource user does attempt to modify the resource, a true private copy is performed behind the scenes and returned to the requestor. This is an optimization especially in cases where resources rarely need to be modified, but you cannot guarantee they won’t be at some point.

One example of this strategy in use is in virtual memory operating systems. Multiple copies of the same process generally have identical binary code in system memory, so the memory used by the first process is marked copy-on-write when additional instances of the process are loaded. If any of these processes do attempt to modify the memory, then the kernel detects the write and makes a transparent copy of the binary code so that the other processes are unaffected.

Copy-on-write can also be used in application code. One possible implementation could involve creating a class which wraps a property defined in a read-only data source. As long as callers ask to read the resource, you can simply return the value stored in the data source. But if a caller wants to modify the value, then the class makes a private local copy and sets a flag indicating that from then on it should return the local copy instead of the data source value.

Here’s some sample code (C++):

class StringWrapper
{
private:
    char* s;
    bool local;
public:
    StringWrapper(char* source) : local(false) { s = source; }
    char* Get() { return s; }
    void Append(char* app)
    {
        if (!local)
        {
            char* temp = new char[strlen(s) + 1];
            strcpy(temp, s);
            s = temp;
            local = true;
        }

        strcat(s, app);
    }
};

Lazy Initialization

The idea behind lazy initialization is that you should try to limit the amount of pre-processing you have to do to get your program to run, until the last possible moment. So you initialize resources the first time they are requested, and no sooner.

For example, let’s say that you have a word processing program that supports spell-checking for hundreds of languages. Each separate language can be loaded from a dictionary file into a language-specific spell-checker object, from which you can call your spell-check method. You could just load every single dictionary file from disk when your word processor loads, but that would probably take a long time, and most of the languages are unlikely to be used in a single user session. In fact, the user might not even use the spell-checker at all. A better strategy would be to wait until the user requests a spell-check, determine whether or not the current language’s dictionary has already been loaded, and load it if it hasn’t yet. Then, you can proceed with your spell-check knowing that the user only incurred the cost of loading a single language at the time that they needed it.

Of course, you have to strike a balance here. If you lazily initialize everything in your program, then there’s a good chance that everything the user does will be a bit sluggish. Would the user be willing to wait a little bit longer for your program to load if it means that the most common operations are quicker? This seems especially relevant for operating systems. Slow boot times are annoying, but if you only reboot once a week, then a few extra seconds of pre-processing might be a good tradeoff for better OS performance.

Here’s some example code (C#):

public class MathConstants
{
    private bool piInit = false;
    private double pi;

    public double PI
    {
        get
        {
            if (!piInit)
            {
                pi = CalcPi();
                piInit = true;
            }

            return pi;
        }
    }
}

Double-Checked Locking

This pattern is often used in conjunction with lazy initialization, but in a multi-threaded environment. For example, in C# you might have a singleton class like so:

public class Singleton
{
    private static Singleton instance;
    private static Object lockObject = new Object();

    public static Singleton Instance
    {
        lock (lockObject)
        {
            if (instance == null)
            {
                instance = new Singleton();
            }
            return instance;
        }
    }
}

This code will prevent multiple threads who are accessing Singleton.Instance at the same time from accidentally creating multiple copies of the singleton. But there is an overhead cost to acquiring the lock on every access, even though the singleton instance is only initialized once! So a better implementation might perform an “unsafe check” first, before acquiring the lock, like so:

public class Singleton
{
    private static volatile Singleton instance;
    private static Object lockObject = new Object();

    public static Singleton Instance
    {
        if (instance == null)
        {
            lock (lockObject)
            {
                if (instance == null)
                    instance = new Singleton();
            }
        }

        return instance;
    }
}

Notice that the test if (instance == null) must be performed twice because two threads could still get past the first if at the same time (since there is no lock preventing them from doing so), and then sequentially create two different singletons, one after the other. Also, the volatile keyword must be used on the instance, indicating that the field might be modified in the program by a concurrently executing thread. This prevents a thread from “caching” the value of instance, and ensures that each thread always retrieves the current value of the object at the point it is requested.

Caching / Lookup Table

Let’s say you want to write a screensaver which will draw tons of circles of random sizes, colors, and positions all over the screen. And let’s say that your algorithm for drawing the arcs involves a loop that looks something like this:

void DrawCircle(int r, int x, int y, Color color)
{
    for (double d = 0.0; d <= 2 * PI; d += 0.001)
    {
        int x1 = x + cos(d) * r;
        int y1 = y + sin(d) * r;
        SetPixel(x1, y1, color);
    }
}

Okay, so for each circle, you need to call cos and sin about 6283 times. Let’s say you’re extremely interested in runtime performance, and want to make this function faster. One thing you can do is to pre-compute the sin/cos values at the beginning of your program and store them in memory, so that instead of calling a potentially expensive math function for each circle, you just access memory instead, which is always fast.

Depending on the operation, you might even try pre-computing these values before the program even starts up, writing the values to a file or putting them directly in source, depending on how many values you need.

void DrawCircle(int r, int x, int y, Color color)
{
    int i = 0;
    if (!initTrig)
    {
        for (double d = 0.0; d <= 2 * PI; d += 0.001)
        {
            costable[i] = cos(d);
            sintable[i++] = sin(d);
        }
        initTrig = true;       
    }

    for (i = 0; i <= 6283; i++)
    {
        int x1 = x + costable[i] * r;
        int y1 = y + sintable[i] * r;
        SetPixel(x1, y1, color);
    }
}

References

Copy-on-Write

Lazy Initialization

Implementing Singleton in C#

volatile (C#)

My Favorite Visual Studio Debugger Tricks

When I graduated from college with my Bachelors in CS, I knew next to nothing about successfully using Visual Studio, or any other visual debugger for that matter, for debugging. In fact, the majority of my debugging experiences involved liberal use of printf and reviewing output logs, which I suppose works to a degree, but it’s just not nearly as powerful as using Visual Studio.

Since then, from my experiences both at National Instruments, as well as working on the Visual Studio Platform team at Microsoft, I have learned a lot of neat tricks when using Visual Studio for debugging both managed and unmanaged code.

How to create and use a debugging project

I never knew you could do this until I joined Microsoft. If you want to create a “debugging project”, all you really have to do is File -> Open Project, and then find the executable you want to debug. Voila, when you hit F5, your “project” will automatically run the executable and attach to it. This is really handy for cases when you can’t attach to an already running process, because you need to attach as soon as possible before any loading takes place. If you edit your project properties you can customize the kind of debugging you do.

Attach to a running process

When you’re using Visual Studio to write, build, and run your application, you don’t have to do this, because you can just build your code and then run it like any normal project. However, if you’re debugging in a production environment, with a sizable codebase that doesn’t build in Visual Studio, you don’t really have this option. Instead, what you can do is load the source code you’re interested in, set breakpoints, and then attach to an already running application to do your debugging. This works remarkably well, and you don’t have to load the entire project into VS.

To do this, choose Debug -> Attach to Process, and find the name of the currently running executable that you want to debug. Make sure that you also click on the Select button to pick the specific type of debugging you want to do, namely Managed, Native, or both. I usually do both, but only because I usually debug mixed-mode applications. If your project is entirely managed or entirely native then you can improve debugging performance by picking whichever one applies to you.

Disable Just My Code

Just My Code is one of the many default settings that I can’t stand because I always want to turn it off, just like “Hide extensions for known file types” and “Insert tabs”. I guess the idea behind Just My Code is that the average programmer might not care if some low-level library is throwing exceptions, they only want to focus on their own code. But we don’t want to be average programmers, we want to be rockstar programmers, so turn it off and you can actually debug into the programs you’re attaching to as deep as you need to go. Trust me, turn this off.

Loading Symbols

The next step after disabling Just My Code is usually adjusting your symbol settings and making sure that your symbols are loaded. If you go to Debug -> Windows -> Modules after running or attaching to your executable, you can see a list of every assembly or DLL loaded by the application, and whether or not symbols have been loaded for that module, among other things. There are three things you usually need for debugging:

Source code
The assemblies or DLLs being debugged
Program Database (pdb) files

The PDB files are the files built for Debug builds which actually contains the debugging information, otherwise known as symbols. These files are the link between your binary module and your textual source code, so loading them means that you can now set breakpoints in your source code and the Visual Studio debugger will honor those breakpoints and allow you to debug.

If your symbols aren’t being loaded for the module you’re interested in, it’s probably just because Visual Studio doesn’t know where to look for your PDBs. Right-click on the Modules window and choose Symbol Settings, and you can give Visual Studio a list of directories to look in for PDB files. If some of these symbols live on the network, it is also usually a good idea to choose a local directory as a symbol cache so that you only have to download symbols once. If “Load symbols using the updated settings when this dialog is closed” is checked, Visual Studio will attempt to load every single PDB it can find in the directories you specified. Sometimes that’s fine but other times you may wish to uncheck this so that you don’t load symbols for everything in the world when you only care about a single module.

Disabling Native Images

Native Images are basically managed assemblies compiled into processor-specific machine code. The .NET runtime can use these natives images, which are stored in the native image cache, instead of having to use the just-in-time compiler every time a managed assembly is loaded. Application developers can use ngen or the Native Image Service to generate these native images.

The bad thing about native images however is that, because they are compiled into processor-specific optimized machine code, they are much harder to debug. So in some cases you might want to disable these native images when running your Visual Studio debugger. The instructions are available here: Reference Source FAQ, but essentially what you have to do is set the environment variable COMPLUS_ZapDisable=1 in your environment before launching Visual Studio, and then disable the Visual Studio Hosting Process. This will cause Visual Studio to ignore the native images and use the managed assemblies instead, so now you can debug your previously optimized code.

Set Next Statement

Set Next Statement is a powerful debugging technique that I had ignored until I saw someone use it, and finally I realized why it might come in handy. When you’re debugging in Visual Studio, and the application is paused by the debugger, you can elect to skip the natural execution path of the program and choose the next statement your program will execute. All you have to do is right-click in the text editor on the next statement you want to run, select Set Next Statement, and Visual Studio automatically skips there next instead of executing the current line, changing the program’s instruction pointer.

Why would you want to do this? Maybe you want to see what would have happened if a certain condition was met and step into an if or else that wouldn’t have occurred otherwise. Maybe you want to see what would happen if you skip some code or execute it again. The possibilities are endless, and you don’t even have to recompile your code to do it.

Modify variables at runtime

This technique is kind of similar to the previous, in that you’re modifying the natural execution of a running program by changing variable values, or even values in memory, at runtime. Simply find the variable you’re interested in, either via Locals, Autos, or the Watch window, double-click on its value, and change it to whatever you want. Similarly, if you know the address of a pointer to memory you’d like to change, you can open up the Memory window, type in the hexadecimal address, and use the hex-editor to modify memory values.

Like the previous technique, you can use this to see what would have happened if a certain variable was set to something else. For example, you could be calling a function which is returning an incorrect value, but you want to double-check to make sure your code would work correctly if the correct value was actually being returned. Simply change the value after you call the function, and now you can find out.

Freeze and thaw threads

In multi-threaded applications, it’s extremely important to make sure that no matter what, your program cannot get into a deadlock situation where two threads block each other from being able to continue executing. Unfortunately, this is very difficult to prove, and simply running your program and verifying that it didn’t crash isn’t enough, because of the indeterministic nature of multi-threading. So how do you test/verify your code? Use the Threads window in Visual Studio and use it to freeze/thaw threads.

When you open the Threads window, and the program is paused, you will see a list of the currently executing threads for your process. Each thread has an ID, a category, a name, a location, and a priority. When you’re debugging a multithreaded application, you want to brainstorm ways in which to deterministically control which thread executes which code in which order, so after you’ve broken into your first breakpoint, you can freeze that thread and then let the other thread catch up to the point where you want to freeze it. If you pick the right freeze/thaw points for each thread, and your program has the possibility of deadlock, you should be able to force the program into it by controlling the execution timing. If you can successfully do this, your code is flawed and must be fixed.

Determine which DLL or assembly to load based on a virtual function pointer

I learned this technique very recently from a colleague at Microsoft. Sometimes you might be debugging an application, and you want to step into a particular virtual function call, but you can’t because Visual Studio hasn’t loaded the symbols for whatever module the function is located in. Also, you don’t actually know offhand which DLL it is, and you don’t want to just load every symbol in the application because it takes too long and slows you down too much.

So here’s what you can do, sometimes. Let’s say you have a pointer to a virtual class which implements the method you’re interested in. Use Intellisense to find out more about that pointer, until you find the virtual function table. Now you have a memory address for where a particular method implementation is located. Open up your Modules window in Visual Studio, and sort by Address. Find out which address range corresponds to the virtual function pointer, and that row is the module you’re looking for. Right-click on it and choose to Load Symbols, and now the next time you try to step into that function call, it will succeed because the symbols are now loaded. Here’s a screenshot of this in action:

Summary

So there you have it, some of my favorite Visual Studio debugging tricks. Since I’m pretty new to the Visual Studio Platform team I am sure I will learn new tricks as I go along, so I will be sure to post about them as I discover them.

Cryptogram Solver

Introduction

If you’re anything like me, everytime you see a cryptogram in the entertainment section of the newspaper, you stare at it for about 60 seconds and then you give up. I’ve always wanted to be able to solve cryptograms but I never really learned how. Furthermore, even after I read a few things about the strategies you can use to solve them, I was intrigued by (in my mind) a much more interesting problem – could you write a computer program to solve cryptograms for you?

First, some definition of the problem is in order. The object of the program is to change a ciphertext consisting of cipher words into a cleartext made up of words which exist in a dictionary file, by mapping each cipher letter into exactly one cleartext letter. There is a 1-to-1 mapping in that no two cipher letters share the same cleartext and vice versa. I will also allow for apostrophes as letters which always map to apostrophes, and ignore all other characters (periods, commas). Words are separated by any non-alphabetic or apostrophe letter.

Example

Gb py bgioy lkq ckd’y oqwwttc, yil, yil prpgd.

Random Assignment

My first attempt at solving this problem was very rudimentary. Basically, assign a random mapping of all cipher letters to cleartext letters and produce the result. Check to see that every word is in fact in the dictionary. This solution will inevitably work, but it will also take forever. How many mappings are there for 26 letters? Well, for “A” you have 26 choices, for “B” you have 25 choices left, etc. In other words there are 26! mappings to choose from and only one will give you the right answer. In fact this is worse than just looping through all possibilities because you will start duplicating random assignments that you’ve already tried. Don’t do this.

Distribution Ranking

This is a similar approach to what a human would do. Basically, we know that for most texts, e is the most common letter, followed by t, a, o, i, n, s, h, and r. Insert RSTLNE joke here. What we can try to do is to analyze our ciphertext and rank the letters by occurrence frequency and then assign letters based on our letter ranking list. As it turns out, this approach didn’t work very well. If your text has exactly the same letter distribution as the English language in general, then your first assignment should be the answer, and you’re done. This is not the case, and it’s even possible that the most common letter isn’t even E. And that’s a big problem, because when it comes to recursive algorithms, getting the first part wrong means you spend lots of time searching for solutions where none will be found. There may be a way to do this using some kind of breadth first search which will lead to a relatively quick solution, but I have to say I think this approach is misguided.

Pattern Search

The solution I eventually came up with has much less to do with the letters themselves and more to do with the uniqueness of each word. When you’re looking at a cipher word, you don’t know what the letters actually represent, but you do know one very important thing. You know that everytime the same letter is used in the cipher, it is the same letter in the real word too. In other words, the letter pattern of a word is a property shared by the cleartext of that word.

Here’s an example:

oqwwttc (could be rewritten as)
0122334 (numerically speaking)
abccdde (as a normalized cipher word)
succeed (an actual word with this pattern)

As it turns out, in my dictionary, there are only five seven-letter words with that letter pattern, and succeed is one of them. Fantastic! We now know that the solution, if it will be found, must assign letters according to one of those five words. This leads us to the following pseudocode:

Load the dictionary into a hash table where the hash is the normalized letter pattern of each word, and the real words are added to the table according to their hash
For each ciphertext word, normalize it and get a list of all English words that match this pattern
Sort the list of ciphertext words in increasing count of English words
Recursively assign a word to the current cipher. Double check that this does not violate any previously assigned letters for previous words; if so, back out. Pick the next word and recurse.

This algorithm is actually really fast. For the cipher I gave above, there are only 5 choices for the first* word and only 7 for the second*, and this results in an assignment of 8 letters immediately which have a high (1/35) chance of being correct. The search space increases to 49 choices for the next word, and more for each word following, but by the time you reach the words with a high number of pattern matches you’ve already decided most of your letter assignments already, so your choices are easy to prune.

Here’s the source: View Source

Summary

A true programmatic crypogram solver doesn’t necessarily need to use the same skills as a human would use to solve the same problem; we can use the computer’s advantage of being able to complete repetitive tasks by pre-processing every word in the dictionary based on its letter pattern, and draw on that information to choose whole word assignments instead of individual letters. Choosing from the smallest number of options severely reduces the recursive search space, and from there it’s just a matter of testing the remaining word patterns until we reach the solution(s).

If you see any glaring errors in my code, or possible optimizations, please feel free to add a comment saying how I could improve. Thanks!

Oh and by the way, if at first you don’t succeed, try, try again.

* Not actually the first word, but the word with the lowest matching pattern count in the dictionary.

Lambda Functions in C++ for RAII

I learned a new trick recently at Microsoft involving the use of C++ lambda functions for automatic resource cleanup, which I thought was pretty cool. It involves combining the RAII programming pattern with a new feature of C++ 0x, namely lambda functions.

What is RAII?

RAII stands for Resource Acquisition Is Initialization, a design pattern which is popular in languages such as C++, D, and Ada. The idea is that you want to acquire resources during the initialization of objects, i.e. as soon as possible, so that you cannot accidentally use an uninitialized object, and also that you want your object to automatically release the resource upon destruction. One of the main advantages of this pattern is that your resources will always be released, even if there are errors or exceptions between when your object is initialized and your object goes out of scope. How does one do this? Here’s a simple example:

#include 
using namespace std;
class FileCloser
{
public:
    FileCloser(char* fname)
    {
        fp = fopen(fname, "r");
    }
    void ReadLine(char* line, int count)
    {
        fgets(line, count, fp);
    }
    ~FileCloser()
    {
        fclose(fp);
    }
private:
    FileCloser() { }
    FILE* fp;
};

int main(int argc, char* argv[])
{
    FileCloser fc("test.txt");
    char line[100];
    fc.ReadLine(line, 100);
    cout << line << endl;
    return 0;
}

As you can see, we didn’t have to explicitly call fclose on the file pointer because our FileCloser object’s destructor did it for us as soon as the FileCloser object went out of scope in main. Thus, even if we change main to the following, we will still close fp after the exception is thrown:

int main(int argc, char* argv[])
{
    FileCloser fc("test.txt");
    char line[100];
    fc.ReadLine(line, 100);
    cout << line << endl;
    throw;
    return 0;
}

What are lambda functions?

Lambda functions are a new feature of the proposed new standard for the C++ programming language called C++0x, although it’s likely to be introduced sometime in 2009. They are a functional programming technique based on lambda calculus, which you may or may not remember from Theory of Computation. Or was it Programming Languages? Either way, I like to think of it as defining an anonymous inline method where you need it, instead of having to define your own function pointer or delegate method elsewhere. Here’s an example of a simple lambda function:

#include 
#include 
#include 
using namespace std;
int main(int argc, char* argv[])
{
    vector<int> v = { 1, 2, 3, 4, 5 }; // Another new feature of C++ 0x
    for_each(v.begin(), v.end(), [](int& x) { x = x * x; });
    for_each(v.begin(), v.end(), [](int x) { cout << x << endl; });
    return 0;
}

How to use lambda functions to perform RAII

Here’s where we combine these two techniques to perform RAII using lambda functions. In the first code snippet I showed you where we used RAII to automatically release the resource, we still had to define our own class, complete with a destructor, in order to get the kind of resource release we want in the face of errors and exceptions. And although you could design a generic class which could handle automatically deleting pointers which were allocated via new, you would have to create a separate class for each resource type if you have to do something a little bit more complicated to release a resource (for example, by calling a method). But thanks to lambda functions, this is no problem:

#include 
#include 
using namespace std;
using namespace std::tr1;

int main(int argc, char* argv[])
{
    FILE* fp = fopen("test.txt", "r");
    shared_ptr fileReleaser(fp, [](FILE* fp) { fclose(fp); });
    char line[100];
    fgets(line, 100, fp);
    cout << line << endl;
    throw;
    return 0;
}

The shared_ptr in this example is used to create a sharable pointer to the object we want to release. The arguments to its constructor are first the pointer, and then a pointer to a deleter method, in this case the lambda function. When the shared_ptr goes out of scope outside of main it will automatically call the lambda function to release the file.

Summary

In summary, RAII is a great defensive programming technique you can use to make sure your resources are released and your code doesn’t leak, and lambda functions are a great new way to make using RAII much less painful than it ever was before.

References

Wikipedia: RAII
HackCraft: RAII
Wikipedia: C++0x
Herb Sutter’s Blog
MSDN: shared_ptr

Top Ten Things I Miss in Austin

10. MoPac and 183

I never thought I’d say that I miss an intracity highway, but there’s something to be said for a 3-lane highway that can get you from the tech suburbs to downtown in 20 minutes. My typical commute from the U-District to Microsoft in Seattle is about an hour on 520 (a 2-lane highway), so I definitely miss being able to get around town fast.

9. Barton Springs

Barton Springs might be the coldest body of water in Austin, but it’s also one of the coolest. The fact that Austin decided to turn the springs into a public swimming pool, complete with diving boards, is pretty awesome. It’s best to go on a really hot day and alternate between freezing your skin off and drying off in the sun.

8. Brisket – Rudy’s, Salt Lick, County Line

Austin has some of the best BBQ in the country. Where else would you find affordable and delicious fast food barbecue than at Rudy’s? And you really can’t beat the cash-only BYOB experience at the Salt Lick. Their brisket is absolutely amazing.

7. Town Lake (aka Ladybird Lake)

Town Lake has everything you could ever want in a jogging trail. Variable distances, nice dirt paths, a great view of the water, and even a dog park! Plus there’s free water. Thanks RunTex!

6. Austin City Limits

Three days of fun in the sun and all-you-can hear music at an affordable price in Zilker Park. Some of my favorite bands over the years have been Muse, Cake, Sheryl Crow, John Mayer, Blue October, Regina Spektor, Ghostland Observatory, Guster, Brazilian Girls… I could go on and on.

5. Lake Travis

Party barges, cliff diving, and scuba diving are among the few of many activities I have participated in at Lake Travis. All of them were incredibly fun. The water is so warm in the summer you don’t even need a wetsuit, even if you’re 60 feet underwater scuba diving. Lake Travis more than makes up for the incessant Texas summer heat.

4. Sixth Street

If you haven’t heard of Sixth Street yet, you probably haven’t heard of Austin. A street so populated with bars and so popular on Friday and Saturday nights that the police closes off traffic in preparation for all of the stumbling foot traffic. Vendors sell pizza and the best wurst you’ve ever had after the bars close, and let me tell you, it’s delicious.

3. Tubing on the Guadalupe and Comal Rivers

I love tubing on the Guadalupe River. Spending the whole day laying around, having fun with your friends, and shooting through the “rapids”. Okay, so they aren’t that fast, but they are fun.

2. Tex Mex – Trudy’s and Chuy’s, even Taco Cabana

Finding great Tex Mex in Seattle is like trying to go snowboarding in Austin. No matter how hard you look, you just won’t find it. Trudy’s has both delicious stuffed avocados, and potent Mexican Martinis. Chuy’s has a Chuychanga that is easily my favorite chimichanga ever made, and their secret jalapeno ranch salsa makes tortilla chips into a dessert. Even Taco Cabana, a fast food joint in Austin, has some pretty tasty eats.

1. Friends

Since my first foray into Austin as an intern at National Instruments, the friends I made were the reason I was able to do so many fun and exciting things, because without friends to share them with, they would have just been things. To those of you I left behind in Austin, I miss you and I hope you visit Seattle soon.

Solving Tetris via a Scoring Algorithm

When I was in college, I wrote a simple Windows Tetris game I called WinTetris, because the name wasn’t taken and I wasn’t feeling very creative that day. This project was at first just an exercise in Win32 programming and game logic, and the first version featured very ugly GDI graphics with DrawRect.

Over time, I polished it quite a bit, and added a lot of new features. I replaced the ugly graphics with DirectDraw, added support for mouse/keyboard controls, added sound and music, A/B game types, and LAN multiplayer. But quite possibly my favorite new feature was the “demo mode”, which starts when you launch the program.

Demo mode was a simple way for me to use the tetris engine I had already developed to do something cool; write an algorithm that could play tetris extremely well. The bonus was that I could show off both my AI programming and my game at the same time, thanks to my demo mode.

So how does it work? At the top-most level, it does the following:

Considers every possible piece placement for the current piece, including both lateral movement and rotation.
Assigns each piece placement a score, according to some kind of scoring mechanism.
Chooses the placement with the highest score.
Moves and rotates the piece into place.

This arrangement is pretty logical, but everything hinges on the scoring algorithm. How would you write such a function? Personally, I thought a bit about things that are good, and things that are bad when it comes to playing tetris, in general:

Completing a line is a good thing. Completing more than one line at once, all the way up to a tetris, is even better.
Reducing the maximum stack height is a good thing. Conversely, making the maximum stack height higher is bad.
Placing a piece lower in the playing field is generally better than placing it higher.
Creating empty holes beneath a piece is bad.

So now that you know what to look for, you write methods that will tell you the effects of your piece placement, assign each measure a weight, and total up the plusses and minuses. But what weight values to pick?

Personally, what I did was to pick weights that seemed reasonable, watch how the game played, and then made adjustments if I thought it was playing in a way that was either too reckless or too safe. And although I didn’t mention it before, my goal was an algorithm that would take a long time to lose, not one that loves to set up tetrises or rack up a high score.

In the end, I made the following weight table:

Hole Count: -500

Lines Completed: +500

Block Height: -150

Chasm Height: -400

If I was to tweak these weights again, I would want to take a more scientific approach. I could use even more AI programming to run thousands of tetris simulations, and see which weight values yielded the lowest average stack height, and use those values. Perhaps that could be a future project of mine.

The last trick I added was a modification of the process, not the scoring algorithm. In the process I gave above, the code only evaluates the current piece. But players get to see the next piece! So instead of choosing the piece placement with the highest score, I modified my algorithm to calculate the best combined score (A + B) for the current piece as well as the next piece, and use that information to place only the current piece. So the current piece is placed with the highest potential score. The weird thing about this is that the algorithm is not committed to that second placement. It can choose to do something completely different if the next piece changes the optimal two-piece score.

So now that you know how to write a Tetris AI, break out your favorite compiler and improve on my methods. I implemented WinTetris such that you can create your own AI DLLs if you want to play around with it. The installer and source code for WinTetris is available at http://www.hexar.net/wintetris.php. Enjoy!

How Much Money I Lost in Economic Storm 2008

I like to track my finances every month; I like knowing not just how much money is in my accounts right now, but also where exactly my money went. I use a new Excel spreadsheet for every new month, with a tab for each individual account, as well as a budget tracking tab and a summary page. It sounds like a lot of work, and it is, but it’s worth it for me to know where my money is being spent on. It gives me, at the very least, some illusion of control over my finances.

But, for all of 2008, I was frustrated. Frustrated because of the one number I looked at most month to month, my net worth. This number is easily calculated as my assets minus my liabilities. In previous years, starting in 2004, I saw this number gradually rise from a negative number (thanks student loans) to a positive one. And then to grow further from there. At the end of each year I could see how much this number increased on average per month. It was very reassuring. But not in 2008. Despite my best efforts to save money, my number didn’t budge.

As you know, 2008 was a bad year for the stock market. But I didn’t actually realize how bad it really was. Take a look at this graph:

(image from Google Finance)

Between Dec. 28, 2007 and Dec. 31, 2008, the S&P 500 index dropped from 1478.49 to 903.25. That’s a reduction of about 38.9% in a single year, which is a lot more than I realized. Furthermore, in the beginning of January 2008 I had money invested in my 401k and Roth IRA to the tune of about 52% of my yearly salary. I won’t tell you how much I make, but I will say that this means I lost money totaling around 20% of my salary in the stock market, just from money that I had in January. Not to mention all of the money I invested up until October, when the market started really going south.

In a weird way, I find this information comforting. The reason is that I was beating myself up over not being able to make any headway with my net worth over an entire year. But I failed to realize just how strongly I was trying to swim against the current. The fact that my net worth didn’t move much over a year is actually a good thing; it could have been much worse. And with prices as they are right now, my new 401k and Roth IRA investments have a lot more purchasing power for the same amount of money. Perhaps I should care less about the net worth itself, and worry more about how many new investment shares I acquired over the course of the year. Someday, when the market bounces back, I will be glad I continued to invest even in such a year as 2008 ended up being.

What about you? How were you affected by the Economic Storm of 2008?

Hole Count:	-500
Lines Completed:	+500
Block Height:	-150
Chasm Height:	-400