Is a fake stack faster than a real stack

Question

I'm doing some recursive parsing.

Currently I have a fake stack, where I store states for my finite state machine, so as I drill down recursively I push the state I was in, and pop it later after I've finished processing the recursive bit of text.

Would it be faster to have a 'state id' stack like:

 int* stack = 0
 int top = 0;
 // ...
 // drill down bit
 if (stack == 0)
     stack = (int*)malloc(STACK_JUMP_SIZE);
 else if (top % STACK_JUMP_SIZE == 0)
     stack = (int*)realloc(stack, (top+STACK_JUMP_SIZE) * sizeof(int));
 stack[top++] = currentState;
 // ...
 // pop up later
 {currentState = stack[--top]; {
 if (top == 0) {
     free(stack);
     stack = 0;
 } else if ((top+1) % STACK_JUMP_SIZE == 0) {
     stack = (int*)realloc(stack, (top+1)*sizeof(int));
 }

Or would it be faster to split the thing up into proper functions and let C++ worry about the stack.

(I know someone's gonna tell me 'that's C, it's not c++', so I pre-emptively answer, my program's c++ but has a lot of c in it).

Answer 1

It depends on the implementation—there's no way to say in advance. On a machine where function calls are cheap (e.g. SPARC), the function stack would probably be faster, but even there, issues like localisation intervene. (The machine stack takes more room, because it stacks more information, than your simulated stack.) I'd split the thing up into proper recursive functions, and only try manual stack management if this proves to be a bottleneck. Unless... Manual stack management does have one important advantage: error handling. Machine stack overflow is undefined behavior: if malloc or realloc return a null pointer, you can at least report the error cleanly.

If you do simulate the stack, you should consider using std::vector, and not malloc/realloc/free. It will save you if there is an exception, and it is also likely to be a little bit faster. If you can set an upper limit to the stack size, and it's not unreasonably big, declaring the stack as a C style array on the stack would be even faster.