the idea would be to develop a new faster threaded-code backend for the
BGBScript VM, which would basically be used "behind the scenes" while
still keeping the existing high-level bytecode.

as-is, the interpreter already translates the bytecode into a
stack-based threaded-code format (which is faster than running it
directly via a "switch()", but still could be somewhat faster).

so, the general idea would be to "unwind" the stack-based bytecode
(vaguely like JVM or AVM2 bytecode) into using a register-machine model
(more like Dalvik or Parrot), and essentially use a register-machine to
execute the code.

a lesser goal is that it could also potentially lessen the work of
writing a JIT backend (to allow for a smaller and simpler JIT, which
should ideally be easier to implement, debug, and maintain).

First Message:
<===
but, I just went and wrote up a basic "idea spec" for the new
interpreter idea, which I decided to call FastRIR.

it is yet to be proven though whether it would be much faster than the
current interpreter (the number of inner-loop pointer-operations is not
likely to be much different than my current interpreter).

note that the basic premise of operation for this sort of interpreter is
that the function-pointers inside the structures are generally what are
used to direct control flow (so, the logic that sets up the execution
path will generally set up the structures and fill in function pointers
as-appropriate).

this is in contrast to a more traditional "while loop and switch"
interpreter, but this style of interpreters tend to be a little faster
IME (without being drastically more complicated).

this is far from comprehensive, so a little imagination would be needed
to "fill in the gaps".

(the main focus here is on the part of the interpreter which tends to
consume the bulk of the execution time, which often tends to be the
thing spinning in a loop and executing operations).

