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 Economics of School Supplies

I'm interested in economics for one particular reason: incentives are fascinating.

There's the psychology aspect: how can you influence people's behavior? To really do this well you need to understand how people think.

There's the engineering aspect: human society is an enormously complex system, even more complex than the systems we work with in technology today. We can do things to nudge a complex system in one direction or another, but we can't always predict what will happen to it.

And then there are the results: you provide incentives in order to get people to do what you want. And that's a powerful thing! I don't mean this in a cold-blooded way; everybody does this every day of their lives.

Incentives in the Classroom

My wife is a high school teacher, and we had an interesting talk the other day. It was about how she handles providing a classroom supply of extra paper, extra pens, and all that for kids to use when they forget their own.

In years past, she had a system for this. She kept a supply closet, and early in September would give the kids extra credit for bringing in up to two items for the supply closet. Since she did this at the beginning of the year, kids quickly donated all kinds of stuff to get the easy points, and the closet filled up. Before the year had even started she had a year's worth of supplies.

This year, for the first time, she consciously tried not to do that, because she reasoned that it's not really an academic thing — so it wasn't a good idea to give out points for it. Makes sense, right? And besides, the school provides a certain amount of supplies for the teachers which she might be able to use.

But I'm sure you can guess what happened. With almost 200 kids in and out of her classroom each day, all it takes is a few percent each day to need paper and it'll add up fast. So she very quickly ran through her school-provided allotment, and by November, she was bringing in supplies from home to make up the difference.

And thus the dilemma: should she offer extra credit again? Or stick to her principles and not give out points?

Three approaches

As we talked, we came up with basically three approaches to the problem.

1. Do nothing. This is what she had been doing, and she wasn't really happy with it. The kids could borrow from each other — and some did. Or she could provide her own supplies — which she had started to do. Or kids would just fail the day's assignment when they didn't have the supplies for it... but that's very hard on a public school teacher who wants every kid to succeed.

2. Positive incentives. This is the extra-credit approach. She had mixed feelings about this at first, until I pointed out that the extra credit was just a tiny fraction of their grade — something like 1% of a single quarter. That isn't going to turn a failing student into a passing one; it might turn a B into a B+, and so on, but that's all. And then she raised the excellent point that roughly 20% (!!) of their grade is class participation anyway. Providing supplies really helps the community of the classroom, just like class participation does, so that's a fine place to apply the extra credit.

3. Negative incentives. I suggested that another approach would be to penalize the students for coming to class unprepared. Charge kids 1 point (or even just 1/10th of a point) each day that they borrow paper or a pen. The size of the incentive doesn't matter, it just matters that it's negative.

Now, different people will have different feelings about each of these. And you can do different variations on them — charging a penny instead of a point for paper, etc. But those are the basic choices.

Creating an Atmosphere

In practice, both the positive and negative incentives should work. But I pointed out that the main difference between these two is not the first-order results of the incentive ... the main difference is how she will be perceived after applying each one.

Why? Well, even as you incentivize the students with one of these actions, they in turn give you an incentive back with how they react.

If you're the teacher who is chintzy about paper and deducts fractions of points for every little thing, you'll be a Scrooge and the students won't like you. Negative reinforcement yields negative emotions.

But on the other hand, what if you're the teacher who provides extra-credit and then free paper? Why, then you're the wonderfully generous and nice teacher whom they love. Positive reinforcement yields positive emotions.

It's almost Machiavellian: do you want to be feared or loved?

Knowing my wife as I do, in her classroom she works best when she's loved. And so I told her to go back to what she had been doing — give out extra credit to fill up the supply closet. It's funny that after actually dissecting the problem and analyzing it, we came up with the same solution that she'd done more or less instinctively in the first place.

Remembering Apollo 11

Today marks the 40th anniversary of the Apollo 11 moon landing.

I hope you're listening to the mission audio, or following the JFK Presidential Library's webcast. The landing itself will be replayed at 4:17pm EDT, and Neil Armstrong's first steps should be at 10:56pm EDT. NASA has been doing a number of things for the occasion, including releasing some very cool photos from orbiters which show the Apollo landing sites as they exist today.

The anniversary is getting a lot of attention this year. It's on magazine covers, it's on TV, and there's an undercurrent of buzz among my geek friends about it.

So I figured I'd take a break from my usual hectic schedule of "not blogging" to share some thoughts.

The first-time cost

Going to the moon was fantastically expensive.

Just think: landing on the moon required an absolutely unparalleled effort. It required the US to bring together technology, manufacturing, research, money, management, a boatload of sciences (psychology, physiology, physics, chemistry, materials, culinary, more), training, politics, leadership, public relations, the military, hard work, and a bottomless amount of determination.

The men who walked on the moon did so at the pinnacle of an enormous pyramid of marshaled resources — virtually the entire resources of a nation, bent to a single purpose. And they did it all with 1960's technology, in a spacecraft that had less computational power than your phone does today. (Heck, probably less than your refrigerator.) This is the stuff of which legends are made.

That pyramid of resources was amazing — and fragile.

We got to the moon and it was pretty freakin' cool. But it wasn't cool enough.

Snapping back

After getting there the first time, we just kind of stopped. The last mission that landed on the moon was Apollo 17 in 1972, just a few short years after the first one.

Why? Well, the moon just wasn't that interesting.

Hang on, I'd like to clarify that. In fact there's a ton of interesting stuff on the moon. But it's probably fair to say the cost of that vast, overreaching pyramid of resources was greater than the return we were getting back.

The truth is that the moon really didn't have anything that 1970's America really needed; no useful minerals, no water, no oil, and we can't even live there. So it makes sense that after briefly overreaching ourselves just to get there, that there would be a period of time where the pendulum swung back: where we'd stop going entirely.

But there is one key thing to remember. It's not 1970 any more.

What a difference 40 years makes

The cost of everything trends downward over time. Or you can put it another way: our civilization gets comparatively wealthier over time, so that a constant cost eventually becomes much more affordable. It doesn't really matter which way you want to look at it, since they're two sides of the same coin.

In the 1960's the cost of putting a man into space — not just the raw materials and rockets, but the entire infrastructure — was so large that it could only be attempted by the world's largest industrial powers.

In the 2000's we've seen the cost fall to the point where it just takes the resources of a single large corporation. In the next two years we should see commercial sub-orbital space travel offered by Virgin Galactic. And you can bet Virgin will have competitors before long.

Space travel isn't quite "cheap", but it's getting surprisingly affordable. It won't be long before we're back at the moon. In fact, I'll go so far as to make a few easy predictions:

A man will walk on the moon again by 2019. That's less than ten years, so on or before the 50th anniversary of Apollo 11. NASA has a plan to do it, and so do the Chinese. Barring bureaucratic screwups, another Great Depression, or the singularity, it seems very likely.

A woman will walk on the moon by 2019. The title of "first woman on the moon" is still wide open, and there's no shortage of talented female astronauts. It's an easy bet that the first return mission will include one.

What can the moon offer us now?

Why would we go back, anyway? Science-fiction fans will have no shortage of ideas about the long-term future, but I find it more interesting to consider the short term — because that's really where the rubber meets the road.

What are the realistic, short-term benefits that we might get from the moon when we go back?

A few thoughts:

• Tourism. We already have space tourism, where rich people pay millions of dollars simply to go into space. Once commercial spaceflight takes off — and Virgin Galactic plans its inaugural flight within just two years — how long do you think it'll be until someone wants a tour of the moon?

• An outpost. Rather like McMurdo Station in Antarctica, an outpost on the moon would be a center for scientific research and exploration, as well as a central base for other activities.

• Mining, and ultimately manufacturing. Silicon, aluminum, and iron are probably the most useful and easily-extracted resources in the short term. (Many people talk about Helium-3, but it's not currently exploitable so I'm leaving it off.) But why would we mine the moon for this stuff instead of getting it from Earth? It's useful, but not exceptionally scarce.

  The answer is really that it's about relative scarcity. These raw materials are not exceptionally scarce here on Earth, but they sure are hard to come by up in orbit!

  It's a question of cost again. It's expensive to get things out of the earth's gravity well. If you want something even moderately large on the moon or in space — habitats, satellites, ships, mirrors, radiation shields — it may be cheaper to build it in place, with materials from the moon instead of from Earth.

I'd guess that these things are likely to happen in roughly that order: Tourism first, because there is a huge pent-up demand. This will be followed soon afterward by a small outpost — mostly for research, but also supporting (and partially funded by) tourism. And finally the mining and manufacturing, which can then can be used to build up the outpost even more.

Even though we've gotten used to space travel as a NASA thing, it's possible these may not be governmental projects at all, or they may be hybrid ventures which are part commercial and part subsidized. Either way, the feeling that the pendulum is finally swinging back is terrific. I can't wait!

Now it's your turn. What do you think the moon will have to offer us during the 2020's?

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

MarsEdit Markdown Scripts updated to 1.0.3

No piece of software, however simple, is bug-free.

Daniel Jalkut was kind enough to point out to me that my Markdown scripts for MarsEdit didn't deal properly with Unicode text.

Silly me. I'd forgotten that AppleScript (with its very early-1990s roots) still needs to be explicitly told not to lose data when writing out files. He offered a fix — a few «class utf8» coercions in the right place and all was well again. That was 1.0.1.

However, just immediately after release, I discovered that the scripts needed to do some more aggressive transcoding of UTF8 into ASCII in order to get Python to read the file in html2text. So I've added support for that. This slows down the HTML-to-Markdown reverse conversion a little bit, but at least it's correct now. That was 1.0.2.

Finally, later in the evening I realized it was pretty stupid to write AppleScript code to transcode the UTF8 into ASCII, because AppleScript's support for Unicode is so horribly primitive and I was doing it character by character. So I rewrote that whole section as a one-line Perl script. Now it's blazing fast. And that's 1.0.3.

I've updated the scripts. Download them now!

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.

What should TV shows cost?

While reading Daring Fireball today, I saw that Apple has posted a press release scolding NBC for wanting to more than double the cost of their content.

Apple® today announced that it will not be selling NBC television shows for the upcoming television season on its online iTunes® Store (www.itunes.com). The move follows NBC's decision to not renew its agreement with iTunes after Apple declined to pay more than double the wholesale price for each NBC TV episode, which would have resulted in the retail price to consumers increasing to $4.99 per episode from the current $1.99. ABC, CBS, FOX and The CW, along with more than 50 cable networks, are signed up to sell TV shows from their upcoming season on iTunes at $1.99 per episode.

'We are disappointed to see NBC leave iTunes because we would not agree to their dramatic price increase,' said Eddy Cue, Apple's vice president of iTunes. 'We hope they will change their minds and offer their TV shows to the tens of millions of iTunes customers.'

First of all, I'm totally amused that Apple is dragging this dirty laundry out in public to shame NBC. It's a smart business move, and I have no objections to it: I just get a kick out of big corporations fighting.

Second, it brings up an excellent question about the value of content. Particularly content that is sometimes expensive to produce. What exactly do consumers perceive as the "right price" for something like a TV show?

What Content Producers Think

I think content producers operate on a couple of different mental models when it comes to pricing their content for digital distribution. Most of these models are terribly flawed, because they're not looking at the consumer's point of view.

  Production Cost: "The more expensive it is to produce, the higher the price should be."

  Length: "A one-hour TV show should cost around the same as a one-hour CD."

  Cross-Media Comparisons: (To the most expensive alternative.) "We can sell a full season of DVDs for $60, which works out to $5 per show."

  Threat of Withholding: "You're going to buy it at whatever price we ask, or else you won't get it at all."

