The Sad Tragedy of Micro-Optimization Theater

I'll just come right out and say it: I love strings. As far as I'm concerned, there isn't a problem that I can't solve with a string and perhaps a regular expression or two. But maybe that's just my lack of math skills talking.

In all seriousness, though, the type of programming we do on Stack Overflow is intimately tied to strings. We're constantly building them, merging them, processing them, or dumping them out to a HTTP stream. Sometimes I even give them relaxing massages. Now, if you've worked with strings at all, you know that this is code you desperately want to avoid writing:

static string Shlemiel()
{
    string result = "";
    for (int i = 0; i < 314159; i++)
    {
        result += getStringData(i);
    }
    return result;
}

In most garbage collected languages, strings are immutable: when you add two strings, the contents of both are copied. As you keep adding to result in this loop, more and more memory is allocated each time. This leads directly to awful quadradic n² performance, or as Joel likes to call it, Shlemiel the painter performance.

Who is Shlemiel? He's the guy in this joke:

Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck.

The next day Shlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck.

The next day Shlemiel paints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?"

"I can't help it," says Shlemiel. "Every day I get farther and farther away from the paint can!"

This is a softball question. You all knew that. Every decent programmer knows that string concatenation, while fine in small doses, is deadly poison in loops.

But what if you're doing nothing but small bits of string concatenation, dozens to hundreds of times -- as in most web apps? Then you might develop a nagging doubt, as I did, that lots of little Shlemiels could possibly be as bad as one giant Shlemiel.

Let's say we wanted to build this HTML fragment:

<div class="user-action-time">stuff</div>
<div class="user-gravatar32">stuff</div>
<div class="user-details">stuff<br/>stuff</div>

Which might appear on a given Stack Overflow page anywhere from one to sixty times. And we're serving up hundreds of thousands of these pages per day.

Not so clear-cut, now, is it?

So, which of these methods of forming the above string do you think is fastest over a hundred thousand iterations?

1: Simple Concatenation

string s = 
@"<div class=""user-action-time"">" + st() + st() + @"</div>
<div class=""user-gravatar32"">" + st() + @"</div>
<div class=""user-details"">" + st() + "<br/>" + st() + "</div>";
return s;

2: String.Format

string s = 
@"<div class=""user-action-time"">{0}{1}</div>
<div class=""user-gravatar32"">{2}</div>
<div class=""user-details"">{3}<br/>{4}</div>";
return String.Format(s, st(), st(), st(), st(), st());

3: string.Concat

string s = 
string.Concat(@"<div class=""user-action-time"">", st(), st(),
    @"</div><div class=""user-gravatar32"">", st(), 
    @"</div><div class=""user-details"">", st(), "<br/>",
    st(), "</div>");
return s;

4: String.Replace

string s =
@"<div class=""user-action-time"">{s1}{s2}</div>
<div class=""user-gravatar32"">{s3}</div>
<div class=""user-details"">{s4}<br/>{s5}</div>";
s = s.Replace("{s1}", st()).Replace("{s2}", st()).
    Replace("{s3}", st()).Replace("{s4}", st()).
    Replace("{s5}", st());
return s;

5: StringBuilder

var sb = new StringBuilder(256);
sb.Append(@"<div class=""user-action-time"">");
sb.Append(st());
sb.Append(st());
sb.Append(@"</div><div class=""user-gravatar32"">");
sb.Append(st());
sb.Append(@"</div><div class=""user-details"">");
sb.Append(st());
sb.Append("<br/>");
sb.Append(st());
sb.Append("</div>");
return sb.ToString();

Take your itchy little trigger finger off that compile key and think about this for a minute. Which one of these methods will be faster?

Got an answer? Great!

And.. drumroll please.. the correct answer:

It. Just. Doesn't. Matter!

We already know none of these operations will be performed in a loop, so we can rule out brutally poor performance characteristics of naive string concatenation. All that's left is micro-optimization, and the minute you begin worrying about tiny little optimizations, you've already gone down the wrong path.

Oh, you don't believe me? Sadly, I didn't believe it myself, which is why I got drawn into this in the first place. Here are my results -- for 100,000 iterations, on a dual core 3.5 GHz Core 2 Duo.

Even if we went from the worst performing technique to the best one, we would have saved a lousy 391 milliseconds over a hundred thousand iterations. Not the sort of thing that I'd throw a victory party over. I guess I figured out that using .Replace is best avoided, but even that has some readability benefits that might outweigh the miniscule cost.

Now, you might very well ask which of these techniques has the lowest memory usage, as Rico Mariani did. I didn't get a chance to run these against CLRProfiler to see if there was a clear winner in that regard. It's a valid point, but I doubt the results would change much. In my experience, techniques that abuse memory also tend to take a lot of clock time. Memory allocations are fast on modern PCs, but they're far from free.

Opinions vary on just how many strings you have to concatenate before you should start worrying about performance. The general consensus is around 10. But you'll also read crazy stuff, like this:

Don't use += concatenating ever. Too many changes are taking place behind the scene, which aren't obvious from my code in the first place. I advise you to use String.Concat() explicitly with any overload (2 strings, 3 strings, string array). This will clearly show what your code does without any surprises, while allowing yourself to keep a check on the efficiency.

Never? Ever? Never ever ever? Not even once? Not even if it doesn't matter? Any time you see "don't ever do X", alarm bells should be going off. Like they hopefully are right now.

Yes, you should avoid the obvious beginner mistakes of string concatenation, the stuff every programmer learns their first year on the job. But after that, you should be more worried about the maintainability and readability of your code than its performance. And that is perhaps the most tragic thing about letting yourself get sucked into micro-optimization theater -- it distracts you from your real goal: writing better code.

The Ultimate Dogfooding Story

