Moritz Beutel <"Moritz Beutel" <>> wrote:

> Barry Kelly wrote:
> 
> > Why you might want to use anonymous methods: if you want to delay
> > evaluation of some kind, such as symbol table lookup, but not have to
> > write some elaborate fixup or callback mechanism (and possibly need to
> > worry about arguments). A simple list of closure references can work
> > nicely here, with variable capture transporting the arguments.
> 
> it might be different in your case, but for the compiler I was working
> on, the fixups were pretty straightforward (one additional pass after
> compilation which simply swapped a few values), and using closures for
> those fixups might have doubled or tripled the compilation time since
> they were many. (Not to mention that I would have had to write a memory
> manager first. <g>)

Not for actual executable or object file fixups, no (tables have to be
produced for those anyway), but things can get complicated if you're
e.g. trying to parse generics in a single pass, where e.g. a method of a
generic type may return an inner type of the type being compiled -
essentially requiring the compiler to instantiate a partial type.

> > Subclassing polymorphism isn't a Delphiism distinct from C++, but it
> > is also very useful in compiler implementation, as any kind of
> > interface encapsulation would be in any system broken up into
> > modules. For example, consider porting a compiler across multiple
> > different back ends or platforms: substituting different
> > implementations of a common interface is far preferable to a liberal
> > sprinkling of #ifdefs and alternating linker command lines, relying
> > of linker resolution for different implementations of the same
> > symbols, but without the type safety.
> 
> Again YMMV, but something like EmitMove(a,b) being a /virtual/ method
> would have impacted performance perceptibly in my case.

EmitMove is too low a level for what I'm talking about, it would be e.g.
at the GenCode(expressionTree) level.

> > On the other hand, I see templates beyond generic data structure
> > definition and traversal of relatively little sensible use.
> 
> Templates make it possible to have a polymorphic EmitMove(a,b), without
> dirty linker tricks and without a virtual function call :) I rarely opt
> for static template polymorphism in everyday programming, but I think
> it has its uses when performance is critical.

Yes, but that would require you to thread the type you are
discriminating the template instantiation by throughout the program,
from the compiler driver through to the code generator, solely to take
advantage of template specialization for this very low-level (in terms
of the abstraction stack) task. Essentially, every method on the call
chain would need to be templated.

> > Pattern matching in the style of a functional language, or automatic
> > support for type equality and memoization, or garbage collection, on
> > the other hand, would provide large advantages for compiler
> > implementation over and above either Delphi or C++.
> 
> I don't know about the performance aspects of those (and it seems that
> for DCC, performance is highly critical), but I'd certainly agree that
> modern functional languages would allow for much more /elegant/
> compilers than the classic procedural approach, and that isn't specific
> to compilers.

When programmers start thinking about performance, odd things start
happening in their heads. Implementations they are familiar with from
past experience become much more desirable than implementations that are
alien to them, or even implementations they haven't thought much about.


There are two kinds of pieces: the set of data structure types to be
processed, and the different pieces of code - the operations - which are
going to work with them. The job is to match the two up. The task is
dynamic, so some kind of runtime lookup is going to be involved (so no
outs via e.g. templates). Typical approaches:


* C: use an enum-discriminated union for the data structure, and a
lookup table of function pointers for the operations. Maintainability
can be improved by e.g. using a header that instantiates an
include-point defined macro, so that you can do e.g.:


fn_ptr ops[] = {
#define T(x) Gen##x
#include "kinds.h"
};


and rely on the compiler finding GenFoo, GenBar etc.


* Object-oriented (C++ / Delphi, though these could use a C-like
approach): use double-dispatch (the visitor pattern) to separate the
code from the data structure definitions, or alternatively include the
operations as virtual methods of the types.


* Functional: use sum types for the data structures and pattern-matched
functions for the operations. This way, the operations are separated
from the data structure definitions, but the implementation is free to
use e.g. the C-style approach of a lookup table for the actual
implementation.


The functional approach enables the combination of better type safety
than the C approach (it's easy to muck up your discriminated unions in
C), better modularization in terms of separating code from data (the
code could be one of many analysis passes, wouldn't want to include
every possible pass in the data structure definitions etc.), but without
the double indirection penalty of the OO approach.


Moreover, pattern matching is more flexible than simple tag-based
lookup. It could look up on multiple arguments, or on fields of the data
structures, but still not pay any penalty for tag-based lookups, by
making the first lookup phase a table lookup on tag, followed by search
trees to narrow down those more specific patterns.


With respect to dcc32's speed, it has grown from maintenance such that
it is hard to disentangle various threads to optimize particular aspects
independent of semantics. C's lack of abstractions hasn't helped. For
example, dcc32 uses hash codes of 1 byte - an unsigned char - throughout
for symbol tables. It's particularly obvious in compiling Windows.pas -
compilation slows down dramatically towards the end of the unit as the
hash bucket chains grow to silly lengths. (This is a reason to keep the
Windows unit early in the uses list, as symbol lookups are performed in
reverse order of uses.) Fixing this hash code issue would mean changing
large portions of the source; most of the hash code lookups are
hand-coded directly, rather than encapsulated in any reasonable way. A
simple comparison of e.g. MS C# compilation speed against dcc32 using
roughly transliterated code - just parsing of declarations, with empty
method bodies - is revealing: dcc32 is usually slower. Dcc32 can win in
other ways, as it can save unit state to DCU while C# must recompile all
..cs in an assembly every time, but it is certainly clear that dcc32 is
no longer benefiting so much from all the assumptions baked into it back
in the early 90s, when machines were less powerful and programs much
smaller.


-- Barry


-- 
http://barrkel.blogspot.com/