Conference turris::languages

    I believe that the ASPLOS II procedings had an article on a
    "SuperOptimizing" mini-compiler based on prolog.
    
    I found it pretty interesting.
    
    
    --  Barry

    	If an example is any use, then on one occasion I checked the
    code that BLISS generated where I was setting several fields in
    a RAB. In some cases where I was initialising two adjacent word
    length fields the compiler produced a single longword move.
    
    	Now as an assembly language programmer I have no reason to know
    that those two named fields are adjacent, and even if I happen to
    know it I might not notice. Even if I knew I was initialising two
    adjacent word length fields I would only use the longword move if
    I was sure that it was time-critical, and I would expect to have
    to add *very* prominent comments to explain what I was doing.

	I don't have any references for you.

	All I can say is that there is a lot of documentation about
optimization techniques for compilers. I would imagine that many of them are
not understood or applied by the average assembler programmer (some are quite
difficult to analyze by compilers themselves).

	I've never heard of a study of examining the average assembler code
vs. compiler optimized assembler code. It may exist (please let us know if you
find references), but I wouldn't be suprised if an author of such comments
just drew that conclusion after reviewing some of the optimization literature.

Chuck

    The other aspect of this question is its simply not "reasonable" to
    code many applications that say are written in Ada or COBOL, in
    assembler. So, even if the "average" assembly language coder could do a
    better job at writing optimized code, his productivity would probably
    be orders of magnitude less than the HLL's.
    
    Or try writting a complex arithmetic computation in assembler ... 

	This is a side issue to what you raised in the topic base note.

	If compilers will usually beat assembly language programmers
	(it terms of code quality), there should be no reason to
	code applications in assembler.

	I've heard two reasons for programming in assembler on occasion

	1)	Writing a device driver
		(certain instructions not generated)
	2)	Fine tuning a time-critical code section
		after looking at optimized code produced by
		a high-level language compiler.
	3)	Doing things you can't do in a high-level language
		(not many, but probably a few)

	Other than that I wouldn't advocate writing assembler.

	Many people are under the misconception that if you
	write in assembler you will generate less code and
	it will execute faster. That is usually not the case.

	I know a colleague of mine visited American Airlines
	(who maintain SABRE - the airline reservation system)
	and they write all of their code in assembler.

	Chuck

>    < Note 192.5 by COOKIE::DOUCETTE "Chuck Doucette, Database A/D @CXO" >
>                     -< reasons for writing in assembler >-

>	I've heard two reasons for programming in assembler on occasion

>	1)	Writing a device driver
>		(certain instructions not generated)
>	2)	Fine tuning a time-critical code section
>		after looking at optimized code produced by
>		a high-level language compiler.
>	3)	Doing things you can't do in a high-level language
>		(not many, but probably a few)

 
    My two reasons for programming in MACRO are:
    
    	6)  	I like the simplicity and directness of the langauge
    
    douglas

    Please, let's not get sidetracked.  I too love VAX MACRO (it is
    one of the best high-level languages I know :-), but another
    personality in me loves much of what it sees in Ada.  If we must
    carry on a debate regarding the relative merits of VAX MACRO versus
    some HLL, let's do it in another topic.
    
    All I'd like is a reference or two (or a reference to a place likely
    to give me a reference) on the quality of compilers these days.
    Studies aren't necessary;  if we can catch someone like Backus (you
    know, Mr. B of BNF) or anyone else making that kind of generalization,
    that will be good enough.  Thanks.
    
    Lloyd

    Please read the title of .6 carefully.
    
    Then read the note carefully, including the part quoted from earlier
    notes.
    
    Then read between the lines for an appropriate typographic icon.
    
       Gary

Re .0:

Sorry, the oldest reference I have is 13 years old, not 10.

From pages 2-3 of "The Design of an Optimizing Compiler", by Wulf, Johnsson,
Weinstock, Hobbs and Geschke, copyright 1975 Elsevier North-Holland, Inc.:

"
Chapter 1 - Introduction
...
3.  The problem domain for which Bliss/11 is intended, the development of
production-quality systems programs, warrants the expenditure of a relatively
large amount of compile time in order to achieve runtime efficiency.  An
explicit goal of the design is to produce _better_ object code than that
written by good systems programmers on moderately large programs (say longer
than 1000 instructions).
"

For a discussion of the issue, read the preface to chapter 10 (Code
Optimization) of Aho, Sethi and Ullman's "Compilers: Principles, Techniques,
and Tools".
				/AHM
P. S.  Did you consider making up some references and letting the customer spend
a couple of Saturdays at the library trying to find them?

    A reason for using a compiler even if the code quality is lower
    than hand-tuned code is that modifications to hand-tuned 
    assembly code are dangerous and slow;  modifications to the
    higher-level language source are much less dangerous and faster.
    
    				John Bishop

here is some anecdotal evidence, in case anyone still cares.

back in the late 70s we were still trying to convince DEC people to use
any high level language, and bliss in particular.
maurice marks and i put together what data we could find to compare bliss
to macro in several dimensions, including code size.  there was not much data.

