Optimizing Stack Based Architectures?

An anonymous reader queries: "I'm currently writing a stack oriented interpreter (*ahem* Managed Code Environment) with complimentary compiler (that will be under MIT license), and was wondering if there have been any advances in stack architecture optimization? Some intense Googling turned up this paper, but it seems a bit dated, and focuses mainly on managing local variables, which is inapplicable to me because my interpreter directly supports local vars. Any thoughts or useful links on the topic would be appreciated."

Comments

Hi.

[Anonymous Coward]

Tail-call optimization turns a call followed by an exit into a jump.

Re:Hi.

[Daleks]

Funny, but it's true, when the call is recursive. The tail call optimization causes a recursive function to execute in constant space, which is a pretty significant optimization.

The algorithm will only operate in constant space correctly if the recursive call doesn't pass a variable by value on the stack that indirectly references another value currently on the stack. Meaning, don't pass a pointer to a stack allocated variable to a tail-call optimized recursive function that will overwrite the current functions stack activation frame. This (and pointer aliasing) are why C can't as a general rule tail-call optimize. A language such as Java can do it, but tail-call optimization sets the stack pointer to the original stack pointer of the preceeding call. Thus giving the current function to the last function's stack address space, which can be a security problem.

GNU Vmgen

[Carl]

If you haven't looked at it then I would recommend GNU Vmgen, a virtual machine interpreter generator. http://savannah.gnu.org/projects/vmgen/

It comes with a nice manual that is an interesting read even if you are writing your interpreter by hand: http://www.complang.tuwien.ac.at/anton/vmgen/html- docs/

citeseer

[blueAcid]

I have no first hand knowledge in the subject, but perhaps this link to citeseer will help.
-blue

Barking up the wrong tree

[Anonymous Coward]

You need to read through comp.compilers.

It's not just about the VM

[ltratt]

In the paper referenced, the claim is that 1 in 4 instructions in a Forth VM is a DUP. That instantly makes me think that either the instruction set is horribly designed, or the compiler was generating massively inefficient code. Possibly both. The possible lesson to be learned from this is that, regardless of whether you have a stack or register based VM, other design decisions are likely to have at least as great an impact on performance.

There's also the possibility to use a hybrid machine that's mostly stack based, but if - for some reason - you find yourself DUP'ing or SWAP'ing a lot, having a few registers knocking around may solve that problem very nicely, without turning the whole thing into a register based machine. i.e. you can bolt it on in a mostly backwards compatible, low effort, fashion if you find you have the need.

Re:It's not just about the VM

[mparker762]

Not necessarily -- MOV's are extremely common in code generated for register machines -- data movement is simply a very common activity.

Re:Et tu Brute?

[beef3k]

You seem to have left out that Python has JIT these days...

Re:searching papers: citeseer.ist.psu.edu

[fprog]

You should try citeseer or one of its mirror too.
Most paper are free for download.
IEEE is another website or ACM queue.

http://citeseer.ist.psu.edu/cis?cs=1&q=stack+based +virtual+machine

Look at Lua 4 vs. Lua 5 VM

[Anonymous Coward]

Lua switched from a stack based VM to a (semi-unbounded) register based VM for Lua 5. The speed improvement is quite noticeable (>30% if you do not account for time spent in C libraries). And there is still room for improvement if you are willing to drop portability and/or debugging/tracing.

The source code is very concise and reads nicely. The VM interpreter core loop is < 400 lines in src/lvm.c. Read this along with src/lopcodes.h.

Please read and understand both Lua 4 and Lua 5 VM core BEFORE designing your own VM. Go and download the code at www.lua.org/ftp/, it's less than 200K each.

BTW: It has tail calls, too.