Sign in to follow this  
JohnGalt

Stack Implementation in my VM

Recommended Posts

I was just trying to calculate fibonacci numbers on my virtual machine from another thread, and ran into some trouble. Using the recursive fibonacci algorithm I can only calculate to about 300 and my VM gives a stack overflow error. I believe I know why this is happening (my stack is not very memory efficient). How does everyone else handle this in their VM's? Here is my design: there is a system stack (for function calls) and a user stack (for arguments and other user stuff). The stack is just a character array and when I push something, I push the value, then I push the number of bytes used by that value. In the system stack I push all the variables that are used to keep track of the currently running procedure (program counter, bytecode module, procedure address, and offset for procedure's local memory). I've since thought of a better way to do it but maybe some of you other guys working on VM's could give me some ideas about your designs.

Share this post


Link to post
Share on other sites
How big did you make each stack? Which one is overflowing?

On the real architecture, there is of course only one stack; auto variables local to a function get pushed onto the stack right after the input parameters. (Actually the first thing that will be pushed is likely empty space, for a return value.) Of course, I suppose I am thinking of things in very C-coloured terms. :s

Share this post


Link to post
Share on other sites
The problem is you algorithm. The stack depth is O(2^n). There are several much better algorithms out there for this sequence.

karg

Share this post


Link to post
Share on other sites
Quote:
Original post by Karg
The problem is you algorithm. The stack depth is O(2^n). There are several much better algorithms out there for this sequence.

karg

wow, no wonder it wasn't working! I also tried a non-recursive version and that works fine. I had no idea it used up so much stack space, but it does make sense.


My stack is 100 KB. I was trying to use fib(5000), so that would definately take up too much space to work.

Thanks for the help

Share this post


Link to post
Share on other sites
i just figured out the more awsome way to implement a stack
(what CPU's and the JVM's do i think) should think about this one too:

one large block on contiguous memory
for simplifications sake, we shall have a VM with only integer
stack space.


vector<int> theStack;
DWORD stackPointer; //keeps the _INDEX_ of where we are in the stack


void VM::Call()
{
MOV(theStack[stackPointer++], FunctionsLocalVar1);
MOV(theStack[stackPointer++], FunctionsLocalVar2);
}

void VM::RET()
{
stackPointer -= LastFunction.StackPushCount;
}



see what im getting at here?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this