any ideas for how to make such a design idea faster are welcome (apart
maybe from putting everything in globals, which yes, can make things
faster, but kills thread-safety, and also doesn't help much on ELF targets).

but, anyways, here is the current idea spec:
-----

Fast Register IR:
Low-level statically-untyped (weakly-typed) register-machine model.

Operations are statically typed and operate on registers.
Most operations will follow a 3 register form.

add_i dest, srca, srcb

so:
add_i, add_l, add_f, add_d
sub_i, sub_l, sub_f, sub_d
...

This will be used for a threaded-code interpreter.
FRIR code will be organized into traces.

FRIR will have up to 256 registers of each type.

union FRIR_Value_u
{
     s32 i;
     s64 l;
     float f;
     double d;
     byte *pb;
     dyt r;

FRIR_Frame *frame;                //active frame
FRIR_Frame **fspos;                //frame stack position
FRIR_Value *vspos;                //var stack pos
FRIR_Value *aspos;                //arg stack pos

int ret;    //ctx return state (0=normal execution)

//register state (shared with frame)
int *ri;
s64 *rl;
float *rf;
double *rd;
byte **ra;

A method will hold an array of opcodes and traces.
The opcode array will hold all opcodes in the method.
Traces will represent subsets of this opcode array.
A trace may not contain a jump or an operation which may throw an
exception, but may terminate with such an instruction.

struct FRIR_Method_s {
FRIR_Opcode *ops;        //first opcode in method
FRIR_Trace *trace;        //first trace in method
int n_ops;                //number of opcodes
int n_trace;            //number of traces

struct FRIR_Opcode_s {
void (*fcn)(FRIR_Context *ctx, FRIR_Opcode *op);
int op;
int a, b, c;
FRIR_Value i;

lea_b dest(RA), base(RA), index(RI)
lea_w dest(RA), base(RA), index(RI)
lea_i dest(RA), base(RA), index(RI)

lea2_b dest(RA), base(RA), index(RI), offset(II)
lea2_w dest(RA), base(RA), index(RI), offset(II)
lea2_i dest(RA), base(RA), index(RI), offset(II)

void ThOp_Add_I(FRIR_Context *ctx, FRIR_Opcode *op)
{
     ctx->ri[op->c]=ctx->ri[op->a]+ctx->ri[op->b];

     op=tr->ops;
     ope=tr->ops+tr->n_ops-1;
     while(op<ope)
         { op->fcn(ctx, op); op++; }
     return(tr->end(ctx, tr, op));

     op=tr->ops;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     return(tr->end(ctx, tr, op));

     op=tr->ops;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     op->fcn(ctx, op); op++;
     return(tr->end(ctx, tr, op));

void FRIR_Thread_RunStep(FRIR_Context *ctx)
{
     FRIR_Trace *tr;

     tr=ctx->trace;
     while(!ctx->ret)
         { tr=trace->run(ctx, tr); }
     ctx->trace=tr;

Second Message:
<===
investigating more (and [after] looking some at Dalvik, ...) it seems
there is a bit more room for possible optimizations at the interpreter
level for a register-IR.

a register IR also allows for more easily eliminating common
sub-expressions (could likely be "recognized" from the stack-based input
bytecode).

(I also looked at Parrot and LLVM IR, but these are less closely related
to my current VM).

as-is, things are still in a "general design and basic experiments" stage...

apparently, people working in similar situations in the past, were able
to get a roughly 25%-30% speedup by translating to a register IR (for an
interpreter). this was for Java ByteCode.

some further speedup is possible as it is considered that the conversion
step would also better nail down things like variable scope and object
field access, which are currently handled dynamically (FRIR will be much
lower-level than the BSVM bytecode).

for example, FRIR will distinguish between local variables, function
arguments, and captured lexical variables (in the BSVM bytecode, these
are all treated as a single unified "stack", but which may not be
physically continuous in memory, essentially requiring a linked-list walk).

basically, for example, it could possibly optimize accessing an object
slot from something like (present):
check object type;
fetch slot by name (hash-key lookup);
dispatch by field type and fetch value.

to something more like:
*(int *)(((byte *)obj->data)+op->i.i);
which would likely be significantly faster than the current logic.

(the above case could be optimized in the current interpreter, but I
hadn't done so previously because it would be a hassle, requiring more
complex logic for emitting the threaded code...).

a similar speedup may be possible for array handling (it will no longer
need to type-check the array, like to determine that it is an array).

these will likely be specific to typed variables, so:
var obj:MyClass = new MyClass();
obj.x=3;
or:
var arr:int[] = new int[256];
arr[31]=4;

Most Forth's coded in C use a switch() since that's the C way of doing
things.  I didn't use a C switch() statement for my interpreter.  I
interpret the same way as early ITC Forth's in assembly, but using C
instead of assembly.

From my own experiences, I can "see" issues with needing a register
allocator, keeping track of which data is in which registers, spilling of
registers when you run out of available registers, etc.

The first issue is that the "register" keyword only works on "auto" or
procedure local variables for GCC.  GCC deprecated the use of the "register"
keyword for file scope or global variables.

The second issue is:

"If I can't use the 'register' keyword on globals, and I've got four
procedures operating on my globals, how do I get all four procedures merged
into a _single_ procedure so that my globals become 'auto' types and can be
optimized?"

The first answer to that is something C doesn't have: nested procedures.
The second answer to that -possibly- is something C doesn't have either:
inheritance.  The third answer to that is: "I'm still working on that one!"
At this point, I'm considering *anything*, like even a small switch() or
Duff's device, in order to get 'auto' types.  I just haven't attempted to
get something working, yet.

Or, just abort...

N.B. My experience is very low, but I'll try to add a few tidbits.

Just see what GForth does, they seem to know what they're doing (GCC's computed goto?).

so, the point now is mostly looking into taking a different and more
efficient route towards the interpreter backend.

note that, unlike Forth or similar, the BGBScript bytecode follows
similar stack-use restrictions to JVM bytecode, basically that on a
given jump/label, the stack layout is required to match.

the prior interpreter basically operated as a sort of
continuation-passing-style, where every opcode would return the next
opcode to execute.

this time I am factoring this out and instead using "traces".
the hope is that by better nailing down the opcode-level control flow, a
more efficient means of executing the instruction traces may be used.

threaded code is a little faster, but all of those function
calls/returns and indirect function calls are also expensive (note:
can't use computed goto as my interpreter is not GCC specific).

sadly, there is no really "good" option short of writing the whole
interpreter core in ASM, and by this point I may as well just write a JIT.

this will likely exceed the number of x86 registers, but the threaded
code will use a "potentially unbounded" number of virtual registers.

if a JIT were used, likely it would use a mapping heuristic to figure
out which VM registers to map to hardware registers (this would more
likely apply to x86-64, I suspect that 32-bit x86 is sufficiently
register-starved to where any sort of aggressive mapping would likely do
more harm than good, and ESI/EDI would likely be needed mostly for
holding the current VM state).

so, you can avoid the need to "spill" by simply having 256 (or more) as
the max number of VM registers, and by making the VM preserve register
state across calls.

the need for a full register allocator can also be avoided at this stage
as well (they can be allocated either sequentially or in a stack-like
manner.

it is the same sort of issue as checking if an exception-state variable
has been set. it seems simple enough, but it can eat lots of clock
cycles in a tight loop.

typically, a stack might be accessed like:
ctx->stackpos--;
*(int *)ctx->stackpos=((int *)ctx->stackpos)[0]+
        ((int *)ctx->stackpos)[1];

but, if we add something like:
if(ctx->stackpos<0)
        { ... }

then suddenly lots of clock cycles are being wasted just performing this
silly little check.

and, if our dispatch loop is something like:
while(op && !ctx->ret)
        { op=op->fcn(ctx, op); }

that "&& !ctx->ret" also adds a bit of cost.

here is the inner-loop for the in-development interpreter:
BGBFRIR_API FRIR_Trace *FRIR_Trace_RunDefault(
        FRIR_Context *ctx, FRIR_Trace *tr)
{
        FRIR_Opcode *op, *ope;

        op=tr->ops;
        ope=tr->ops+tr->n_ops-1;
        while(op<ope)
                { op->fcn(ctx, op); op++; }
        return(tr->end(ctx, tr, op));

an integer type makes more sense, but leaves the minor annoyance of sign
and address-size (x86 addresses are unsigned and 32-bit, x86-64 is
signed and 64-bit), requiring a little bit of special handling in
certain cases.

at the IR level, the 'A' (address type) is partly disjoint from the
integer types, so at least the issue shouldn't be apparent.

there are operations like: "conv_a2l" and "conv_l2a" to convert between
pointers and long (signed 64-bit), but doing this is not as efficient on
32-bit x86 (shouldn't matter too much, as this isn't likely to be all
that common).

but, as-is, IR would look something like:
llload_i 2, 7   //load local var 7 into r2
llload_i 3, 8   //load local var 8 into r3
add_i 2, 2, 3   //add r2=r2+r3
llstore_i 2, 9  //store r2 into local var 9

there may likely end up being a few more special cases, like:
lladd_ic 11, 2  //add 2 to local var 11
which would in C look something like:
BGBFRIR_API void FRIR_ThOp_LLADD_IC(FRIR_Context *ctx, FRIR_Opcode *op)
        { ctx->llvars[op->c].i+=op->i.i; }

this mostly precludes the use of compiler-specific features.

granted, yes, conditionals are also expensive, so the number of
conditional expressions and unpredictable branches needs to hopefully be
minimized.

ironically, BGBScript has computed goto (but this is of little help in
implementing an interpreter for it).

I was aware of Dalvik and Parrot though, so these are mostly what I was
looking into.

note that the use of a register interpreter backend will not effect the
use of a high-level stack-based bytecode.

like, in script code:
try {
        ...

"abort()" is no-go, given the type of app I am developing...

usually, if the exception can't be handled in script code, then the VM
will set up for an "uncaught exception" and return back into C land with
an error code (this was chosen as preferable to trying to throw an
exception in C land, which is kind of a mess).

theoretically, it means that code calling into the VM "should" check for
an exception whenever an error code is returned, or the return-value is
"undefined", but sadly, a lot of code doesn't bother.

mostly this doesn't matter as much, as script-code is generally
considered as less important than the underlying C code for the program.

note that script code may also throw things like:
"NullPointerException", "UndefinedMethodException", ...

However, without underflow/overflow checks how do you confirm underflow or
overflow for push/pop?  And, where would you?  Do you just allow push/pop to
crash/halt the application or overwrite non-stack memory?

I've no elegant solution to this other than to insert the checks.  I was
hoping to maybe analyze the program in more depth in the future to determine
other code locations where the checks could be placed.  I.e., somewhere
where they weren't constantly being checked, but checked frequently enough
that they would prevent or detect most overflows/underflows prior to them
occurring.

Clearly, you can rework the code to fix trivial stuff like eliminating the
need for "-1" for ope either by adjusting tr->n_ops or using op<=ope.

Anyway, I'm not entirely sure what you're doing with all the ctx and tr->ops
and op->fnc(ctx,op) stuff.  The best I can tell, this is a loop through a
list of functions to be called.  The functions get called.  They also get
passed 'ctx' - which I'm not sure what is.  I would guess that fcn and op
should be all that's needed ...  However, I've seen other code use 'ctx' and
it's usually something like a register struct or a VM save state.  If so, it
seems like it's doing some additonal work since ctx pointer keeps being
passed, i.e., allocated and deallocated on the stack for each function call.
Won't declaring the fcn function as "void func(void)" reduce some overhead?
It should eliminate the prolog(ue) or epilog(ue) code for the procedure.
But, that requires op and ctx to be globals instead of locals.  For GCC,
you'll still end up with some stack adjustments upon procedure entry or
exit.  For other C compilers, you should be able to make the function
"naked" by using "void func(void)".  Or, you can use special compiler
attributes to do so.

granted, yes, another potential cause of error is an
"OutOfMemoryException", but this is potentially a bit more severe
(basically, it means that the heap is all used up and that the garbage
collector can't free up any more, so a memory-allocation request has
failed).

stack-overflows are potentially a little more common with my VM as it
typically uses smaller stacks than are generally used by native threads,
but this is counterbalanced by my VM not generally allocating storage
for objects or arrays on the stack.

this means that, granted, an overflow exception may be generated even if
the execution path which would generate the overflow is never called.

but, say, if we know that the method has, say, a maximum stack-depth of
11, then we only need to reserve space for 11 stack items.

similar goes for reserving space for things like lexical environment
frames, ...

I don't know whether this would be applicable or not to something like
Forth, but given the VM has a similar stack-usage restriction to the JVM
(namely that stack layout and element types be statically determinable),
this makes things a little easier.

the VM is mostly used by the "BGBTech Game Engine":
http://www.youtube.com/user/BGBTech
ex:
http://www.youtube.com/watch?v=E1kN_bM6KBs&feature=plcp

note that this 3D engine is itself internally multi-threaded in many areas.

or, in other words, using global variables would risk making stuff blow
up pretty damn hard... (and TLS costs more than passing state around in
arguments).

the ctx and op are basically the VM-state-context and opcode-state.

the reason for all the function-calls through function-pointers stuff is
that, in my tests, this has generally be one of the fastest ways I know
of to do this.

{
   int Boo; // Allocated on the stack

   try
   {  ...
   }
   catch (ex:StackOverflowException)
   {
      printf("Stack blew up when Boo=%d!\n", Boo);

Anyway. Handling exceptions in this way is much like co-routine calls. A
co-routine may have stack of its own. I wonder what could become of that.
(Not returning to on-clauses of early PL/1 of course.)

Using a very simple mock-up of the interpreter (just repeatedly executing a
single bytecode, that used for an unindexed loop, but it will test the
dispatching), I got these results (to execute this bytecode a billion
times):

4.5 seconds   (C using a do-while loop, and calling handlers via function
pointers)
3.4 seconds   (C using a big switch statement)
3.3 seconds   (C using gotos to gcc's indirect labels; a kind of threaded
code)
2.1 seconds   (x86 ASM also using direct threading)
1.9 seconds   (The current interpreter also using direct threading)

So if I'm going to use C at all, then it will be probably be a switch.

Either make it optional (for debugging for example), or check it
infrequently, perhaps per function-call (since stack overflow is most likely
to be caused by out-of-control recursion) rather than per expression.
(Assuming it is too hard to detect an actual stack fault.)

but, the stack issue is not actually an issue.

this is partly because local variables are not "only" stored on the
stack, but any captured bindings (due to a closure or otherwise) will
typically end up in heap-allocated environment frames.

actually, even then, within the current interpreter, variables have
their own stack, and there are parallel stacks for various tasks:
value-stack (holds intermediate values);
mark-stack (holds "marks" for the value-stack);
flow-control stack (holds call frames);
local variable stack (holds non-captured local variables and similar);
dynamic variable stack (holds any dynamically-scoped variables);
...

actually, the bytecode makes the lexical environment itself look like a
single big stack, except that this stack is not physically contiguous in
memory whenever closures are made (the lexical environment is more of a
linked-list structure).

currently, different threaded code is generated based on whether or not
the current function has captured bindings or is itself a closure
(captures bindings from a parent function).

in the case of FRIR, it would actually keep track of the difference
between lexical and local variables, and identifies lexical variables
via a pair of numbers (indicating how many levels to walk outwards, and
the binding within that level).

ex: "3, 8" means "up 3 levels, entry 8".

currently a stack-overflow exception doesn't actually indicate which
stack overflowed.

this is mostly because the current interpreter is internally implemented
using CPS (continuation-passing-style), and uses its own internal
stacks. similarly, calls within the VM don't actually use any more space
on the CPU stack, mostly because in C land, it is all just a single
trampoline loop which spins in place (so, the interpreter is not
recursive in this case).

granted, a possible issue is that MSVC generates some pretty bad code
for switch statements.

so, an indirect call via a function pointer will typically outperform
the "switch()" IME.

usually, this would be for a few scenarios:
the interpreted code has returned from the outermost level;
the code has blocked or executed a sleep call;
an exception has been thrown;
a call is being made back into C land;
...

The switching to a some emergency stack is only for the purpose of the
exception handling mechanism which may need its own stack frames.

Anyway, in protected operating systems, interrupts and exceptions (the
real, architectural ones) are handled on a different stack inside the
kernel.  You cannot rely on unprivileged mode to have a stack for catching
interrupts and exceptions. Suppose user space has pushed its stack pointer all
the way to the edge of available space so that the next address is an unmapped
page. In that situation, interrupts like the clock tick or network receive
still have to work! They do because the exception handling in the architecture
switches to a kernel stack before saving the machine state.

A stack overflow situation might be intercepted at the CPU level, and
turned into an exception that traps to the kernel, on the kernels' stack.
That kernel code could pull some strings to arrange for the user code to have a
different stack for running the user handler for that condition.

Unix has a such a thing: sigaltstack.

http://pubs.opengroup.org/onlinepubs/007904875/functions/sigaltstack....

"The sigaltstack() function allows a process to define and examine the state of
an alternate stack for signal handlers for the current thread. Signals that
have been explicitly declared to execute on the alternate stack shall be
delivered on the alternate stack."

I was working some on adding basic mechanisms, like function calls, but
am left thinking more about "efficient" ways to manage scoping, and
hopefully not be left with ugly problem areas or poor performance (the
whole effort would be pointless if most of the speedup is squandered
away again with something like slow method or variable lookups).

a partial tradeoff is between "directness" and "mutability", for
example, consider I am calling a "static method":
I can cache the static method with the instruction, so that the next
time around the static method is invoked directly, and does not incur a
performance hit from having to fetch it. but what then if the class
containing the method is redefined and the method is replaced?...

this implies the added cost of fetching the method again each time from
the class's vtable (~ 45ns).

the only other obvious solution is for the interpreter to basically
retain pointers to all static method calls, which can then be flushed
as-needed (setting the method-pointer back to NULL, and setting the
handler from the direct-call case to the "lookup and then attempt to
call" case).

another alternative here being of course a kind of "static method call
table", where basically all of the active static methods are laid out in
a big global table which calls are directed through. the static-calls
would then hold pointers to the table entries. (note that entries would
likely be keyed as "class-qname"+"methodname"+"signature").

as of yet, I have doubts about strategies that would nail down the class
or object types (as-is, there are currently 2 major types of object, one
used for class/instance and dynamic classes, and another used for
prototype-OO via ex-nihilo objects, which are currently also used to
implement packages).

as-is, the currently existing interpreter will just fetch the method
from the class/object each time (and then use type-checks to see how to
apply it). this works but isn't particularly efficient.

otherwise, here is something from an email:

<---
after fiddling around with image compression stuff more, and a brief run
of trying to optimize my 3D engine somewhat, I went and finally got
around to finishing up the new "FRIR" (the "register IR") interpreter
enough to test it (at least in a very minimalistic form).

so, for the FRIR interpreter test, the equivalent of a "for()" loop
spins 45.2M cycles per second (23.23s to spin 1,000,000,000 times).

native "for()" loop, 385M cycles per second (2.6s).
IOW: "for(i=0; i<1000000000; i++);"

difference: 8.9x of native.

this seems promising, as it is nearly 7x as fast as my current interpreter.

this is not to say though that it wouldn't slow down once weighted down
by all the other crap and used for "actual" script-code.

though, it would probably at least be somewhat faster, as the existing
script interpreter is still a bit of a cobbled-together mess...

not like my other "real" benchmarks were that realistic, as most were
doing things like the recursive fibonacci function and implementing
bubble-sort and similar, which aren't likely to be particularly
representative of the normal workloads... (which has thus far been
mostly for running part of the AIs for several of the monster types,
among other mostly misc things...).

will see though if I actually do much with it.
it would still take a bit of work to really make the new backend "ready
for use".
--->