Re: Threaded Interpreter

Ian Rogers <ian.rogers@manchester.ac.uk>
21 Nov 2005 22:47:16 -0500

          From comp.compilers

Related articles
Threaded Interpreter acampbellb@hotmail.com (Avatar) (2005-11-19)
Re: Threaded Interpreter anton@mips.complang.tuwien.ac.at (2005-11-21)
Re: Threaded Interpreter egagnon@sablevm.org (Etienne Gagnon) (2005-11-21)
Re: Threaded Interpreter jeffrey.kenton@comcast.net (Jeff Kenton) (2005-11-21)
Re: Threaded Interpreter gowrikumar_ch@yahoo.com (chandramouli gowrikumar) (2005-11-21)
Re: Threaded Interpreter ian.rogers@manchester.ac.uk (Ian Rogers) (2005-11-21)
Re: Threaded Interpreter dave@mips.complang.tuwien.ac.at (2005-11-27)
| List of all articles for this month |

From: Ian Rogers <ian.rogers@manchester.ac.uk>
Newsgroups: comp.compilers
Date: 21 Nov 2005 22:47:16 -0500
Organization: School of Computer Science, University of Manchester, U.K.
References: 05-11-091
Keywords: interpreter
Posted-Date: 21 Nov 2005 22:47:16 EST

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


Post a followup to this message

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