WEBster Home Page

The Great Debate

"Will Compilers Ever Produce Code as Good as an Expert Assembly Language Programmer?"

(Randall Hyde)

The "Great Debate" is a very emotional exchange that has been running continuously since the late '70s. On some newsgroup somewhere, you will find a thread discussing this topic; although you will have the best luck looking at the Internet comp.lang.asm.x86, comp.lang.c, alt.assembly, or comp.lang.c++ newsgroups. Of course, almost anything you read in these newsgroups is rubbish, no matter what side of the argument the author is championing. Because this debate has been raging for (what seems like) forever, it is clear there is no easy answer; especially one that someone can make up off the top of their head (this describes about 99.9% of all postings to a usenet newsgroup). This page contains a series of essays that discuss the advances of compilers and machine architectures in an attempt to answer the above question.

Although I intend to write a large number of these essays, I encourage others, even those with opposing viewpoints, to contribute to this exchange. If you would like to contribute a "well thought out, non-emotional essay" to this series, please send your contribution (HTML is best, ASCII text is second best) to

debate@webster.ucr.edu



To begin with, I would like to address the topic of the debate itself. This is very important, because so many discussions about this subject quickly get "off-track" and people begin arguing about other questions still assuming they are arguing about whether compilers can produce better code than humans. Here are some of the questions whose answers people try to apply to the above question:

(1) Is it cost-effective to write code in assembly language?

(2) Is assembly language useful for writing portable code?

(3a) Is assembly language harder to read than HLL code?

(3b) Is assembly language harder to maintain than HLL code?

(3c) Is assembly language harder to write than HLL code?

(4) Is assembly language practical on RISC machines?

(5) Is it easy to implement algorithm xyz in assembly language?

(6) How many people know assembly language?

(7) Will compilers ever produce code as good as a newbie assembly programmer?

(8) Will compilers ever produce code as good as an intermediate asm programmer?

(9) Will code optimized for one member of a CPU architecture be optimal for another?

etc.

While these questions are interesting in their own right, and many essays in these series will address the questions they raise, keep in mind that these questions may have different answers than the original question "Will compilers ever produce code as good as an expert assembly language programmer?" Switching the question mid-way through an argument is not a good way to win that argument; indeed, it's a tacit admission of failure.

So let's put to rest the "theoretical" answer to this question right away. "Will compilers ever produce better code than Humans?"

The answer is an obvious "NO!" The reason is quite simple; humans can look at the output of a compiler and improve upon it. Therefore, there is no theoretical reason for a the statement "compilers will get to the point that they produce better code." People can always observe what the compiler is doing, learn from this, and adjust their code accordingly. Therefore, the absolute best that a compiler could do is produce code that is equivalent to the best code an expert assembly language programmer could produce.

"That's not fair..." you might claim. "Why should humans be allowed to look at the compiler's output?"

Well, life isn't fair. If we're talking about producing the absolute best code, it's perfectly reasonable for a compiler to use every piece of information at its disposal; likewise, it's perfectly fair for humans to take the same approach. And one piece of information at a human's disposal is the output from a good compiler. The fact that compilers cannot respond in like, and rip off the good ideas from a human programmer is the primary reason why a compiler will not be able to better the output of a human being.

Note, by the way, I cannot absolutely defend the converse statement: "Will an expert assembly language programmer always be able to produce better code than a compiler?" Conceivably, compilers could get to the point that this is not true. It's very unlikely that compilers could achieve this status, but it is imaginable.

Of course, if a compiler could always produce code that matches what the best humans could produce, one could argue that assembly language is obsolete purely on economic terms (unquestionably, it is generally more expensive to develop optimal assembly software than HLL code). The whole reason the argument continues until today is because compilers aren't even close to this goal.

Some related questions:

"(7) Will compilers ever produce code as good as a newbie assembly programmer?"

