is RITE stack based or register based VM?

[rolo]

Hi

RITE is a stack based VM like JVM or Register based like Parrot?

regards,
rolo

 

[Yukihiro Matsumoto]

Hi,

In message "is RITE stack based or register based VM?"

|RITE is a stack based VM like JVM or Register based like Parrot?

Stack based, as I believe.

matz.

 

[Guillaume Marcais]

Le 4 avr. 04, à 20:00, Yukihiro Matsumoto a écrit :

Hi,

In message "is RITE stack based or register based VM?"

|RITE is a stack based VM like JVM or Register based like Parrot?

Stack based, as I believe.

Do you mean 'I believe RITE is stack based' or 'RITE is stack based, as
it is the technology I believe in'?

 

[Yukihiro Matsumoto]

Hi,

In message "Re: is RITE stack based or register based VM?"

|> Stack based, as I believe.
|
|Do you mean 'I believe RITE is stack based' or 'RITE is stack based, as
|it is the technology I believe in'?

Hmm, ambiguity in the English language is interesting. I meant the
former, but I'd say "both".

matz.

 

[Jean-Hugues ROBERT]

Hi,

Skip this msg unless theory about interpreters implementations matters to you.

Stack based... to what extend (speculations about RITE) ?

Two things:
1) I guess we are not talking of the micro-processor's stack (SP) here.
Stack "less" interpreters are considered easier/better approach.
See stackless Python. Anyway, Continuations make it tricky to use the
processor's stack. You need a SpaghettiStack.
2) Regarding the "expression evaluation stack". That is a different matter.
Probably the one involved when talking about "stack based vs register
based".

For this case, I may point out that sometimes the compiler can get some
knowledge about "how deep" that stack most probably needs to be (I
suppose it
can never actually know the max depth, due to
Continuation/Blocks/eval()).

However, for the cases where the compiler knows about the stack depth,
it is faster to perform absolute addressing instead of relative
addressing
with some SP (you avoid the ++SP/--SP house keeping, among others).

Example 1: Stack based imaginary VM. c = a + b
push b # Alloc stack slot, link to previous, put b's value in it
push a # Alloc stack slot, link to previous, put a's value in it
meth +, 2 # Invoke method, dealloc 1 stack slot
pop c # Mov top-of-stack to c, dealloc 1 stack slot.

Example 2: Precomputed stack accesses
stack 2 # Alloc stack slots, done once when
ActivationRecord is created.
mov b, 0 # put b's value in first slot
mov a, 1 # put a's value in second slot
meth +, 0, 2 # Invoke method, args in first & second slots
mov 0, c # Mov first slot's value to c

Benefit:
- Speed ! One allocation only
Drawback:
- Compiler must compute @stackDepth of each method definition.
- Efficient allocation of stacks requires some pool management for
most frequent stack sizes.

Considering that Rite's main purpose is speed, stack management probably
deserve to be as efficient as possible.

I don't know wether the result should be called stack based or register
based, because there still is a variable depth stack yet you most of the
time use it as an array of registers.

Yours,

Jean-Hugues Robert

See also:
http://www.c2.com/cgi/wiki?ActivationRecord
http://www.c2.com/cgi/wiki?StacklessPython
http://www.c2.com/cgi/wiki?ContinuationExplanation
http://www.c2.com/cgi/wiki?SpaghettiStack

 

[Jean-Hugues ROBERT]

Hi,

For this case, I may point out that sometimes the compiler can get some
knowledge about "how deep" that stack most probably needs to be (I
suppose it
can never actually know the max depth, due to
Continuation/Blocks/eval()).

[rolo] Do you mean that based on the information that max depth is
unknown, a stack based RITE would not be as efficient as it can be using
registers?

I don't know about that. What I do know is that when the
evaluation stack max depth can be determined by the compiler,
it is more efficient to allocate that stack once (per ActivationRecord)
and use the stack as an array with absolute indexes, instead of
computing some SP at runtime.
I would have to investigate more about what "register" means in modern
interpretor, because the understanding I have is based on some work
done by C compilers twenty years ago ;-) I may do that to see if the
optimization I did implement in an interpretor a while ago is related
in anyway to "registers", even thought at this point I think it is
not and is more like an optimized stack based scheme.

When the stack size cannot be pre-determined, I guess that the only
solution is to allocate more chunks of stack slots as needed (kind
of catching stack-overflow as is done by some OS). The only optimization
I can think of here is to allocate bigger chuncks versus one slot at
the time.

Yours,

Jean-Hugues