In software circles, dogfooding refers to the practice of using your own products. It was apparently popularized by Microsoft:

The idea originated in television commercials for Alpo brand dog food; actor Lorne Greene would tout the benefits of the dog food, and then would say it's so good that he feeds it to his own dogs. In 1988, Microsoft manager Paul Maritz sent Brian Valentine, test manager for Microsoft LAN Manager, an email titled "Eating our own Dogfood" challenging him to increase internal usage of the product.

Buried deep in Eric Sink's post Yours, Mine and Ours is perhaps the ultimate example of the power of dogfooding.

If you'll indulge me briefly, I'd like to tell you what I think is the best dogfooding story ever. However, it's not a software story. It's a woodworking story.

The primary machine tool in any well-equipped woodshop is a table saw. Basically, it's a polished cast iron table with a slot through which protrudes a circular saw blade, ten inches in diameter. Wood is cut by sliding it across the table into the spinning blade.

A table saw is an extremely dangerous tool. My saw can cut a 2-inch thick piece of hard maple with no effort at all. Frankly, it's a tool which should only be used by someone who is a little bit afraid of it. It should be obvious what would happen if a finger ever came in contact with the spinning blade. Over 3,000 people each year lose a finger in an accident with a table saw.

A guy named Stephen Gass has come up with an amazing solution to this problem. He is a woodworker, but he also has a PhD in physics. His technology is called Sawstop. It consists of two basic inventions:

• He has a sensor which can detect the difference in capacitance between a finger and a piece of wood.
• He has a way to stop a spinning table saw blade within 1/100 of a second, less than a quarter turn of rotation.

The videos of this product are amazing. Slide a piece of wood into the spinning blade, and it cuts the board just like it should. Slide a hot dog into the spinning blade, and it stops instantly, leaving the frankfurter with nothing more than a nick.

Here's the spooky part: Stephen Gass tested his product on his own finger! This is a guy who really wanted to close the distance between him and his customers. No matter how much I believed in my product, I think I would find it incredibly difficult to stick my finger in a spinning table saw blade.

The creator actually did stick his own finger in a SawStop on camera, apparently on the Discovery Channel show Time Warp, but I can't locate any web video of it. There is a video of the sawstop in action on YouTube, using a hotdog in place of an errant digit. Personally, I find this demonstration no less effective than an actual finger.

Does it work? Yes, but it still has unavoidable limitations based on the laws of physics:

The bottom line is that this saw cuts you about 1/16" for every foot per second that you're moving. If you hit the blade while feeding the wood you're likely to get cut about 1/16" or less. If you hit the blade while you're falling you'll likely get a 3/16" deep cut instead of multiple finger amputation. If you hit it while pitching a baseball for the major leagues the injury will be even worse.

Dogfooding your own code isn't always possible, but it's worth looking very closely at any ways you can use your own software internally. As Mr. Gass proves, nothing exudes confidence like software developers who are willing to stick their own extremities into the spinning blades of software they've written.

Update: I found this quote from Havoc Pennington rather illustrative.

It would be wonderful discipline for any software dev team serious about Linux 'on the desktop' (whatever that means) to ban their own use of terminals. Of course, none of us have ever done this, and that explains a lot about the resulting products.

A Scripter at Heart

What's the difference between a programming language and a scripting language? Is there even a difference at all? Larry Wall's epic Programming is Hard, Let's Go Scripting attempts to survey the scripting landscape and identify commonalities.

When you go out to so-called primitive tribes and analyze their languages, you find that structurally they're just about as complex as any other human language. Basically, you can say pretty much anything in any human language, if you work at it long enough. Human languages are Turing complete, as it were.

Human languages therefore differ not so much in what you can say but in what you must say. In English, you are forced to differentiate singular from plural. In Japanese, you don't have to distinguish singular from plural, but you do have to pick a specific level of politeness, taking into account not only your degree of respect for the person you're talking to, but also your degree of respect for the person or thing you're talking about.

So languages differ in what you're forced to say. Obviously, if your language forces you to say something, you can't be concise in that particular dimension using your language. Which brings us back to scripting.

How many ways are there for different scripting languages to be concise?

How many recipes for borscht are there in Russia?

Larry highlights the following axes of language design in his survey:

1. Binding: Early or Late?
2. Dispatch: Single or Multiple?
3. Evaluation: Eager or Lazy?
4. Typology: Eager or Lazy?
5. Structures: Limited or Rich?
6. Symbolic or Wordy?
7. Compile Time or Run Time?
8. Declarational or Operational?
9. Classes: Immutable or Mutable?
10. Class-based or Prototype-based?
11. Passive data, global consistency or Active data, local consistency?
12. Encapsulatation: by class? by time? by OS constructs? by GUI elements?
13. Scoping: Syntactic, Semantic, or Pragmatic?

It's difficult to talk about Larry Wall without pointing out that Perl 6 has been missing in action for a very long time. In this 2002 Slashdot interview with Larry, he talks about Perl 6 casually, like it's just around the corner. Sadly, it has yet to be released. That's not quite Duke Nukem Forever vaporware territory, but it's darn close.

While interesting, I have to admit that I have a problem with all this pontificating about the nature of scripting languages, and the endlessly delayed release of Perl 6. Aren't Mr. Wall's actions, on some level, contrary to the spirit of the very thing he's discussing? The essence of a scripting language is immediate gratification. They're Show, Don't Tell in action.

In fact, my first programming experiences didn't begin with a compile and link cycle. They began something like this:

As soon as you booted the computer, the first thing you were greeted with is that pesky blinking cursor. It's right there, inviting you.

C'mon. Type something. See what happens.

That's the ineffable, undeniable beauty of a scripting language. You don't need to read a giant Larry Wall article, or wait 8 years for Perl 6 to figure that out. It's right there in front of you. Literally. Try entering this in your browser's address bar:

javascript:alert('hello world');

But it's not real programming, right?

My first experience with real programming was in high school. Armed with a purchased copy of the the classic K&R book and a pirated C compiler for my Amiga 1000, I knew it was finally time to put my childish AmigaBASIC programs aside.

I remember that evening only vaguely (in my defense: I am old). My mom was throwing some kind of party downstairs, and one of the guests tried to draw me out of my room and be social. She was a very nice lady, with the best of intentions. I brandished my K&R book as a shield, holding it up and explaining to her: "No. You don't understand. This is important. I need to learn what's in this book." Tonight, I become a real programmer. And so I began.

What happened next was the eight unhappiest hours of my computing life. Between the painfully slow compile cycles and the torturous, unforgiving dance of pointers and memory allocation, I was almost ready to give up programming altogether. C wasn't for me, certainly. But I couldn't shake the nagging feeling that there was something altogether wrong with this type of programming. How could C suck all the carefree joy out of my stupid little AmigaBASIC adventures? This language took what I had known as programming and contorted it beyond recognition, into something stark and cruel.

I didn't know it then, but I sure do now. I hadn't been programming at all. I had been scripting.

I don't think my revulsion for C is something I need to apologize for. In fact, I think it's the other way around. I've just been waiting for the rest of the world to catch up to what I always knew.

The reason why dynamic languages like Perl, Python, and PHP are so important is key to understanding the paradigm shift. Unlike applications from the previous paradigm, web applications are not released in one to three year cycles. They are updated every day, sometimes every hour. Rather than being finished paintings, they are sketches, continually being redrawn in response to new data.

In my talk, I compared web applications to Von Kempelen's famous hoax, the mechanical Turk, a 1770 mechanical chess playing machine with a man hidden inside. Web applications aren't a hoax, but like the mechanical Turk, they do have a programmer inside. And that programmer is sketching away madly.

Now, I do appreciate and admire the seminal influence of C. In the right hands, it's an incredibly powerful tool. Every language has its place, and every programmer should choose the language that best fits their skillset and the task at hand.

I know, I know, I'll never be a real programmer. But I've come to terms with my limitations, because I'm a scripter at heart.

Open Source Software, Self Service Software

Have you ever used those self-service checkout machines at a grocery store or supermarket?

What fascinates me about self-service checkout devices is that the store is making you do work they would normally pay their employees to do. Think about this for a minute. You're playing the role of the paying customer and the cashier employee. Under the watchful eyes of security cameras and at least one human monitor, naturally, but still. We continue to check ourselves out. Not only willingly, but enthusiastically. For that one brief moment, we're working for the supermarket at the lowest possible pay scale: none.

That's the paradox of self-checkout. But to me it's no riddle at all: nobody else in that store cares about getting Jeff Atwood checked out nearly as much as Jeff Atwood does. I always choose self-service checkout, except in extraordinary cases. The people with the most vested interest in the outcome of the checkout process are the very same people that self-checkout puts in charge: me! How could it not work? It's the perfect alignment of self-interest.

I don't mean this as a dig against supermarket employees. They're (usually) competent and friendly enough. I should know; I worked my way through high school and part of college as a Safeway checker. I tried my level best to be good at my job, and move customers through my line as quickly as possible. I'm sure I could check someone out faster than they could do it themselves. But there's only one me, and at most a half-dozen other checkers working the store, compared to the multitudes of customers. It doesn't scale.

If you combine the self-interest angle and the scaling issue, self-service checkout seems obvious, a win for everyone. But self-service is not without issues of its own:

• What if the item you're scanning isn't found, or can't be scanned?
• Some of the self-service machines have fairly elaborate and non-obvious rules in place, to prevent fraud and theft. Also, the user interface can sometimes be less than ideal on the machines.
• How do you handle coupons? Loyalty cards? Buying 20 of the same item? Scanning the wrong item?
• The self-service stations are lightly manned. The ratio between employee monitors and self-checkout machines runs about 1:4 in my experience. If you have a problem, you might end up waiting longer than a traditional manned checkout.
• How do you ring up items like fruit and vegetables which don't have UPC codes, and have to be weighed?
• What about unusual, awkwardly shaped items or oversize items?
• Customers who have trouble during self-checkout may feel they're stupid, or that they did something wrong. Guess where they're going to lay the blame for those feelings?

There are certain rituals to using the self-service checkout machines. And we know that. We programmers fundamentally grok the hoops that the self-service checkout machines make customers jump through. They are, after all, devices designed by our fellow programmers. Every item has to be scanned, then carefully and individually placed in the bagging area which doubles as a scale to verify the item was moved there. One at time. In strict sequence. Repeated exactly the same every time. We live this system every day; it's completely natural for a programmer. But it isn't natural for average people. I've seen plenty of customers in front of me struggle with self-service checkout machines, puzzled by the workings of this mysterious device that seems so painfully obvious to a programmer. I get frustrated to the point that I almost want to rush over and help them myself. Which would defeat the purpose of a.. self-service device.

I was thinking about this while reading Michael Meeks' article, Measuring the true success of OpenOffice.org. He reaches some depressing conclusions about the current state of OpenOffice, a high profile open source competitor to Microsoft Office:

Crude as they are, the statistics show a picture of slow disengagement by Sun, combined with a spectacular lack of growth in the developer community. In a healthy project we would expect to see a large number of volunteer developers involved, in addition - we would expect to see a large number of peer companies contributing to the common code pool; we do not see this in OpenOffice.org. Indeed, quite the opposite. We appear to have the lowest number of active developers on OO.o since records began: 24, this contrasts negatively with Linux's recent low of 160+. Even spun in the most positive way, OpenOffice.org is at best stagnating from a development perspective.