They already do. Indeed, in most cases the output of a C/C++ compiler (whose input is reasonable quality C/C++ code) is quite a bit better than the hand written code produced by someone who has just learned assembly language. Indeed, this is the reason most people feel compilers do such a good job today -- they learn just enough assembly to put a working assembly language program together and then are surprised to find that a C/C++ compilers beats the pants off their code, despite assembly language's legendary performance benefits. Such programmers then spend the rest of their life praising the quality of compiler output when, in fact, they do not have the experience to make such claims.

"(8) Will compilers ever produce code as good as an intermediate asm programmer?"

They already do. An average assembly language programmer can always beat a large number of compilers out there. However, there are many high-performance compilers that will beat the pants off an intermediate programmer."

"Will compilers ever produce code as good as an advanced assembly language programmer?" This is the question answered above (the answer is no). However, it is important to point out that an advanced assembly language programmer has to take considerable care. If such a programmer is careless or gets lazy, the compiler might produce better code. This is, perhaps, the best argument for using both HLL and assembly code in the same program. The advanced assembly language programmer can concentrate on the important sections of code and leave the lesser important pieces for the compiler to work on.


The "Proof by Example Myth"

Often, someone will try to "prove" to me that compilers produce really good code by taking some HLL sequence of statements and showing me the outstanding assembly sequence that compiler produces. Folks, there is only one way to prove an "always" condition by example; that's by enumerating all possibilities and showing the condition to be true for all such possibilities. Since there are (for all practical purposes) an infinite number of possible programs one can write, you will not be able to prove a compiler's worthiness by example.

Note that the general question is not "Can a compiler produce a code sequence that is as good as (or better than) a human would?" I consider myself to be an expert assembly language programmer. However, I am not ashamed to admit that I've learned some assembly language tricks by studying the output of various compilers. Just because I wrote some assembly sequence (without looking at some compiler's output) and you found a compiler that bests me doesn't make the compiler better than me. If you feed the same input to a compiler twice, you will always (assuming a deterministic program) get the same output. Give the same problem to an assembly language programmer twice and you're likely to get two different solutions. One will probably be better than the other. Have compilers ever beaten me? Yes. They do it all the time. But on different code sequences I beat the compiler every time. If I really apply myself, I can beat the compiler every time.

Another problem with the "Proof by Example" myth is the fact that pro-compiler types will often use the output of several different compilers to boost their arguments. That is, given three or four different algorithms/code sequences, they may run the code through several different compilers and pick the best output. The problem with this approach is that no single compiler implements everything in the best possible fashion. Some compilers will excel in one area and totally suck in another. If the output of three compilers is complementary (i.e., they each excel where the other two fail), it is possible to pick the best results from the different compilers and present them as though they were outputs from a single compiler. This tends to hide the fact that compilers often fail miserably at some things that a human would handle automatically.

The argument for this policy is simply "Well, if existing compilers can do all these good things seaparately, surely we can merge the best of these compilers into a single product and have something really great." This line of reasoning fails for three reasons-

(1) some optimizations are mutually exclusive. That is, if you perform one type of optimization you cannot perform some other type of optimization on the code. If the "best" example from one compiler uses an optimization technique that is mutually exclusive with the "best" example from a different compiler on a different problem, it may not be possible to merge those two techniques into the same product.

(2) Don't forget that most compilers are commercial products. The quality of the optimizer is often a trade secret and other vendors may not be able to directly clone an optimization technique.

(3) Even if two optimizations are not mutually exclusive, putting the two of them into the same program could produce difficult to maintain code or severely impact the performance of the compiler.

Software engineers have been promising for 20 years now that compilers would merge all known techniques into a single product and we've have really great compilers someday soon. Compilers have gotten better, but they're still a long ways off from perfect.

Note that it is possible to disprove a theory with a single example Therefore, if you want to claim that compilers can always produce better code than humans, all I've got to provide is one example to the contrary. Proving that compilers, on the average, produce better code than an expert assembly language program is far more difficult.


