Optimizing everything: some details matter a lot, most don't

Optimization is something that all engineers and product designers (all people, really) should understand. However, their words and behavior suggest that most either don't understand it, or haven't really internalized the lessons of optimization. (and by the way, I'm talking about CS-style "make it better" optimization, not "make it optimal" optimization)

Like everything, optimization is a complex topic, so I'm going to simplify it into three easy steps:

1. Find the problems ("profiling")
   
2. Sort the problems according to benefit-of-fixing/cost-of-fixing ("ROI")
   
3. Fix them, in the order of highest benefit/cost to lowest
   

Most programmers probably think of optimization primarily in terms of CPU profiling, but it really applies to everything. (and in fact, this post is about the general process of optimizing, especially for things other than code -- for specific cases of hardcore game engine optimization or whatever it might be totally wrong)

For example, people who continually "pinch pennies" (perhaps driving around town to save a few cents on gas) but then waste thousands of dollars on something stupid like a fancy car or credit card interest are probably not optimizing their spending very well. They are putting most of their effort into low reward activities (saving a few cents on gas) while losing much more money in other places. Big, dumb, Dilbertesque companies are also notorious for this kind of thing, cutting back on pencils while running super-bowl commercials, or something.

This is also the kind of activity that I was talking about in my post titled "Wasting time on things that really don't matter". It's not that there is zero difference between two slightly different ways of testing for the empty string, it's just that your product probably has 100,000 more serious problems, and so time spent worrying about the empty string style is time NOT spent fixing those more important problems. Put another way, fix all of the other problems first, then debate the empty string.

Of course you may enjoy debating the empty string (and in fact there are some interesting arguments), and that's fine. The zeroth step in optimization is to decide what you are optimizing for. If you're looking to maximize the amount of time spent on endless debates, or perhaps code "beauty", then maybe the empty string debate really is the highest benefit/cost activity (because the benefit is so high). If, on the other hand, you are trying to maximize the success of your product, then the empty string debate probably has negative value and should be strongly avoided.

The empty string comparison is obviously a small detail, and it's tempting to think that we should not bother with such small details, but that too is a huge mistake. Another important lesson of optimization is that some small fraction of the details will determine the majority of the outcome. This is commonly referred to as the 80/20 or 90/10 rule, stating for example that "90% of the time is spent in 10% of the code", but it could just as easily be 99/1 or something like that (and for code that has already been well optimized, this 80/20 rule may not hold -- it's just a heuristic). In code it may be just a few lines in the "inner loop", or perhaps it's the interest rate on your mortgage ("what's a few percent?"). I once profiled a server at Google and discovered that something like 90% of the time was being spent on a single line of code: a call to sscanf (repeated millions of times) that someone had snuck into the scoring code (that's the 99999/1 rule).

