Re: General byte-codes reference

  "Makhno" <mak@imakhno.freeserve.co.uk> writes:
>Hi, I'm interested in learning a bit more about byte codes in
>general. ie: If one were to write an interpreted language, what sort
>of byte codes to use? Nothing specific, but a gist of some general
>rules and recommendations. ie:
>
>1) Is it best to follow machine-code like rules, even if the
> byte-codes may not be running directly on the processor?
>
>2) What is needed for optimum code?
> eg Does it necessarily follow that less bytes = fast bytes ?
>
>3) Does it even matter? (as long as you don't go completely mad)


What are your goals?


So, since you are considering an interpreter, you are apparently
interested in compilation speed (otherwise, why not write a translator
to C?) and ease of implementation (otherwise, why not produce native
code?), and are prepared to take a factor 10 slowdown over optimized C
on some programs. However, you may want to limit that slowdown to this
factor, and not get a few more orders of magnitude slowdown like some
interpreters do.


So, you will design your code such that your compiler can produce it
quickly and easily, and such that your interpreter can interpret it
quickly.


>Have any papers been written on this subject?


Yes:


@Book{debaere&vancampenhout90,
    author = "Eddy H. Debaere and Jan M. {Van Campenhout}",
    title = "Interpretation and Instruction Path Coprocessing",
    publisher = "The MIT Press",
    year = 1990,
    annote = "Good discussion about interpretation with big
bibliography. They propose instruction path
coprocessing as a means to speed up interpreters. An
instruction Path coprocessor is similar to a
microcode sequencer that has the code to be
interpreted as machine code and the machine code of
the main processor as microcode."
}


@InProceedings{ertl95pldi,
    author = "M. Anton Ertl",
    title = "Stack Caching for Interpreters",
    crossref = "sigplan95",
    pages = "315--327",
    url = "http://www.complang.tuwien.ac.at/papers/ertl95pldi.ps.gz",
    abstract = "An interpreter can spend a significant part of its
                                    execution time on arguments of virtual machine
                                    instructions. This paper explores two methods to
                                    reduce this overhead for virtual stack machines by
                                    caching top-of-stack values in (real machine)
                                    registers. The {\em dynamic method} is based on
                                    having, for every possible state of the cache, one
                                    specialized version of the whole interpreter; the
                                    execution of an instruction usually changes the
                                    state of the cache and the next instruction is
                                    executed in the version corresponding to the new
                                    state. In the {\em static method} a state machine
                                    that keeps track of the cache state is added to the
                                    compiler. Common instructions exist in specialized
                                    versions for several states, but it is not necessary
                                    to have a version of every instruction for every
                                    cache state. Stack manipulation instructions are
                                    optimized away."
}


@Proceedings{sigplan95,
    booktitle = "SIGPLAN '95 Conference on Programming Language
                                    Design and Implementation",
    title = "SIGPLAN '95 Conference on Programming Language
                                    Design and Implementation",
    year = "1995",
    key = "SIGPLAN '95"
}


@Article{hoogerbrugge+99,
    author = "Jan Hoogerbrugge and Lex Augusteijn and Jeroen Trum
                                  and Rik van de Wiel",
    title = "A code compression system based on pipelined
                                  interpreters",
    journal = "Soft\-ware---Prac\-tice and Experience",
    volume = "29",
    number = "11",
    pages = "1005--1023",
    month = sep,
    year = "1999",
    coden = "SPEXBL",
    ISSN = "0038-0644",
    bibdate = "Sat Sep 18 18:25:59 MDT 1999",
    url = "http://www3.interscience.wiley.com/cgi-bin/fulltext?ID=63501205&;PLACEBO=IE.pdf;
                                  http://www3.interscience.wiley.com/cgi-bin/abstract?ID=63501205",
    acknowledgement = ack-nhfb,
}


@Article{klint81,
    author = "Paul Klint",
    title = "Interpretation Techniques",
    journal = spe,
    year = 1981,
    volume = 11,
    pages = "963--973",
    annote = "General discussion of interpreters. Empirical
comparison of direct threading, indirect threading
and token threading on PDP-11 and CYBER-73."
}


@InProceedings{proebsting95,
    author = "Todd A. Proebsting",
    title = "Optimizing an {ANSI~C} Interpreter with Superoperators",
    crossref = "popl95",
    pages = "322--332",
    annote = "Interpreter performance is optimized by combining
operators during code generation, when they are
still organized as trees. So a different, optimized
interpreter
is used for each program. Speedups of 1.8--3.1 are
achieved, but this is probably strongly dependent on
the original set of operators. The paper uses lccs
intermediate code operators \cite{fraser&hanson91a}."
}


@InProceedings{costa99,
        Author = {Santos Costa, V\'{\i}tor},
        Title = {Optimising Bytecode Emulation for {Prolog}},
          Booktitle = "LNCS 1702, Proceedings of PPDP'99",
          Publisher="Springer-Verlag",
          Month = {September},
          Pages="261--267",
          Year = "1999" }


>[There's lots of folklore, dunno of any papers. All else being equal,
>the fewer trips you make through your interpreter loop, the faster your
>program will run so you want to minimize operations, not necessarily
>bytes. Bytecode interpreters are more like CISC than RISC machines.
>-John]


However, usually not all else is equal, and those interpreters that
try to do a lot in each trip through the interpreter tend to be very
slow on the trip through the interpreter and therefore slow on
programs that use simple operations (e.g., Tcl, Perl).


So, my advice is to design an interpreter that does well on simple
operations; once you have that, you can add frequently used
macro-instructions and get a speedup.


However, in many cases you can get more speed by doing specialization
of some macro instruction at compile-time, even if this means breaking
the macro instruction into several smaller ones; OTOH, the downside of
such an approach is a slower and more complex compiler.


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

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