The Law of Diminishing Returns

Perhaps the best indication of how well compilers in the future will operate is in the past. By looking at how well compilers have improved their code generation capabilities over the past several decades, we can anticipate how much better they will get over the next decade.

In the late 70's and early 80's there was a flurry of activity with respect to the production of optimization compilers. The result was quite impressive. In ten years, the code from compilers for a give language doubled, tripled, or improved by an even greater percentage. Coincidentally, it was during this time that "Software Engineering" came of age and people began to move away from assembly language because compilers promised high performance with less work.

Unfortunately, compilers in the later 80's and early 90's failed to produce the dramatic improvements seen in the late 70's and early 80's. Indeed, most major performance improvements during this time period came from architectural improvements to the CPU rather than any great advance in compiler technology. Whereas performance gains in the 100-500% area were common with the first way of microprocessor compilers, the improvments dropped well below 100% in the second wave of products (late 80's and early 90's). Today, compiler writers are scratching in the dirt to get gains of 15-30%. Computer architects aren't doing much better. Compiler writing is a fairly mature science at this point. It is very unlikely (short of someone proving that P=NP) that we will ever again see impressive gains in compiler technology with respect to raw performance improvement.

Therefore, extrapolating the past performance of compiler writers to predict how much faster the code will run that compilers will produce ten years from now is very dangerous. Unless there is a radical shift in computer architectures that favors HLLs at the expense of assembly language, it is unlikely the performance gap between good HLL programs and good assembly language programs will become much narrower. Indeed, the only real thing left to do is to consolidate as many optimizations as possible into a single compiler (we are a long ways off from this today). This will probably improve performance by another 50% on the average.


The Architecture is King

As I mentioned in the previous section, most of the big perfomance gains over the past 20 years have been due to architectural improvements, not to compiler improvements. The mere fact that we've gone from a 5MHz 8088 to a 200MHz Pentium Pro in a high-end PC in 15 years has a lot more to do with the speed of software today than with the quality of compilers. While certain technologies, such as RISC, have closed the gap between human-based machine code output and compiler-based machine code output, the performance boost by compilers pales in comparison that that provided by the newer hardware.


The "Myopic" Debator

Another problem with contributors to "The Great Debate" is the limited exposure many people have. If you get involved in a thread arguing the relative merits of assembly language vs. C, you will often find the pro-HLL types leading the charge are UNIX programmers. Now I don't want to pigeon-hole all UNIX programmers, but the types I've seen making the argument against assembly language have very little experience outside the UNIX (or mainframe) O/S arena. I think that one could make a very good case that assembly language is a bad thing to use under UNIX. Does that mean assembly language isn't useful elsewhere? Gee, some programmers wearing UNIX blinders sure seem to think so.

Before you start coming up with reasons why assembly language is not a practical tool, make sure you state the domain in which you operate. Claiming "Code doesn't really need to get any faster" or "We don't need to worry about saving memory" are fine arguments when you're working on a 500 MHz DEC Alpha with 1 GByte main memory installed. Are the claims you're making for your environment going to apply to the engineer trying to convince a Barbie doll that it should talk using a $0.50 microcomputer system? Keep in mind, it's the C/C++ (and other HLL) programmers arguing that you should never have to use assembly. The assembly programmers never (okay, rarely) argue that you should always use assembly[1]. It is very difficult to defend a term like "never". It is very easy to defend a term like "sometimes" or "occasionally." Just because you've never been forced to use assembly language in order to achieve some goal doesn't mean it is always possible to avoid assembly. Be careful about those blinders you're wearing when arguing against assembly.


(2) Is Assembly Language Useful for Writing Portable Code?

