# Stack Implementation in my VM

This topic is 5267 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 on other sites
Quote:
 Original post by KargThe 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 on other sites
i just figured out the more awsome way to implement a stack

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 stackvoid VM::Call(){  MOV(theStack[stackPointer++], FunctionsLocalVar1);  MOV(theStack[stackPointer++], FunctionsLocalVar2);}void VM::RET(){  stackPointer -= LastFunction.StackPushCount;}

see what im getting at here?

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 15
• 14
• 46
• ### Forum Statistics

• Total Topics
634066
• Total Posts
3015315
×