Determining which details matter a lot (and which don't) is also the key to designing successful products. In the classic slashdot iPod post from 2001, they summarized the newly released iPod thusly: "No wireless. Less space than a nomad. Lame."

History suggests that those weren't the important details, since it's 2007 and there still isn't an iPod with wireless (not until the 29th, at least), and most iPods have less than the original 5GB of storage. Apple did, however, get a few very important details right: it's easy to get your music onto an iPod, it holds "enough" music (unlike the early flash players), and it fits easily into your pocket (unlike the early disk-based players).

So how do we determine which details are important? Observation. (and some judgment, but I think that's mostly formed via observation) If you're optimizing an application, observe which resources are being exhausted or causing the delay (it's not always CPU -- it's often disk seeks), and then observe where they are being consumed. If you're trying to optimize money, first observe where most of the money goes to and comes from. To optimize a product design, observe which things are most "useful", and which are most painful or annoying (waiting or thinking, usually).

If you get all of the important details right, you'll be so far ahead of everyone else that the other details probably won't matter. But remember, your time is finite, so time spent on unimportant details is time not spent on important details! Most engineers are very detail oriented people, and this is good because they can really focus on the important details, and it is bad because they can really focus on the unimportant details! I suspect that learning to tell the difference will be worth your time.

By the way, to get even more details right, decrease the cost side of the benefit/cost equation so that you can do more things in less time (by finding easier solutions, avoiding endless debates, etc).

Java running faster than C

Note: A lot of people seem to be taking this post to be the "Ultimate C vs Java shootout". It's not. Performance is a very complex topic. My only real point is this: Java (which used to be slow) has reached the class of "fast languages". For the majority of applications, speed is no longer a valid excuse for using C++ instead of Java.

I just saw this page comparing the performance of several languages on a simple Mandelbrot set generator. His numbers show Java being over twice as slow as C, but then I noticed that he's using an older version of java and only running the test once, which doesn't really give the JVM a chance to show off.

I quickly hacked up the code to run 100 iterations 3 times and then used my standard "go fast" flags (there may be better flags, but I'm lazy). Here are my results:

$ java -server -XX:CompileThreshold=1 Mandelbrot 2>/dev/null
Java Elapsed 2.994
Java Elapsed 1.926
Java Elapsed 1.955

$ gcc -O8 mandelbrot.c
$ ./a.out 2>/dev/null
C Elapsed 2.03
C Elapsed 2.04
C Elapsed 2.05

C still wins on the first iteration, but Java is actually slightly faster on subsequent iterations!

Obviously the results will be different with different code and different machines, but it's clear that the JVM is getting quite fast.

This test was run with Java 1.6.0-b105 and gcc 4.1.2 under Linux 2.6.17 under Parallels on my 2.33GHz Core 2 Duo MacBook Pro. Here is the hacked up code: Java and C.


For extra fun, I also tried running the JS test using the Rhino compiler:

$ java -cp rhino1_6R5/js.jar -server -XX:CompileThreshold=1 org.mozilla.javascript.tools.shell.Main -O 9 mandelbrot.js 2>/dev/null
JavaScript Elapsed 21.95
JavaScript Elapsed 17.039
JavaScript Elapsed 17.466
JavaScript Elapsed 17.147

Compiled JS is about 9x slower than C on this test. If CPU speed doubles every 18 months, then JS in 2007 performs like C in 2002.


Update: A few more cpp flags have been suggested. -march=pentium4 helps a little, but it's still slower than Java.

$ gcc -O9 -march=pentium4 mandelbrot2.c
$ ./a.out 2>/dev/null
C Elapsed 1.99
C Elapsed 1.99
C Elapsed 1.99

Adding -ffast-math puts C in the lead, but I'm not sure what the downside is. The gcc man page says, "This option should never be turned on by any -O option since it can result in incorrect output for programs which depend on an exact implementation of IEEE or ISO rules/specifications for math functions." That sounds like an optimization that Java might not use.

$ gcc -ffast-math -O9 -march=pentium4 mandelbrot2.c
$ ./a.out 2>/dev/null
C Elapsed 1.66
C Elapsed 1.67
C Elapsed 1.67

Update: Several people have claimed that the performance difference is due to fputs (including the top rated comment on reddit, aumusingly). That is not correct, at least not on my computer. I tried replacing the print calls with a trivial function (but with side-effects), and it actually helped the Java more than the C:

C Elapsed 1.88
Java Elapsed 1.554

Many people have pointed out that '-O8' is more than enough 'O' levels. I know, and I don't care -- it's just as good as '-O3' or whatever.

Wasting time on things that really don't matter

It's easy to waste a lot of time debating things that aren't very important. Maybe that's fun if you don't have anything better to do, but when you're actually trying to accomplish something it can be deadly.

This post on "coding horror" is a great example of this phenomenon, or more specifically, the comments are a great example. At least half of the comments are from people who are debating which of these two lines of code are better:

if (s == String.Empty)
if (s == "")

Here's my answer: It's not important!

It's easy to get dragged into these debates because we all have opinions (and the one form really is better!), and of course the more time is spent talking about the issue the more important it seems.

Here's my trick for killing these stupid debates: Let's list all the issues and problems that we are facing right now. Now, where does this issue rank on that list? Is it in the top 10? The top 100? The top 1000? Are we spending more time talking about this one minor issue than we are spending working on any of our top ten issues? (You don't necessarily have to make the list -- just suggest that it exists and then guess where on the list the issue appears)

Sometimes that works. Sometimes it brings a little perspective.

And yes, this misallocation of time (aka "worrying about dumb stuff") is probably a top 10 productivity killer.


Update: Here's a good link (via news.yc) which offers one explanation for why people often spend the most time on the least important issues:

Parkinson shows how you can go in to the board of directors and get approval for building a multi-million or even billion dollar atomic power plant, but if you want to build a bike shed you will be tangled up in endless discussions.

Parkinson explains that this is because an atomic plant is so vast, so expensive and so complicated that people cannot grasp it, and rather than try, they fall back on the assumption that somebody else checked all the details before it got this far. Richard P. Feynmann gives a couple of interesting, and very much to the point, examples relating to Los Alamos in his books.

A bike shed on the other hand. Anyone can build one of those over a weekend, and still have time to watch the game on TV. So no matter how well prepared, no matter how reasonable you are with your proposal, somebody will seize the chance to show that he is doing his job, that he is paying attention, that he is *here*.

Update Two: Wasting time is fine, and even inane discussions of the best way to compare empty strings can be interesting. My real point is this: if we are actually trying to get something done, then we need to kill this stuff, or it will kill productivity. If, on the other hand, we're ok being in time-wasting-mode, then silly debates are probably harmless enough. I picked on the blog comments above not because there is anything wrong with them per-se (what are blogs for, if not inane debate?), but because it reminded me a lot of the silly debates that I've seen on work mailing lists (where they do cause harm).

Amazingly bad APIs

I actually don't hate the Java language (at least it's killing off c++), but every time I use it I'm blown away by how hostile the APIs are.

For example, let's say that we want to scale an image file. That's a fairly common thing to do, so it's probably only one line of code, right? Wrong. It turns out that they haven't even bothered to include a reasonable API for doing this. Instead, you have to take the awkward APIs that they do provide, and then write about 50 lines of code to do what you really want. This article that explains what the "right" way is.

Once the image is scaled, you'll want to save the smaller version too. Luckily, that's only a few lines of code. Of course that's only if you're happy with the default settings -- what if you want to use a different JPEG quality level? Here are the docs -- see if you can figure it out (the solution involves 4 additional classes).

For comparison, here is some Python code which loads an image, scales it, and then saves it at a non-default quality level:

from PIL import Image

i = Image.open("/tmp/c.jpg")
i.thumbnail([220, 133], Image.ANTIALIAS)
i.save('/tmp/c-thumb.jpg', quality=90)

Doing the same thing in Java requires closer to 100 lines, not because the language is bad, but because the APIs are terrible.

How did this happen? My theory is that the people who made the Java APIs just sat in a room making stuff up (and possibly drawing UML diagrams). Meanwhile, the Python people were actually writing software and creating libraries to make their life easier.

There is a lesson in this: If you are building a platform, you should also be writing applications for that platform, and the platform should be designed to make life very simple for those apps. It's my understanding that Ruby on Rails came out of a process such as this (they extracted the common tasks out of their web apps). If you just sit around staring at the clouds while writing your APIs, you'll probably end up with something bad.

I also have a second theory about what happened to Java: it attracted people who like to write piles of code filled with endless abstractions. When I worked at Google, one of the engineers on our Java mailing list suggested that we ban the keyword 'new'! I was puzzled by this suggestion, but after a little research I learned that one of the hot fashions in Java is to use factories instead of 'new' (not that factories are bad, but "sometimes good" does not imply "always best"). Better yet, you don't reference the factories directly (not enough abstraction), instead you have some framework that injects the factories into your classes according to what is written in an XML configuration file. In this way, you can make your code perfectly unreadable, but more importantly, it is very abstract.


Update: Several people have interpreted this post to mean that I'm opposed to the factory pattern. That is, of course, silly. Factories, when the situation calls for them, are fine. For example, the python code above is using a factory. What harms code is the blanket application of the factory pattern in every possible situation. To put this another way, Tabasco sauce is delicious on eggs, but I still don't put it on ice cream. (but don't think I haven't tried!)

Update Two: It's not about Java, really! My point here is that your APIs should emerge from the needs of real applications, and that they should make common tasks super-easy. Bad APIs are common in many languages, Java just happens to be the language that I'm using right now.

Why didn't I simply hunt down+install some third-party image library? Because that's a hassle too (probably more work than copying code off of some web page), and all I want is to generate nice looking thumbnails.

Flash, Silverlight, and JavaFX all look nice, but what I really want is better file upload

One of the most annoying limitations when writing web apps comes from the <input type="file"> form element, which is the standard way of uploading files.

Here are a few of the problems with <input type="file">:

• You can only select a single file per input element, and there is no way to select entire folders.
  
• Web browsers just pop-open the standard file open dialog, which is often not very good. For example, the dialog probably just shows a list of files, not thumbnails. This can make it difficult to pick the correct file if they all have names like IMG_3485.JPG, and it's therefore easy to upload the wrong file.
  
• There is no way to actually read the data locally without first sending it to the server and then having the server send it back.
  
• There is no way to do any local processing on the data, such as scaling images to make them smaller.
  

Flash apparently solves the multiple file problem (kind of), but it's my understanding that it still has all of the other problems (I'd love to be wrong about this though).

Java applets can actually do most of these things if they are signed and the user agrees to allow the applet access to their filesystem. Unfortunately, Java applets don't actually work, and after 11 years of not working, I'm not expecting that to change. Facebook has a nice image uploader applet that lets you browse your photos locally and then scales them before uploading to make the whole thing go fast. The only problem, other than the annoying "do you want to trust this applet" prompt, is that it crashed my browser the second time I tried it.

To me, the great thing about flash is that it fills in basic capabilities missing from the browser, such is video, sound, camera and microphone access, and they did it with a reasonably small and stable browser plugin that I'm not afraid to allow onto my computer. A few months ago, I accidentally upgraded one of my computers to Flash 9 -- I don't remember how exactly, I just remember that it was simple and non-eventful.

Here's my idea: I want to create a small, reliable browser plugin that does for file uploads what flash does for audio and video. It should work with all the modern browser/os combinations, and install with minimal effort and fuss (browser restarts avoided if possible). It would be free and open source, but hosted in a common location for easy install.

Popular Ajax libraries such as jQuery, YUI, and Dojo can add support in such a way that people who don't have the plugin just get the regular browser upload control (and maybe a link to install the plugin), while those who do have the plugin get a better ui. Clearly, getting people to install a new plugin isn't easy, but once any site convinces them, their experience automatically gets better on all other sites that support the plugin. There isn't a chicken&egg problem because the plugin simply provides an enhancement to the already existing (but very poor) browser functionality, so sites can easily add support without fear of losing people who don't have the plugin (unlike building a whole app in silverlight, or whatever).

I'd like to hear from anyone with experience writing browser plugins. How difficult is the technology side of this? (making it small, reliable, and stable -- crashing browsers is not ok) Also, are you interested it writing this plugin? I'm serious about this, and willing to pay quite a bit of money to make it happen.

Here are a few more details on how I imagine the plugin working:

It would not have any in-browser UI -- it would simply be an object that can be called from javascript and that would pop open a nice file browser with thumbnails and all that (similar to windows explorer, perhaps). It would also provide upload-related utility functions, such as image resizing. Since the file access is read-only and limited to what the user selects, security shouldn't be a big problem, assuming of course that the plugin implementation is secure (and it must be).

Here is some JS illustrating how I imagine using this plugin (UploadHelper is the object provided by the plugin):

// Have the user choose files or directories to upload.
// Returns undefined if user clicks Cancel. Doing this with a
// callback instead of a return value would also be ok.
var files = UploadHelper.chooseFiles(
              {filter:'*.jpg,*.gif,*.png', allowDirectories:true});
if (files) {
  var s = 'You selected: ';
  for (var f in files) {
    var file = files[f];
    s += (file.name + " (" + 
          file.imageinfo().width + "x" +
          file.imageinfo().height + ", original size = " + file.size);

    files[f] = file.scaleImage({maxwidth:100, maxheight:100, quality:5});
    s += " scaled size = " + files[f].size + ") ";

    // If I could somehow insert this image on the current web page
    // too, that would be really awsome.
  }
  alert(s);
  
  // using jquery XMLHTTP wrapper
  $.ajax({
    type: "POST",
    url: "/upload",
    data: UploadHelper.encode(files, 'multipart/form-data'),
    contentType: 'multipart/form-data'
  });
}

var files = UploadHelper.chooseFiles({filter:'*.txt'});
if (files) {
  // We can also read the content of the selected file
  // The ability to get chunks of a file also means that it's possible
  // to restart failed uploads, and to chunk large files into multiple
  // POSTs.
  for (var f in files) {
    var file = files[f];
    var d = file.getData(0, 50); // get the first 50 bytes
    if (file.size > 50) d += "...";
    alert(files[f].name + ": " + d);
  }
}

Update:

Several people have suggested that I should instead try to get this feature added to web browsers or (better yet) the web browser standards. That's a fine long-term solution, but realistically it will take years to happen. I would rather have an immediate (months, not years) fix in the form of a plugin, and then let the web browsers add it as a standard feature on their own schedule. This is somewhat similar to the path followed by XMLHTTP.

Sriram Krishnan of Microsoft makes a few good points:

• The standard file open dialog in windows already has a thumbnail view. Unfortunately, this feature is hidden under a completely unremarkable icon and despite having used windows for many years, I've never seen it before today. This is a great example of why simply adding a feature isn't good enough -- it also needs a good ui or else it may as well not even exist. Furthermore, not existing seems to be the status of the thumbnail view on OSX -- hopefully that will be fixed in 10.5.
• This feature request could be implemented in Silverlight. That's great news! MS should write and release a little Silverlight control that provides these functions to JS. I would be very hesitant to write (or rewrite) my apps in Silverlight, but if I could simply embed a little Silverlight module the same way that I would a flash mp3 player, then I'd definitely use that. This would be a very effective way for MS to get people started installing and using Silverlight (start with something small and optional).

Silverlight sounds pretty nice. Google or Adobe had better have an open alternative on the way, or else MS may be able to recapture the application platform.

Update Two:
I believe that within a few months we will have a few reasonable solutions to this problem!

When people don't know how to change something, they often start searching for a way to justify failure, rather than thinking about how they could try doing something different to make it work.
...
If we pretend that you can teach anyone anything, we'll find out where it's not (yet) true. But if we think that when someone isn't learning it means they can't be taught, no one will even try.
...
If you take the attitude that anything is possible, you'll find that a lot of things that were previously thought impossible actually do become possible.

Page 125

Beliefs, intelligence, and failure

From the book "Hard Facts, Dangerous Half-Truths, and Total Nonsense" (via this blog, via an email from a friend):

A series of studies by Columbia University's Carol Dweck shows .... that when people believe they are born with natural and unchangeable smarts ... [they] learn less over time. They don't bother to keep learning new things.

People who believe that intelligence is malleable keep getting smarter and more skilled ... and are willing to do new things.

That's a pretty important fact. It's also an excellent example of how your success is determined by your beliefs/mindset/frame. If you believe that you can't get smarter, you won't!

I searched around a bit and found another interesting quote:

...beliefs about the nature of intelligence have a significant impact on the way they approach challenging intellectual tasks: Students who view their intelligence as an unchangeable internal characteristic tend to shy away from academic challenges, whereas students who believe that their intelligence can be increased through effort and persistence seek them out.

Students who hold an "entity" theory of intelligence agree with statements such as "Your intelligence is something about you that you can't change very much." Since they believe their intelligence is fixed, these students place high value on success. They worry that failure-or even having to work very hard at something-will be perceived as evidence of their low intelligence. Therefore, they make academic choices that maximize the possibility that they will perform well. For example, a student may opt to take a lower-level course because it will be easier to earn an A. In contrast, students who have an "incremental" theory of intelligence are not threatened by failure. Because they believe that their intelligence can be increased through effort and persistence, these students set mastery goals and seek academic challenges that they believe will help them to grow intellectually.

Not only does a belief in fixed intelligence prevent learning, it also makes people more risk averse! It's easy to see how some cultures or micro-cultures make people successful, while others keep them mired in failure.

I expect that this same basic principle applies to most things, whether it's skills with computers or skills with people. Obviously "nature" plays some role, but beliefs, knowledge, and determination are usually more important. Furthermore, I suspect that you can learn to enjoy these activities, and that finding the fun is the key to mastering the skill.