Okay, it seems like a stupid question. Obviously any code written in assembly language is going to have a difficult time running on a different processor (it may not even run efficiently on a processor that is a member of the processor family for which the original code was written). Worse still, you will have to learn several different assembly languages in order to move your code amongst processors. While learning a second or third assembly language is much easier than learning your first, learning all the idiosyncrases that you must know to write fast code still requires quite a bit of work. So it seems that porting code involving assembly language is not a brillant idea.

On the other hand, Software Engineering Researchers typically point out that coding represents only about 30% of the software development effort. Even if your program were written in 100% pure assembly language, one would expect that it would require no more than 40% of the original effort to completely port the code to a new processor (the extra 10% provides some time to handle bugs introduced by typos, etc.).

Perhaps you're thinking 40% is pretty bad. Keep in mind, however, that porting C/C++ code doesn't take zero effort; particularly if you switch operating systems while porting your code. If you're the careful type, who constantly reviews their code to ensure it's portable, you're simply paying this price during initial development rather than during a porting phase (and there is a cost to carefully writing portable code). I am not trying to say that it is as easy to port assembly code as it is to port C/C++ code, I'm only saying that the difference isn't as great as it seems. This is especially true when porting code between operating systems that have different APIs (e.g., porting between flavors of UNIX is easy; now try UNIX -> Windows -> Macintosh -> OS/400 -> MVS -> etc).


(3a) Is assembly language easier to read than HLL code?

Is assembly language easier to read than HLL code? Being an expert assembly language programmer and a fairly accomplished C programmer, I find my own assembly language programs only slightly more difficult to read than my own C programs. On the other hand, I generally take great pains to structure my source code so that it is fairly easy to read (take a look at my code on this web site). I will say this - I've seen some assembly code out there that is absolutely unreadable. Of course, I've also seen my share of C/C++ code that looks like an explosion in an alphabet soup factory.

Of course, only the person doing the reading can really make this judgement call. Obviously, if you know assembly but don't know C/C++, you'll find assembly is easier to read. The reverse is also true. I happen to know both really well and I find a well-written C/C++ program a little easier to read than an assembly language program. Poorly written examples in both languages are so bad they are incomparable. Once a program is unreadable, it is difficult to determine how unreadable it is.

Quick quiz: What does the following C statement do and how long did it take you to figure this out?

*(++s) && *(++s) && *(++s) && *(++s);

Most people (who know 80x86 assembly) would find the corresponding 8086 code much more precise and readable:




	mov	bx, s
	mov	al, 0
	inc	bx
	cmp	al, [bx]
	jz	Done

	inc	bx
	cmp	al, [bx]
	jz	Done

	inc	bx
	cmp	al, [bx]
	jz	Done

	inc	bx
Done:


(3b) Is assembly language harder to maintain than HLL code?

This notion exists because people tend to save assembly language programming for the very time critical (and often complex) components of their program. Obviously if you've spent a lot of time and effort arranging the instructions in a certain sequence to ensure the pipeline never stalls, and then you discover that you need to modify the computation that is going on, the new changes will introduce a lot of work since you will have to reschedule each of the instructions.

Of course, it never occurs to people that similar low-level optimizations that occur in HLL programs are very difficult to maintain as well. Consider the well-written (from a performance point of view) Berkeley string routines. These routines need to be completely redone if you move from a 32-bit processor to a 16-bit processor or a 64-bit processor.

As a general rule, any code that is optimized is difficult to maintain. This has led to the proverb "Early optimization is the root of all evil." People perceive that it is difficult to maintain assembly code mainly because the assembly code they've had to deal with is generally optimized code.

What if we don't go in and pull out every unnecessary cycle out of a section of assembly code? Will the code be easier to maintain? Sure. For the same reason non-optimal C code is easy (?) to maintain.

