Optimization Goals

In my day job, I've worked with many different teams of programmers. Game engine, game tools, OS, SDK, middleware, test engineers, you name it. Many of the people I work with are the best in the industry, true world-class programmers. And others, well, aren't... and that's okay too. :-)

Personally, I find that I've learned a ton from interacting with all of these different groups.

One of the most important lessons I've learned — and I'm frankly surprised this isn't more widely talked about — is that there are many different and equally valid possible optimization goals in programming.

When I talk to a new team, that's often the first thing I try to find out: what are your primary goals? What are you looking for?

The most common definition of optimization involves improving the runtime speed of the code. For example, game engine programmers are often very focused on this, because they have to cram as much work as they can into one frame — generally either 1/30th of a second (33.3ms) or 1/60th of a second (16.6ms). Naturally, this leads to a lot of counting cycles and downcoding inner loops into assembly.

However, game tool programmers tend to be a little more willing to sacrifice speed in favor of optimizing for other goals: development time, correctness, and ease-of-use. For example, it's often OK to use an unoptimized implementation of some algorithm in a tool, since a high-end PC will run it "fast enough". In other cases a tool might only run infrequently or overnight. Or it might be feasible to simply throw more hardware at the problem.

You also see it among different teams: a studio making a AAA game might be very focused on optimizing runtime speed, while a small indie team might be focused on optimizing for development cost — doing the work as cheaply as possible. These teams will have very different optimization goals, to the point that what the AAA game has downcoded to assembly might be C++ objects and STL in the other.

Then there are the sports games — which live in a fascinating alternate world all their own. These guys have to iterate and ship a new version once a year, every single year! Slipping is simply not an option, so they tend to optimize first for reliability, upgradeability, and ease-of-maintenance.

This got me thinking: what are all the possible optimization goals you might have?

Possible Optimization Goals

Here are some things that you may choose to optimize for in your development. It's impossible to optimize for all of these things simultaneously, but it's common to target more than one.