This is troubling, because open source software development is the ultimate self-service industry. As Michael notes, the project is sadly undermining itself:

Kill the ossified, paralysed and gerrymandered political system in OpenOffice.org. Instead put the developers (all of them), and those actively contributing, into the driving seat. This in turn should help to kill the many horribly demotivating and dysfunctional process steps currently used to stop code from getting included, and should help to attract volunteers. Once they are attracted and active, listen to them without patronizing.

Indeed, once you destroy the twin intrinsic motivators of self-determination and autonomy on an open source project, I'd argue you're no better off than you were with traditional closed source software. You've created a self-service checkout machine so painful to use, so awkward to operate, that it gives the self-service concept a bad name. And that's heartbreaking, because self-service is the soul of open source:

Why is my bug not fixed? Why is the UI still so unpleasant? Why is performance still poor? Why does it consume more memory than necessary? Why is it getting slower to start? Why? Why? The answer lies with developers: Will you help us make OpenOffice.org better?

In order for open source software projects to survive, they must ensure that they present as few barriers to self-service software development as possible. And any barriers they do present must be very low -- radically low. Asking your customers to learn C++ programming to improve their Open Office experience is a pretty far cry indeed from asking them to operate a scanner and touchscreen to improve their checkout experience. And if you can't convince an audience of programmers, who are inclined to understand and love this stuff, who exactly are you expecting to convince?

So, if you're having difficulty getting software developers to participate in your open source project, I'd say the community isn't failing your project. Your project is failing the community.

The One Thing Programmers and Musicians Have In Common

In my previous post, a commenter asked this question:

So many of the best minds I have met in computing have a love for music. Is it something to do with being able to see beauty in complex numerical systems?

I adore music. I have a vast music collection and I love listening to music and exploring new bands and genres I haven't heard. But I have zero musical ability. So it's not really appropriate for me to comment on this. I've read the same observation expressed in many different places. Enough so that I do wonder if there's some kind of relationship between being a musician and being a programmer.

For informed opinions, let's turn to programmers who are actually musicians. I thought Rob Birdwell, who left a single plaintive 2003 blog entry on his programming blog, summarized it well:

• Let's be practical: musicians become programmers, generally not the other way around, simply because those gigs actually pay the bills.
• Creating music and software are simultaneously collaborative and individualistic undertakings.
• Musicians, regardless of era, are generally technically engaged. The instruments themselves (the hardware) often interface with other devices (amps, mixers, mutes) to achieve different sounds. Composers often deal with an array of technologies to get their music written, performed and/or produced.
• Music is an abstract medium - the printed note requires interpretation and execution. Like the written line of code, there is often much more than meets the eye.
• Music is a form of self-expression. Many programmers, often to the dismay of corporate managers, try to express themselves through code.
• One famous music educator, Dick Grove, once said that composers/musicians often like to solve puzzles. (Dick Grove was very computer saavy - although I'm not sure he wrote code, I wouldn't doubt his ability to do so.)

Rob is clearly a guy with feet in both worlds, although music is obviously winning. Rob has an active music blog with way more than one entry. There are even some programming tidbits mixed in here and there.

I noticed one comment on Rob's programming blog entry from Carl Franklin, who also happens to be an amazing musician. He can prove it, too: here's Carl performing the song Jungle Love as a one man band. Incredible! Carl also sees parallels between musicians and programmers:

Instrumentalists in particular (guitar players for example) make great programmers. It's not just about math and music being similar, or the fundamentals vs the art. Instrumentalists have to zoom in to work with very repetitive technical details, and so become very focused - like a guitar player practicing a piece of music at a slow speed. But, the best programmers are able to then zoom out and see the big picture, and where their coding fits into the whole project, much like an artist has to step back from a painting and see the whole of it, or an instrumentalists has to produce something that communicates a complete work, not just the scales and technical aspects of it.

Carl is something of a fixture in the .NET programming community from the very earliest days. He now runs a little media empire; I participated peripherally in that empire when I recorded a .NET Rocks podcast with him and Richard Campbell about two years ago.

While I certainly appreciate Carl and Rob's first hand opinions as both programmers and musicians, I worry that this is just another convenient, self-fulfilling analogy we programmers use to puff ourselves up. Sort of like Paul Graham comparing programmers to painters. Or when Alistair Cockburn said software development was a collaborative game, and software projects are like rock climbing.

We're the programmers; programming is whatever we say it is.

There is a feeling I get from being "in the zone" when listening to music that strongly resembles the feeling of being immersed in an enjoyable bit of programming. There are rhythms and cadences of algorithmic flow. But I'm hesitant to draw any deeper parallels.

I've been a software developer in a (theoretically) professional capacity for 15 years now. And every year of coding that goes by, I find myself agreeing more and more with a particular Frank Zappa lyric from the song A Little Green Rosetta.

They're pretty good musicians
But it don't make no difference
If they're good musicians
Because anybody who would buy this record
Doesn't give a f**k if there's good musicians

Now that's the one thing programmers and musicians really have in common.

A Visit With Alan Kay

Alan Kay is one of my computing heroes. All this stuff we do every day as programmers? Kay had a hand in inventing a huge swath of it:

Computer scientist Kay was the leader of the group that invented object-oriented programming, the graphical user interface, 3D computer graphics, and ARPANET, the predecessor of the Internet

So as you might imagine, I was pretty thrilled to see he was dabbling a little in Stack Overflow. It's difficult to fathom the participation of a legend like Alan in a site for regular programmers. Maybe we should add a Turing Award badge. At least people can't complain that it is unobtainable.

Jeff Moser, an avid Stack Overflow user with a an outstanding blog of his own, had the opportunity to meet Alan recently and ask him about it. Jeff gave me permission to reprint his field report here.

