Chad Austin

Your Version Control and Build Systems Don’t Scale

2010-03-04T08:02:18Z

Let’s spend a minute and talk about the performance of a tool you use every day: your build system. For this purpose, they’re all the same, so let’s assume you use GNU Make. For a no-op build, what is Make’s running time? You know, that O(N) stuff.

If you said O(Files), you’re right. Every time you type make and press enter, it scans every file in the project, looking for out-of-date sources. That doesn’t sound so bad. Linear algorithms are good, right?

Oh, but projects grow over time, typically in proportion with the number of engineers (even if some are net negative). Since projects grow:

O(Files) = O(Engineers * Time)

Assuming you’re successful, your team is probably growing too:

O(Engineers) = O(Time)

Applying some substitutions:

O(Make) = O(Files) = O(Engineers * Time) = O(Time^2)

A no-op make is quadratic in the duration of the project?!

Exhibit A, Mozilla:

Chad@laptop /c/xulrunner/mozilla-central/obj-xulrunner
$ time make
rm -f -rf ./dist/sdk
[tons of output snipped]
make[1]: Leaving directory `/c/xulrunner/mozilla-central/obj-xulrunner'

real    21m31.526s
user    4m13.292s
sys     9m15.066s

21.5 MINUTES! This is a no-op build! I changed nothing from the last build!

Mozilla’s build is an especially egregious example, but it’s not uncommon for nontrivial Make, SCons, or Jam no-op builds to exceed 15 seconds. Every time you run SCons, for example, it:

loads Python,
imports a bunch of Python code,
creates an entire dependency graph in memory,
scans all files for changes,
determines what to build,
builds it,
and throws all of those intermediate results away.

Am I the only person who thinks this situation is insane? We’re spending all of our time improving constant factors rather than addressing fundamentally quadratic build algorithms.

No-op builds should be O(1) and instantaneous, and most other builds should be O(WhateverChanged). What if I told you this is possible?

Introducing IBB: I/O-Bound Build

Dusty, one of the best engineers I know, once told me that C compilers are now fast enough that they’re I/O-bound, not CPU-bound as you’d expect. This was inspiration for a ~~build system~~ dependency engine architecture:

A long-running server process that contains a complete dependency graph between files, including the commands required to update targets from sources.
An ultra-tiny C program that communicates build requests to the build server.
A background thread that watches for filesystem updates (via ReadDirectoryChangesW or libfam) and updates the dependency graph in memory.

I have built a prototype of ibb’s architecture, and its code is available on my github.

In ibb, a no-op build takes constant time, no matter the size of the project. I tested with Noel Llopis’s build system stress test and no-op builds are merely 50 milliseconds. Take that, everyone else!

A Faster Grep

Let’s say you wanted to run a regular expression across your entire codebase. On Windows, you’ll spend all of your time in kernel calls, even if the files are in cache. However, remember that modern memory bandwidths are measured in GB/s…

ibb’s file search implementation can run a regular expression across 200 MB of PHP and JavaScript in 100 milliseconds. It copies file data into memory on the first run and rapidly scans across that memory on future runs. It could just as easily mmap and use OS’s disk cache to avoid kernel calls.

Minimal Test Runner

Carl Masak’s inspirational addictive TDD harness is also possible with ibb. If you can determine which unit tests depend on which source files (via an __import__ hook in Python, say), you can run appropriate tests immediately after saving a source file.

Version Control

I’ve watched both git and Subversion fall apart as a codebase grows. git is so faaast… until you import a 20 GB repository. Then it’s O(Files) just like everything else.

$ time git status
# On branch master
nothing to commit (working directory clean)

real    0m9.603s
user    0m0.858s
sys     0m7.378s

10 seconds to see what files I’ve modified. Ouch.

Imagine if ibb could keep track of which files have changed…

What This Means For You

Running tests, grepping code, and building binaries from source are equivalent problems. ibb’s architecture supports lightning-fast implementations of all of the above.

By converting an O(Time^2) build, test runner, or version control system to O(1), we eliminate hours of costly engineer time and encourage good habits like committing often and frequently running tests, no matter the age of the project. Frankly, instant feedback feels great.

It’s crazy to me that this architecture isn’t standard practice across development tools.

Take ibb’s concepts or code, integrate it with your engineering processes, and improve the quality of your team’s life today.

The Completionist’s Guide to Sims 3 iPhone

2010-01-05T03:56:25Z

I play simulation games in two phases: first, I tackle the often-repetitive mechanics, unlocking every option and building up money so that I can creatively decorate my house or farm or whatever.

Sims 3 for iPhone was no different. Having accomplished nearly everything in the game, I will share a strategy for completing all 73 goals and acquiring the best job: $600 per day at the Pawn Shop.

The Objective

To open the pawn shop, you must complete the following 73 goals:

Goals for all Sims (55)

Try fishing
Try cooking
Buy fishing kit
Buy watering can
Buy repair kit
Buy a stove
Buy a bath
Gain a skill point at cooking
Gain a skill point at fishing
Gain a skill point at repairing
Meet a new Sim
Befriend a Sim
Begin a romantic relationship
Make an enemy
Make a Sim laugh
Annoy a Sim
Insult a Sim
Creep-out another Sim
Slap a Sim
Get a job
Buy something
Catch a fish
Catch a trout
Catch a salmon
Catch a catfish
Repair something
Discover a new recipe
Cook something
Cook grilled cheese
Cook steak & veggies
Cook minestrone
Grow something
Grow carrots
Grow corn
Grow tomato
Watch TV
Kick over a Trash Can
Sleep in another Sim’s bed
Use another Sim’s shower
Use another Sim’s toilet
Get a better couch
Get a better TV
Accumulate $1000
Catch 15 fish
Harvest 30 crops
Stay entertained for three days
Stay fed for three days
Stay rested for three days
Stay clean for three days
Meet all the Sims in town
Make a Sim jealous of you
Sleep in three other Sim’s beds
WooHoo with someone
Get a promotion
Reach the top of the career ladder

Maniac Personal Goals (4)

Use everyone’s toilet at least once
Use everyone’s shower at least once
Creep out five people
Watch three people sleeping

Sleaze Personal Goals (2)

Be romantically involved with three Sims
WooHoo eight times in one day

Power Seeker Personal Goals (3)

Accumulate $5000
Own the best house
Own the best TV, stereo and stove

Nice Guy Personal Goals (2)

Get married
Be liked by all the Sims in town

Jerk Personal Goals (4)

Be disliked by all the Sims in town
Slap four people
Insult five people
Kick over all the trash cans in town

Jack of All Trades Personal Goals (3)

Achieve the highest fishing skill level
Achieve the highest repairing skill level
Achieve the highest cooking skill level

There are six Sim classes:

Jack of All Trades
Nice Guy
Jerk
Sleaze
Power Seeker
Maniac

As previously mentioned, you will need to complete every Goal to unlock the Pawn Shop. Of the 73 total Goals, 55 randomly appear as Wishes, no matter which Sim class you choose, and they’re generally easy to complete.

On the other hand, each Sim’s Personal Goals are relatively difficult. You’ll need to create at least six Sims, one of each type. For the optimal path through the game, you should complete their personal goals from hardest to easiest. I will give an efficient play sequence below.

Play Order

Jack of All Trades

Create six Sims, and designate one as your “main” Sim. Your main Sim is the one with which you most identify.

Your main Sim is a Jack of All Trades (you’ll later need its Repair skill at the Pawn Shop). Play him or her first, building up skill levels as rapidly as possible. Learn to fish, because fishing is the best way to make money. As you accumulate money, buy as many of the cheapest stereos you can afford, filling your house. Each time you enter the house to eat or rest, turn them all on. Eventually, they will start breaking down, allowing you to practice repairing.

Practicing cooking is easy – simply buy bread, cheese, and the Grilled Cheese recipe and make it over and over again.

Once fishing, repairing, and cooking are level 5, save, quit and move to the next Sim.

Power Seeker

Your second Sim is your Power Seeker. Fish until you have $5000 and tool around town until you have the option to upgrade your house twice and buy the most expensive TV, stereo, and stove. Furniture and home upgrades simply take time. This is a good opportunity to accumulate general Goals.

At this point, you should have most of the 55 general Goals.

The Other Sim Types

Sleaze, Nice Guy, Jerk, and Maniac have fairly easy Personal Goals. The order in which you complete them does not matter.

At this point, you should have almost all of the Personal Goals. If not, keep playing — they’ll eventually show up.

Goal Tips

If you need the “Buy XXX” goal but you already have XXX, then try selling it. Eventually the Goal should appear as a Wish. Lock it in and repurchase the item.

If you need the “Gain a skill point at XXX” goal and you’re maxed out, switch to a Sim that is not maxed out.

If you’re having trouble Meeting all Sims, double-check all of the houses at different times of the day. I’ve noticed Bernie can be hard to find. Most Sims are sleeping in the middle of the night – try breaking into their houses, waking them up, and meeting them.

If you need to befriend a Sim but you’re already friends with all of the Sims, start a new Sim or insult a Sim until it becomes an enemy, then befriend him or her.

The best way to annoy, insult, and creep-out other Sims is to find a house with two Sims (e.g. Marcell and Theresa), barge in, and start flirting with one of them. Both will be creeped out and annoyed, and the flirting will insult the other and make him or her jealous. If that doesn’t work, start using their toilet, shower, and fridge.

Tips and Tricks

Fishing is the best way to make money. Each tuna sells at QuickMart for $100, and salmon for $65.

Besides the Pawn Shop, working at the Town Hall is the best. It’s easy to get promotions (both Ruth and the Town Hall are nearby) and you just need to be friends with everyone in town. As Vice President, you can make $300 per day.

Creating romantic relationships is easy. It sounds rude, but keep pestering the Sim with Flirt, Tender Embrace, Hot Smooch, and WooHoo. You should be able marry a Sim within two conversations.

Too many WooHoos and your Sim will die! Don’t overdo it in the bedroom!

If you get married, give your spouse a phone call and invite him or her over. Once your spouse arrives, you can invite him or her to move in.

Since the Town Hall is right by your house, it’s the best job until the Pawn Shop is open.

The Sims

Nina
Ruth
Johnny
Kia
Jake
Maggie
Jack
Jill
Walter
Luke
Bernie
Marcell
Theresa

The Jobs

Town Hall (boss: Ruth)

Campaign Intern ($100/day) M-F 8:30-18:00
City Council Member ($150/day) M-F 8:30-18:00
Local Representative ($200/day) M-F 9:00-18:00
Mayor ($250/day) M-F 10:00-18:00
Vice President ($300/day) M-F 10:00-17:00

Corsican Bistro (boss: Marcell)

Kitchen Scullion ($100/day) M-F 10:30-18:30
Ingredient Taster ($150/day) M-F 10:30-18:30
Line Chef ($200/day) Tue-Sat 11:00-17:00
Sous-Chef ($250/day) Tue-Sat 11:00-17:00
Chef de Cuisine ($300/day) Tue-Fri 11:00-17:00

Laboratory (boss: Kia)

Test Subject ($100/day) M-F 9:00-16:00
Lab Tech ($150/day) M-F 09:00-16:00
Fertilizer Analyst ($200/day) M-F 09:00-16:00
Carnivorous Plant Tender ($250/day) M-F 09:00-16:00
Genetic Resequencer ($300/day) M-F 10:00-16:00

Quickmart (boss: Bernie)

Filing Clerk ($100/day) M-F 08:30-18:30
It’s not worth getting promotions at Quickmart. Bernie is a dick and you have to work there FOREVER before he’ll promote you.

Pawn Shop (boss: Nina)

Con Artist ($300/day) M-F 16:30-23:55
Safecracker ($400/day) M-F 16:30-23:55
Cat Burglar ($500/day) M-F 17:00-23:55
Master Thief ($600/day) M-F 17:00-23:00

In the End

With the information given above, you should have no problem achieving 73 goals and as much money as you need to decorate your dream home.

If you get stuck at any point, feel free to leave a comment on this page and I’ll update the document.

Comparing Final Fantasy III to Final Fantasy IV

2010-01-05T03:57:31Z

Having grown up with Final Fantasy IV on SNES, I recently enjoyed playing through Final Fantasy III. For my own edification and those curious, I’d like to note some of the design similarities between the games, providing color on the evolution of the Final Fantasy franchise.

Airships are a primary theme, both as transportation and cultural status.
Final Fantasy 3 introduced the character class system in a big way, setting the stage for the classes used in FF4’s story.
Desch and Yang provide similar service to their respective stories: help the party for a while, followed by dramatic sacrifice.
FF3 introduced the Toad and Mini status effects as first-class gameplay elements. Toad allows you to swim and Mini allows you to fit in tiny passages. While Mini, your attacks are useless but magic still works. These status effects remained in FF4, although vestigial. (I always wondered why “mini-mages” were so common in FF4. Without having played FF3, they didn’t make sense.)
FF3 introduced the Leviathan, Odin, Bahamut hierarchy.
Eureka (FF3) paralleled the Lunar Subterrane (FF4). They’re both extremely hard when you first enter, but they force the party to gain about ten levels. In addition, they contain several smaller bosses and a bunch of powerful equipment. Both provide a sense of progress and accomplishment, without feeling like grind.
The last areas and bosses of both games are unusually difficult. They each took me multiple attempts to complete.
In both final battles, previous allies provide “spiritual assistance”, making it possible to defeat the overpowering final boss.

However incomplete this list, these are the similarities I noted. Final Fantasy 3 had not quite discovered the Final Fantasy “sauce”, but it was an important step along the way.

Avoid Manual Initialization

2010-01-01T07:20:39Z

Too many software libraries require that you manually initialize them before use. As illustration:

library.initialize()
window = library.createLibraryObject()

Why require your users to remember initialization busywork? createLibraryObject should initialize the library, refcounting the initialization if necessary.

The primary benefit is cognitive. If a library requires initialization, its objects and functions have an additional, externally-visible behavior: “If not initialized, return error.”

If the library’s internal state is managed implicitly, it does not leak out of the API. createLibraryObject should lazily initialize the library on object construction. Optionally, on object destruction, it can deinitialize the library.

A secondary benefit of lazy initialization is performance: interactive desktop applications rarely need immediate access to all of its subsystems. By deferring as much initialization as possible, application startup time is reduced.

[This post is a test of my new host: prgmr.com]

9 Reasons Why MinTTY is the Best Terminal on Windows

2009-10-20T08:33:42Z

MinTTY is a fantastic piece of software that smoothes some of the edges of the Windows command line experience. You should use it and here’s why:

MinTTY comes with Cygwin

Installing MinTTY is trivial: just select the mintty package in Cygwin’s setup.exe and point your Cygwin shortcut to C:\cygwin\bin\mintty.exe -. The trailing hyphen is important.

Sane copy and paste

By default, MinTTY copies on select and pastes on right-click, just like Linux. However, you can make it behave like a typical Windows application and show a context menu upon right-click.

I won’t bother explaining how difficult copying and pasting is in standard Windows consoles.

Resizing

MinTTY supports arbitrary window sizes, including maximized. Enough said.

Works with less/emacs/ssh

Because MinTTY is based on PuTTY, it doesn’t display output strangely when running emacs over ssh, among other examples.

It’s FAST

Anyone who has done command line work on Windows has surely noticed that, when a program spews output to the console, system performance nosedives. Sometimes, even the mouse cursor skips, making it hard to kill the program responsible.

MinTTY doesn’t have this problem — it uses minimal CPU, even under heavy load.

Doesn’t bypass RSI Guard

Five years ago, I was diagnosed with repetitive stress injuries from programming. To make matters worse, I get obsessive when I work, and nothing can pull me away from the keyboard.

RSI Guard keeps my wrists and elbows pain-free by enforcing short, periodic breaks. However… years of exposure to RSI Guard has caused me to discover its holes. For example, native console windows bypass RSI Guard’s protection, so when RSI Guard blocked keyboard and mouse input, I would quickly switch to typing in a console window and continue to work. Because MinTTY is a standard Windows application, it closes this backdoor.

Closes even when programs are backgrounded

Open a fresh Cygwin and type notepad & followed by exit. The Cygwin console sticks open until you close Notepad.

In MinTTY, you can always close the window, no matter how many background processes you’ve started.

Alt-F2 opens a new terminal window

Pure convenience: Alt-F2 opens a new terminal. No need to reach for the mouse.

Shift-PageUp and Shift-PageDown!

For rapidly paging through previous lines of output, you can press Shift-PageUp and Shift-PageDown, just like the Linux console. Another huge convenience.

OpenCL Rocks: Why You Care

2009-08-24T05:28:08Z

Today I attended the Hot Chips 2009 conference, where I was introduced to OpenCL*. I’d never heard of OpenCL before, but it’s totally hot and I will tell you why.

What is OpenCL?

OpenCL (Open Computing Library) is an open and free API that lets your programs efficiently leverage all of the computing power in your computer, including multiple CPU cores, vector computation units, GPUs, Cell coprocessors, DSPs, etc. OpenCL programs, called kernels, are written in a variant of C and are automatically scheduled across your available hardware. Your customers don’t have a GPU but their processor has 2 or 4 cores? No problem: OpenCL will utilize that spare power.

In addition, OpenCL specifies 4-, 8-, and 16-wide SIMD vector types, meaning it can easily leverage both the vector computation units on GPUs and extended vector instruction sets on CPUs, such as SSE and AVX. (Looking forward to Larrabee.)

With OpenCL, Apple and the Khronos Group are cleanly solving two clear market needs: we have increasing amounts of computational hardware available to us, but each bit of hardware is a bit different, with separate APIs, performance, and instruction sets. As much as possible, OpenCL unifies the interface to this hardware.

It’s true that GPUs and CPUs have different performance characteristics, but the same types of programs run efficiently on both: do way more math than memory loads and split your program into large parallel chunks.

Where do I get it?

The major vendors are starting to provide OpenCL implementations:

Intel’s on the way, I’m sure. I expect we’ll see an OpenCL implementation on Larrabee as well.

How do I use it?

OpenCL programs are called kernels — functions that run in parallel across large amounts of data. You’re given a lot of freedom: OpenCL uses a variant of the C99 programming language, with only a handful of restrictions.

If you find that too onerous, you can use OpenCL with native functions you’ve already written! Just let it schedule your tasks and manage task dependencies to easily get started running code on multiple cores.

I won’t go into the details of the memory model or API; you can look that up on Google. However, here’s an example kernel:

kernel void square(
    global float* input,
    global float* output
) {
    int i = get_global_id(0);
    output[i] = input[i] * input[i];
}

It squares a bunch of numbers in an array, storing the results in an output array. This trivial example will easily consume all of the compute power in your system. (Defining compute to mean ALU + memory, of course…)

Next Steps

I hope that’s enough information to get you excited about OpenCL! OpenCL is a huge step towards transparently leveraging additional cores, vector instructions, and GPUs.

* Full disclaimer: I have never actually used OpenCL, but I’ve definitely struggled with the problems it solves. The IMVU client has some optimized inner loops that we’ve hand-implemented for the GPU, SSE, or C-compiled x87 code. Unfortunately, we have had to manually select between those code paths based on the capabilities of the hardware. This sucks. With even decent OpenCL implementations, we could avoid all of that work and transparently benefit from future hardware improvements.

IMVU Crash Reporting: Stalls and Deadlocks

2009-06-18T06:52:38Z

By mid-2006, we’d primarily focused on access violations and unhandled exceptions, the explosive application failures. After extensive effort, we got our client’s crash rate down to 2% or so, where 2% of all sessions ended in a crash.* Still the customers cried “Fix the crashes!”

It turns out that when a customer says “crash” they mean “it stopped doing what I wanted”, but engineers hear “the program threw an exception or caused an access violation”. Thus, to the customer, crash can mean:

the application was unresponsive for a period of time
the UI failed to load, making the client unusable
the application has been disconnected from the server

In short, any time the customer cannot make progress and it’s not (perceived to be) their fault, the application has crashed.

OK, we’ve got our work cut out for us… Let’s start by considering deadlocks and stalls.

First, some terminology: in computer science, a deadlock is a situation where two threads or processes are waiting for each other, so neither makes progress. That definition is a bit academic for our purposes. Let’s redefine deadlock as any situation where the program becomes unresponsive for an unreasonable length of time. This definition includes livelock, slow operations without progress indication, and network (or disk!) I/O that blocks the program from responding to input.

It actually doesn’t matter whether the program will eventually respond to input. People get impatient quickly. You’ve only got a few seconds to respond to the customer’s commands.

Detecting Deadlocks in C++

The embedded programming world has a “watchdog timer” concept. Your program is responsible for periodically pinging the watchdog, and if for several seconds you don’t, the watchdog restarts your program and reports debugging information.

Implementing this in C++ is straightforward:

Start a watchdog thread that wakes up every few seconds to check that the program is still responding to events.
Add a heartbeat to your main event loop that frequently pings the watchdog.
If the watchdog timer detects the program is unresponsive, record stack traces and log files, then report the failure.

IMVU’s CallStack API allows us to grab the C++ call stack of an arbitrary thread, so, if the main thread is unresponsive, we report its current stack every couple of seconds. This is often all that’s needed to find and fix the deadlock.

Detecting Deadlocks in Python

In Python, we can take the same approach as above:

Start a watchdog thread.
Ping the Python watchdog thread in your main loop.
If the watchdog detects that you’re unresponsive, record the main thread’s Python stack (this time with sys._current_frames) and report it.

Python’s global interpreter lock (GIL) can throw a wrench in this plan. If one thread enters an infinite loop while keeping the GIL held (say, in a native extension), the watchdog thread will never wake and so cannot report a deadlock. In practice, this isn’t a problem, because the C++ deadlock detector will notice and report a deadlock. Plus, most common deadlocks are caused by calls that release the GIL: threading.Lock.acquire, socket.read, file.read, and so on.

It might help to think of the Python deadlock detector as a fallback that, if successful, adds richer information to your deadlock reports. If it failed, whatever. The C++ deadlock detector is probably enough to diagnose and fix the problem.

What did we learn?

It turned out the IMVU client had several bugs where we blocked the main thread on the network, sometimes for up to 30 seconds. By that point, most users just clicked the close box [X] and terminated the process. Oops.

In addition, the deadlock detectors pointed out places where we were doing too much work in between message pumps. For example, loading some assets into the 3D scene might nominally take 200ms. On a computer with 256 MB of RAM, though, the system might start thrashing and loading the same assets would take 5s and report as a “deadlock”. The solution was to reducing the program’s working set and bite off smaller chunks of work in between pumps.

I don’t recall seeing many “computer science” deadlocks, but these watchdogs were invaluable in tracking down important failure conditions in the IMVU client.

Next time, we’ll improve the accuracy of our crash metrics and answer the question “How do you know your metrics are valid?”

* Median session length is a more useful reliability metric. It’s possible to fix crashes and see no change in your percentage of failed sessions, if fixing crashes simply causes sessions to become longer.

How I Lost 20 Pounds in 20 Weeks With My iPhone (or: Data is King)

2009-06-07T21:53:27Z

Well, it was really more like 17 weeks, but who’s counting. ;) First, I’ll give the punchline.

Chad, you were skinny! Why diet?

High school: 140 pounds
College: 150 pounds
Grad school: 160 pounds
After four years at IMVU in delicious downtown Palo Alto: 180 pounds

At my height, 180 lbs. isn’t terrible, but the trajectory is obviously wrong. Without adjustments to my lifestyle, you can see what would happen. So I started paying attention.

In February, Laura and I got iPhones. Shortly after, I discovered Lose It!, a calorie-counting and weight-tracking app. I knew my eat-box-of-cheez-its-when-bored habit was bad, so I began simply tracking calories with Lose It!, hoping to break some bad habits. After all, if you give an engineer some data, he’ll optimize it.

A few weeks later, I ended up reading The Hacker’s Diet. It’s a quick, educational, and inspirational read. John Walker’s thesis is that anyone can lose weight if they correct the flawed feedback mechanisms causing them to eat more than they consume every day.

See, our bodies are complicated machines. We can’t entirely understand them, so we use models (created by people smarter than me) to help us predict how our bodies will behave under various inputs. Thus, there are tons of weight loss plans, and I’m sure they’ve all worked for someone: all raw, low-carb, no-carb, low-calorie, intense exercise, glass of red wine every night, protein shakes in the morning, seven snacks a day, etc. etc.

All of that is too complicated for me, so I chose the simplest model I knew: Calories In, Calories Out. It goes something like this:

The Hacker’s Diet (Theory)

(I am not an expert! This is what worked for me. Consult your nutritionist and physician. Don’t starve yourself. Take your vitamins. Etc.)

1 lb. of body fat = 3500 calories
Calories stored = calories eaten - calories burned
Every day, I eat X calories
Every day, I burn ~2500 calories


If X > 2500, you will gain weight at (X-2500)/3500 pounds per day.
If X < 2500, you will lose weight at (2500-X)/3500 pounds per day.

Thus, if you eat 500 calories less than you burn every day, you will lose one pound per week.

Key insight: this is not difficult! For example, a strawberry milkshake from In-n-Out is 700 calories. A 6 oz. frozen yogurt with strawberries and mangos from Fraiche is 200 calories. That’s 500 calories saved right there!

Sounds great! How do I deal with this on a day-to-day basis?

The Hacker’s Diet (Practice)

My mother once told me “Chad, be very careful with drugs and alcohol. You have an obsessive personality.” She was absolutely right about the obsessive personality; fortunately, I’ve learned to channel my obsessions productively. (Although I did spend a year and hundreds of dollars on Travian…)

Here’s how calorie-counting with Lose It! works in practice:

Keep track of everything you eat. This is pretty easy because their database contains most common foods. If it’s not in the database, just enter it yourself. Record it right before or after you eat so you don’t forget.
Estimate your daily caloric burn. There are standard estimation formulae, but the exact amount doesn’t matter a great deal. If you are losing weight faster than you expected, increase your burn. If you are losing weight slower than you expected, decrease your burn. I started at 2500 calories/day, but shortly realized my actual burn was 2300 calories/day.
Stay within your daily calorie budget! Treat it as a hard limit so that, if you screw up and eat a Double Double and Shake (1400 calories total) for lunch, you’ll be very sad at dinner when you can’t eat anything else. :( You won’t make that mistake again. *cough*
Drink water. Take vitamins. Sleep. Take care of yourself if you get sick.
Weigh yourself every day. Watch the mostly-linear progress!

That’s all there is to it! Time + calorie deficit = easy weight loss!

Really? Surely there’s more to it…

Unexpected Side Effects

The first couple weeks after I reduced my caloric intake to ~1800, I got hungry. Then tired. REALLY TIRED. I started sleeping 10 hours a night. It turns out that your body is good at noticing “Hey, where’d the energy go? Time to slow the engine down.” I suspect this is the part where most people quit, especially if they don’t see immediate progress. Remember: this effect is annoying, but temporary. Your body will adjust to the reduced intake and before you know it you’ll feel great again.
My headaches are GONE! I used to get very frequent headaches related to low blood sugar. Maybe burning fat means I have a more even supply of energy through the day? Maybe eating less means my blood sugar doesn’t spike? Who knows, but I’ll take it!
Body fat is an inert material. For years, it quietly stores all kinds of chemicals and toxins. Burning fat means those chemicals go into your bloodstream. Some of those chemicals reek. Thus, you will randomly smell like holy hell for a week or so. You can’t predict when either. I thought John Walker was exaggerating… but it’s true:

As your body chemistry adjusts, other curious things may happen. One day, trapped in a tedious meeting, I began to emit an odor evocative of a roadkill skunk marinated in ratpiss. My esteemed colleagues were either too polite to remark upon this phenomenon, or (more likely) unsure of the culprit, so I managed to escape to the open air unfingered as the malodorous miscreant. This situation persisted for about two weeks, after which it disappeared for good as suddenly as its onset.
Optimizing for fullness per calorie has unexpected effects. Pizza is actually low-calorie when you consider that two slices of pepperoni is only 600 calories and filling. Fruit is also great: 100 calories for a pear.
Alcohol is full of calories. 80 for a shot of whiskey. :x Turns out I’d rather eat some bread than have a beer.
It’s way too easy to blow your budget on soda and juice. Switch to diet soda, iced tea, black coffee, and water. Liquid calories aren’t worth it.
Speaking of, caffeine is awesome. Suppresses appetite and gives you energy.
Body weight is noisy. On any given day, you may be 4 pounds heavier or lighter than the day before. (You can try this at home: drink two bottles of water before weighing yourself.) Some weeks, it will look like you’ve made no progress. It’s infuriating, but hang in there. In the end, your weight graph will be linear.
When it comes to nutrition, everyone’s an expert. “Are you exercising?” No. “Are you eating healthy food?” Do pizza, burritos, and frozen White Castle count? Dieting is hard enough by itself. Actively avoid being too ambitious. It’s much easier to cut calories if you can still eat things you love. Worry about the low-order bits after you hit your target weight.
I used to love the feeling of a full stomach. Now it’s unpleasant. I’ve finally defeated that post-great-depression “EAT EVERYTHING ON YOUR PLATE OR YOU’RE GROUNDED!” instinct.

Getting Through Rough Days

Let’s face it. Some days you’ll screw up and eat too much for breakfast or lunch. At 11:00 p.m. you can’t sleep because you’re too hungry. How do you take the edge off without blowing your calorie budget?

Tomatoes. 35 calories PER! If you like ‘em, chow down.
Cantaloupe. 35 calories per 1/8 melon.
Hot chicken broth in a mug. Warm, tasty, and 50 calories.
Strawberries. 8 calories per delicious berry!
Low-calorie yogurt. 60 calories.
String cheese. 70 calories.
Pickles. ZERO.
Water. ZERO. Somehow, drinking water can make you less hungry!
Also, if you still want crackers or cookies, 100 calorie packs are pretty common these days.

And finally, my secret weapon… Trader Joe’s Whole Wheat Bread. I can’t remember its exact name, but it comes in half-rounds and has three ingredients: whole wheat, water, salt. 200 calories, 16g of protein and 16g of fiber per EXTREMELY FILLING slice. You can eat this stuff until your jaw hurts. It’s epic. However, keep in mind that 16g of fiber is a ton. Stay near a bathroom.

What About Exercise?

Remember the basic equation:

Calories stored = Calories eaten - Calories burned

You can lose weight with exercise, but it’s harder than you’d think. Exercising tends to make me hungry, causing me to eat more than I would normally. Plus, it takes a lot of exercise to burn off a significant number of calories. If you vigorously lifted weights for an hour, you’d only burn ~400 calories, less than a single cheeseburger! You’d have to keep that up every single day without increasing your diet to lose a less than a pound per week. I decided it’s easier to simply eat less.

Note that I’m not saying that exercise is not valuable. Exercise has great health, happiness, and life extension benefits. I just don’t think it’s an efficient way for me to lose weight.

What Next?

What next? I think I’m going to try to drive my weight down a bit further and then replace the pounds of fat lost with muscle. Or maybe I’ll get myself to floss every day. We’ll see!

I always thought weight loss was hard because I’d witnessed people throw themselves at it hardcore and then fail just as hard. In contrast, I chose an easy, long-term, data-driven plan and stuck with it. Small changes over a long time make a big difference.

Fast Builds: Incremental Linking and Embedded SxS Manifests

2009-06-01T03:48:36Z

As I’ve said before, fast builds are crucial for efficient development. But for those of us who use C++ regularly, link times are killer. It’s not uncommon to spend minutes linking your compiled objects into a single binary. Incremental linking helps a great deal, but, as you’ll see, incremental linking has become a lot harder in the last few versions of Visual Studio…

Linking an EXE or DLL is a very expensive operation — it’s roughly O(N) where N is the amount of code being linked. Worse, several optimizing linkers defer code generation to link time, exacerbating the problem! When you’re trying to practice TDD, even a couple seconds in your red-green-refactor iteration loop is brutal. And it’s not uncommon for large projects to spend minutes linking.

Luckily, Visual C++ supports an /INCREMENTAL flag, instructing relinks to modify the DLL or EXE in-place, reducing link time to O(changed code) rather than O(all code). In the olden days of Visual C++ 6, all you had to do was enable /INCREMENTAL, and bam, fast builds.

These days, it’s not so simple. Let’s take an excursion into how modern Windows finds DLL dependencies…

Side-by-Side (SxS) Manifests

Let’s say you’re writing a DLL foo.dll that depends on the CRT by using, say, printf or std::string. When you link foo.dll, the linker will also produce foo.dll.manifest. Windows XP and Vista use .manifest files to load the correct CRT version. (This prevents DLL hell: two programs can depend on different versions of the same DLL.)

Since remembering to carry around .manifest files is annoying and error-prone, Microsoft and others recommend that you embed them into your EXE or DLL as a resource:

mt.exe –manifest foo.dll.manifest -outputresource:foo.dll;2

Convenient, but it modifies the DLL in place, breaking incremental links! This is a known problem, and the “solutions” others suggest are INSANE. My favorite is the 300-line makefile with a note from the author “[If this does not work], please let me know ASAP. I will try fixing it for you.” Why doesn’t Visual Studio just provide an /EMBEDMANIFESTRESOURCE flag that would automatically solve the problem?!

I just want incremental linking and embedded manifests. Is that so much to ask? I tried a bunch of approaches. Most didn’t work. I’ll show them, and then give my current (working) approach. If you don’t care about the sordid journey, skip to the end.

What Didn’t Work

Not embedding manifests at all.

What went wrong: I could never figure out the rules where by manifest dependencies are discovered. If python.exe depends on the release CRT and your module DLL depends on the debug CRT, and they live in different directories (??), loading the module DLL would fail. Gave up.

Linking a temporary file (foo.pre.dll), making a copy (foo.pre.dll -> foo.dll), and embedding foo.pre.dll.manifest into foo.dll with mt.exe.

What went wrong: As far as I can tell, mt.exe is a terrible piece of code. In procmon I’ve watched it close file handles it didn’t open, causing permissions violations down the line. (?!) Sometimes it silently corrupts your EXEs and DLLs too. This may be a known weakness in UpdateResource. Yay! (Thanks to Kevin Gadd; he was instrumental in diagnosing these bugs.) mt.exe may or may not be fixed in recent Visual Studios. Either way, I’m convinced mt.exe has caused us several intermittent build failures in the past. Avoiding it is a good thing.

Linking to a temporary file (foo.pre.dll), generating a resource script (foo.pre.rc) from (foo.pre.dll.manifest), compiling said resource script (foo.pre.res), and including the compiled resource into the final link (foo.dll).

What went wrong: This approach is reliable but slow. Linking each DLL and EXE twice, even if both links are incremental, is often slower than just doing a full link to begin with.

Linking foo.dll with foo.dll.manifest (via a resource script, as above) if it exists. If foo.dll.manifest changed as a result of the link, relink.

I didn’t actually try this one because non-DAG builds scare me. I like the simplicity and reliability of the “inputs -> command -> outputs” build model. It’s weird if foo.dll.manifest is an input and an output of the link. Yes, technically, that’s how incremental linking works at all, but the non-DAG machinery is hidden in link.exe. From SCons’s perspective, it’s still a DAG.

Finally, a working solution:

For every build configuration {debug,release} and dependency {CRT,MFC,…}, link a tiny program to generate said dependency manifest. Compile manifest into a resource script (.rc -> .res) and link the compiled manifest resources into your other DLLs and EXEs.

This approach has several advantages:

These pre-generated manifest resources are created once and reused in future builds, with no impact to build time.
The build is a DAG.
We avoid letting mt.exe wreak havoc on our build by sidestepping it entirely.

I can think of one disadvantage – you need to know up-front on which SxS DLLs you depend. For most programs, the CRT is the only one. And hopefully understanding your dependencies isn’t a bad thing, though. ;)

After several evenings of investigation, we’re back to the same link times we had with Visual C++ 6! Yay!

The Code

If you care, here’s our SCons implementation of embedded manifests:

# manifest_resource(env, is_dll) returns a manifest resource suitable for inclusion into
# the sources list of a Program or SharedLibrary.
manifest_resources = {}
def manifest_resource(env, is_dll):
    if is_dll:
        resource_type = 2 #define ISOLATIONAWARE_MANIFEST_RESOURCE_ID 2
    else:
        resource_type = 1 #define CREATEPROCESS_MANIFEST_RESOURCE_ID  1

    is_debug = env['DEBUG'] # could use a 'build_config' key if we had more than debug/release
    del env

    def build_manifest_resource():
        if is_debug:
            env = baseEnv.Clone(tools=[Debug])
        else:
            env = baseEnv.Clone(tools=[Release])
        env['LINKFLAGS'].remove('/MANIFEST:NO')

        if is_dll:
            linker = env.SharedLibrary
            target_name = 'crt_manifest.dll'
            source = env.File('#/MSVC/crt_manifest_dll.cpp')
        else:
            linker = env.Program
            target_name = 'crt_manifest.exe'
            source = env.File('#/MSVC/crt_manifest_exe.cpp')

        env['OUTPUT_PATH'] = '#/${BUILDDIR}/${IMVU_BUILDDIR_NAME}/%s' % (target_name,)

        obj = env.SharedObject('${OUTPUT_PATH}.obj', source)
        result = linker([env.File('${OUTPUT_PATH}'), '${OUTPUT_PATH}.manifest'], obj)
        manifest = result[1]

        def genrc(env, target, source):
            [target] = target
            [source] = source
            # 24 = RT_MANIFEST
            file(target.abspath, 'w').write('%d 24 "%s"' % (resource_type, source.abspath,))

        rc = env.Command('${OUTPUT_PATH}.rc', manifest, genrc)
        res = env.RES('${OUTPUT_PATH}.res', rc)
        env.Depends(res, manifest)
        return res
    
    key = (is_debug, resource_type)
    try:
        return manifest_resources[key]
    except KeyError:
        res = build_manifest_resource()

        manifest_resources[key] = res
        return res

Fast Builds: Unintrusive Precompiled Headers (PCH)

2009-06-01T00:42:29Z

Fast builds are critical to the C++ programmer’s productivity and happiness. One common technique for reducing build times is precompiled headers (PCH). There’s plenty of literature out there; I won’t describe PCH in detail here.

But one thing that’s always bothered me about PCH is that it affects your code. #pragma hdrstop and #include "StdAfx.h" everywhere. Gross.

I’m a strong believer in clean code without boilerplate, so can’t we do better? Ideally we could make a simple tweak to the build system and see build times magically improve. Enno enticed me with mentions of his fast builds, so I took a look…

Using PCH in Visual C++ requires a header (call it Precompiled.h) that includes all of the expensive dependencies:

#include <vector>
#include <map>
#include <iostream>
#include <fstream>
#include <boost/python.hpp>
#include <windows.h>
#include <mmsystem.h>

Additionally, we need a source file (let’s get creative and call it Precompiled.cpp), which is empty except for #include "Precompiled.h".

Compile Precompiled.cpp with /Yc Precompiled.h to generate Precompiled.pch, the actual precompiled header. Then, use the precompiled header on the rest of your files with /Yu Precompiled.h.

OK, here’s the step that prevented me from using PCH for so long: every single source file in your project must #include "Precompiled.h" on its first line.

That’s ridiculous! I don’t want to touch every file!

It turns out our savior is the /FI option. From the documentation:

This option has the same effect as specifying the file with double quotation marks in an #include directive on the first line of every source file specified on the command line [...]

Exactly what we want!

But wait, doesn’t that mean every .cpp in our project will have access to every symbol included by the PCH? Yes. :( It’s worth the build speedup.

However, explicit physical dependencies are important, and the only way to prevent important things from breaking is by blocking commits if they fail. Since enabling and disabling PCH does not require any code changes, it’s easy enough to add a “disable PCH” option to your build system and run it on your continuous integration server:

If somebody uses std::string but forgets to #include <string>, the build will fail and block commits.

In the end, here’s the bit of SCons magic that lets me quickly drop PCH into a project:

def enable_pch(env, source_file, header):
    if PCH_ENABLED:
        PCH, PCH_OBJ = env.PCH(source_file)
        env['PCH'] = PCH
        env['PCHSTOP'] = header
        env.Append(CPPFLAGS=['/FI' + header])
        return [PCH_OBJ]
    else:
        return [source_file]

Now you can benefit from fast builds with minimal effort and no change to your existing code!