Re: Writing fast compilers...

[Copied from comp.arch. -John]


On 10 Aug 91 16:16:13 GMT, byron@archone.tamu.edu (Byron Rakitzis) said:


In article <1991Aug10.132405.19359@walter.bellcore.com>
mo@gizmo.bellcore.com () writes:


mo> I suggest people interested in this topic ftp the Plan 9 paper set
mo> from research.att.com. Ken Thompson's paper on his new compiler
mo> is quite impressive [ ... ]


Now, now, let's not get carried away. He has done a clone of Turbo
Pascal, or of the small/fast Pascal compiler from ETH. It is good
implementation architecture, yes, but it shines only in comparison with
the awful things we usually get and accept.


mo> Once again, we get a too-badly-needed reminder that quantity is
mo> utterly unrelated to quality.


But quantity is related to sales to the incompetent; paraphrasing a well
known proverb "nobody has ever gone bankrupt by underestimating the
competence of America's MIS managers" :-).


In a collection of Dijkstra's papers he tells of a conference on
compiler writing, where each compiler writer that got to speak before
him proudly announced the number of source lines for their fortran,
cobol, pl/1 compilers, in the many dozens of thousand lines region, with
an increasingly excited and cheering audience. He got to talk eventually
on his own work and he made a very embarassed and coldly received talk
because he had to admit that his Algol 60 compiler was only 2,500 lines
long :-).


byron> I've read this paper and I've found it very interesting.


If you found this very interesting, your eyes will pop when you read
about TWIG, or about the ETH small Pascal compiler, or about many other
little known feats.


byron> For those who havent, here's my recollection of where the Big
byron> Wins come from:


byron> Everything is done in one pass. That is, cpp, the parser and the
byron> code generator are all bundled into one process. The compiler
byron> emits an object file which is then loaded by a special linker.


Turbo Pascal precisely...


byron> The big win here is that the compiler does not keep writing and
byron> reading files from /tmp.


No, not quite, that should be covered by a decent caching
implementation. The big wins are that the linker is special, and that
the compiler is well written; there were and maybe there still are
excellent reasons to put temporary files in /tmp, and if you don't want
to do it, the Sun and the GNU C compilers allow you to use pipes between
the compiler passes, with the -pipe option, which can be a big win on
multiprocessors (but not on monoprocessors).


byron> In contrast, here's what happens on my sun when I compile a
byron> hello-world program:


byron> ; cat>a.c
byron> main(){printf("hello,world\n");}


A Real C Programmer! :-)


byron> ; cc -O -v a.c
byron> /lib/cpp -undef -Dunix -Dsun -Dsparc a.c >/tmp/cpp.29354.0.i
byron> /lib/ccom - -XO2 /tmp/ccom.29354.2.ir </tmp/cpp.29354.0.i >/tmp/ccom.29354.1.s
byron> rm /tmp/cpp.29354.0.i
byron> /usr/lib/iropt -O2 -o /tmp/iropt.29354.3.ir /tmp/ccom.29354.2.ir
byron> rm /tmp/ccom.29354.2.ir
byron> /usr/lib/cg /tmp/iropt.29354.3.ir >/tmp/cg.29354.4.s
byron> rm /tmp/iropt.29354.3.ir
byron> /bin/as -o a.o -O2 /tmp/ccom.29354.1.s /tmp/cg.29354.4.s
byron> rm /tmp/ccom.29354.1.s
byron> /bin/ld -dc -dp -e start -X -o a.out /usr/lib/crt0.o a.o -lc
byron> rm /tmp/cg.29354.4.s
byron> rm a.o
byron> ;


byron> This is awful! There are (count em!) 6 stages in the compilation
byron> process, with 5 of those stages talking to /tmp. No wonder a
byron> compiler like this is i/o bound..


Well, well. This compiler structure is simply the traditional one, and
it worked very well on the PDP-11, which had limited address and data
space. Using separate processes and /tmp does not really add that much
overhead; if you use a nice size buffer cache, say 2MB, your compiles
can be entirely memory resident.


There is an excellent chance that if the cache is large enough a
compiler intermediary file is unlinked before it is written out, thus
eliminating IO transactions entirely. I have this happen often; in an
edit/compile/link cycle I often don't get a single IO transaction (more
recent Unixes that use a hardened file system unfortunately do write out
inodes immediately). This can also be easily observed under DOS with a
suitable cache management driver.


Sun also have implemented a mostly-RAM-resident filesystem precisely to
optimize /tmp performance, kind of flexible RAM disk. Notice that
however this is a seriously less preferable alternative to having a
large cache, as a large cache will also cache source files and include
files and library files wherever they are, not just /tmp files.


Then you are left with the overheads of copying things to/from the
buffer cache, but that is usually a minor problem, especially with a
decent pipe implementations. Context switching is possibly a bigger
problem. And even the copy from/to the cache can be obviated if less
inefficient IPC technology than pipes were used.


Moreover if you look at the times and IO counts of the sequence above,
you will notice that the real drag of the traditional Unix compiler
environment is the linker, not the compiler. Linking is a terrible
thing, and indeed most bullett compilers, such as Turbo Pascal, or
WATFIV, or Thompson's, gain most of their speed from a special linker,
rather than from the compiler.


byron> Ken's compiler does not, I think, attempt what I term "herioc
byron> optimizations" e.g., I bet it does not fold common
byron> subexpressions, and so on.


Triple cheers!


Many "optimizing" compilers have impossibly expensive optimization
phases; for example the SPARC and MIPS compilers have a global
optimization algorithm with a time complexity of O(n^3), and the GNU CC
compiler has a space complexity of O(n^2). These are well past any
reasonable cost/benefit ratio... Clearly anything well done compares
well against these monsters.


So, don't exxxxxagerate the importance of Thompson's new C compiler, or
of Plan 9 itself, or even Unix; none of these things has exactly been
ground breaking work, they are simply well engineered developments of
well known technology. It is amazing that merely good implementation
architecture is newsworthy, but yes, such is the sorry state of the art.


If you want to read something really interesting on the "small is
beautiful" technology front, do a literature search for TWIG, the
Princeton code generator tool, and its successors. I have even seen a
very interesting TWIG implementation is Standard ML, now that's
something amusing.


Incidentally, I don't know what is the legal status of TWIG, but surely
I would love it if the GNU CC code generator were replaced with TWIG, or
its successors, just for fun. I could even do it myself, in my copious
spare time :-).




A final remark: isn't it amazing that Unix was supposed to be the system
where the name of the game was composing little modules with a flexible
low overhead glue like pipes or cached files (really the same thing in
the original implementation), and now we have one of the designers do
precisely the opposite for performance reasons? This is about as ironic
as having a stdio library...
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@aber.ac.uk
--

Return to the comp.compilers page.
Search the comp.compilers archives again.