Threaded interpreter in Java

[Krystal Mok]

Thanks Rémi!

On Thu, Aug 4, 2016 at 5:36 PM, Remi Forax <forax at univ-mlv.fr> wrote:

> Hi Krys,
>
>
> On August 3, 2016 3:41:46 PM PDT, Krystal Mok <rednaxelafx at gmail.com>
> wrote:
> >(Having missed last night's dinner and all the fun there...)
> >
> >When Rémi started talking about this interpreter today, I thought it'd
> >be
> >tailcall related.
>
> I would love that it was tailcall related too. people seams to reduce
> tailcall to a feature of some obscure languages but in reality each time
> you have to do some argument transformations/injections/checking in a
> generic way, it screams for tailcall.
>
> >
> >In college, my introductory course to computer systems was based on the
> >book "Introduction to Computing Systems: From Bits & Gates to C &
> >Beyond",
> >where it introduces a small educational 16-bit architecture called
> >LC-2. We
> >were given a LC-2 simulator to run our "assembly" programs.
> >Later on, when I've learned enough Java to be dangerous, I wanted to
> >write
> >a more powerful simulator (interpreter) of the LC-2 ISA in Java.
> >
> >My first version was a most straightforward switch-threaded one.
> >Nothing
> >much to be said about that.
> >
> >The next version, wanting to mimic a indirect-threaded style, was
> >structured in very much the same way Rémi presented in the link, but
> >MethodHandle was still years from available so I didn't have the luxury
> >of
> >using it. Instead, I modeled the opcode handlers as "single-method
> >objects", and do a virtual call at the end of each handler.
> >(So, instead of Rémi's MH calls, I'm just using a table lookup +
> >virtual
> >call)
> >
> >public class NopHandler extends AbstractHandler // or implements
> >Handler
> >{
> >  public void execute(State s) {
> >    HANDLERS[s.code[s.pc++]].execute(s); // dispatch
> >  }
> >}
> >
> >That's didn't work out quite well. The performance was okay-ish with
> >small
> >program inputs. But HotSpot's JIT compilers doesn't implement tail call
> >optimizations (well, recursive inlining sort of counts...), so with a
> >long-enough program the stack blows up. And it didn't take that long of
> >a
> >LC-2 assembler program to make it blow up.
> >
>
> To avoid of blowing the stack, the trick is to stop the "trace" at the end
> of a basic block, i.e. when you have a jump or a return. It also means that
> things like null check, things that should not jump, has to be encoded with
> a different bytecode that conditional jump because you don't want to stop
> the trace for them.
>
> Cool! I haven't thought about using this trick in the context of an
interpreter in Java. That's really neat!


> >Need a good trampoline. Need proper tail calls.
>
> YES !
>
> YES!!

Thanks,
Kris


> >
> >- Kris
>
> Rémi
>
> >
> >On Wed, Aug 3, 2016 at 3:14 PM, John Rose <john.r.rose at oracle.com>
> >wrote:
> >
> >> On Aug 3, 2016, at 1:22 PM, Remi Forax <forax at univ-mlv.fr> wrote:
> >> >
> >> > Charles ask if we can make a fast register interpreter in Java,
> >> > here is my take on a threaded-like interpreter
> >> >
> >> > https://gist.github.com/forax/f38b533e089217cfc4d0ae3c6e2de9c9
> >>
> >> Nicely done.  We were talking last night at dinner about making
> >> bytecode interpreters go fast, and this is helpful.
> >>
> >> I think there may be a combinator here, for bytecode dispatch loops.
> >> (This feels like the PIC combinator, both fundamental and tricky to
> >get
> >> right.)
> >> A "bytecode" dispatch combinator might provide a pattern like the
> >> following:
> >>
> >> MethodHandle init, pred, step, fini, index;
> >> @NonNull MethodHandle[] tab;
> >> R dispatch(A… a) {
> >>    V v = init(a…);  // one here; there might be many v…
> >>    while (pred(a…)) {
> >>       v = step(v, a…);
> >>       // execute one "instruction":
> >>       int i = index(v, a…);
> >>       tab[i].invokeExact(v, a…);
> >>    }
> >>    return fini(V, a…);
> >> }
> >>
> >> The explicit table would be recopied internally to an @Stable array
> >for
> >> constant folding.
> >> The various index values could be tracked and turned into traces (or
> >some
> >> other profile
> >> driven structure) which would be compiled together, in specialized
> >> segments of the unrolled
> >> interpreter loop.
> >>
> >> Or maybe just the table lookup part alone makes a good combinator, to
> >be
> >> paired
> >> with the loop combinators?
> >>
> >> Comments welcome…
> >>
> >> — John
> >>
> >> P.S. Another new RFE:
> >> experimental hook for creating heisenboxes
> >> https://bugs.openjdk.java.net/browse/JDK-8163133
> >> _______________________________________________
> >> mlvm-dev mailing list
> >> mlvm-dev at openjdk.java.net
> >> http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
> >>
> >
> >
> >------------------------------------------------------------------------
> >
> >_______________________________________________
> >mlvm-dev mailing list
> >mlvm-dev at openjdk.java.net
> >http://mail.openjdk.java.net/mailman/listinfo/mlvm-dev
>
> --
> Sent from my Android device with K-9 Mail. Please excuse my brevity.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20160804/bbcabad0/attachment.html>