c - 堆栈问题: Local variables vs Arithmetics

Question

我有一个关于保存算术计算以限制堆栈使用是否有益的问题。

假设我有一个像这样的递归函数:

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

这种方法限制了很多实际所需的数学运算，但在每次调用时，它都必须获取数组中的单元格，而不是从寄存器中读取它。

我正在尝试尽可能多地进行基准测试以找到最佳解决方案，但如果有最佳实践或我在这里缺少的东西，请告诉我。

Answer 1

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 位模式)字节的堆栈。但是，嘿，这就是您为优化付出的代价!

我不太清楚您最关心的是运行时还是堆栈使用。无论哪种方式，消息都是将其留给编译器，当且仅当事情太慢时才担心，然后只担心分析显示的问题!