伪造的堆栈比真正的堆栈更快

Question

我正在做一些递归解析.

目前我有一个假堆栈,我在那里为我的有限状态机存储状态,所以当我递归地向下钻取时我按下我所处的状态,并在我完成处理递归的文本后稍后弹出它.

拥有'state id'堆栈会更快吗？

 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));
 }

或者将事物拆分成适当的函数并让C++担心堆栈会更快.

(我知道有人会告诉我'那是C,它不是c ++',所以我先发制人地回答,我的程序是c ++但其中有很多c).

Answer 1

这取决于实施 - 没有办法提前说.在函数调用便宜的机器上(例如SPARC),函数堆栈可能会更快,但即便如此,本地化等问题也会介入.(机器堆栈需要更多空间,因为它比模拟堆栈堆积更多信息.)我将事物拆分为适当的递归函数,并且只有在证明是瓶颈的情况下才尝试手动堆栈管理.除非......手动堆栈管理确实有一个重要优势:错误处理.机器堆栈溢出是未定义的行为:如果malloc或realloc返回空指针,您至少可以干净地报告错误.

如果你模拟堆栈,你应该考虑使用std::vector,而不是malloc/ realloc/ free.如果存在异常,它将为您节省时间,并且它可能会更快一点.如果你可以设置堆栈大小的上限,并且它不是不合理的大,那么将堆栈声明为堆栈上的C样式数组会更快.