我有一个关于保存算术计算以限制堆栈使用是否有益的问题。
假设我有一个像这样的递归函数:
void foo (unsigned char x, unsigned char z) {
if (!x || !z)
return;
// Do something
for (unsigned char i = 0; i < 100; ++i) {
foo(x - 1, z);
foo(x, z - 1);
}
}
这里主要看到的是每次在循环中计算的 x - 1
和 z - 1
。
为了提高性能,我会这样做:
const unsigned char minus_x = x - 1;
const unsigned char minus_z = z - 1;
for (unsigned char i = 0; i < 100; ++i) {
foo(minus_x, z);
foo(x, minus_z);
}
但是这样做意味着每次调用时,minus_x
和 minus_z
都会保存在堆栈中。递归函数可能被调用数千次,这意味着堆栈中使用了数千个字节。此外,涉及的数学并不像 -1
那么简单。
这是个好主意吗?
编辑:它实际上是无用的,因为它是编译器的一个非常标准的优化:Loop-invariant code motion (参见 HansPassant 的评论)
使用包含如下计算的静态数组是否是一个更好的主意:
static const char minuses[256] = {/* 0 for x = 0; x - 1 for x = 1 to 255 */}
然后执行:
foo(minuses[x], z);
foo(x, minuses[z]);
这种方法限制了很多实际所需的数学运算,但在每次调用时,它都必须获取数组中的单元格,而不是从寄存器中读取它。
我正在尝试尽可能多地进行基准测试以找到最佳解决方案,但如果有最佳实践或我在这里缺少的东西,请告诉我。
最佳答案
FWIW,我用 gcc 尝试了两个函数 foo_1()
(没有额外的变量)和 foo_2()
(额外变量)。
使用 -03 gcc 展开 for 循环 (!),这两个函数的大小完全相同,但代码不完全相同。我很遗憾没有时间弄清楚它们有何不同以及为何不同。
使用 -02 gcc 生成与 foo_1
完全相同的代码和foo_2
。正如人们所预料的那样,它分配了一个寄存器给 x
, z
, x-1
, z-1
和i
,并压入/弹出这些值以保留父级的值——每次调用使用 6 x 8(64 位机器)字节的堆栈(包括返回地址)。
您报告使用了 24 个字节的堆栈...这是 32 位机器吗?
使用 -O0 时,情况有所不同,foo_1
做了x-1
和z-1
每次循环时,在这两种情况下变量都保存在内存中。 foo_1
稍微短一些,我怀疑减法在现代处理器上没有什么区别!在这种情况下,foo_1
和foo_2
使用相同数量的堆栈。这是因为 foo
中的所有变量是 unsigned char
,以及额外的minus_x
和minus_z
与 i
打包在一起,使用其他方式填充的空间。如果你改变minus_x
和minus_z
至unsigned long long
,你会得到差异。奇怪的是,foo_1
还使用了 6 x 8 字节的堆栈。堆栈帧中有 16 个未使用的字节,因此即使考虑到将 RSP 和 RBP 对齐到 16 字节边界,它似乎使用了超出需要的字节...我不知道为什么。
我快速浏览了一个静态数组 x - 1
。对于-O0,它对堆栈使用没有影响(原因与之前相同)。对于-O2,它看了一下foo(x, minuses[z]);
并悬挂minuses[z]
跳出循环 !这是应该预料到的......并且堆栈使用保持不变(6 x 8)。
更一般地说,正如其他地方所指出的,任何有效的优化量都会尽可能地将计算从循环中提升出来。正在发生的另一件事是大量使用寄存器来保存变量——真实变量(您已命名的变量)和“伪”变量(用于保存提升内容的预先计算结果)。这些寄存器需要在子例程调用之间保存——无论是由调用者还是被调用者。 x86 压入/弹出操作在整个寄存器上,因此寄存器中保存的无符号字符将需要完整的 8 或 4(64 位或 32 位模式)字节的堆栈。但是,嘿,这就是您为优化付出的代价!
我不太清楚您最关心的是运行时还是堆栈使用。无论哪种方式,消息都是将其留给编译器,当且仅当事情太慢时才担心,然后只担心分析显示的问题!
关于c - 堆栈问题: Local variables vs Arithmetics,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25032858/