we found one component of vms copy that had been done in bliss and then
rewritten in macro.  the rumor was that the macro version was 12 bytes
smaller, out of about 600 bytes. when i finally got both source programs
i found the .objs differed by 6 bytes.  the bliss compilers were in active
development then, and new optimizations were added fairly often.

i've often wondered if the bliss code ever got smaller than the macro.

by the way, that is another advantage of a hll, the code can improve
without any work by the author of the code.

when we presented what we had found, i said i doubted there was ever a 10%
difference between bliss and macro, for any real program where bliss was
appropriate.  i've made the same claim many times since.  no one has
ever presented a counterexample.
[but not very many people ever get to write the program twice.]

about the same time the towers of hanoi was coded in several languages.
macro beat bliss by about 4 bytes out of about 100.  the other languages
were much larger, i think about 200 bytes.  that difference was caused
primarily by program unit overhead such as establishing exit handlers
and condition handlers.  i think the code in the algorithm proper was
about 10-20% bigger than the macro or bliss code.  i have less confidence
in the 10-20 than in any other number here.

one more data point, and this goes back to about 67-68.

a commercial application was written in ibm 360 bal (assembly language).
it was rewritten in cobol and the cobol version was smaller.
the two programs used mostly the same logic, but there was no attempt
to be an exact port.  the difference was significant, i think about 15-25%.
the generated cobol code was really bad.
the reason the bad code was smaller?  better register allocation.
an early bad decision on addressability and the assignment of registers
meant that much of the assembler code was loading and saving registers
so that the needed data could be accessed.  since the decision was 
distributed over about 2000 lines of code, it was almost impossible to 
change.  since vax is not limited to 12 bit displacements, and has other
addressing modes besides base-displacement, this effect
would not be as large as it was on the 360.

the relative performance of the vax compilers is probably much different
now from what it was back in the 70s.  more work has gone into the other
compilers than into bliss, since then, and much more is known about 
generating fast, compact code.  i suspect several of them may produce 
code that is close to what can be done in macro.

one of the earlier replies noted pleasant surprise at some generated code.
i've heard compiler developers say they can generate code that an assembly
language programmer would be fired for. no one has to understand and 
maintain it, and the code will be different but still correct if the 
coincidence that allowed the obscure code ever changes.

some notes in this conference have led to the same problem being solved in
different languages.  often, different algorithms were used, but there
might be some valid data points.

    re .11:
    
    Please note that code size is not the right metric.  BLISS often
    is small but at the expense of run-time speed, especially for the
    newer, long pipeline machines.  Alpha motion, name CSEs and 
    branch-chaining are some of the BLISS optimizations which decrease
    space at the expense of time.  Code alignment would change this
    as well.
    
    I'm the BLISS project leader, and if and when I get to fix this
    BLISS code will get bigger, but faster.
    
    			-John Bishop

    Re .11:
    
    Yes, at least I still care.  On the other hand, I've recently seen
    the customer and he hasn't brought it up, so he may well have
    forgotten.  I've been so busy at the library that I've not had time to 
    read this notesfile.  :-)
    
    Re .9:
    
    The preface to the "Code Optimization" chapter in Aho, Sethi, and
    Ullman (*Compilers:  Principles, Techniques, and Tools*), is less
    than enthusiastic about the possibility of machine-generated code
    even coming close to hand-coding, in terms of either space or time.
    Given what I've heard and seen elsewhere, they may be referring
    to *machine-independent* optimizers or to their experience in the
    U**x world, where most manufacturers don't spend a whole lot of
    time creating a good optimizing compiler (which would, of course,
    take advantage of machine-dependent optimizations).  Although I
    have no evidence to support this bald assertion, I am sure that
    DIGITAL is more serious about optimization in Ultrix compilers than
    most other folks.
    
    Re .0:
    
    We've heard a lot of anecdotal evidence here (which is much better
    than nothing).  Apart from the overwhelmingly important issues such
    as readability, maintainability, and so on, the general idea seems
    to be:
    
	Most of the time, even if the code generated is a little slower
    	than what you could do in assembler, the productivity gain from
    	using a HLL (as well as other factors, including the ability
    	for the code to "improve" when recompiled [I hope that the folks
    	relying on this are doing regression-testing]) is much more
    	significant, in terms of dollars.

    	Code generators can take advantage of fortunate circumstances
    	which, if a human were to use them, the human would be shot
    	(in the general case).
    
    	There is some extra run-time baggage associated with HLLs,
	particularly surrounding procedure-call semantics.  The amount
    	of baggage is language/OS dependent.
    
    	Some compilers/languages provide mechanisms for reducing the
    	cost associated with this extra semantic baggage.  An article
    	by someone from DECwest ("Inline routines in VAXELN Pascal",
    	Proceedings of ACM SIGPLAN '84 Symposium on Compiler Construction, 
    	in SIGPLAN Notices Vol 19, Number 6, June 1984) compared CALL
    	and JSB linkage versus inlining (I hope I'm remembering the
    	correct source for this, but I know the article exists) and
    	found that inlining was preferable because it allowed
    	routine-global optimizations to occur.
    
    	At the same time, when we look at small code streams emitted
    	by some of our code generators (I'm thinking of VCG as the VAX Ada
	backend) seems less than optimal.  For example, I've observed
    	the following code sequence "MOVZBL mem,Rn", "BBS Rn,dest" among
    	others (no special semantics associated with the object involved),
    	but I've also been impressed with other code generated (extracting
    	a word-aligned bitfield with a BICW instruction, but using EXTZV
    	when the field was not aligned).
    
    	Generally, code optimizers do their best when allowed to perform
    	global optimizations.  The quality of peephole optimization
    	may vary more widely between VCG and non-VCG generators, at
    	least in the short term.
    
    Anyway, in my not-terribly-thorough-and-unassisted-by-machine
    literature search, I did find one article which directly supports
    the contention that a compiler can produce code comparable to that
    produced by hand.  The reference is:
    
    	D. Boyle, P. Mundy, T.M. Spence, "Optimization and Code Generation
    	in a Compiler for Several Machines", IBM Journal of Research
    	and Development, Vol 24, Number 6, November 1980.  pp. 677-683.
    
    They demonstrate (through coding reasonably large examples in both 
    assembler and a subset PL/I which incorporates some C-like
    capabilities) that their compiler could produce code which was within
    10percent of the size and speed of equivalent assembly language.
    The targets involved were the IBM 8100 and a number of proprietary
    microprocessors involved in various peripheral devices.
    
    While I'm not terribly pleased with the thought of using a reference
    generated by IBM, the fact that the reference was in 1980 and was
    sufficiently uninteresting (from an academic standpoint) to appear
    in a "company organ" rather than an independent journal, I can make
    the argument that this is all pretty much old hat for most respectable
    compiler-development shops, ours included.  After all, 8years is
    a long time.
    
    At the same time, I'm not so overwhelmed with the support for my
    original statement about code quality that I'm going to repeat it
    unless I absolutely must, and then it will be couched in terms of
    "our experience has shown...global optimizations...inlined code...".
    
    If someone has access to and funding available for an automated
    literature search on the subject, we could probably turn up something
    better.  If we were to perform this kind of analysis ourselves (code
    up some stuff in VAX MACRO and language X, and see how it plays)
    it might be worth putting in a DIGITAL Technical Journal (yo!
    Technical Languages!  want something else to do? :-) ).

    Thanks for your help on this.  Please send me mail if you add a
    new response (I'll be an even less regular reader of this notesfile
    in the future).
    
    Lloyd

