Slashdot Mirror

← Back to Stories (view on slashdot.org)

Optimizing Stack Based Architectures?

Posted by Cliff on from the saving-bytes-and-increasing-speed dept.

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."

4 of 31 comments (clear)

  1. Hi. by Anonymous Coward · · Score: 3, Informative

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

    1. Re:Hi. by Daleks · · Score: 3, Informative

      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.

  2. GNU Vmgen by Carl · · Score: 4, Informative

    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/

  3. Look at Lua 4 vs. Lua 5 VM by Anonymous Coward · · Score: 3, Informative

    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.