Please create an account to participate in the Slashdot moderation system

 


Forgot your password?
Close
typodupeerror
×
Programming IT Technology

Optimizing Stack Based Architectures? 31

Posted by Cliff 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."
This discussion has been archived. No new comments can be posted.

Optimizing Stack Based Architectures? More

Optimizing Stack Based Architectures?

Comments Filter:

  • Hi. (Score:3, Informative)

    by Anonymous Coward on Wednesday May 12, 2004 @10:31AM (#9126982)
    Tail-call optimization turns a call followed by an exit into a jump.

    • Re:Hi. (Score:5, Interesting)

      by Uma Thurman ( 623807 ) on Wednesday May 12, 2004 @10:41AM (#9127110) Homepage Journal
      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.

      You can even make this work if you've got a bunch of functions that call each other recursively with a tail call.

      For more tips, I'd recommend reading the source code to another stack machine. Outside of some very hard to read dissertations on a dusty shelf, I doubt that the lore of stack machine optimization can be found anywhere else. This is just one of those cases where "did you Gooogle the thing?" just doesn't apply.
      • Umm... it also works when the call isn't recursive.

      • Re:Hi. (Score:4, Informative)

        by Daleks ( 226923 ) on Wednesday May 12, 2004 @07:49PM (#9134599)
        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.
        • 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.

          Indeed it is problematic to mix stack inspection as in Java with tail recursion (Here I'm refering to languages like Scheme which promise to give you tail recursion.) But they can actually work together. See the paper "A Tail-Recursive Machine with Stack Inspe

  • GNU Vmgen (Score:5, Informative)

    by Carl ( 12719 ) on Wednesday May 12, 2004 @10:31AM (#9126988) Homepage
    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/

  • Forth archives (Score:4, Interesting)

    by MrIrwin ( 761231 ) on Wednesday May 12, 2004 @10:33AM (#9127012) Journal
    The document may be dated but back in the early 80's a lot of versions of Forth were produced.

    A german company even developed a microprocessor specifically designed for running forth.

    Unfortunately there was not much internet in those days and no HTML, but I think that is a good timespan to look at in your research.

    Look up Forth in MIT's library archives, it is more likely to throw up stuff than Google.

  • citeseer (Score:2, Informative)

    by blueAcid ( 526907 )
    I have no first hand knowledge in the subject, but perhaps this link [psu.edu] to citeseer [psu.edu] will help.
    -blue

  • Complimentary Compiler (Score:5, Funny)

    by mithras the prophet ( 579978 ) on Wednesday May 12, 2004 @11:41AM (#9128180) Homepage Journal
    A complimentary compiler [reference.com], huh? I agree, after a few frustrating hours with GCC and its nasty little invectives, that would be a great technology to develop...
    [mithras ~/src] alias cc="complimentary_compiler"
    [mithras ~/src] cc myprog.c

    myprog.c:7: In function `main':
    myprog.c:7: compliment: Wow, great job with those open and close braces!
    myprog.c:7: compliment: They really look wonderful, perfectly indented.

    myprog.c:83: In function `calculate_stuff':
    myprog.c:83: compliment: Ingenious coding here.
    myprog.c:83: compliment: Your use of the unused high bits of this array is pretty sweet, nice work.

    myprog.c:125: In function `foo':
    myprog.c:125: error: This line looks like it will be very powerful,
    myprog.c:125: error: but I can't quite figure it out. Perhaps you forgot a semicolon?
    myprog.c:125: error: Don't worry about it, I do that all the time.
    myprog.c:125: error: You've already been so productive today, you deserve a break!

  • Stack Folding (Score:4, Interesting)

    by pagercam2 ( 533686 ) on Wednesday May 12, 2004 @11:52AM (#9128354)
    I looked into stack machine optimization some time ago, and all the material seemed to fall into the category called "stack folding" which basicly amounts to combining loads with ALU ops rather than pushing onto the stack and then performing the op, just do the op as the data won't be used again on the stack. VM optimization as opposed to HW stack machine optimization is a slightly diferent ballgame as you don't have the direct bottleneck issues of the hardware. The benifits of stack machines are that they have one bottleneck and that can be optimized, but this also means that that bottleneck is always there you are really limited in pipelining as to keep the stack valid you need to wait for each operation to complete in sequence. The reason to VM a stack arch is the simplicity, but the stack becomes the bottleneck so it isn't the best solution for speed. I think that Stacks make a lot of sense for HW but I'm unsure if there is a benifit in VM SW, seems to me that a VM RISC arch would remove all the stack maintainence issues and all else being equal being that you are running your VM on a machine that probably has multiple registers that the code using the underlying arch would be faster. The VM wants to be the greatest common denominator of all target arch's which isn't going to be simple but without direct stack support on the uP you will have a fair amount of overhead.

  • use a register machine (Score:5, Interesting)

    by Aardappel ( 50644 ) on Wednesday May 12, 2004 @02:02PM (#9130373) Homepage
    You are asking the wrong question.

    Don't get me wrong, stack machines are certainly the simplest and arguably the most elegant & compact format, and certainly nice to use if you final target is mostly JIT/native code.

    If you are interpreting, your primary concern is _speed_. Speed in an interpreter on modern architectures (especially the P4!) is determined by almost constant branch mispredictions for every interpreted instruction (assuming a for(;;) switch(..) {..}; central interpreting loop, which sadly is still the fastest portable way of doing things). So your goal is to have the minimum amount of instructions generated for any particular language construct.

    Generating code for a register machine can be just as easy as for a stack machine if you have the right infrastructure (assuming you don't work with a bounded set of registers, which you have no need to in an interpreter).

    Register machines do much better here than stack machines, I would estimate about 1.5 times less instructions overal. Don't worry so much about the amount of work inside an instruction, aim to do as much as possible at once without branching as your VM design.

    It may be even be worth it to integrate struct field and array indirection as part of your opcode, as once you switch to a register machine, "getfield" type instructions will become your most frequent ones. So having say an "add" instruction that can directly address struct fields for its 3 arguments is going to be a big win (i.e. compile a.b = c.d + e.f into a single instruction). By having a pointer in your stack frame that points to itself, you can even do this for single variables in the same instruction.

    • Sure - if you never call functions (Score:1, Interesting)

      by Anonymous Coward
      Once you start interpreting an OO-like or procedural language on this register-based machine you'll find that you have to create a stack anyway in order to save all the registers between function calls. Stack based machine or register based machine - in the end it's a complete wash.

    • Look at Lua 4 vs. Lua 5 VM (Score:3, Informative)

      by 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 desig

  • Barking up the wrong tree (Score:1, Informative)

    by Anonymous Coward
    You need to read through comp.compilers.
  • 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
    • Not necessarily -- MOV's are extremely common in code generated for register machines -- data movement is simply a very common activity.
      • MOV's are typically very cheap, stack operations typically aren't. At the risk of generalizing, I'll assert that generally stack based VMs are built with a particular target language in mind, and that register machines aren't. With a register machine you're more likely to be playing by someone elses rules.

        IME if you develop and analyse your instruction set carefully, you can often reduce the amount of 'redundant' instructions necessary in a stack based solution. Let me give you a trivial example. In someth

  • searching papers: portal.acm.org (Score:3, Insightful)

    by hubertf ( 124995 ) on Wednesday May 12, 2004 @06:32PM (#9133964) Homepage Journal
    Try giving your query at http://portal.acm.org/ [acm.org], they return quite a bunch of articles, dunno how many of them are relevant. Download of article text may cost, though...

    - Hubert
  • For what its worth I've been writing an interpreter for mathematical equations in Java. The principal problem here is handeling different types of vectors and matricies (i.e. 2,3 & 4 dimensional vectors, 2 by 2 matricies etc). For each datatype I've used a different stack, so three different stacks for the three different vector types, and 9 stacks for matricies. Theres also corresponding heeps for each data type which are allocated during the compilation stage, eliminating the need for any object creat
  • One of the early stack machines was the Burroughs computers from the 60's (B5000/B6000/B7000/A Series). The machines were pretty fast and had some interesting things they did in hardware. In the 80's Unisys had developed an A Series emulator that ran on a PC.

    From what I know today, the A Series emulator runs on big Intel clusters with very good performance.

    You might want to extend your Google search to include the Burroughs/Unisys stack machines. A trip over to comp.sys.unisys with your question may

Slashdot Top Deals

"The whole problem with the world is that fools and fanatics are always so certain of themselves, but wiser people so full of doubts." -- Bertrand Russell

Close