Home > Archive > Compilers > November 2005 > Threaded Interpreter
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Threaded Interpreter
|
|
| Avatar 2005-11-19, 3:57 am |
| I am searching for reference implementations of a threaded interpreter
(as opposed to the traditional switch dispatch method). Any
suggestions would be greatly appreciated.
Thanks
[I've always taken it to mean that rather than a string of byte codes,
you have a string of routine addresses, and the dispatch is via
something that in C might be written goto *ip++;
There was a long thread in comp.compilers some years back about how you
could write fairly machine independent threaded C code using some gross
hacks. -John]
| |
| Anton Ertl 2005-11-22, 4:00 am |
| "Avatar" <acampbellb@hotmail.com> writes:
>I am searching for reference implementations of a threaded interpreter
>(as opposed to the traditional switch dispatch method).
For a trivial implementation, look at my interpreter dispatch
micro-benchmark:
http://www.complang.tuwien.ac.at/forth/threading/
For something a little more substantial, you could look at the
examples provided with Vmgen
<http://www.complang.tuwien.ac.at/anton/vmgen/>. Since Vmgen is
distributed with Gforth, you also get a full-size threaded-code
interpreter with additional optimizations.
Finally, you can look at full-size interpreters like Gforth, SableVM,
the Ocaml "bytecode" interpreter, YAP or Sicstus Prolog.
>There was a long thread in comp.compilers some years back about how you
>could write fairly machine independent threaded C code using some gross
>hacks. -John]
No gross hacks needed, just the labels-as-values feature supported by
gcc and a number of other C compilers.
Fortran also supports this feature (under the name "assigned goto"),
so writing a threaded-code interpreter in Fortran should be possible.
- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html
| |
|
|
| Jeff Kenton 2005-11-22, 4:00 am |
| Avatar wrote:
> I am searching for reference implementations of a threaded interpreter
> (as opposed to the traditional switch dispatch method).
Some early versions of the PDP-11 Fortran compilers used this method, but I
don't have any direct references for you.
jeff
[The Unix 6th edition fc (known unfortunately as fc-tran) and the DEC
Fortran both used threaded code. You can probably find fc in some of
the ancient Unix archives. It's written in pdp-11 assembler, not C.
-John]
| |
|
|
| Ian Rogers 2005-11-22, 4:01 am |
| Optimizing Direct Threaded Code By Selective Inlining by Ian Piumarta,
Fabio Riccardi (1998 -
http://citeseer.ist.psu.edu/piumarta98optimizing.html) is a good
reference on threaded interpretation. The implementation described there
is heavily used by QEMU (http://fabrice.bellard.free.fr/qemu/) a popular
emulator. However, the tricks used to make QEMU work with GCC have
stopped working in GCC version 4.0+.
When implementing threaded interpreters you sometimes need to do it in a
type safe language such as Java. Obviously the goto *ip++ trick isn't
going to work. What you can do is take advantage of the compilation system:
class Interpreter {
static Interpreter interpreters[NUM_INSTRUCTIONS];
static {
interpreters[NOP] = new Interpreter() {
Interpreter execute() {
IP += 4;
return interpreters[memory[IP]];
}
};
interpreters[ADD] = new Interpreter() {
Interpreter execute() {
IP += 4;
// do add...
return interpreters[memory[IP]];
}
};
// ...
}
// ...
static void execute(Address IP) {
Interpeter currentInterpreter = interpreters[memory[IP]];
while(true) {
currentInterpreter = currentInterpreter.execute();
}
}
}
the idea behind threaded interpreters is that certain sequences of
instructions are more common. For example a compare is usual before a
branch. The threaded interpreter beats regular interpretation with a
switch statement as the branch predictor can predict where the next
instruction will be (there are lots of local de-multiplexes rather than
a big global de-multiplex at the head of the switch statement). With the
code above the result of the load at the end of the execute is
predictable and local to the current instruction - so the compilation
system can predict in the interpreter that branches will more often than
not come after compares. The net effect of this in a JVM system like
HotSpot or IBM's J9 is that the threaded implementation above will be
about 10% faster than a switch based implementation.
Regards,
Dr. Ian Rogers
The University of Manchester, UK
| |
| David Gregg 2005-11-27, 3:57 am |
| Ian Rogers (ian.rogers@manchester.ac.uk) wrote:
: the idea behind threaded interpreters is that certain sequences of
: instructions are more common. For example a compare is usual before a
: branch. The threaded interpreter beats regular interpretation with a
: switch statement as the branch predictor can predict where the next
: instruction will be
It's possibly worth pointing out that threaded code has been used
since long before indirect branch predictors became widely
available. Bell's original paper on threaded code appeared in
1973. The original advantage of threaded code over using a switch
statement would have been a saving of a couple of instructions in each
dispatch in the interpreter. The behaviour of threaded code on branch
predictors was just a nice side effect that people noticed much later.
It's possible to capture the same effect without using threaded code,
although you still need to use GNU C's labels-as-values extension (or
program in Fortran or assembly). Just dispatch through a table of
labels. Something like:
goto *(dispatch_table[opcode]);
Just make sure that there is a separate goto at the end of the code
that implements each VM instruction. This gets a large chunk of the
benefits of using direct threaded code without all the pesky
translation of the bytecode to a new format.
David.
|
|
|
|
|