It seems to me that if you wanted to really put an end to the old “C is faster than X” (where X is your favorite High Level Language) snickers and arguments you’d start taking advantage of the vast amounts of information contained in a High Level Language program as opposed to a Low Level Language program.

What do I mean? Well, because C programs are so low-level—they’re all about byte manipulation, basically—the compiler doesn’t really know anything more than byte operations. There is no high-level semantics. The constraints and meanings embedded in the semantics of a high-level language allow for lots and lots of optimizations.

Let’s look at some successes.

By far, I think the one that comes to mind the most easily is Haskell. Part of the semantics defined by the language is that there are no visible side-effects (at least in a large portion of the code). This means that the compiler can optimize out lots of unnecessary computation. How does it do it? No side effects means that you can do lazy evaluation. Basically, that means don’t calculate anything you don’t need to, and if you do calculate it, you might as well remember it so you won’t have to calculate it ever again.

So, automatically, all of this code you wrote that would, using a naive version, create billions of conses now only creates a few hundred. Automatic optimization. You can’t do that in C because there’s no way to know what the program is trying to do—because anything is allowed. And all of that information is used at run-time. Haskell does some other cool optimizations, too. I just don’t know enough about them.

Here’s another example: tail-call removal in Scheme. Most Common Lisp implementations do it, too. But in Scheme it’s part of the standard. What does it mean? When you write a recursive function in a certain format, it is automatically converted to an iterative function that generates the same value.

Steve Yegge has a whole talk on how run-time information trumps compile-time information. He says there are techniques now that can let a VM adapt to dynamic typing information so that it approaches the speed of static typing. But only if you have some kind of runtime environment.

These are all great. But they’re not enough. So many optimizations are done at a low level. But they only gain so much. Here’s a question: would you rather optimize a function so that it takes 10 instructions instead of 15 OR optimize the whole algorithm to call the function half the number of times? High-level, algorithmic optimizations trump low-level optimizations.

Here’s an optimization I wish my Lisp implementation did (if it does do this, let me know. I’ll jump for joy): convert (= 10 (length list)) to (length= 10 list).

Huh?

This is what I mean: it should rearrange the AST at compile-time to semantically equivalent programs that are more efficient.

If I write (length list), it will recurse down the list and add 1 for each cons in it. But if I only want to know if there are exactly ten items in the list, the LENGTH function is going to go to the end of the list anyway. Even if there are 10 billion items in the list. That is not smart. What most people say is that you should do it yourself, changing (= 10 (length list)) to (length= 10 list), which only recurses 10 times at most.

But what I say is that the compiler can do it. LENGTH is part of the standard language, and so is =. They should get compiled away. Further, I think there should be an entire framework that lets you define and manage your own optimizations. Since you know the semantics of your own programs, you should be able to define all sorts of great optimizations without having to mess up your clean code.

Oh, and why is tail-call removal the only kind of recursion-to-iteration techniques used? There are lots more! Read the paper called “A system which automatically improves programs”. I love old papers! So full of untapped goodness.

That paper is so chock full of good stuff that I’ll reserve giving it a thorough review here. However, this quote will explain nearly everything:

(defun reverse (x)
   (if (null x)
      nil
      (append (reverse (rest x))
         (list (first x)))))

(defun reverse (x)
   (let ((result nil)
      (temp nil))
      (loop while (not (null x))
         do (setf temp (rest x))
         (setf (rest x) result)
         (setf result x)
         (setf x temp))
      result))

So the code it transforms it into in the quote above is destructive: it modifies the list. But in the paper it shows that it’s optional. The Lisp implementation they wrote makes that an interactive step. But the conversion of the recursion to iteration is just as safe as tail-call elimination—and clearly defined in the paper. Why aren’t we doing this?

I would love to see a system where you can define your own optimizations as transformations of the AST. Transformations that are applied automatically or optionally turned on or off if you like. Simple pattern matching would do. The paper I cited is not a simple pattern matching operation. It’s more complex—but definitely doable.

While the C coders are busy digging through their optimized spaghetti code, the Common Lisp compiler is intelligently rewriting your highly abstract program for you. I love it!

Related Posts:

• No Related Posts