Since I knew I'd be seeing Alan Kay at Rebooting Computing, I decided to verify his Stack Overflow usage in person. According to Alan, he found the original question using an automated search alert just like Atwood had guessed.

We then proceeded to discuss how it's sad that identity is still hard online. For example, it's hard to prove if I'm telling the truth here. As for that, the best I can offer is to look at my picture on my blog and compare with this picture from the Summit:

(Alan is on my right)

Alan is a great person to talk to because of his huge experience in the computing field.

He's currently working at the Viewpoints Research Institute where they're doing some classic PARC style research of trying to do for software what Moore's Law did for hardware. A decent explanation by Alan Kay himself is available here (wmv). For specifics, you might want to check out the recent PhD thesis of Alessandro Warth, one of Alan's students.

One of the greatest lessons I've personally learned from Alan is just how important computing history is in order to understand the context of inventions. One of Alan's greatest heroes is J.C.R. Licklider (a.k.a. "Lick"). Our discussions a few months ago led me to read "The Dream Machine" and write a post about it.

A consequence of studying history well is that you'll notice that a ton of the really cool and interesting stuff was developed in the ARPA->PARC days and it's slowed down since. I'd assume that's why he's curious about anything post-PARC's peak days (e.g. 1980+).

I'd say that Alan firmly believes that the "Computer Revolution Hasn't Happened Yet" (still) even though he's been talking about it for decades.

For example:

• see his '97 talk at OOPSLA.
• and this video from last month at the 40 Year Anniversary of Engelbart's "Mother of all Demos".

Speculating from discussions, I'd say that the problem he sees is that computers should help us become better thinkers rather than "distracting/entertaining ourselves to death." Alan likes to use the example that our "pop culture" is more concerned with "air guitar" and "Guitar Hero" rather than appreciating genuine beauty and expressiveness of real instruments (even though it takes a bit longer to master). Check out 1:03:40 of this video from program for the Future. In effect, we're selling our potential short.

I think that's my biggest take away from Alan about computing: computers can do so much more than we're using them for now (e.g. provide "a teacher for every learner").

Hope this helps provide some context.

Indeed it does, Jeff. If you'd like to get a sense of what Alan is about and the things he's working on, I recommend this Conversation with Alan Kay from the ACM.

It's not that people are completely stupid, but if there's a big idea and you have deadlines and you have expedience and you have competitors, very likely what you'll do is take a low-pass filter on that idea and implement one part of it and miss what has to be done next. This happens over and over again. If you're using early-binding languages as most people do, rather than late-binding languages, then you really start getting locked in to stuff that you've already done. You can't reformulate things that easily.

Let's say the adoption of programming languages has very often been somewhat accidental, and the emphasis has very often been on how easy it is to implement the programming language rather than on its actual merits and features. For instance, Basic would never have surfaced because there was always a language better than Basic for that purpose. That language was Joss, which predated Basic and was beautiful. But Basic happened to be on a GE timesharing system that was done by Dartmouth, and when GE decided to franchise that, it started spreading Basic around just because it was there, not because it had any intrinsic merits whatsoever.

This happens over and over again. The languages of Niklaus Wirth have spread wildly and widely because he has been one of the most conscientious documenters of languages and one of the earlier ones to do algorithmic languages using p-codes (pseudocodes) -- the same kinds of things that we use. The idea of using those things has a common origin in the hardware of a machine called the Burroughs B5000 from the early 1960s, which the establishment hated.

Any similarity between the above and PHP is, I'm sure, completely coincidental. That sound you're hearing is just a little bit of history repeating.

To me, the quintessential Alan Kay presentation is Doing with Images Makes Symbols: Communicating With Computers.

As the video illustrates, computers are almost secondary to most of Alan's work; that's the true brilliance of it. The real goal is teaching and learning. I'm reminded of a comment Andrew Stuart, a veteran software development recruiter, once sent me in email:

One subtle but interesting observation that I would make - your article points out that "what software developers do best is learn" - this is close to the mark, though I would rearrange the words slightly to "what the best software developers do is learn." Not all software developers learn, but the best ones certainly do.

And this, I think, lies at the heart of everything Alan does -- computing not as an end in itself, but as a vehicle for learning how to learn.

The Two Types of Browser Zoom

From the dawn of the web -- at least since Netscape Navigator 4.x -- it has been possible to resize the text on a web page. This is typically done through the View menu.

This was fine in the early, primitive days of the web, when page layouts were simple and unsophisticated. Want the font to be three times larger? No problem! Pump it up until your eyes bleed; you're unlikely to break the design, because there's precious little design at all.

But this was a time long before the web had become a platform for full-blown applications, with complex, dense, almost GUI-like designs.

The accepted web design guidance is that you should generally produce web page layouts that work at:

1. the default font size (obviously)
2. one size below the default font size
3. one size above the default font size

I agree, and you should be testing for this on your own websites. The handy keyboard equivalents in most browsers are:

(yes, holding down the Ctrl key and then scrolling your mouse scroll wheel works, too, but no real programmer would use that.)

It is important to let the user control their browsing experience. But I think that the traditional method of font-only browser sizing is a solution whose time has come and gone. There's a better way. Opera was the first browser to introduce full page zoom as an alternative to traditional font sizing, but Firefox 3 is where most people actually experience it. In fact, in Firefox 3, it's the default page sizing mode.

Note that "Zoom Text Only" is unchecked. And for good reason. Compare for yourself. Here's the Digg homepage using old-school Netscape 4.x style font scaling.

Browser Font Scaling: Default

Browser Font Scaling: Size +1

Browser Font Scaling: Size +2