Re .13:

>    The preface to the "Code Optimization" chapter in Aho, Sethi, and
>    Ullman (*Compilers:  Principles, Techniques, and Tools*), is less
>    than enthusiastic about the possibility of machine-generated code
>    even coming close to hand-coding, in terms of either space or time.

That does not bear upon the problem posed in the base note.  The basis for
comparison in .0 is not "... code that is as good as can be written by hand"
[ASU, p 585], but "... code produced by "average" assembly language programmers
who have not spent quite a long time "optimizing" their code."  Since hand
optimization is a time-consuming process, it is not surprising that it is much
easier to merely do as good as an "average" programmer who isn't exerting
himself.

>    Given what I've heard and seen elsewhere, they may be referring
>    to *machine-independent* optimizers or to their experience in the
>    U**x world, where most manufacturers don't spend a whole lot of
>    time creating a good optimizing compiler (which would, of course,
>    take advantage of machine-dependent optimizations).

Beware of generalizing on the basis of pcc, f77 and their ilk to all Unix-based
vendors.  I suspect that the compiler developers at places like Convex (and
Sun?) would love to compare their technologies with ours.  While there are
probably plenty of iron vendors that eschew pumping $$$'s into software
development, it's not true of everyone.
				/AHM
P. S.  If the customer acts up again, have him write some of that semi-optimal
assembly code he's so fond of, and then transcribe it into your favorite
language and see how good a job the compiler does.  Hopefully the compiler will
pull *some* trick he can't figure out for a while.  That's the sort of thing
that really converts people.

    re: .14
    
    Have them get stuck with a lot of code written in macroxxx that
    doesn't port to the hardware that they buy n years from now.
    THAT'S the kind of thing that converts people.
    
    Matt -- once a happy SUDS user. Where have all the 20s gone?
    

    Many years ago when I worked in a University Computer centre, a
    colleague and I took a users FORTRAN subroutine, which was the most
    time consuming part of his program, set the compiler to output the
    machine level code, and then hand optimised it, reducing the execution
    time of the whole program by a goodly amount. 
    
    The computer manufacturer (no it wasn't digital) then released an
    improved FORTRAN compiler, so we went to repeat the same optimisation. 
    
    We look at the code generated, there was our optimised version except
    for insignificant register differences. There was no way we could
    improve the code this time.
    
    I expect that the current Digital compilers are approaching this level
    of perfection.