• runtime speed - Run as fast as possible on your target system. Most of the optimization literature focuses on this. It involves choosing algorithms carefully, choosing your data layout carefully, looking for early exit opportunities, hand-optimizing inner loops, and so on.
  
  
• development time - Complete the engineering work as quickly as possible. In other words, finish the job in a day or a week, rather than a month. Optimizing for development time may mean that you use the highest-level language available that will do the job, along with whatever third-party frameworks you can pull in to solve the problems you need solved. C#, Python, Ruby, etc.
  
  
• development cost - Complete the engineering work as cheaply as possible. This is closely related to development time, but slightly different! The primary difference is the choice of who is doing the work: it might be cheaper (and a better investment) to have an intern use a task as a learning project and work on it for three months, than to have a senior programmer crank it out in three weeks.
  
  
• correctness - Be absolutely sure there are no mistakes or bugs. Bug-free code is always a goal, of course, but sometimes it's even more important than usual. There are two common situations I can think of where correctness is your primary goal: (1) when creating a reference implementation of an algorithm, for possible later optimization. (2) when you're making important architectural decisions based on the results of some investigation or other; you'll generally double- and triple-check the investigation, if you're smart.
  
  
• ease-of-use - Make sure users can grasp your interface quickly and achieve what they need to do. Funnily enough, this applies to both applications (user interfaces) and to middleware (developer interfaces). In both cases, you need to understand how people will expect to use the product. The fastest or easiest way to do things might not be the most understandable.
  
  
• ease-of-maintenance - Make the code so straightforward a monkey could maintain it. Or you, in a few years. ;-) If you've ever had to go back and bug-fix some code that you (or god help you, someone else) wrote more than five years ago, you'll appreciate the value of this. Code that is well-written, easy to read, well-commented, and shaped well to fit the problem is code that is optimized for ease of maintenance. To some extent, this goal can be a cause of "not-invented-here" syndrome; the preference for in-house code is often born from a perfectly rational and reasonable desire to know how to maintain that code.
  
  
• reliability - Never fail. Keep on going in the face of problems. At runtime, if the program gets unexpected input, don't crash: flag it, log it, and continue on with a sensible fallback behavior. At development time, always have a reference implementation to fall back to if the optimized version isn't working. In the extreme, reliability might require a reduction (hopefully small) in average-case performance just to ensure that the code can reliably handle uncommon edge cases. (LibC's memset and memcpy are examples of that.)
  
  
• upgradeability - Make sure every subsystem can be upgraded. This is most commonly achieved with modularity. Good module separation should mean that individual pieces can be swapped out without too much trouble. If you remove modularity in order to run faster with today's situation, then you may be unable to upgrade to handle tomorrow's situation without a full rewrite.
  
  
• iteration time - Minimize the time difference between when you make a change and when you are able to view and test the result. This covers a lot of ground and may include things like build time reduction, file loading, dynamic loading of updated assets, console boot time, and more. This is surprisingly important: the people who write the best software will almost always tell you that rapid iteration is king.

Did I miss any? What are you optimizing for?

Variants of CompareAndSwap

I ran across an interesting issue the other day while trying to make a cross-platform atomics header work on Mac OS X.

Compare-and-Swap (hereafter, CAS) is one of the fundamental atomic primitives: given a working CAS you can implement any other atomic operation.

But there are in fact two common variants of CAS:

    // Returns the old value from *ptr
    int ValueCAS(volatile int *ptr, int compare, int swap);

    // Returns true if a swap occurred
    bool BoolCAS(volatile int *ptr, int compare, int swap);

That's OK, though, because it's theoretically possible to convert either one into the other.

It's trivial to implement BoolCAS in terms of ValueCAS. Here's how you do it:

    // GOOD: this works correctly.
    bool BoolCAS(volatile int *ptr, int compare, int swap) {
        return compare == ValueCAS(ptr,compare,swap);
    }

But for what I was doing, I needed to go the other way around. Mac OS X provides BoolCAS functions in <libkern/OSAtomic.h>, and I needed to convert those to ValueCAS functions.

It turns out to be subtly difficult to go the other way around, and I thought I'd share the reasons why.

First attempt

My first attempt was fairly simple, using just an extra load and branch:

    // BAD: do not use! Broken!
    int ValueCAS(volatile int *ptr, int compare, int swap) {
        if (BoolCAS(ptr,compare,swap))
            return compare;
        else
            return *ptr;
    }

The idea is that if the CAS worked, then the old value of *ptr must have been the same as compare, so we can just return that. That's absolutely correct.

However, if the CAS failed, what was the previous value? I was naïvely re-reading *ptr. But my unit tests (oh yes, this is the kind of thing you unit-test thoroughly) showed that very rarely — once per several million iterations — it would fail to do the right thing.

What was going wrong?

The problem comes down to how callers detect success and failure from ValueCAS. If ValueCAS returns compare, the CAS is assumed to have succeeded. If ValueCAS returns any other value, the CAS is assumed to have failed.

Once we recognize this, we can see that the naïve implementation above has not one, but two failure cases:

1. Spurious CAS failure. This can happen on nearly any system, for a variety of reasons. I'd rather not get too deep into explanations of CPU behavior here, but the typical example might be if an interrupt occurred at exactly the wrong moment. Even if *ptr == compare when the CAS runs, a spurious failure might exit the CAS without changing the value of *ptr. This would cause ValueCAS to incorrectly report success!
2. Race between CAS and reload. If more than one thread is atomically modifying *ptr, then there's a window between the CAS and the reload where *ptr could be changed to anything at all — including getting set back to compare. Again, this would cause ValueCAS to incorrectly report success!

Another approach

One tempting way to fix it is to simply lie about the old value of *ptr. I didn't actually try this, but I'll admit I considered it for a moment:

    // BAD: do not use! Semantically incorrect!
    int ValueCAS(volatile int *ptr, int compare, int swap) {
        if (BoolCAS(ptr,compare,swap))
            return compare;
        else
            return (compare-1); // or any value other than compare
    }

But this is wrong! It breaks the semantics of the CAS. CAS is supposed to return the old value. But the value this function returns is totally bogus, and may never have existed at *ptr. To help imagine why this is bad, consider what might happen if the caller is using the value as a bitmask. We might wind up returning an illegal mask with bits that had never been set. This could have unintended, ugly, subtle side-effects.

Third time's the charm

As far as I can tell, the best way to fix it is by adding both an extra load and two branches:

    // GOOD: works correctly
    int ValueCAS(volatile int *ptr, int compare, int swap) {
        int old;
        do {
            if (BoolCAS(ptr,compare,swap))
                return compare;
            old = *ptr;
        } while (old == compare); // never return compare if CAS failed
        return old;
    }

And sure enough, it's a little heavy-handed, but it works. Proper branch hinting will help, but I'm still a bit surprised that it's so expensive (relatively speaking) to do this conversion.

Can anyone come up with a better way?

A Christmas Present to Myself: My New Office

I've moved my home office from one room of the basement to another.

I know, how boring, but this has given me a much-appreciated chance to completely rip out everything and get rid of the mess and abandoned stuff that I don't really use any more. (Heck, back when I moved into my former office, I was still working for Apple.)

As part of the move, I'm making an effort to make everything as wireless and high-speed as I can.

Upgrades include:

• Tons of electrical outlets. Spent several days with an electrician to get this all done. 3 drops, each three feet apart, and each drop has 4 outlets above the desk and 4 outlets below the desk. Plus we put a bonus 4-outlet drop on the side. Grand total: 28. Yes, twenty-eight! I'm incredibly happy with the result... you have no idea how much I hate power strips. :-)
• Clean wired network. I still had some older Cat-5 cables which kept me from getting maximum throughput. Now all hubs are 1Gb Ethernet and cables are Cat-6 or Cat-5e. This should scale up to 10Gb Ethernet when the time comes.
• Wireless speakers. Specifically, Harman-Kardon SoundSticks II attached to an AirPort Express, driven with iTunes and Airfoil. Yes, I poked fun at AirTunes when it first came out, but it's become surprisingly useful. I do virtually all of my work on a laptop these days, and when I'm in my office I want good sound without having a cable plugged in.
• AirPort Base Station with simultaneous dual-band. I'm getting a little tired of upgrading base stations, honestly. But since I have a ton of devices on my wireless network, and use it to access other machines on my local net, having 802.11n actually run at 802.11n speed is worth it.
• WiEx zBoost YX510-PCS-CEL cellular booster. Properly installed with an antenna on the roof, this has given me 5 bars — in the basement, with AT&T. Infinity percent better than what I could get before! Love it!
• Hawking HBB1 broadband booster. OK, this provides almost no feedback so I'm not actually sure how I'm supposed to measure its effectiveness. But it's cheap, dead simple to set up, and the network feels more responsive with it enabled. With so many wireless devices and no QoS in Apple's AirPort, I figured that having some traffic shaping was better than none.
• Wall-mounted shelf to hold all the networking gear (DSL modem, base station, cell booster, broadband booster). I prefer to keep things off the desk since (ideally) there should be no need to touch this stuff once it's running. Individual wall mounts are out since the walls are concrete. A simple black shelf from Home Depot did the trick nicely — now everything is elevated and out of the way.

I'm also asking Santa for these extras:

• Atomic wall clock, because I enjoy having an analog clock around. And once you've had a clock that automatically sets itself from the WWVB atomic time broadcast, you can't go back.
• Indoor/outdoor thermometer. My new desk is right next to a window, so this is easy. I want one with a wired probe, not wireless, because I prefer it to be reliable and low-maintenance.

(FYI, some of the above are affiliate links. I only ever do that for products that I use myself and that I'm very happy with.)

Removed, and recycled or craigslisted:

• Several 40' runs of cable that are no longer needed, since my desk is now much closer to where the services come into the house.
• Three power strips and two extension cords. Yay!
• Quite a few mystery DC power adapters. Often something like a FireWire hub or USB DVD burner that I used to use and now don't, or a charger for something. I'm not a big gadget freak, but after five years in one place these definitely accumulate. (Seriously, wireless power can't get here fast enough.)
• Last year's AirPort 802.11n base station. Sigh.
• An old 32-bit Gateway PC that doesn't meet my needs any more.
• PowerMac G5 that I no longer use.
• 2 Cinema Displays with ADC connections. These were really a great investment and they lasted an incredibly long time. But sorry ADC, you're dead, and converting you to DVI is an expensive pain in the ass.
• Apple DVI to ADC adapter with broken plastic. Huge by modern standards - about the size of a Mac mini.
• Ancient software and unread books that had piled up on my bookshelf. Yeah, I'm pretty sure that copy of DiskWarrior from 2002 isn't going to do me any good any more.
• My home server. I used to maintain a web and file server at home. (It was a PowerMac G4, nearly ten years old now.) I didn't derive a huge benefit from it, but most of the time the cost was minimal too — just a constant-but-small amount of maintenance. But over time, I found that periodically it created an enormous amount of trouble and expense when a hard drive failed or I needed to upgrade something. I've realized that there's just no value in my messing around with that stuff any more, so I've switched to offsite hosting and online backup.

I've also ordered some new iMacs for work - to use both as a local distributed build cluster, and for local testing. I'm going to put Windows 7 x64 on one, and the other will have OSX 10.6 running a couple of Linux VMs.

One of the nice side benefits is that moving has really given me a chance to clean up the cabling. Every single cable I've installed so far is neat and tidy, either cut to length or neatly bundled with a cable tie — so everything is tangle-free. I'm sure this will only last right up until I need to reconfigure everything in a hurry for some new task, but it's pretty sweet for now. :-)

Done anything nice for your office lately?

The Case Against Insensitivity

One of the most controversial parts of my earlier post, Don't Be a ZFS Hater, was when I mentioned off-handedly in the comments that I don't like case-insensitivity in filesystems.

Boy, did that spur a storm of replies.

I resolved to not pollute the ZFS discussion with a discussion of case-insensitivity and promised to make a separate blog post about it. It took a while, but this is that post. I blame a busy work schedule and an even busier travel schedule. (Recently in the span of two weeks I was in California, Ohio, London, Liverpool, London, Bristol, London, Amsterdam, London, then back to Ohio. Phew!)

Here's Why Case-Insensitive Filesystems Are Bad

I've worked in and around filesystems for most of my career; if not in the filesystem itself then usually a layer just above or below it. I'm speaking from experience when I tell you:

Case-insensitivity is a bad idea in filesystems.

And here's why:

1. It's poorly defined.
2. Every filesystem does it differently.
3. Case-insensitivity is a layering violation.
4. Case-insensitivity forces layering violations upon other code.
5. Case-insensitivity is contagious.
6. Case-insensitivity adds complexity and provides no actual benefit.

I'll expand on each of these below.

It's poorly defined

When I say "case-insensitive", what does that mean to you?

If you only speak one language and that language is English, it probably seems perfectly reasonable: map the letter a to A, b to B, and so on through z to Z. There, you're done. What was so hard about that?

But that's ASCII thinking; the world left that behind a long time ago. Modern systems are expected to deal with case differences in all sorts of languages. Instead of a simple 26-letter transformation, "case insensitivity" really means handling all the other alphabets too.

The problem with doing that, however, is that it brings language and orthography into the picture. And human languages are inherently vague, large, messy, and constantly evolving.

Can you make a strict definition of "case insensitivity" without any hand-waving?

One way to do it is with an equivalence table: start listing all the characters that are equal to other characters. We can go through all the variants of Latin alphabets, including a huge list of accents: acute, grave, circumflex, umlaut, tilde, cedilla, macron, breve, dot, ring, ogonek, hacek, and bar. Don't forget to find all the special ligatures and other letters, too, such as Æ vs æ and Ø vs ø.

Okay, our table is pretty big so far. Now let's start adding in other alphabets with case: Greek, Armenian, and the Cyrillic alphabets. And don't forget the more obscure ones, like Coptic. Phew. It's getting pretty big.

Did we miss any? Well, for any given version of the Unicode standard it's always possible to enumerate all letters, so it's certainly possible to do all the legwork and prove that we've got all the case mappings for, say, Unicode 5.0.0 which is the latest at the time of this writing. But Unicode is an evolving standard and new characters are added frequently. Every time a new script with case is added we'll need to update our table.

There are also some other hard questions for case insensitivity:

• Digraph characters may have three equivalent mappings, depending on how they are being written: all-lowercase, all-uppercase, or title-case. (For example: dz, DZ, or Dz.) But this breaks some case-mapping tables which didn't anticipate the need for an N-way equivalence.

• The German letter ß is considered equal to lowercase ss. Should "Straße" and "STRASSE" be considered equivalent? They are in German. But this breaks some case-mapping tables which didn't anticipate the need for an N-to-M character translation (1:2, in this case).

• Capital letters can significantly alter the meaning of a word or phrase. In German, capital letters indicate nouns, so the word Essen means "food", while the word essen means "to eat". We make similar distinctions in English between proper nouns and regular nouns: God vs god, China vs china, Turkey vs turkey, and so on. Should "essen" and "Essen", or "china" and "China" really be considered equivalent?

• Some Hebrew letters use different forms when at the end of a word, such as פ vs ף, or נ vs ן. Are these equivalent?

• In Georgian, people recently experimented with using an obsolete alphabet called Asomtavruli to reintroduce capital letters to the written language. What if this had caught on?

• What about any future characters which are not present in the current version of the Unicode standard?

Case is a concept that is built into written languages. And human language is inherently messy. This means that case-insensitivity is always going to be poorly defined, no matter how hard we try.

Every filesystem does it differently

Unfortunately, filesystems can't engage in hand-waving. Filesystem data must be persistent and forward-compatible. People expect that the data they wrote to a disk last year should still be readable this year, even if they've had an operating system upgrade.

That's a perfectly reasonable expectation. But it means that the on-disk filesystem specification needs to freeze and stop changing when it's released to the world.

Because our notion of what exactly "case-insensitive" means has changed over the past twenty years, however, we've seen a number of different methods of case-insensitivity emerge.

Here are a handful of the most popular case-insensitive filesystems and how they handle case-mapping:

• FAT-32: ASCII upper- and lower-case letters, but a-z and A-Z are considered identical. Also variable IBM code pages in high ASCII.
• HFS: ASCII upper- and lower-case letters, but a-z and A-Z are considered identical. Also variable Mac encodings in high ASCII.
• NTFS: Case-insensitive in different ways depending on the version of Windows that created the volume.
• HFS+: Case-insensitive with a mapping table which was frozen circa 1996, and thus lacks case mappings for any newer characters.

None of these — except for NTFS created by Vista — are actually up-to-date with the current Unicode specification. That's because they all predate it. Similarly, if a new filesystem were to introduce case-insensitivity today, it would be locked into, say, Unicode 5.0.0's case mappings. And that would be all well and good until Unicode 5.1.0 came along.

The history of filesystems is littered with broken historical case mappings like a trail of tears.

Case-insensitivity is a layering violation

When people argue for case-insensitivity in the filesystem, they almost always give user interface reasons for it. (The only other arguments I've seen are based on contagion, which I'll talk about in a moment.) Here is the canonical example:

My Aunt Tillie doesn't know the difference between letter.txt and Letter.txt. The filesystem should help her out.

But in fact this is a UI problem. The problem relates to the display and management of information, not the storage of this information.

Don't believe me?

• When any application displays items in a window, who sorts them case-insensitively? The filesystem? No! The application does it.

• When you type-select, typing b-a-b-y to select the folder "Baby Pictures" in an application, who does the case-insensitive mapping of the letters you type to the files you select? The filesystem? No! The application again.

• When you save or copy files, who does the case-insensitive test to warn you if you're creating "file.txt" when "File.txt" already exists? The filesystem? Yes!

Why does the third question have a different answer than the rest?

And we've already talked about how filesystems are chronically out-of-date with their case mappings. If your aunt is a Turkish Mac user, for example, she's probably going to notice that the behavior of the third one is different for no good reason. Why are you confusing your Aunt Tülay?

One last point was summarized nicely by Mike Ash in the comments of Don't Be a ZFS Hater. I'll just quote him wholesale here:

Yes, Aunt Tillie will think that "Muffin Recipe.rtf" and "muffin recipe.rtf" ought to be the same file. But you know what? She'll also think that "Muffin Recipe .rtf" and "Recipe for Muffins.rtf" and "Mufin Recipe.txt" ought to be the same file too.

Users already don't generally understand how the OS decides whether two files are the same or not. Trying to alleviate this problem by mapping names with different case to the same file solves only 1% of the problem and just isn't worth the effort.

I agree completely.

Case-insensitivity forces layering violations upon other code

All too often, pieces of code around the system are required to hard-code knowledge about case-insensitive filesystem behavior. Here are a few examples off the top of my head:

• Collision prediction. An application may need to know if two files would conflict before it actually writes either of them to disk. If you are writing an application where a user creates a group of documents — a web page editor, perhaps — you may need to know when banana.jpg and BANANA.JPG will conflict.
  
  The most common way that programmers solve this is by hard-coding some knowledge about the case-insensitivity of the filesystem in their code. That's a classic layering violation.

• Filename hashing. If you are writing code to hash strings that are filenames, you probably want equivalent paths to generate the same hash. But it's impossible to know which files are equivalent unless you know the filesystem's rules for case-mapping.
  
  Again, the most common solution is a layering violation. You either hard-code some knowledge about the case-insensitivity tables, or you hard-code some knowledge about your input data. (For example, you may just require that you'll never, never, ever have multiple access paths for the same file in your input data. Like all layering violations, that might work wonderfully for a while ... right up until the day that it fails miserably.)

I'm sure there are more examples out there.

Case-insensitivity is contagious

This is the worst part. It's all too easy to accidentally introduce a dependence on case-insensitivity: just use an incorrect path with bad case.

The moment somebody creates an application or other system that inadvertently depends on case-insensitivity, it forces people to use a case-insensitive filesystem if they want to use that app or system. And that's one of the major reasons why case-insensitivity has stuck around — because it's historically been very difficult to get rid of.

I've seen this happen with:

• Source code. Some bozo writes #include "utils.h" when the file is named Utils.h. Sounds innocent enough, until you find that it's repeated dozens of times across hundreds of files. Now that project can only ever be compiled on a case-insensitive filesystem.

• Game assets. A game tries to load lipsync.dat instead of LIPSYNC.DAT. Without knowing it, the artist or developer has accidentally locked that game so that it can only run on a case-insensitive filesystem. (This causes real, constant problems in game pipelines; teams create and test their games on case-insensitive NTFS and don't notice such problems until it's burned to a case-sensitive UDF filesystem on DVD or Blu-Ray.)

• Application libraries. DLLs and shared library references are sometimes generated by a build script which uses the wrong case. When that happens, the application may simply fail to launch from a case-sensitive filesystem.

• Miscellaneous data files. Sometimes an application will appear to run on a case-sensitive filesystem but some feature will fail to work because it fails to load a critical data file: the spell-checking dictionary, a required font, a nib, you name it.

Happily, since Mac OS X shipped in 2001, Apple has been busy solving its own problems with case-insensitivity and encouraging its developers to test with case-sensitive filesystems. Two important initiatives in this direction have been NFS home directories and case-sensitive HFSX.

The upshot of it is that Mac OS X is actually very friendly to case-sensitive disks these days; very little that's bad happens when you use case-sensitive HFSX today.

Case-insensitivity adds complexity with no actual benefit

I'm going to make an assertion here:

ONE HUNDRED PERCENT of the path lookups happening on your Mac right now are made with correct case.

Think about that for a moment.

First off, you may think this contradicts the point I just made in the previous section. Nope; I'm simply rounding. The actual figure is something like 99.999%, and I'd probably get tired of typing 9's before I actually approached the real number. There are infinitesimally few path accesses made with incorrect case compared to the ones that are made with the proper case.

Modern computers make hundreds of filesystem accesses per second. As I type this single sentence in MarsEdit on Mac OS X 10.4.11, my computer has made 3692 filesystem accesses by path. (Yes, really. MarsEdit's "Preview" window is invoking Perl to run Markdown, which loads a handful of modules, and then WebKit re-renders the page. That's a lot of it, but meanwhile there's background activity from Mail, Activity Monitor, iChat, SystemUIServer, iCalAlarmScheduler, AirPort Base Station Agent, Radioshift, NetNewsWire, Twitterrific, and Safari.)

Under Mac OS X you can measure it yourself with this command in Terminal:

  sudo fs_usage -f filesys | grep / > /tmp/accesses.txt

The vast majority of file accesses are made with paths that were returned from the filesystem itself: some bit of code read the contents of a directory, and passed the results on to another bit of code, which eventually decided to access one of those files. So most of the time the filesystem is getting back the paths that it has returned earlier. Very very few accesses are made with paths that come directly from an error-prone human, which is why essentially 100% of filesystem accesses are made with correct case.

But if essentially all filesystem accesses are made with the correct case to begin with, why do we even have case-insensitivity at all?

We've already discussed the problems of contagion, which is a circular justification: we have to do it because someone else did it first. We've also discussed UI decisions being incorrectly implemented in the bottommost layer of the operating system. Other than those two, what good is it?

I don't have an answer to that. For the life of me I can't come up with any reason to justify case-insensitive filesystems from a pure design standpoint. That leads me to my closing argument, which is...

A thought experiment

Suppose case-insensitive filesystems had never been invented. You're the leader of a team of engineers in charge of XYZZYFS, the next big thing in filesystems. One day you tell the other people who work on it:

"Hey! I've got this great idea! It's called case-insensitivity. We'll take every path that comes into the filesystem and compare it against a huge table to create a case-folded version of the path which we'll use for comparisons and sorting. This will add a bunch of complexity to the code, slow down all path lookups, increase our RAM footprint, make it more difficult for users of our filesystem to handle paths, and create a compatibility nightmare for future versions if we ever decide to change the table. But, you see, it'll all be worth it, because... _________________."

Can you fill in the blank?

ZFS Hater Redux

MWJ has responded to my last post, Don't Be a ZFS Hater, with a post of their own: You don't have to hate ZFS to know it's wrong for you.

I don't like the point-by-point quote and response format — it's way too much like an old-school Usenet flamewar. So I will simply try to hit the high points of their arguments.

Where we agree

• ZFS is not ready to deploy to the entire Mac OS X user base today. There's still some work to be done.

• ZFS isn't necessary for most of today's Macintosh computers. If you have been using your Mac with no storage-related problems, then you can keep on using it that way. Perform regular backups and you'll be just fine.

• It would be an absolutely terrible idea to take people's perfectly working HFS+ installations on existing computers and forcibly convert them to ZFS, chuckling evilly all the while. Not quite sure where that strawman came from.

• ZFS fatzaps are expensive for small files. If it were true that 20% of the files in a Mac OS X installation required a fatzap (pdf link to ZFS-on-disk specification), that would indeed be unnecessarily wasteful.

• A typical Mac OS X 10.4.x installation has on the order of about 600,000 files.

I think that's about it. But of course there are a number of places where we disagree too.

ZFS would be awfully nice for a small segment of the Mac OS X user base if it were ready today.

If you spend any amount of time managing storage — if drives have gone bad on you, if you have ever run out of space on a desktop system and needed to add a drive (or two), if you have a RAID array — then you are the sort of user that could see some immediate benefit.

But of course as we already agreed, it's not ready today. You haven't been "cheated" and I'm sure you don't feel that way. But feel free to look forward to it: I sure am.

ZFS — or something with all the features of ZFS — will be more than nice, it will be necessary for tomorrow's Macintosh computers.

Both storage sizes and consumer consumption of storage grow exponentially. I tried to make this point last time, but MWJ seems to have misunderstood and accused me of misquoting. Let's try again.

In 1997, 20GB of storage meant a server RAID array. Ten years later, in 2007, 20GB of storage is considered "not enough" by most people. Across my entire household I have drives larger than that in my computer, in my TiVo, in my PlayStation 3, and even in my iPod. Now let's extrapolate that into the future.

In 2007, 20TB of storage means a server RAID array. Ten years from now, in 2017, 20TB of storage will similarly be considered "not enough". MWJ scoffed at ZFS because it's really pretty good at the problems of large storage. But you know what? A solution to managing that much data will need to be in place in Mac OS X well before 20TB drives become the norm. Better hope someone's working on it today.

Meanwhile — and this is what scares the pants off me — the reliability numbers for hard drives have improved much more slowly than capacity.

Here's a fairly typical Seagate drive with a capacity of ~150GB = ~1.2 x 10¹² bits. The recoverable error rate is listed as 10 bits per 10¹² bits. Let's put those numbers together. That means that if you read the entire surface of the disk, you'll typically get twelve bits back that are wrong and which a retry could have fixed. (Updated Oct 11 2007: In the comments, Anton corrected me: I should've used the unrecoverable error rate here, not the recoverable error rate. The net result is that in ideal operating conditions bit errors occur over 100x less frequently than I originally suggested. However, it's still not zero. The net result is still a looming problem when you scale it across (installed base) x (storage consumption) x (time). See the comment thread.)

Yes, really. Did you catch the implications of that? Silent single-bit errors are happening today. They happen much more often at high-end capacities and utilizations, and we often get lucky because some types of data (video, audio, etc) are resistant to that kind of single-bit error. But today's high end is tomorrow's medium end, and the day after tomorrow's low end. This problem is only going to get worse.

Worse, bit errors are cumulative. If you read and get a bit error, you might wind up writing it back out to disk too. Oops! Now that bit error just went from transient to permanent.

Still think end-to-end data integrity isn't worth it?

Apple using ZFS rather than writing their own is a smart choice.

As I hope I made abundantly clear in the last post, extending HFS+ to the future that we can see looming is just not an option — its structure is simply too far removed from these problems. It's really just not worth it. It's pretty awesome that the original HFS design scaled as far as it did: how many people can come up with a 20-year filesystem? But you have to know when to throw in the towel.

So if you accept that the things I described above are real, looming problems, then Apple really does need a filesystem with at least several of the more important attributes of ZFS.

The choices at this point are essentially twofold: (1) start completely from scratch, or (2) use ZFS. There's really no point in starting over. ZFS has a usable license and has been under development for at least five years by now. By the time you started over and burned five years on catching up it would be too late.

And I really do want to reiterate that the shared community of engineers from Apple, Sun, and FreeBSD working on ZFS is a real and measurable benefit. I've heard as much from friends in CoreOS. I can't understand the hostility to this very clear and obvious fact. It's as if Apple suddenly doubled or tripled the number of filesystem engineers it has available, snagging some really brilliant guys at the top of their profession in the process, and then multiplied its testing force by a factor of 10.

(To respond to a query voiced by MWJ, HFS+ never gathered that community when it was open-sourced because the design was already quite old at that point. It frankly didn't have anything new and exciting to offer, and it was saddled with performance problems and historical compromises of various kinds, so very few people were interested in it.)

ZFS fatzaps are unlikely to be a significant problem.

This gets a bit technical. Please skip this section if you don't care about this level of detail.

MWJ really pounded on this one. That was a bit weird to me, since it seemed to be suggesting that Apple would not expend any engineering effort on solving any obvious glaring problems with ZFS before releasing it. That's not the Apple I know.

But okay, let's suppose that we're stuck with ZFS and Mac OS X both frozen as they stand today. Let's try to make an a priori prediction of the actual cost of ZFS fatzaps on a typical Mac OS X system.

• Classic HFS attributes (FinderInfo, ExtendedFinderInfo, etc) are largely unnecessary and unused today because the Finder uses .DS_Store files instead. In the few cases where these attributes are set and used by legacy code, they should fit easily in a small number of microzaps.

• Extended attributes may create fatzaps. Today it seems like extended attributes are typically used on large files: disk images, digital photos, etc. This may provoke squawking from the peanut gallery, but once a file is above a certain size — roughly a couple of megabytes — using an extra 128KiB is negligible. If you have a 4MiB file and you add 128KiB to track its attributes, big deal: you've added 3%. It's not nothing, but it's hardly a significant problem.

• Another likely source of fatzaps in ZFS on Mac OS X is the resource fork. But with Classic gone, new Macs ship with virtually no resource forks on disk. There are none in the BSD subsystem. There are a handful in /System and /Library, mostly fonts. The biggest culprits are large old applications like Quicken and Microsoft Office. A quick measurement on my heavily-used one-year-old laptop shows that I have exactly 1877 resource forks out of 722210 files — that's 0.2%, not 20%.

  (Fun fact: The space that would be consumed by fatzap headers for these resource files comes out to just 235 MiB, or roughly six and a half Keyboard Software Updates. Again: not nothing, but hardly a crisis to scream about.)

Want to measure it yourself? Amit Singh's excellent hfsdebug utility will show you a quick summary. Just run "sudo hfsdebug -s" and look at the numbers for "files" and "non-zero resource forks". Or try "sudo hfsdebug -b attributes -l any | less" to examine the files which have extended attributes on your disk.

ZFS snapshots don't have to be wasteful

The cheesesteak analogy was cute. But rather than imagining that snapshots just eat and eat and eat storage until you choke in a greasy pile of death, it would help if we all actually understand how hard drive storage is actually used in practice, and how ZFS can work with that.

There are three major classes of stored data.

• Static data is data that you want to keep and almost never modify. This is your archive. Photographs, music, digital video, applications, email, etc. Archives are additive: unless you really run out of room, you rarely delete the old — you only add new stuff. You want the contents safe and immediately accessible, but they are essentially unchanging.

Snapshotting static data is close enough to free that you won't notice: the only cost is the basic cost of the snapshot. No extraneous data copies are ever created, because you never modify or delete this stuff anyway.

• Dynamic data is data that you want to keep, but are modifying with some frequency. This is whatever you are working on at the moment. It might be writing a novel, working in Photoshop, or writing code: in all cases you keep saving new versions over the old.

Snapshotting dynamic data is more expensive, because if you do it too much without recycling your old snapshots then you can build up a large backlog.

• Transient data is data that should not be persistent at all. These are your temporary files: local caches, scratch files, compiler object files, downloaded zip files or disk images, etc. These may be created, modified, or deleted at any moment.

Snapshotting transient data is generally a bad idea — by definition you don't care that much about it and you'd prefer it to be deleted immediately.

Got all that? Okay. Now I need to make a couple of points.

First, I assert that virtually all of the data on personal computer hard drives is static most of the time. Think about that. The operating system is static the whole time you are using it, until you install a system update. (And even then, usually just a few hundred megabytes change out of several gigabytes.) Your /Applications folder is static. Your music is static. And so on. Usually a few percent of your data is dynamic, and a few more percent is transient. But in most cases well over 95% is static. (Exceptions are easy to come up with: Sometimes you generate a large amount of transient data while building a disk image in iDVD or importing DV footage. That can shift the ratio below 95%. But once that task is complete you're back to the original ratio.)

Second, the biggest distinction that matters when snapshotting is separating persistent data from transient data. Taking snapshots of transient data is what will waste disk space in a hurry. Taking snapshots of dynamic data as a local backup is often valuable enough that it's okay to burn the small amount of disk space that it takes, because remember: that's the actual data that you're actively working on. And as we already mentioned, snapshots of static data are free.

Now here's where it gets interesting.

With ZFS, snapshots work on the filesystem level. Because it no longer uses the "big floppy" model of storage, new filesystems are very cheap to create. (They are almost as lightweight as directories, and often used to replace them.) So let's create one or more special filesystems just for transient data and exclude them from our regular snapshot process. In fact on Mac OS X that's easy: we have well-defined directories for transient data: ~/Library/Caches, /tmp, and so on. Link those all off to one or more transient filesystems and they will never wind up in a snapshot of the important stuff. I wouldn't expect users to do this for themselves, of course — but it could certainly be set up that way automatically by Apple.

Once the transient data is out of the picture, our snapshots will consist of 95% or more static data — which is not copied in any way — and a tiny percentage of dynamic data. And remember, the dynamic data is not even copied unless and until it changes. The net effect is very similar to doing an incremental backup of exactly and only the files you are working on. This is essentially a perfect local backup: no duplication except where it's actually needed.

Will you want to allow snapshots to live forever? Of course not. One reasonable model for taking backup snapshots might be to remember 12 hourly snapshots, 7 daily snapshots, and 4 weekly snapshots. If you are getting tight on storage the system could take new snapshots less frequently and expire them more aggressively. Remember: when nothing is changing the snapshots don't take up any space.

Wrap-up: Listen to the smart guys

Some very smart people at Sun started the ball rolling by putting an awful lot of thought into the future of storage, and they came up with ZFS.

After they announced it and started talking about it, other brilliant people at Apple (and FreeBSD, and NetBSD) paid attention to what they were doing. And they listened, and thought about it, and looked at the code, and wound up coming around to the side of ZFS as well.

If you think I'm smart, just know that I'm in awe of some of the guys who've been involved with this project.

If you think I'm stupid, why, I look forward to hearing from you in the comments.

Don't be a ZFS Hater

John Gruber recently linked to — and thus gave credibility to — a MWJ post ripping on a fairly reasonable AppleInsider post about ZFS. Representative quote:

“We don't find HFS Plus administration to be complex, and we can't tell you what those other things mean, but they sound really cool, and therefore we want them. On the magic unlocked iPhone. For free.”

Har har har. Wait. Hold on a minute. Why is it suddenly fashionable to bash on ZFS?

Part of it is a backlash to the weird and obviously fake rumor about it becoming the default in Leopard, I guess. (No thanks to Sun's CEO Jonathan Schwartz here, who as far as I know has never publicly said anything about why he either misspoke or misunderstood what was going on back in June.)

But don't do that. Don't be a ZFS hater.

A word about my background

Let's get the credentials out of the way up front. Today I work on a file I/O subsystem for PlayStation 3 games. Before that, I worked in Apple's CoreOS filesystems group. Before that, I worked on DiscRecording.framework, and singlehandedly created the content subframework that streamed out HFS+, ISO-9660, and Joliet filesystems. Before that, I worked on the same thing for Mac OS 9. And before that, I worked on mass storage drivers for external USB/FireWire drives and internal ATA/ATAPI/SCSI drives.

You might say I know a thing or two about filesystems and storage.

What bugged me about the article

1. ZFS is a fine candidate to replace HFS+ eventually. It's not going to happen overnight, no. And it'll be available as an option for early adopters way before it becomes the default. But several years from now? Absolutely.

2. The bizarre rants about ZFS wasting processor time and disk space. I'm sorry, I wasn't aware that we were still using 30MHz machines with 1.44MB floppies. ZFS is great specifically because it takes two things that modern computers tend to have a surplus of — CPU time and hard disk space — and borrows a bit of it in the name of data integrity and ease of use. This tradeoff made very little sense in, say, 1992. But here in 2007 it's brilliant.

3. Sneeringly implying that HFS+ is sufficient. Sure, HFS+ administration is simple, but it's also inflexible. It locks you into what I call the "big floppy" model of storage. This only gets more and more painful as disks get bigger and bigger. Storage management has come a long way since the original HFS was created, and ZFS administration lets you do things that HFS+ can only dream of.

4. Claiming that RAID-Z is required for checksums to be useful. This is flat-out wrong. Sure, RAID-Z helps a lot by storing an error-correcting code. But even without RAID-Z, simply recognizing that the data is bad gets you well down the road to recovering from an error — depending on the exact nature of the problem, a simple retry loop can in fact get you the right data the second or third time. And as soon as you know there is a problem you can mark the block as bad and aggressively copy it elsewhere to preserve it. I suppose the author would prefer that the filesystem silently returned bad data?

5. Completely ignoring Moore's Law. How dumb do you need to be to willfully ignore the fact that the things that are bleeding-edge today will be commonplace tomorrow? Twenty gigabyte disks were massive server arrays ten years ago. Today I use a hard drive ten times bigger than that just to watch TV.

Reading this article made me feel like I was back in 1996 listening to people debate cooperative vs preemptive multitasking. In the Mac community at that time there were, I'm ashamed to say, a lot of heated discussions about how preemptive threading was unnecessary. There were some people (like me) who were clamoring for a preemptive scheduler, while others defended the status quo — claiming, among other things, that Mac OS 8's cooperative threads "weren't that bad" and were "fine if you used them correctly". Um, yeah.

Since then we've thoroughly settled that debate, of course. And if you know anything about technology you might be able to understand why there's a difference between "not that bad" and "a completely new paradigm".

ZFS is cool

Let's do a short rundown of reasons why I, a qualified filesystem and storage engineer, think that ZFS is cool. I'll leave out some of the more technical reasons and just try to keep it in plain English, with links for further reading.

• Logical Volume Management. Hard disks are no longer big floppies. They are building blocks that you can just drop in to add storage to your system. Partitioning, formatting, migrating data from old small drive to new big drive -- these all go away.

• Adaptive Replacement Caching. ZFS uses a smarter cache eviction algorithm than OSX's UBC, which lets it deal well with data that is streamed and only read once. (Sound familiar? It could obsolete the need for F_NOCACHE.)

• Snapshots. Think about how drastically the trash can metaphor changed the way people worked with files. Snapshots are the same concept, extended system-wide. They can eliminate entire classes of problems.

  I don't know about you, but in the past year I have done all of the following, sometimes more than once. Snapshots would've made these a non-issue:

  • installed a software update and then found out it broke something
  • held off on installing a software update because I was afraid something might break
  • lost some work in between backups
  • accidentally deleted an entire directory with a mistyped rm -rf or SCM delete command.

• Copy-on-write in the filesystem makes snapshots super-cheap to implement. No, not "free", just "so cheap you wouldn't possibly notice". If you are grousing about wasted disk space, you don't understand how it works. Mac OS X uses copy-on-write extensively in its virtual memory system because it's both cheap and incredibly effective at reducing wasted memory. The same thing applies to the filesystem.

• End-to-end data integrity. Journaling is the only thing HFS+ does to prevent data loss. This is hugely important, and big props are due to Dominic Giampaolo for hacking it in. But journaling only protects the write stage. Once the bits are on the disk, HFS+ simply assumes they're correct.

  But as disks get larger and cheaper, we're finding that this isn't sufficient any more. The odds of any one bit being wrong are very small. And yet the 200GB hard disk in my laptop has a capacity of about 1.6 trillion bits. The cumulative probability that EVERY SINGLE ONE of those bits are correct is effectively zero. Zero!

  Backups are one answer to this problem, but as your data set gets larger they get more and more expensive and slow. (How do you back up a terabyte's worth of data? How long does it take? Worse still, how do you really know that your backup actually worked instead of just appearing to work?) So far, disk capacity has consistently grown faster than disk speed, meaning that backups will only continue to get slower and slower. Boy, wouldn't it be great if the filesystem — which is the natural bottleneck for everything disk-related — helped you out a little more on this? ZFS does.

• Combinations of the above. There are some pretty cool results that fall out of having all of these things together in one place. Even if HFS+ supported snapshots, you'd still be limited by the "big floppy" storage model. It really starts to get interesting when you combine snapshots with smart use of logical volume management. And we've already discussed how RAID-Z enhances ZFS's basic built-in end-to-end data integrity by adding stronger error correction. There are other cool combinations too. It all adds up to a whole which is greater than the sum of its parts.

Is any of this stuff new and unique to ZFS? Not really. Bits and pieces of everything I've mentioned above have showed up in many places.

What ZFS brings to the table is that it's the total package — everything all wrapped up in one place, already integrated, and in fact already shipping and working. If you happened to be looking for a next-generation filesystem, and Apple is, you wouldn't need to look much further than ZFS.

Still not convinced?

Okay, here are three further high-level benefits of ZFS over HFS+:

• Designed to support Unix. There are a lot of subtleties to supporting a modern Unix system. HFS+ was not really designed for that purpose. Yes, it's been hacked up to support Unix permissions, node locking, lazy zero-fill, symbolic links, hard links, NFS readdir semantics, and more. Some of these were easy. Others were painful and exhibit subtle bugs or performance problems to this day.

• Designed to support modern filesystem concepts. Transactions. Write cache safety. Sparse files. Extended metadata attributes. I/O sorting and priority. Multiple prefetch streams. Compression. Encryption. And that's just off the top of my head.

  HFS+ is 10-year-old code built on a 20-year-old design. It's been extended to do some of this, and could in theory be extended to do some of the others... but not all of them. You'll just have to trust me that it's getting to the point where some of this stuff is just not worth the engineering cost of hacking it in. HFS+ is great, but it's getting old and creaky.

• Actually used by someone besides Apple. Don't underestimate the value of a shared standard. If both Sun and Apple start using the same open-source filesystem, it creates a lot of momentum behind it. Having more OS clients means that you get a lot more eyes on the code, which improves the code via bugfixes and performance enhancements. This makes the code better, which makes ZFS more attractive to new clients, which means more eyes on the code, which means the code gets better.... it's a virtuous circle.

Is ZFS the perfect filesystem? I doubt it. I'm sure it's got its limitations just like any other filesystem. In particular, wrapping a GUI around its administration options and coming up with good default parameters will be an interesting trick, and I look forward to seeing how Apple does it.

But really, seriously, dude. The kid is cool. Don't be like that.

Don't be a ZFS hater.

Updates:

MWJ's response: You don't have to be a ZFS hater to know it's wrong for you.
My followup: ZFS Hater Redux

Microbenchmarking

I want to talk a little about a technique that can be very useful. Like all programming tools, however, it's a double-edged sword and can easily be abused.

I'm talking about microbenchmarks. A microbenchmark is a form of benchmark. Let's quickly define our terms:

Benchmark

noun: a relative measure of the performance of an operation (or set of operations) in computer software. Many factors may be used to create this measure, such as memory use or I/O, but when unspecified the measure is usually speed.

verb: to create or run a benchmark.

Microbenchmarks

Sometimes the term "benchmark" is too broad. I want to specifically talk about single benchmarks that are limited in scope. One commonly used term for this is "microbenchmark".

Microbenchmark

noun: a benchmark that measures the performance of a single operation which is a very small portion of a larger system.

verb: to create or run a microbenchmark.

I would consider each of the following to be an example of a microbenchmark:

• Implementation comparisons. Suppose you are choosing between multiple implementations of the C standard library routine strcmp(). You might use a microbenchmark to compare different implementations against each other until you find the one that's right for you.

• Equivalent function comparison. Sometimes there's more than one way to achieve your goal. If you want to know which is faster, you might use a microbenchmark to compare the different functions.

• Inter-language primitive comparisons. Microbenchmarks are often used to compare programming languages. For example, Java, C++, and C# are often microbenchmarked to see which has the faster string comparison, stack allocation, heap allocation, and so on.

• Individual aspects of a large system's performance. Examples might include adding a row to a database table, sorting a large list of input files, or even application launch time. These aspects may be measured in isolation (i.e., without a strict performance target) with the presumption that speeding them up is generally useful, since the end user's experience is comprised of lots of these small operations.

I think the last example above is the most generic description of a microbenchmark, because it encompasses the others. When you are benchmarking strcmp(), you are really measuring an individual aspect of the C library's performance. And when you are comparing language primitives, you are again measuring an individual aspect of the language's performance.

The prefix "micro-" is relative, of course. If your job description is "Chief Programmer: strcmp()", then measuring the performance of strcmp() is simply benchmarking, not microbenchmarking. But if you are working on a large modern GUI application for a consumer OS, measuring the performance of strcmp() becomes a microbenchmark because it's such a small part of your overall system.

Losing Track of the Macro

Before I start talking about how to do microbenchmarks, there's an important point to be made. Improperly applied microbenchmarks can actually be hazardous to real-world performance.

Benchmarking goes hand-in-hand with optimization when it's done correctly. You benchmark first, and then optimize. Similarly, microbenchmarking goes hand-in-hand with microoptimization. And microoptimization is rarely a good idea.

That's not to say that microbenchmarks are bad. They can be really useful when applied correctly. I remember the competitions at Apple to create the fastest BlockMove for PowerPC, which were often repeated with each new generation of processor. Since it was one of the most heavily-used system calls in the Mac OS, each incremental improvement made the OS faster. Many individual benchmarks, such as drawing and text manipulation, got faster whenever BlockMove was improved.

The danger comes not from the microbenchmarking itself. The real problem occurs when you focus so much on the micro that you forget about the big picture. There are three main negative outcomes possible:

Dangers of Microbenchmarking and Microoptimization

• Wasting development time. Newbie programmers sometimes burn weeks optimizing something that doesn't really need optimizing. This doesn't matter much when you're doing it as a hobby, but it matters a lot when you're in a real job.

• Making something else slower. Sometimes performance can be like a carpet. Push it down over here, and it pops up over there. If the operation that you're microbenchmarking does not crop up often in real-world scenarios, you may find that all your micro-optimizing actually decreases your real-world performance.

• Introducing bugs. Sloppy optimization can be worse than no optimization. Your code might work today, but the trick you used might not be future-proof.

Performance is Chunky

There are two important lessons that I've learned about software performance over the years:

Lesson 1: Performance is "chunky". Not all parts of the code contribute equally to the software's speed. A small piece of code might turn out to be a very big chunk of the performance, and a big piece of code might be almost immaterial. You need to know what your chunks look like before you can optimize intelligently.

Lesson 2: Design trumps everything. Choosing the right design or algorithm for your code is far more important than almost any microoptimization you can make. If your code calls strcmp() 4 million times in a loop, you're better off changing your design to call it less often. There's no reason to waste time looking for a faster strcmp().

From these two lessons we can pretty easily derive the types of optimizations that work best. Here they are, from most effective to least effective:

Ordered Rules for Optimization

Want to make your code faster? Follow these rules in order.

1. Design for efficiency. Understand the real task. Eliminate redundancy. Understand how your algorithm is performing, and the ways it might not be optimal. Redesign the whole thing until it is optimal.

2. Optimize areas where your code spends a lot of time. Sometimes there is an inner loop which is repeated millions of times. The first answer is always rule #1: "don't do that" — try to redesign your code to reduce the number of times you perform that operation. But if it truly can't be avoided, then go ahead and expend some effort on speeding it up.

3. Microoptimization. Pick a single operation and make it faster in isolation. This is almost always the wrong thing to do.

Why are microbenchmarking and microoptimization almost always wrong? Because you should be taking care of #1 or #2 first. And the fundamental essence of programming is that the first two are never complete.

When should you microbenchmark?

If you are writing part of an operating system, a virtual machine, or the runtime for a programming language. Compiler writers may also microbenchmark the output of their compiler.

Very occasionally, it might be useful to do it as part of the first two optimization tasks. Perhaps you're choosing between different algorithms, one which involves calling functionA() a thousand times, and one which involves calling functionB() a thousand times. Rather than writing two complete implementations and comparing them, it might be instructive to do a quick microbenchmark to see which of the two is faster in isolation.

You can also do it for your own amusement and education, or for a blog entry. While not terribly useful, it can be informative and teach you a thing or two about your OS.

How to write a microbenchmark

With all that said, let's get down to the details. Suppose that you eventually find yourself in a position where you really do need to run a microbenchmark.

I use a ten-step process:

1. Consider all the factors that may impact performance. There may be non-obvious considerations like memory alignment, cache characteristics, or data set size. Decide exactly how you want to test your operation with those factors in mind.

2. Write a loop to perform the operation a large number of times. Any single measurement might be way off, because your computer is busy doing all sorts of things like processing interrupts in the background that are out of your control. So you need to average over a longish interval. Try starting with about a hundred thousand iterations, then add multiples of ten until you wind up with a total runtime of a second or two.

3. Use a high-resolution timer to record the start and stop time. Your data is only as good as your timer. Find the best one available. On Mac OS X that's mach_absolute_time(), and on Windows it's QueryPerformanceCounter(). Other platforms usually have an equivalent high-resolution timer. Call it only twice: once before the big loop, and once after.

4. Write code to compute the result. The approximate time it takes for a single operation will be elapsedTime / numberOfIterations. The elapsedTime is generally (stopTime - startTime) / timerFrequency. Watch out for integer overflow and floating-point precision loss: it's easiest to just use double-precision math.

5. Consider whether you should compile your code at the highest optimization level available. Compilers generate significantly slower code when optimization is off. You're almost certainly interested in the performance of the fully optimized build rather than the unoptimized debug build, but optimization can introduce its own difficulties. It depends on what exactly you're benchmarking.

6. Compile, then disassemble your test to make sure it's really doing what you think it's doing. This step is non-negotiable!! If you can't read assembly, you shouldn't be doing microbenchmarking. Compilers can be tricky and there's no guarantee that it's actually doing what you think it's doing until you look. If you are testing strcmp(), for example, you might find that the compiler has decided to optimize out all ten million calls in your inner loop because you're using a string constant instead of a variable. Or perhaps your ten million iterations of input = input + 1 are being optimized out to input = input + 10000000. If this is happening to you, you'll need to figure out a way to force the compiler to do what you want. With gcc, for example, you might need to link functions in via separate modules to prevent inlining, or specify additional flags on the command line.

7. Quiesce your system. You don't have to shut everything down, but do make sure that you're not running under abnormally heavy load. Most systems these days have a CPU meter which can tell you what's going on. If you're writing code on an embedded system, make sure that any asynchronous startup operations (like initializing the network stack) have finished before you begin.

8. Run the test and get the results. If it runs too quickly or too slowly, you might need to adjust your iteration count and try again. If you get what looks like a good result, there's one more step:

9. Run the test several more times and make sure your result is reproducible. This will also give you an idea of the typical error in your measurement.

10. If you support different platforms or processors, run the test on each one. Sometimes constructs which work well with one processor are the worst-case for another. Occasionally operating systems will change the implementation of their standard library functions enough to perturb performance. Don't assume that just because it's faster on one configuration that it will always be faster everywhere.

Code Sample

Here's a piece of sample code I wrote to microbenchmark the speed of a function call on Mac OS X. I've removed the function body in order to simply show the overall technique.

/* foo.cpp */
#include <stdio.h>
#include <mach/mach_time.h>

int testfunc(int arg1, int arg2);

int main(int, const char **)
{
    struct mach_timebase_info  tb;
    uint64_t   start, stop, elapsed;
    double     seconds;
    const int  iterations = 300000000;
    int result = 0;

    mach_timebase_info(&tb);

    // Run the test.
    start = mach_absolute_time();
    for (int i=0; i<iterations; ++i)
        result = testfunc(result,i);
    stop = mach_absolute_time();
    elapsed = stop - start;

    // Print results.
    seconds = ((double)elapsed * tb.denom / tb.numer) / (1000*1000*1000);
    printf("%d iterations = %0.9lf seconds\n", iterations, seconds);
    printf("1 iteration = %0.9lf seconds\n", seconds/iterations);
    return 0;
}

/* bar.cpp */
int testfunc(int, int)
{
    return 0;
}

Notice how the function that it's calling is in a completely different source file? That's because on my first attempt gcc's inlining optimizer actually completely eliminated the function call. This was only visible upon inspecting the disassembly (step 6). Putting the target function in another module was the easiest way to stop the function from being inlined. (Yes, I tried -fno-inline and __attribute__((noinline)). Neither has the desired effect.)

I've chosen to ignore the overhead of the loop itself in this measurement. It's essentially negligible for most types of microbenchmarks. Furthermore, as long as you wind up comparing the result against another test run with identical loop overhead, it will simply cancel from both sides of the equation.

So that's it. Anyone have any interesting situations where you've found that you needed to run a microbenchmark? Does your technique differ from mine? Found any unexpected results? Let me know in the comments.

When Benchmarks Attack

In my professional life I've found myself measured by an external benchmark many times. One time that comes to mind was when I was writing disk drivers for Mac OS 8.

The disk driver's job in Mac OS 8 was simply to pass requests from the filesystem layer to the underlying storage medium. Requests would come in for such-and-such amount of data at such-and-such an offset from the start of the volume. After some very minimal translation, we'd pass this request onward to the ATA Manager, or USB Manager, or FireWire libraries.

(Sounds easy, right? Well, yes, but the devil was in the details. USB and FireWire supported "hot-plugging", i.e. attaching or removing the drive while the computer was still running. Supporting this in an OS that was never designed for it was a big chore. CD and DVD drives were also much more difficult to handle than regular hard drives, for similar reasons.)

But we ran into a problem as we were preparing our drivers for release. The hardware manufacturers that were buying our drivers wanted to make sure our drivers were "fast". So they ran disk benchmarks against our drivers. Not an unreasonable thing to do, you might say, although as I've stated there really wasn't a lot of code in the critical path. The problem is that most of the disk benchmarks turned out to be inappropriate as measures of driver performance.

Measuring weight with a ruler

One common disk benchmark of the time was to read sequential 512-byte blocks from a large file. In Mac OS 8 these reads were passed directly down to the disk driver.

Remember, the disk driver's job was supposed to be to simply pass the incoming requests on to the next layer in the OS. The vast majority of the time would be spent accessing the hardware. So no matter what the requests were, in effect this test should have returned almost exactly the same results for all drivers, with code differences accounting for less than 1% of the results. Right? Wrong.

As we ran the tests, we found out that on this particular benchmark, our drivers were much slower than existing third-party drivers (our competition, more or less). Dramatically slower, in fact -- if we ran the test in 100 seconds, they ran it in 10 seconds.

Upon further examination, we found out the reason why they did so well on this benchmark. They had already been optimized for it!

We discovered that the other drivers contained caching logic which would cluster these small 512-byte sequential reads into larger 32KiB or so chunks. Doing so would decrease the number of round-trips to the hardware needed, which increased their performance on this benchmark.

Do what sells, not what's right

Now, it's important to understand that this tiny-sequential-read benchmark doesn't even reflect real-world use. The fact that larger I/O requests perform better than smaller I/O requests has been well known for decades, and almost every commercial application out there used large I/O requests for this very reason. Buffered I/O is built into the standard C libraries, for pete's sake. In the real world, requests that came into the disk driver tended to be either large or non-sequential.

Modifying our drivers to do the same thing would basically be pointless -- a lot of work for very little performance difference.

(It only gets worse when you realize that our disk driver was directly underneath the Mac OS disk cache. A driver-level cache was almost completely redundant. And the right place to do this sort of readahead caching would have been there, in the existing OS cache layer, not in each individual disk driver.)

But ... sigh. The real world doesn't always make sense. These small sequential reads were a well-known benchmark, even if it was a disk benchmark and not a driver benchmark. And that simple fact elevated this atypical scenario into the eyes of a lot of people who didn't really understand what it meant. To them, if our driver didn't do the same thing as the competition, we wouldn't measure up.

De-optimizing to improve the benchmark

So in order to make sales we were forced to burn another month adding and testing driver-level caching so that we'd perform better on this benchmark.

The irony? The work we did to improve this atypical benchmark actually increased the amount of time we spent in the driver code, and sometimes increased the amount of data we read, which in turn decreased real-world performance by as much as 1-2%.

But hey, at least that benchmark got faster.

And we sold our driver.

New Parallels Desktop Beta

A new beta update of Parallels Desktop has been released that updates Parallels Desktop for Mac to Build 1862 Beta.

This update fixes the disk caching policy problem that PD Tweaker was created for. If you were wondering, PD Tweaker is perfectly safe to run with the new update and doesn't conflict with it at all. But it will be unnecessary once you have configured your VM properly.

Curiously, instead of just fixing it they decided to make it an option under the virtual machine settings -> Options -> VM flags:

Choose virtual hard disk cache policy for better performance of:

[X] Virtual machine
[ ] Mac OS X

"Virtual machine" is the default setting. For the technically-minded among you, this is like having a radio button to select between two behaviors: "incorrect" and "correct", and defaulting to "incorrect".

In this case the correct behavior is to select the second option, "Mac OS X". There are rare scenarios where you might want the other behavior, for example if you were setting up a dedicated server box that does nothing except run virtual machines. But in almost all other cases the second option is correct. I'll blog more about this later.

There are several significant other improvements, including video acceleration -- which completely eliminates the display-update lag when you're typing in Windows, hooray! All in all it seems like a very worthwhile update so far. Remember to re-install the Parallels Tools on your client OS after updating so that you get the new drivers.

CLImax 1.5d2 re-released

Any old-school scripters out there might be happy to hear that I've re-released CLImax 1.5d2, which I recently rediscovered on a long-lost backup.

CLImax is an AppleScript command-line interface for the Mac OS. It was originally written in 1996 for System 7.5, and development was stopped in 1998. Ten years after its first release, version 1.5d2 can still run under Classic today. It's not as convenient as it was under 9.2.2 natively, but it's not bad either.

I've received a bunch of positive comments about CLImax from people including Bill Cheeseman (of AppleScript Sourcebook), Ray Barber (of MacScripter), and Peter Hosey (of Adium X). Peter was the one who actually got me to re-release it.

CLImax 1.5d2 is now FREEWARE and available at no charge. Be sure to visit the CLImax homepage for more information, including screenshots.

I'm currently soliciting feedback on whether it'd be worth porting it to Mac OS X and creating a modern version. Thoughts?

PD Tweaker 1.0

For all you fans of Parallels Desktop out there, I've released a quick little hack to fix some problems in their initial release (aka: build 1848). It's called PD Tweaker.

It's very simple and only does two things.

• Optimizes caching for HDD and SAV files

  Caching large files is actually harmful to your Mac's overall performance. HDD files do not need caching because the client OS will already have a cache layer. SAV files are streamed in and out and don't need to reside in the disk cache.

• Always writes HDD and SAV files all the way to disk

  Your data is precious. Especially data like a HDD file that took you hours to install and configure. Shouldn't you treat it that way?

I wrote it primarily because although Parallels Desktop is a great product, I got fed up with the way it wasted my entire 2GB of RAM with the HDD file and made my machine virtually unusable. With PD Tweaker installed, you will not only notice greatly improved performance from your Mac as a whole, but your HDD files will be safer from data corruption as well. And best of all, it's entirely free and the source code is available.

It uses Unsanity's Application Enhancer 2.0 to do its thing.

More information (including some rationale and a technical explanation) is available on the PD Tweaker website. What are you waiting for? Go there now!

Delaying the xnu-x86 source release

[Updated Aug 7 2006; see below.]

Tom Yager at InfoWorld points out that Apple has released the source code to everything in the x86 build of OSX Darwin except for the kernel, xnu.

He also makes what appears to be a completely and utterly unsubstantiated statement about why:

Thanks to pirates, or rather the fear of them, the Intel edition of Apple’s OS X is now a proprietary operating system.

First of all, what? That's a bold statement. Got any source for that claim? That seems like sheer FUD, deliberately sensationalized to create a stir and bring people to the site (and therefore sell ads). From everything I've seen, and I've worked with these people, Apple's security team and upper management know better than to rely on security through obscurity. And to date I don't know of any official or even unofficial statement from Apple about xnu-x86 -- just the fact that several people have noticed that the source still hasn't been released.

[Update 5/22 via John Gruber: Apple's Product Manager for Open Source reiterates that Apple has not made any announcement yet, and drops what sounds like a big hint that xnu-x86 will eventually be released.]

Let me offer two guesses at the real reason why we haven't seen source to xnu-x86 yet:

1. The xnu-x86 source might leak information about a future product. The obvious candidate is the only missing link in the x86 line, the pro desktops. You know, the ones that will replace the "PowerMac". Let's call them "Mac Pro" for lack of a better name.

   For example, if the highest end Mac Pro desktop machines were planned to have, say, 4 CoreDuos packed into them for a whopping 8 CPU cores, then chances are you would see traces of that support show up in several parts of xnu. And when Apple releases a major rev of xnu, there are always some people who pore over it looking at the diffs.

   Apple does have ways to keep prerelease stuff out of the source release, of course, but it adds a layer of complication and risk to go back and hack that up after the fact. Maybe this time they decided it was just simpler to drag their feet for a while until the entire new line has been announced.

2. The xnu-x86 source might currently contain a small amount of licensed proprietary code that does not belong to Apple. If that's the case, they simply might not be legally allowed to release it in its current form.

   Maybe it's virtualization code from Intel, or some sort of Trusted Computing gobbledygook which is currently dormant. If they can't negotiate terms to release it, then they might have to factor the sourcebase somehow to link that other code in separately. Factoring that out seems like it would be totally possible, but kind of a messy task since it's at such a low level in the kernel and they can't sacrifice any performance to do so.

Personally I think #1 fits Apple's modus operandi perfectly. But #2 is also the kind of real-world consideration that could delay a source release for an unknown period of time while the lawyers work things out. I will grant that "fear of pirates" is another technically possible reason why we haven't seen the source, but then again the same could be said for "fear of ninjas".

We'll see what happens. Either way my gut feeling is that this is just a delay in the source release, not a permanent switch to a completely closed-source kernel.

[Update: Aug 7 2006: xnu-x86 has now been released. According to Kevin van Vechten's post at kernel.macosforge.org:

Several changes were made in order to publish the kernel (xnu) sources. As a result, the kernel built from these sources differs from the one found in the 10.4.7 software update. In order to accommodate these changes, several kernel extensions were also modified and must be downloaded and installed in order to run a kernel built from these sources on Mac OS X 10.4.7 for Intel.

Based on that comment, it sounds like the answer is #2 and for the xnu-x86 release they moved some code from the kernel into a kext.]

High-Resolution Images Could Choke Internet

Perhaps you've seen this article, entitled High-Definition Video Could Choke Internet, already:

Every day, it seems, a new service pops up offering to send you video over the Internet. "Desperate Housewives," Stephen Colbert heckling the president, clips of bad dancers at wedding parties: It's all there.

You may be up for it, but is the Internet?

The answer from the major Internet service providers, the telephone and cable companies, is "no." Small clips are fine, but TV-quality and especially high-definition programming could make the Internet choke.

Man. That just sounds really familiar to me for some reason. I've been online for more than a decade now, and this has been bugging me all day. So I started searching through my old floppy disks for news articles that I'd stashed away back in my university days. It turns out this argument isn't new at all! Check it out (sorry, no link to the original -- all I know about the origin is that I saved it off Usenet as jpegbad.txt):

High-Resolution Images Could Choke Internet
By SVEN PETERSON, Microcomputer Technology Writer
Sunday Mar 24, 1996

NEW YORK - Every day, it seems, a new service pops up offering to send you images or software over a new service called the World Wide Web, or WWW. Astronomy pictures of the day, ESPN.SportsZone.com, the Internet Movie Database, DOOM wads, Info-Mac archives: It's all there.

You may be ready for it, but is the Internet?

The answer, from major Internet service providers such as Prodigy, Compuserve, and eWorld, is "no." Small pictures are fine, but GIF animations, full-color JPEGs, and especially high-resolution images could make the Internet choke.

Most home Internet use is in brief bursts: an e-mail here, a gopher session there, followed by some Telnet activity. If people start browsing the World Wide Web like they watch TV -- for hours at a time -- that puts a strain on the Internet that it wasn't designed for, ISPs say, and beefing up the Internet's capacity to prevent that will be expensive.

To offset that cost, ISPs want to start charging content providers to ensure delivery of large JPEG files, for example.

Internet activists and consumer groups are vehemently against those plans, saying they amount to deliberately fouling the Internet's level playing field, one of the things that has encouraged communication and collaboration and may, in the future, provide a much-needed boost to the US economy. They want legislation to guarantee a "neutral" Internet, but prospects appear slim.

At the heart of the debate is a key question: How much would it really cost the Internet carriers to provide a couple of megabytes of JPEG-laden WWW pages over their networks every day?

The carriers are not telling, but there are ways to get close to an answer.

One data point: As a rough estimate, an always-on, 1000 kilobit-per-second connection to the Internet backbone in downtown Cleveland, purchased wholesale, costs an ISP $100 to $200 a month, according to the research firm GeoTelegraphy Inc. An ISP's business is carrying data from that connection to the customer.

One thousand kilobits per second is obviously a lot of bandwidth, so ISPs have to spread that bandwidth out over their subscribers. That connection can serve about 30 users who are using every bit of their 28.8 kilobit-per-second dialup connection. But analysts estimate that ISPs sell around 30 times more bandwidth to their end users than they can connect simultaneously to the Internet, meaning that these thousand kilobits are often shared by roughly 900 users.

In a way, dial-up internet service is like an old-fashioned telephone service, where there are always more lines leading from homes to the local switching station than there are going from the station out of the neighborhood. If everyone picks up the phone at once, there won't be enough outgoing lines for every call to go through. But the system works because that rarely happens.

Oversubscription doesn't present a problem as long as people are only using the Internet for e-mail, telnet, and the occasional FTP download. But if everyone in a neighborhood is trying to "surf" the WWW at the same time, it's just not going to work.

"The simple truth is that today's networks simply don't have the capacity to deliver all that customers expect," says Timothy Taker, Prodigy's top lobbyist.

The solution, of course, is to make the pipes connecting to the Internet fatter. To illustrate what that would mean, Compuserve's chief architect, Franz Kafka, uses the assumption that the cost of providing a month's worth of data to the average user, about 2 megabytes, costs the company $1. That's a fairly small amount compared to the $25 to $47 a month Compuserve charges for dial-up, but then the company has to pay for sales, support, maintenance and a host of other costs.

If that same user were to start downloading twenty print-quality high-resolution JPEGs per month, Compuserve's data cost, not including the cost of maintaining the dial-up line, would go up to $4.50 a month. Higher, but perhaps not high enough to break their business model.

But if the customer starts browsing the WWW like the average household watches broadcast TV, 8 hours a day, Compuserve's cost would go up to $112 a month, enough to inspire nightmares in the corporate accounting department according to Kafka.

"We don't expect to get to the point where we're charging anyone those kinds of prices for Internet service, but it does reflect the kind of impact that high-resolution JPEGs and GIFs could have on the network and business models for the Internet," Kafka said.

To deal with that, Kafka says Compuserve might put caps on the amount of data that a residential user gets for free, and charge extra if the user goes over. Other options include charging content providers extra for guaranteed delivery of JPEG images and GIF animations, which has raised the hackles of Internet content providers and activists.

However, Kafka's estimates for these costs aren't really Compuserve's. Like other ISPs, they don't disclose their actual costs. Instead, Kafka's base figure of $1 for 2 megabytes of data per month is based on an estimate by Dave Tricklestein, sysop of the Dial-Up Prime BBS, and Tricklestein thinks Kafka has it wrong.

"Traffic just isn't growing that fast," Tricklestein said. "It will grow and it will even accelerate, but not fast enough to turn into dollar amounts that really matter." The new WWW service is still just a small fraction of the total amount of internet traffic out there, and that's unlikely to change overnight, in Tricklestein's opinion.

In fact, he said, it will probably be at least two more years before the WWW takes off in a big way. Prices of network equipment like switches and routers have been falling, and that trend is likely to continue.

Tricklestein believes the danger of letting the carriers charge extra for guaranteed delivery is that they'll put the spending for upgrades into creating that extra "toll lane," and won't reduce oversubscription in the rest of the network even though it would be cheap to do so.

Both Compuserve and eWorld have said they won't degrade or block anyone's Internet traffic. But it's impossible to tell what goes on inside their networks.

So what's the message? Stay tuned, and watch your modem connection speeds.

Funny. Whatever happened to Compuserve and that short-lived dial-up business model where you got charged extra for overages? Oh yeah, consumers ran away from it in droves in favor of unlimited-download services so that they could browse the Web without restriction.