Folk Theorem: Assemblers are superior to Compilers
Mike Elliott
I don't think the point is really about assemblers Vs compilers. Many
elequent statements have been made about this debate in this group but we
all already know those answers. Maybe the point to be made is that there
are people out there who are willing to make contentious statements in
high-profile magazines which then lead to 1) such a debate 2) un-informed
people who take anything on paper as gospel (not those in the know :-)
Could articles of this type lead to customers saying "What are the odds of
you coding my new super-ultra-complex system purely in assembly language ?"
Precisely. I think we all know that in microcosm human beings can
out-perform compilers. I specified a "real-world application" rather than
a tight inner loop or a subroutine or two in order to address the
macroscopic problem. The magazine article talked about entire DOS
applications, presumably something on the order of the size of recent
versions of WordPerfect or Lotus 1-2-3.
Actually I had a reference in mind, but I'm not sure it ever existed -- I
just heard about it (a Folk Reference, perhaps?); I've never actually
tracked it down, but . . .
Long ago and far away, when I was a graduate student at Edinburgh
University, I heard that the operating system EMAS (Edinburgh Multi-Access
System) was re-written in the systems programming language IMP from its
predecessor in assembly code. A study of code size difference was
performed, and the results were that the OS had changed very little at all
in overall bulk. Some sections differed by five to ten percent --
sometimes in favor of assembly, sometimes in favor of IMP. Overall it was
basically a wash.
I feel I can't cite this, because I don't know for sure that such a study
was actually done, or if it was, that these are the results. Scholarship
demands more rigor than just vague memories -- besides, I had just been
introduced to the astonishing variety of ales, stouts, lagers, bitters and
whiskies available in Scotland -- so vague memories just don't cut it.
That's the sort of reference I was seeking and I'm disappointed no one has
yet mentioned anything! If such research has not actually been done, then
it seems like it ought to be!
--
Send compilers articles to comp...@iecc.com or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compiler...@iecc.com.
Julian V. Noble
many cases one does not even need a profiler because the bottlenecks in
the algorithm are obvious. For example, in a FFT, don't bother using ass'y
to code the table f(k) = exp[2 i pi k / N ] because it is an O(N) process.
Just optimize the inner loop. Similarly, in Gaussian elimination (or in
the LR decomposition) for linear equations, the inner loop code is
executed N^3 times, everything else N^2 or less, so optimize that loop
(it's a short one, too).
The chief bottleneck in hand-optimizing code is the assemble-link-test
cycle. One reason I prefer FORTH to other languages is the built-in
assembler eliminates this step: words defined in assembler execute like
any others, hence can be tested immediately, etc. etc.
I have not yet had the opportunity to try this for a RISC chip, but for
the 80x86 and MC680x0 -based machines this peephole hand optimization
beats anything compilers produce. --jvn
--
Julian V. Noble
j...@virginia.edu
Freek Wiedijk
> Folk Theorems:
>[assember code is 1) faster and 2) smaller than compiler code]
All I know is that my favorite word processor (WriteNow for
the Mac) is written in assembly. It's the fastest and
smallest word processor on the Mac that I know of.
Freek
[It occurs to me that a salient point is that PC software is becoming more a
consumer item than a traditional computer product, where cost reduction is
a lot more important than we're accustomed to think. Consider embedded
high volume chips in cars and the like -- they do all sorts of gross assembler
hacks to get the memory size to an absolute minimum and to allow them to use
the slowest, cheapest chip that they can. -John]
Dave Gillespie
> float max(float x, float y) {
> union fl {float f; long l;} z;
> z.f = x - y;
> z.l &= ~z.l >> 31;
> return z.f + y;}
Well, when I said "branches are awful" I meant it on the scale of a few
instructions. Coding your method on an 860-like CPU is likely to lose
because of the number of extra operations you do to avoid the branch.
(Again, it's only in a *really* critical, tight loop where this attention
to detail makes sense.)
If you have an absolute-value instruction, you can also use "max(x,y) =
0.5 * (x + y + abs(y-x))". Anyway, identities like this can easily be
programmed by rote into a compiler. My point with my i860 example was
that our trick was extremely effective for the larger idiom "max(x, min(x,
y), -y) with y>0", which is complicated enough to be hard for a compiler
to recognize, and hard for a compiler writer to notice when designing a
set of rote optimizations.
The real answer is to have a cleverer choice of FP instructions. I
believe the Alpha has a conditional move instruction, for example. I've
seen one or two CPU's that had actual "max" and "min" instructions.
CISC can refer to "complex instruction sets" or "sets of complex
instructions." People tend to think in terms of the former as the
downfall of CISC, but actually it's the latter that brings on the
microcoding and the slow cycle times. The 860 is a step in the direction
of RISC processors that still have large, rich instruction sets. I'd like
to see more movement in this direction---why not have conditional move,
*and* min and max, *and* absolute value, and so on. Many of the things
you want are FP instructions, which even tend not to be starved for bits
in the opcode. And compilers would have no trouble using these
instructions, too.
Anyway, this is starting to sound more like comp.arch than comp.compilers.
-- Dave
Ronald F. Guilmette
>The main reason code is big and slow is that there is little pressure to
>make it small and fast. There is much more pressure to add new features,
>to support more device types, and to do that as soon as possible...
I have some vague hope that (when it comes to compilers) we may perhaps
not be getting the absolute best code generation we can for the simple
reason that responsible compiler vendors are doing their level best to
work on the *correctness* of their compilers first, and placing a somewhat
lower priority of all of the whiz-bang optimizations that we all know and
love.
(Who was it that said that you can compute incorrect results infinitely
fast?)
-- Ronald F. Guilmette ------------------------------------------------------
------ domain address: r...@netcom.com ---------------------------------------
------ uucp address: ...!uunet!netcom.com!rfg -------------------------------
Qual Trak
> Folk Theorem 1:
>[assembler code is faster than compiled code]
pre...@watson.ibm.com (Dan Prener) writes:
>I think there are two relevant points.
>
>First, a highly-skilled assembly language programmer can, indeed, produce
>better code than a compiler. However, there are many fewer highly-skilled
>assembly language programmers than most people realize.
>
>Second, even if there were many highly-skilled assembly language
>programmers, who always produced better code than any compiler, and even
>if portability were of no significance, the lower productivity of assembly
>language programmers would lead to the widespread use of higher level
>languages.
A couple of ideas -
Supposing I have a project that takes a year to write in c and my friend
the super assemply language programmer can write to the same spec in say
18 months. His code is twice as fast as mine. BUT six months after he
finishes his version of the product vendor xyz comes out with a new
machine twice as fast as the one we originally coded on. My code ports in
a day or so - he begins another 18 month project (make it a year this
time) and again two years later company def comes out with a processor
twice as fast ...
I seem to remember that once upon a time that Microsoft originally wrote
their macro assembler in assembly language. They introduced a new version
of it that had been rewritten in c and it was touted as being about twice
as fast. I know that it was noticeably faster than the previous
incarnation. I certainly won't claim that the c compiler generated
"tighter" code than the assembly language programmer but it seems that
larger projects seem to benefit from higher level languages.
The above would seem to point out something about assembly language and
large projects - or that Microsoft had some terrible assembly language
programmers - or none of the above - that it was time to clean out the
warts with a rewrite and if they'd done it in assembler it would have been
even faster - but my gut feeling is that managing a medium sized software
project would be considerably more difficult in assembly language than in
a high level language (is c a high level language?). Not to say more
expensive.
--
John Birchfield - QualTrak Corp (408) 748-9500 x 141
3160 De La Cruz Blvd., Suite 206, Santa Clara, CA 95054
j...@QualTrak.COM
Henry Spencer
>>... Didn't Ritchie [say it]
>>accounted for a 10% loss when the Unix kernel was rewritten in C?
>Unix rewritten in C --- this was on a CISC processor.
Bear in mind, also, that this was with a relatively simple compiler. It
put a fair bit of effort into good local code generation, but made not the
slightest attempt at global optimization. Note that when I say "local", I
really mean "local" -- for example, the reason why C has a "register"
keyword for declarations is that the compiler made no attempt to do clever
register allocation.
Actually, I don't recall having seen Dennis quote a specific number like
"10%". It's hard to compare the assembler and C versions of Unix, because
the re-coding in C involved extensive internal redesign, not just
translation. The original Ritchie&Thompson paper quotes a code growth of
about one-third, but notes that the new system had many functional
improvements as well.
--
enry Spencer @ U of Toronto Zoology, he...@zoo.toronto.edu utzoo!henry
Ralph Johnson
I know about is from the Bliss project back in the mid '70s. The Bliss
compiler for the PDP-11 was optimized for size of generated code, not
speed, because the PDP-11 had only a 64KB address space. The authors did
a study in which a dozen or so DEC PDP-11 assembly language experts were
given a couple of programs each to write. The programs took them a day or
so apiece to write. Some people (I don't know if it was the same people
or CMU grad students) wrote the same programs in Bliss given the same
amount of time. There was some variance, of course, but by and large the
Bliss programs were smaller.
The claim was that since the compiler was fairly good, given a fixed
amount of time a Bliss programmer could spend a larger fraction of the
time optimizing the program than the assembly language programmer could,
because it took less time to get the program correct.
I don't know where I saw this paper, but Wulf was probably a coauthor. He
should at least know where it was published. It has been at least 15
years since I read the paper, so it obviously made an impression on me.
-Ralph Johnson
Darrell Raymond
> (Who was it that said that you can compute incorrect results infinitely
> fast?)
I don't know who first said this, but I like Jim Adcock's twist on it:
We can easily guarantee correct results, given an infinite amount of time...
Darrell Raymond
Department of Computer Science
University of Waterloo
Dennis Ritchie
The only time I recall remarking in print on the relative performance of
assembler vs. C was in the BSTJ `Retrospective' paper of 1978:
Compared to the benefits, the costs of using
a high-level language seem negligible...the object
programs seem somewhat larger.... It is hard to
estimate the average increase in size, because in
rewriting it is difficult to resist the opportunity
to redesign....A typical inflation factor for a
well-coded C program would be about 20 to 40 percent.
The decrease in speed is comparable, but can sometimes
be larger, mainly because subroutine linkage tends to
be more costly....
The above guesses of space and time inflation for C
programs are not based on any comprehensive study.
This waffles, but I don't disavow it. I especially stand by the next
part:
Although such a study might be interesting, it would
be somewhat irrelevant, in that no matter what the
results turned out to be, they would not cause us
to start writing assembly language. The operating
system and the important programs that run under it are
acceptably efficient as they are.
That was 1978, this is 1993, folks.
Dennis Ritchie
Steven E. Parker
>I have some vague hope that (when it comes to compilers) we may perhaps
>not be getting the absolute best code generation we can for the simple
>reason that responsible compiler vendors are doing their level best to
>work on the *correctness* of their compilers first, and placing a somewhat
>lower priority of all of the whiz-bang optimizations that we all know and
>love.
Actually what happens in practice is that optimizer people tend to do both
"at the same time". What I have experienced is the following:
1. An idea is generated for an optimization.
NOTE: the word generated in this context implies original work done
by the optimizing team OR work published in the literature of
the area.
2. After cost/time/benefit analysis has shown the optimization to be
worthy, proceed to step 3 otherwise dump the idea and repeat the
process.
3. Design/implement the optimization. *Always* take correctness into
account!
4. Test, test and then test the compiler. Do performance runs to
determine the "goodness" of the optimization, both on its own and in
the broader context of the entire compiler.
5. Depending on the results of step 4 either:
a) Place it into the code base for the next ship.
b) Throw it away.
c) Go back to step 3 to try and get it right.
This process is of course slightly simplified, but in general it does
reflect reality (at least in my experience :-)).
So you see, correctness and performance are very much linked in the
process of creating a "new" optimization. The obvious question then is
"Why aren't all compilers whiz-bang?" Of course there are many reasons for
this. I'll mention some, I'm sure there are many others.
- Financial
- Not all people have the same skills
- Time constraints
- Business pressures
- ...
Regards,
-- Steven Parker. (steven...@acadiau.ca)
David Keppel
> vendors are doing their best to work on correctness first and place
> a lower priority on whiz-bang optimizations.]
I visited one of the implementors of a compiler and was surprised to find
it larger (more lines of source code) than GNU CC. I asked why and was
told that there were a variety of reasons, such as the overhead of
internal modularization; support for various code generation styles such
as shared libraries, support for varied processor implementations, and so
on. However, the biggest single reason for big code was from squeezing
another N% of performance from the generated code. The person argued that
nobody within the company had expressed a crying need for better code but
that market forces and a need to look good on e.g., SPEC benchmarks led
them to focus on detailed optimizations and thus to the larger code.
;-D on ( The Folk Historian ) Pardo
[In the PC tools biz, there seems to be a large market for compilers that
produce very fast but wrong code. Don't ask me why. -John]
James Kanze
|> produce very fast but wrong code. Don't ask me why. -John]
Actually, the market is for compilers which produce very fast code for a
number of small benchmarks. I had the occasion to evalute a couple of C
compilers a few years ago, and found that with one of the best selling
compilers at the time, turning on optimization caused the programs to be
bigger and run slower, in all compilation models except small. What real
application will run in small model? On the other hand, guess which model
is used by Byte et al. when they run their benchmarks.
--
James Kanze email: ka...@us-es.sel.de
GABI Software, Sarl., 8 rue du Faisan, F-67000 Strasbourg, France
Danny Thomas
>the functions are compiled independently. It forbids register allocation
>across function calls. It constrains the compiler to make pessimistic
>assumptions on the register usage by the called functions.
Prototype declarations were included in ANSI C partly with the idea of
allowing parameter passing through registers, at least for functions with
a fixed number of arguments. To quote from p42 of the Rationale
accompanying X3.159-1989 which isn't part of the standard proper but does
provide interesting background:
"This provision constrains the latitude of an implementor because the
parameter passing conventions of a prototype and non-prototype function
calls must be the same for functions accepting a fixed number of
arguments. Implementations in environments where efficient function
calling mechanisms are available must, in effect, use the efficient
calling sequence either in all "fixed argument list" calls or in none.
Since efficient calling sequences often do not allow for variable argument
functions, the fixed part of a variable argument list may be passed in a
completely different fashion than in a fixed argument list with the same
number and type of arguments."
I agree that register passing is an effective optimization but one of the
major problems with C is handling pointers, or more particularly
determining which pointer operations have side-effects on other variables.
cheers,
Danny Thomas
[P.J. Plauger has told me that during most of the standardization discussions,
prototyped and non-prototyped functions weren't supposed to be interchangable.
I don't know when that changed. -John]
Lenny Gray
: Some people (I don't know if it was the same people or CMU grad students)
: wrote the same programs in Bliss given the same amount of time. There was
: some variance, of course, but by and large the Bliss programs were smaller.
This is part of the problem. Nobody says that the compiler isn't faster
for a given amount of development. The question implied that there was
interest in comparing whether or not an assembler was useful _at_all_, and
for sure it is. When an assembler programmer spends an extra _100_ hours
optimizing for the purpose of saving 10,000 users 10% of their run-time of
a program that is run 1 hour a day, his investment is paid back in time-
value to the community 1000% for _every_day_that_program_is_used_.
Paul Robinson
> > [In the PC tools biz, there seems to be a large market for
> > compilers that produce very fast but wrong code. Don't ask me
> > why. -John]
>
> Actually, the market is for compilers which produce very fast
> code for a number of small benchmarks. I had the occasion to
> evalute a couple of C compilers a few years ago, and found
> that with one of the best selling compilers at the time,
> turning on optimization caused the programs to be bigger and
> run slower, in all compilation models except small. What real
> application will run in small model?
I'll take the bait on this one. Not everyone is writing applications that
use environments that take 4 Meg of memory and 50 meg of disk space to
display "Hello World". :)
MSDOS/PCDOS Device Drivers have to fit into small model unless they've
changed things.
Also, whether the people who are writing heavy and bloated applications
that violate every standard of decency :) want to admit it, if more
applications had been given a little thought into being more careful with
resources, we'd be able to run more programs without a kluge like
Microsloth Windoze or Half an Operating System. :)
The original Turbo Pascal - editor AND compiler - fit into less than 40K
of disk space, 128K of memory and for what it did, was pretty good. Or at
least, (to counter some comments) I didn't have any problems or notice any
errors. The latest monstrosity takes 20+ meg of disk space and a 386.
C Compilers are about as bad, too.
There is something to be said for making programs that will work under
less than optimal conditions. Another thought is the palmtop and handheld
computers have 640K. A small memory model program will fit on one of
these; Windows won't.
--
Paul Robinson - TDA...@MCIMAIL.COM