These models probably only make sense to you if you're a content producer talking about your own content. As a consumer, they probably make you angry.

What Consumers Think

As a consumer, these are the things I think about when I am considering buying content.

  Total Usage Time: "How much total time will I spend enjoying this content?"

Total usage time is very different from the length of the content. Total usage time is equal to the length, multiplied by the number of uses I expect to get from it.

For a CD or album, the total usage time is vastly different from that of a TV show. When I buy music, I expect to listen to it again and again. Most TV shows I only watch once. Sure, if it's a download I could watch it again and again, but odds are that the 45 minutes of content in your hour-long show is only going to get 45 minutes of my time. Or less. Movies and concert videos are somewhere in the middle: particularly good movies will sometimes get a second or third viewing, but still nothing approaching what a good CD gets.

  Quality and Extras: "Is this particularly high-quality content? Does it have something extra that I'm interested in, like commentary or subtitles?"

Although this isn't my primary factor, I'm generally willing to pay a little more for content that goes the extra mile. Sometimes that means higher resolution (Blu-Ray vs DVD, or SACD or DVD-Audio vs CD vs MP3), sometimes that means particularly extraordinary special effects, sometimes it's commentary from a director or actor that I admire, sometimes it's a behind-the-scenes "Making Of" featurette.

For example, I almost never buy TV shows on DVD because they're just too expensive. But in the few rare cases where I do, it's because it's a show that I particularly enjoy and would like in a high-quality format with lots of extras.

  Cross-Media Comparisons: (To the least expensive alternative.) "Can I get everything I want somewhere else, for less money?"

Sometimes I simply want to catch up on a show's plot developments. Reality shows are a good example: I sure don't watch them for the quality of the writing. If I'm traveling and I miss a showing of American Idol or Who Wants to Be A Superhero?, I'm not going to spend any significant amount of money at all on finding out who got kicked off this week. I'd rather just look it up online.

If it's a show like Battlestar Galactica that I actually do want to watch and appreciate, well, I own a DVR which lets me record the "free" showings from network or cable TV. Chances are unless I'm in a big hurry, I'll just watch the version that was automatically recorded for me once I get home.

This is also where piracy comes in. As Steve Jobs has said, content producers have to compete with piracy as a business model. Video-sharing sites and BitTorrent servers may offer the content at no cost. Piracy is a funny thing. It isn't attractive to most people ... until you start withholding or overcharging for content. Then it spikes. Personally I don't have any qualms about watching all or part of a TV show on YouTube if it isn't available anywhere else.

You can go into great depth parsing the legal arguments around both of those last two, but you'll be wasting your time. Consumers don't. The fact is that in our minds — yours and mine — TV show downloads are essentially competing with "free", twice over.

  Convenience vs Importance: "Is the price I'm paying (in both money and inconvenience) proportionate to how much I care?"

Sometimes I'm only mildly interested in your content. I think most web browsing falls under this umbrella, which is why it's so difficult to make money by charging for content on the web. If I'm only mildly interested, I'm not going to pay you anything at all for it, but I might spend a few minutes watching it ... if it's free and easy to do so.

Of course, there are times when I'm extremely interested in your content. I'm generally more willing to pay money for it in that case. But the number of things that are quite that important to me necessarily has to be kept very small — because I don't have an infinite amount of money. (IMPORTANT NOTE: If you would like to give me an infinite amount of money, e-mail me and we'll talk.)

Resolving the difficulties

That's it. Those four criteria are what I use to evaluate prices as a consumer, and I would be willing to bet that I'm not alone. Realistically, I think the consumer models are what will ultimately drive the cost.

So what's the fair price for a TV show? If you go by total usage time, the value of a TV show is substantially less than the value of a single track of music, despite the fact that it costs more to produce. The convenience factor of getting it whenever you want it may bump up the price you're willing to pay, but I think that $2 is actually already too expensive in the minds of many consumers. They'd be better at $1 ... or even free.

What's the fair price of a TV show to you?