Digg follows the design rule of thumb I suggested above: it scales to font size +1, but beyond that, all bets are off. With the fonts at +2, the top menu is scrunched, the search box clipped, and the digg numbers are spilling out over the boxes. The "most recent" navigation element has completely disappeared! Now compare this with the newer method of full page zooming:

Browser Full Page Zoom Scaling: Default

Browser Full Page Zoom Scaling: Size +1

Browser Full Page Zoom Scaling: Size +2

While the page does get wider, the full page zoom method has tremendous advantages:

1. Full page zoom works on almost every web page in the world, with no changes whatsoever by the web designers
2. Full page zoom scales far, far beyond the +1/-1 sizes that you can reasonably expect from traditional browser font sizing approaches.

To prove that full page zoom scales like nobody's business, here's a screenshot I captured of the Digg homepage scaled to fit the entire width of my 1920 x 1080 monitor. In comparison, increasing the fonts beyond +2 results in a jumbled, unreadable mess.

Honestly, I can't see much use for traditional browser font sizing. It's increasingly fragile on today's web. I wish more browsers would take the lead from Firefox 3, and adopt full page zoom as the new default page sizing method.

Die, You Gravy Sucking Pig Dog!

In the C programming language, you're regularly forced to deal with the painful, dangerous concepts of pointers and explicit memory allocation.

b1 = (double *)malloc(m*sizeof(double));

In modern garbage collected programming languages, life is much simpler; you simply new up whatever object or variable you need.

Double[] b1 = new Double[m];

Use your objects, and just walk away when you're done. The garbage collector will cruise by periodically, and when he sees stuff you're not using any more, he'll clean up behind you and deal with all that nasty pointer and memory allocation stuff on your behalf. It's totally automatic.

Pretty awesome, right? I'd wager the majority of programmers alive today have never once worried about malloc(). I call this progress, as does Jamie Zawinski:

Based on my experience using both kinds of languages, for years at a stretch, I claim that a good garbage collector always beats doing explicit malloc/free in both computational efficiency and programmer time.

However, I also claim that, because of the amount of programmer time that is saved by using GC rather than explicit malloc/free, as well as the dramatic reduction in hard-to-debug storage-management problems, even using a mediocre garbage collector will still result in your ending up with better software faster.

Most of the time, throwing memory and CPU at the problem is still cheaper than throwing programmer time at the problem, even when you multiply the CPUs/memory by the number of users. This isn't true all the time, but it's probably true more often than you think, because Worse is Better.

But even for programmers who have enjoyed automatic garbage collection their whole careers, there are still some.. oddities. See if you can spot one here:

sqlConnection.Close();
sqlConnection.Dispose();
sqlConnection = null;

That is one hellaciously closed database connection. Why don't you take it out back and shoot it, while you're at it?

Even with your friendly neighborhood garbage collector making regular rounds on commodity desktops/servers where many gigabytes of main memory are commonplace, there are still times when you need to release precious resources right now. Not at some unspecified point in the future, whenever the GC gets around to it. Like, say, a database connection. Sure, your database server may be powerful, but it doesn't support an infinitely large number of concurrent connections, either.

The confusing choice between setting an object to null and calling the Dispose method doesn't help matters any. Is it even clear what state the connection is in after Close is called? Could the connection be reused at that point?

Personally, I view explicit disposal as more of an optimization than anything else, but it can be a pretty important optimization on a heavily loaded webserver, or a performance intensive desktop application plowing through gigabytes of data.

Of course, your average obsessive-compulsive developer sees that he's dealing with a semi-precious system resource, and immediately takes matters into his own hands, because he can do a better job than the garbage collector. K. Scott Allen proposes a solution that might mollify both camps in Disposal Anxiety:

What the IDisposable interface needs is a method that promotes self-efficacy in a developer. A method name that can stir up primal urges as the developer types. What we need is a method like the one in BSD's shutdown.c module.

