Optimization

The first rule of optimization is to optimize later. The second is to see rule one. Based on a treatise on optimizing compilers, let me tell you a small story. Marc, from Germany, wanted to optimize this line of C99 code:

for (int i=0; i < numElems; i++) theArray[i] = 0;

What we have here is an algorithm. Every algorithm has a purpose. Clearly, this algorithm's purpose is to initialize an array of integers to all zeros. Consider an alternative algorithm, also in C99:

int i=numElems; while (--i) theArray[i] = 0;

The algorithm is different, but it has the same purpose and effect. At the end, all elements of theArray are zero. Therefore, one line of code may be replaced with the other. Marc's compiler might produce different machine code for the two algorithms, and one might run a bit faster than the other. Whoopee.

Both of the above two lines of code have forced an unnecessary decision upon Marc. Should the index variable increment or decrement? The best answer is that Marc should not have to think about it. Consequently and for other reasons, Marc's best choice is this algorithm:

memset(theArray, 0, numElems);

My point is that the standard library provides a routine that performs the task well. It doesn't have to be written in C, although it may be. It will be pre-optimized once for your system. The compiler doesn't have to do any special work. But far more important, the purpose and effect of the line of code is infinitely more clear from the function call than it ever was from either explicit loop. This way is more clear. It is shorter and easier to read. It probably takes less run time than anything you might write yourself. The only downside I observed was that I had to look up the argument order. However, if I did use this routine often enough to where that was an issue, I would have learned the argument order just fine. Anyway, modern IDEs are providing hints for that.

All that being said, optimizing compilers are a great deal. They can have a big impact on run times. But please never make comparisons of optimizers based on such simple benchmarks. Spectacular performance comes soonest from having a spectacular library, finely tuned with assembler only wherever it makes a difference.

We might like to write weird numerical algorithms (say, MP3 decoding) in a high-level language and have it be really fast. The first step is always to find a good library that handles the problem already. Otherwise, if your optimizer is pretty good, then you'll be hard-pressed to do better in assembler yourself. And if your compiler doesn't optimize, then you've just found an application for the assembler. But in no event should you bother about hand-optimizing code that runs fast enough already, nor is it practical to re-invent wheels.

A Systems Programming Language?

When we speak of a language suitable for systems programming, we really mean the implementation of the language. After all, interpreted C could exist, but you wouldn't probably want to make a kernel with it, while a Linux kernel has been translated (almost) entirely to ML and used in a research system. If memory serves, the ML Linux kernel was just as fast on all the standard benchmarks as the C version, or perhaps faster.

To get around to the actual question: what are the real characteristics we demand for a systems-programming language implementation, and which are merely an accident of history? I think the answer is this: the implementation should be fast, and it should be possible to exploit the full capabilities of the machine either through constructs of the language directly or by linking assembler modules into the rest of the program. Linkages are well-understood, so the question boils down to making the language execute rapidly.

Certainly we want a means of calculation which produces results quickly, using a minimum of CPU resources. This means that the implementation must translate arithmetic directly to corresponding CPU arithmetic instructions. For this to work, numeric data must be stored in ways that require minimal effort to load and store. This is why the parameters to and local variables of the current routine are ordinarily held as words relative to some register, such as the stack pointer or base pointer on an X86.

So much for arithmetic. There are two other major concerns for a programming language: control and abstractions. The latter can be thought of as procedural and data abstractions.

Control means conditional and repeated execution. If arithmetic happens with CPU-native data types, then CPU-native conditional jumps (or perhaps predicated execution, if you go in for Itanium2-style code) are the choice means to implement control.

