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

Manifesto

I would personally expect the normal functions would be faster .. but someone who's thought a lot than me figured this fake stack thing is faster. Now I'd like to see more opinions from people who thing more than me :) – Manifesto

@matu It depends on the machine. On a Sparc, a function call requires zero memory accesses, and might be considerably faster. On an Intel, you end up saving you return address and the frame pointer in memory, plus any arguments the function requires: that can be very expensive. – Reidreidar

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.

Reidreidar

@SteveJessop Good point. If nothing else, its very name is an expression of intent (which in turn facilitates understanding the code). – Reidreidar

Thanks James. I did originally use vector and found it to be slightly slower. I think because it was reallocing a lot more; which I'm sure could probably be modified though. Thanks Steve. I'll look at std::stack. – Manifesto

@matu std::vector should be allocating less, given it's growth strategy. The exception might be if STACK_JUMP_SIZE is large, and you practically never exceed it. In this case, you might try using reserve(STACK_JUMP_SIZE) when you create the vector. – Reidreidar

When you say 'Solaris (OS)', do you actually mean 'SPARC (arch)'? Solaris runs on Intel machines too. It is SPARC's register windows that makes function calls cheap. – Dedifferentiation

@Dedifferentiation Yes. I should have said on a SPARC architecture, and not on Solaris (which isn't a machine, but an OS). – Reidreidar