die_you_gravy_sucking_pig_dog()
{
	char *empty_environ[] = { NULL };

	syslog(LOG_NOTICE, "%s by %s: %s",
	    doreboot ? "reboot" : dohalt ? "halt" : dopower ? "power-down" : 
	    "shutdown", whom, mbuf);
	(void)sleep(2);

	(void)printf("\r\nSystem shutdown time has arrived\007\007\r\n");
	if (killflg) {
		(void)printf("\rbut you'll have to do it yourself\r\n");
		exit(0);
	}

Now, I know this function was written back in the days when steam engines still ruled the world, but we could modernize the function by applying some .NET naming standards.

sqlConnection.DieYouGravySuckingPigDog();

Can you feel the passion behind this statement? This statement carries the emotion that is hard to find in today's code. I hope you'll support this proposal. Good people will be able to sleep at night once again.

So the next time you feel anxious about letting objects fall out of scope, remember: you could always terminate them with extreme prejudice, if you feel it's necessary.

But it probably isn't.

Top 25 Most Dangerous Programming Mistakes

I don't usually do news and current events here, but I'm making an exception for the CWE/SANS Top 25 Most Dangerous Programming Errors list. This one is important, and deserves a wide audience, so I'm repeating it here -- along with a brief hand-edited summary of each error.

If you work on software in any capacity, at least skim this list. I encourage you to click through for greater detail on anything you're not familiar with, or that piques your interest.

1. Improper Input Validation

   Ensure that your input is valid. If you're expecting a number, it shouldn't contain letters. Nor should the price of a new car be allowed to be a dollar. Incorrect input validation can lead to vulnerabilities when attackers can modify their inputs in unexpected ways. Many of today's most common vulnerabilities can be eliminated, or at least reduced, with strict input validation.

2. Improper Encoding or Escaping of Output

   Insufficient output encoding is at the root of most injection-based attacks. An attacker can modify the commands that you intend to send to other components, possibly leading to a complete compromise of your application - not to mention exposing the other components to exploits that the attacker would not be able to launch directly. When your program generates outputs to other components in the form of structured messages such as queries or requests, be sure to separate control information and metadata from the actual data.

3. Failure to Preserve SQL Query Structure (aka 'SQL Injection')

   If attackers can influence the SQL that you send to your database, they can modify the queries to steal, corrupt, or otherwise change your underlying data. If you use SQL queries in security controls such as authentication, attackers could alter the logic of those queries to bypass security.

4. Failure to Preserve Web Page Structure (aka 'Cross-site Scripting')

   Cross-site scripting (XSS) is a result of combining the stateless nature of HTTP, the mixture of data and script in HTML, lots of data passing between web sites, diverse encoding schemes, and feature-rich web browsers. If you're not careful, attackers can inject Javascript or other browser-executable content into a web page that your application generates. Your web page is then accessed by other users, whose browsers execute that malicious script as if it came from you -- because, after all, it did come from you! Suddenly, your web site is serving code that you didn't write. The attacker can use a variety of techniques to get the input directly into your server, or use an unwitting victim as the middle man.

5. Failure to Preserve OS Command Structure (aka 'OS Command Injection')

   Your software acts as a bridge between an outsider on the network and the internals of your operating system. When you invoke another program on the operating system, and you allow untrusted inputs to be fed into the command string, you are inviting attackers into your operating system.

6. Cleartext Transmission of Sensitive Information

   Information sent across a network crosses many different nodes in transit to its final destination. If your software sends sensitive, private data or authentication credentials, beware: attackers could sniff them right off the wire. All they need to do is control one node along the path to the final destination, any node within the same networks of those transit nodes, or plug into an available interface. Obfuscating traffic using schemes like Base64 and URL encoding offers no protection.

7. Cross-Site Request Forgery (CSRF)

   Cross-site request forgery is like accepting a package from a stranger -- except the attacker tricks a user into activating a HTTP request "package" that goes to your site. The user might not even be aware that the request is being sent, but once the request gets to your server, it looks as if it came from the user -- not the attacker. The attacker has masqueraded as a legitimate user and gained all the potential access that the user has. This is especially handy when the user has administrator privileges, resulting in a complete compromise of your application's functionality.

8. Race Condition

   A race condition involves multiple processes in which the attacker has full control over one process; the attacker exploits the process to create chaos, collisions, or errors. Data corruption and denial of service are the norm. The impact can be local or global, depending on what the race condition affects - such as state variables or security logic - and whether it occurs within multiple threads, processes, or systems.

9. Error Message Information Leak

   Chatty error messages can disclose secrets to any attacker who misuses your software. The secrets could cover a wide range of valuable data, including personally identifiable information (PII), authentication credentials, and server configuration. They might seem like harmless secrets useful to your users and admins, such as the full installation path of your software -- but even these little secrets can greatly simplify a more concerted attack.

10. Failure to Constrain Operations within the Bounds of a Memory Buffer

    The scourge of C applications for decades, buffer overflows have been remarkably resistant to elimination. Attack and detection techniques continue to improve, and today's buffer overflow variants aren't always obvious at first or even second glance. You may think that you're completely immune to buffer overflows because you write your code in higher-level languages instead of C. But what is your favorite "safe" language's interpreter written in? What about the native code you call? What languages are the operating system API's written in? How about the software that runs Internet infrastructure?

11. External Control of Critical State Data

    If you store user state data in a place where an attacker can modify it, this reduces the overhead for a successful compromise. Data could be stored in configuration files, profiles, cookies, hidden form fields, environment variables, registry keys, or other locations, all of which can be modified by an attacker. In stateless protocols such as HTTP, some form of user state information must be captured in each request, so it is exposed to an attacker out of necessity. If you perform any security-critical operations based on this data (such as stating that the user is an administrator), then you can bet that somebody will modify the data in order to trick your application.

12. External Control of File Name or Path

    When you use an outsider's input while constructing a filename, the resulting path could point outside of the intended directory. An attacker could combine multiple ".." or similar sequences to cause the operating system to navigate out of the restricted directory. Other file-related attacks are simplified by external control of a filename, such as symbolic link following, which causes your application to read or modify files that the attacker can't access directly. The same applies if your program is running with raised privileges and it accepts filenames as input. Similar rules apply to URLs and allowing an outsider to specify arbitrary URLs.

13. Untrusted Search Path

    Your software depends on you, or its environment, to provide a search path (or working path) to find critical resources like code libraries or configuration files. If the search path is under attacker control, then the attacker can modify it to point to resources of the attacker's choosing.

14. Failure to Control Generation of Code (aka 'Code Injection')

    While it's tough to deny the sexiness of dynamically-generated code, attackers find it equally appealing. It becomes a serious vulnerability when your code is directly callable by unauthorized parties, if external inputs can affect which code gets executed, or if those inputs are fed directly into the code itself.

15. Download of Code Without Integrity Check

    If you download code and execute it, you're trusting that the source of that code isn't malicious. But attackers can modify that code before it reaches you. They can hack the download site, impersonate it with DNS spoofing or cache poisoning, convince the system to redirect to a different site, or even modify the code in transit as it crosses the network. This scenario even applies to cases in which your own product downloads and installs updates.

16. Improper Resource Shutdown or Release

    When your system resources have reached their end-of-life, you dispose of them: memory, files, cookies, data structures, sessions, communication pipes, and so on. Attackers can exploit improper shutdown to maintain control over those resources well after you thought you got rid of them. Attackers may sift through the disposted items, looking for sensitive data. They could also potentially reuse those resources.

17. Improper Initialization

    If you don't properly initialize your data and variables, an attacker might be able to do the initialization for you, or extract sensitive information that remains from previous sessions. If those variables are used in security-critical operations, such as making an authentication decision, they could be modified to bypass your security. This is most prevalent in obscure errors or conditions that cause your code to inadvertently skip initialization.

18. Incorrect Calculation

    When attackers have control over inputs to numeric calculations, math errors can have security consequences. It might cause you to allocate far more resources than you intended - or far fewer. It could violate business logic (a calculation that produces a negative price), or cause denial of service (a divide-by-zero that triggers a program crash).

19. Improper Access Control (Authorization)

    If you don't ensure that your software's users are only doing what they're allowed to, then attackers will try to exploit your improper authorization and exercise that unauthorized functionality.

20. Use of a Broken or Risky Cryptographic Algorithm

    Grow-your-own cryptography is a welcome sight to attackers. Cryptography is hard. If brilliant mathematicians and computer scientists worldwide can't get it right -- and they're regularly obsoleting their own techniques -- then neither can you.

21. Hard-Coded Password

    Hard-coding a secret account and password into your software is extremely convenient -- for skilled reverse engineers. If the password is the same across all your software, then every customer becomes vulnerable when that password inevitably becomes known. And because it's hard-coded, it's a huge pain to fix.

22. Insecure Permission Assignment for Critical Resource

    Beware critical programs, data stores, or configuration files with default world-readable permissions. While this issue might not be considered during implementation or design, it should be. Don't require your customers to secure your software for you! Try to be secure by default, out of the box.

23. Use of Insufficiently Random Values

    You may depend on randomness without even knowing it, such as when generating session IDs or temporary filenames. Pseudo-Random Number Generators (PRNG) are commonly used, but a variety of things can go wrong. Once an attacker can determine which algorithm is being used, he can guess the next random number often enough to launch a successful attack after a relatively small number of tries.

24. Execution with Unnecessary Privileges

    Your software may need special privileges to perform certain operations; wielding those privileges longer than necessary is risky. When running with extra privileges, your application has access to resources that the application's user can't directly reach. Whenever you launch a separate program with elevated privileges, attackers can potentially exploit those privileges.

25. Client-Side Enforcement of Server-Side Security

    Don't trust the client to perform security checks on behalf of your server. Attackers can reverse engineer your client and write their own custom clients. The consequences will vary depending on what your security checks are protecting, but some of the more common targets are authentication, authorization, and input validation.

Of course there's nothing truly new here; I essentially went over the same basic list in Sins of Software Security almost two years ago. The only difference is the relative priorities, as web applications start to dominate mainstream computing.

This list of software security mistakes serves the same purpose as McConnell's list of classic development mistakes: to raise awareness. A surprisingly large part of success is recognizing the most common mistakes and failure modes. So you can -- at least in theory -- realize when your project is slipping into one of them. Ignorance is the biggest software project killer of them all.

Heck, even if you are aware of these security mistakes, you might end up committing them anyway. I know I have.

Have you?

If You Don't Change the UI, Nobody Notices

I saw a screenshot a few days ago that made me think Windows 7 Beta might actually be worth checking out.

That's right, Microsoft finally improved the calculator app! We've been complaining for years that Microsoft ships new operating systems with the same boring old default applets the previous version had, which makes the entire operating system look bad:

I know it sounds trivial. But isn't the fit and finish of little applets like these -- Notepad, Calculator, Character Map, Paint, Disk Cleanup, Compressed Folders, and dozens of others -- indicative of the care and design that goes into the entire operating system? If Microsoft can't be bothered to bundle a version of Notepad that has basic amenities like a toolbar, what hope does the rest of the operating system have?

If you visually compare Calculator and Notepad in 2001-era Windows XP with their 2007 Windows Vista equivalents, you might conclude they're identical. But, as Raymond Chen notes, this isn't so:

I find it ironic when people complain that Calc and Notepad haven't changed. In fact, both programs have changed. (Notepad gained some additional menu and status bar options. Calc got a severe workover.) I wouldn't be surprised if these are the same people who complain, "Why does Microsoft spend all its effort on making Windows 'look cool'? They should spend all their efforts on making technical improvements and just stop making visual improvements."

And with Calc, that's exactly what happened: Massive technical improvements. No visual improvement. And nobody noticed. In fact, the complaints just keep coming. "Look at Calc, same as it always was."

The innards of Calc - the arithmetic engine - was completely thrown away and rewritten from scratch. The standard IEEE floating point library was replaced with an arbitrary-precision arithmetic library. This was done after people kept writing ha-ha articles about how Calc couldn't do decimal arithmetic correctly, that for example computing 10.21 - 10.2 resulted in 0.0100000000000016. Today, Calc's internal computations are done with infinite precision for basic operations (addition, subtraction, multiplication, division) and 32 digits of precision for advanced operations (square root, transcendental operators).

It's arguably the perfect Raymond Chen post -- technically dead on, while simultaneously proving that being technically dead on is utterly irrelevant. That's Raymond Chen for you: he's a riddle wrapped in a mystery inside an enigma, slathered in delicious secret sauce.

This is why the screenshot of the Windows 7 Calculator, although seemingly trivial, is so exciting to me. It's evidence that Microsoft is going to pay attention to the visible parts of the operating system this time around. I'm a fan of Vista, despite all the nerd rage on the topic, but I'll be the first to admit that Vista had all the polish of a particularly dull rock. Let's just say the overall user experience was.. uninspiring. This led many people to shrug, sigh "why bother?", and stick with crusty old XP.

This was unfortunate, because if you dug into Vista, you'd find quite a few substantive technical improvements over the now-ancient Windows XP. But many of those improvements were under the hood, and thus invisible to the typical user.

Remember, if the user can't find it, the function's not there. Don't bother improving your product unless it results in visible changes the user can see, find, and hopefully appreciate.