假堆栈比真实堆栈快吗
我正在做一些递归解析。
目前我有一个假堆栈，我在其中存储有限状态机的状态，因此当我递归地向下钻取时，我会推送我所处的状态，并在处理完递归文本位后弹出它。
拥有一个像这样的“状态 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）。
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).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这取决于实施——没有办法提前说清楚。
在函数调用成本较低的机器上（例如 SPARC），函数
堆栈可能会更快，但即使如此，也存在本地化等问题
干预。 （机器堆栈占用更多空间，因为它堆叠更多
信息，而不是你的模拟堆栈。）我会把它分成
正确的递归函数，并且只有在这种情况下才尝试手动堆栈管理
事实证明是一个瓶颈。除非...手动堆栈管理确实有
一个重要的优点是：错误处理。机器堆栈溢出是
未定义的行为：如果
malloc或realloc返回空指针，则至少可以干净地报告错误。
如果你确实模拟堆栈，你应该考虑使用 std::vector ，
而不是
malloc/realloc/free。如果有的话它会拯救你例外，而且它也可能会快一点。如果可以的话
设置堆栈大小的上限，并且它不是不合理的大，
将堆栈声明为堆栈上的 C 样式数组将是偶数
快点。
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
mallocorreallocreturn a null pointer, youcan 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 anexception, 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.