Of course, one of the primary reasons for using assembly language is to reduce the use of system resources (i.e., to optimize one's program). Therefore, when using assembly language in place of a HLL, you're typically going to be dealing with hard to maintain code. Don't forget one thing, however, had you chosen to continue using a HLL rather than dropping down into assembly language, the optimization that would have been necessary in the HLL would have produced hard to maintain HLL code. Keep in mind, optimization is the root of the problem, not simply the choice of assembly language.


(3c) Is assembly language easier to write than HLL code?

Is assembly language easier to write than HLL code? Sometimes. There are certain algorithms that, believe it or not, are easier to understand and implement at a very low level. Bit manipulation is one area where this is true. Also see the section on floating point arithmetic later in this document for more details.


(4) Is assembly language practical on RISC machines?

I personally don't know not having really learned assembly language on a RISC chip. I have certainly heard of individuals who have written some butt-kicking code in assembly on a RISC, but this is generally third-hand knowledge. I do know this, though. One of the design principles behind the original RISC design was to study the instructions a typical compiler would use and throw out all the other instructions in a typical CISC instruction set. This suggests that an assembly language programmer has less to work with on RISC chips than on CISC machines. Nevertheless, I will not comment on this subject since I don't have any first hand experience. I invite those who have mastered RISC assembly to write a guest essay for this series.


(5) Is it easy to implement algorithm xyz in assembly language?

That depends entirely on the algorithm. Generally, algorithms will fall into one of four categories:

1) Horrible solution in assembly, horrible solution in some HLL.

2) Horrible solution in assembly, elegant solution in some HLL.

3) Elegant solution in assembly, horrible solution in most HLLs.

4) Elegant solution in assembly, elegant solution in some HLL.

Show me your algorithm, I'll tell you which category I think it belongs in.


(6) How many people know assembly language?

Although the number of people who know assembly language increases daily (faster than programmers are dying or forget assembly language), the number of people who know a given HLL is generally increasing much faster. While this says something bad about assembly language, what it has to do with the question "Will Compilers Ever Produce Better Code than a Human?" is an interesting question in its own right.


(9) Will code optimized for one member of a CPU architecture be optimal for another?

Probably not. This is one big advantage compilers have. If you get a new compiler for a later chip in a CPU family, all you've got to do is recompile your code to take advantage of the new architecture. On the other hand, your hand-written assembly code will need some manual changes to take advantage of architectural changes in the CPU. This fact alone has driven many to condem writing code in assembly. After all, today's super-fast program may run like a dog on tomorrow's architecture. This argument, however, depends upon two fallacies-

(1) Tomorrow's compilers will also take advantage of these architectural features.

(2) The assembly language program used architectural features on today's chips that cause performance losses on tomorrow's chip.

Historically, compilers for the x86 architecture have lagged architectural advances by one or two generations. For example, about the time the Pentium Pro arrived, we were starting to see true 80486 optimizations in compilers. True, many compilers claim to support "Pentium" optmizations. However, such compilers do very little for real programs. Given past support from compiler vendors, coupled with the fact that the trend is to handle really tedious (e.g., instruction scheduling) optimizations directly in the hardware, I personally feel that worrying about a specific member of a CPU family will become a moot point.

Those claiming that hand written assembly language is inferior because the next member of a CPU family will render the code obsolete are missing the whole point of assembly optimization. Except in extreme cases, assembly language programmers rarely optimize at the level of counting cycles or scheduling instructions (as the pro-compiler crowd points out, this is really too tedious a task for human beings). Assembly language programmers achieve their performance gains by typically using "medium-level" optimization that are CPU family dependent, but usually independent of the specific CPU. This is such an important concept that I will devote a completely separate essay in this series to this subject.


More to come...


Further essays in this series will address the question "Is there a true need to use assembly language?" The "Compilers can generate code that is just as good as humans." is one (albeit incorrect) negative answer to this question. In the following essays I will attempt to answer this question in the positive sense.


[1] I have seen some posts on the net by a certain individual who spends his days writing games for cartridge based game machines who swears that using anything but assembly language is crazy. This is probably true in his domain. It certainly does not apply to software written for UNIX workstations.

Number of Web Site Hits since Jan 1, 2000: