Re: Contemplating writing first compiler... comments please.

Herbert Sauro <HSauro@fssc.demon.co.uk> wrote:
>[What's the best way to execute a chunk of code like byte codes?]


Like most things, "best" depends on your needs.


There are five basic methods that I know of:


  - Implement hardware
  - Static compilation to a host processor
  - Decode-and-dispatch interpretation
  - Predecode interpretation (e.g., threaded code)
  - Dynamic cross-compilation (e.g., JIT).


"Decode-and-dispatch interpretation" (ddi) looks at the text of an
instruction each time that is executed. DDI tends to be slow for
complex encodings (e.g., instruction sets for real hardware); speeding
it up tends to mean writing a more complex and more space-hungry
decoder. DDI can be simple and not pokey for simple instruction sets
such as bytecodes where the decoding overhead is small. A limit to
performance is that each instruction is executed in isolation so
there's no opportunity to optimize across multiple instructions. The
"larger" your primitive is, the less this is a restruction; for
example, "pop two stack elements; add; push result" can often be
combined with "pop top stack element; negate; push result", but "draw
filled circle" can be pretty optimized on it's own. Hence languages
with complex primitives, such as PostScript(tm) tend to gain
relatively little from sophisticated optimizations.


"Predecode Interpretation" (PDI) decodes instructions once (say, at
load time or on first execution) and caches a quick-to-decode form of
the instruction. On reexecution, the decode overhead is avoided. PDI
thus avoids the "decode" cost of interpreation. PDI suffers the
problem that if the code changes the cached form must be invalidated
or updated; this may be hard if the original language lacks a
consistancy operation. "Threaded Code Interpretion" (TCI) is a
particularly common, simple and typically fast form of PDI whwere the
decoded form is a pointer to "handler" that implements the desired
action. Typically, handlers written as functions will suffer from
prolog/epilog overhead; GNU CC contains support that makes fasta TCI
implementation possible in a HLL.


"Dynamic Cross-Compilation" (DCC) is a form of PDI where the "fast to
decode" form is host machine instructions. The dispatch cost is
further reduced because DCC uses fast host hardware for decoding; and
because it is possible to optimize between instructions. For example,
the dispatch overhead (except cache costs) can often be completely
removed, redundant work can be amortized over several instructions,
values can be promoted to registers, and so on.


To blow my own horn: there's (somewhat) more about this in the Shade
SIGMETRICS paper and in Conte & Gimarc's Shade book chapter.


%A Bob Cmelik
%A David Keppel
%T Shade: A Fast Instruction-Set Simulator for Execution Profiling
%J Proceedings of the 1994 ACM SIGMETRICS Conference
on the Measurement and Modeling of Computer Systems
%D May 1994
%P 128-137


%T Fast Simulation of Computer Architectures
%E Thomas M. Conte
%E Charles E. Gimarc
%I Kluwer Academic Publishers
%D 1995
%N ISBN 0-7923-9593-X


For more information see


http://www.cs.washington.edu/research/compiler/papers.d/shade.html
ftp://ftp.cs.washington.edu/pub/pardo/shade.ps.Z


The Shade papers contain extensive bibliographies.


;-D on ( Interp Rhett ) Pardo
--

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