Data abstraction is done quite differently in languages like Perl vs. those like Pascal. I claim that the Pascal approach is inherently more reliable. In Perl, everything is either a scalar, a list, or an associative dictionary. Having that, Perl strives to make the most common access patterns to such structures be relatively quick. On the other hand, in Pascal, there is a proper "type algebra" of arrays, records, sets, and scalar types. Expressions in the executable portion of the code must properly match the type declarations up front. In Pascal, this is not done for the programmer's benefit. It's done so that the Pascal compiler can determine at compile time how to write code to access particular data by name or index, without having to keep the names or definitions around at run time. The cost saved is the cost of consulting a dictionary for each use of an aggregate type. The reason type definitions must come before their use in Pascal is that the compiler must be implementable in a single pass. So now we have it: advance knowledge of data structures can be built into data access methods, allowing said methods to be specialized to their actual use, which produces rapid data manipulations. In truth, Perl's lists and hashes are done in terms of these very ideas. However, the generality of the Perl hash is excessive in certain contexts, and it decelerates Perl code. Thus, people don't write kernels in Perl.

As a rule, it seems early generality is a performance brake, despite being a boon to the rapid development of small programs. Consider the standard means of procedural abstraction: the subroutine. I consider subroutines to fall into two categories: those which compute a function of their arguments, and those which cause externally-visible effects based upon their arguments. The latter do not normally return a value, but they may fail for a variety of worldly reasons, and both categories may fail if the arguments are not suited to the operations.

In general, subroutines are converted directly to a stack-based analogue. Each declared routine gets an entry point and a calling convention. Meanwhile, every mention of the routine is converted to a call to this entry point surrounded by appropriate set-up and tear-down. Friends, that's premature generality, and C suffers badly from it. The presence of the "inline" keyword in C99 is more a symptom than a cure: programmers should not be worrying about that detail. Rather, it's incumbent upon a good compiling implementation of a language to automatically identify suitable candidates for "inlining" and just produce good code. For one thing, any routine called from only one place is a fabulous candidate. Also, very small routines are also good candidates. But in any event, the language definition should leave that concern to the compilers. This is why Haskell programs occasionally outrun their C analogues. It's not the algorithm, but the quality of its implementation. Tail-call elimination, for example, seems like a really good idea, but it makes odd demands on the stack. It's easiest done by pushing the return address beneath the actual parameters to a subroutine, but the CPU normally provides a simple way only to do the opposite. Therefore, if you want to eliminate tail calls, you get bulkier programs which probably run just as slow as the naive stack-based evaluator. The real gains come from converting recursive routines into iterative ones, unrolling loops, and automatically inlining good stuff. That's what eliminates wasted cycles. Well, that and fundamental algorithmic improvements.

We know what performance characteristic the CPU stack offers: allocation and release are stupefyingly quick, but you can only release at the top of the stack. This produces a fine model for function evaluation as long as no data outlives its activation record. However, some data usually does. It's called a return value. It has to be given back to the caller. This is usually done with a register, but structured return values can actually be treated as implicit output parameters. The caller provides a pointer to the location where space has been reserved for a returned record. The limitations of the stack are traditionally overcome by way of a dynamic heap. However, consider a kernel: it has no heap in the normal sense. There's just physical ram and an MMU. The kernel must implement a system for the allocation of pages, not bytes. It's also known that an automaton with two or more stacks is Turing-complete. This leads to some ideas for later on. For now, know that dynamic memory allocation is important for applications, but it seems a mistake to embed the idea of a single global heap into the grammar of the programming language.

I have not explicitly deconstructed polymorphism as it relates to data abstraction. Presumably, various concrete classes of data are associated with operations with mutually corresponding semantics. A call that makes use of polymorphism means that we wish to invoke the correct implementation of the semantics given the concrete class of a particular datum, when that concrete class is not necessarily known in advance (such as at compile time). I'm working on this idea that polymorphism is only half of a whole concept. I'll cover it in another article.

By now, we've seen the basic ideas behind a fast implementation of a language. But truly, one factor is often neglected. A good systems programming language must first of all be a good programming language. And this requirement is so huge that it's a topic in itself. The best thing about a good programming language is that the suitability for systems-level programming is only a compiler away.