为什么向函数中添加一个整数不会将递归堆栈深度减半

Question

Edit1: 根据一些评论的建议，我打印了变量的地址。

Edit2: 根据一些评论的建议，我添加了一些操作，以便编译器不能简单地丢弃我的变量

Edit3: 根据一个答案的建议，我修改了变量的打印方式。

Edit4: 加了不少废话让gcc过不去

Edit5: 添加片段三来测试@4386427 的理论——结果看起来支持他的想法，即编译器可能默认保留 32 字节。因此，我们可能需要定义至少 5 个变量才能看到差异。

我对栈内存和堆内存有一些基本的了解。以C为例，如果我在函数中定义一个局部变量，它占用栈内存；如果我定义一个指针并为其分配几个内存块，这些内存块占用堆内存。如果一个函数递归调用自己，栈就会满，就会发生溢出。所以我做了一个简单的测试，片段一和片段二之间的唯一区别是片段二多定义了一个整数：

片段一：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int function(int depth) {
  int tmp = rand() % 65536;
  tmp = tmp - 1;
  printf("val: %d; addr: %p; depth: %d\n", tmp, (void*)&tmp, depth);
  tmp = function(++depth) + 1;
  return tmp;
}
int main() {
  srand(time(NULL));
  int res = function(0);
  printf("%d\n", res);
  return 0;
}

输出一个：

...
val: 57227; addr: 0x7fff00dff78c; depth: 174626
val: 8288; addr: 0x7fff00dff75c; depth: 174627
val: 24194; addr: 0x7fff00dff72c; depth: 174628
Segmentation fault

片段二：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int function(int depth) {
  int tmp0 = rand() % 65536;
  int tmp1 = rand() % 65536;
  tmp0 = tmp0 - 1;
  printf("val: %d, %d; addr: %p, %p; depth: %d\n", tmp0, tmp1, (void*)&tmp0, (void*)&tmp1, depth);
  tmp1 = function(++depth);
  return tmp1 - tmp0;
}
int main() {
  srand(time(NULL));
  int res = function(0);
  printf("%d\n", res);
  return 0;
}

输出二：

...
val: 40745, 32446; addr: 0x7ffcb80b079c, 0x7ffcb80b0798; depth: 174528
val: 34014, 57470; addr: 0x7ffcb80b076c, 0x7ffcb80b0768; depth: 174529
val: 56801, 34478; addr: 0x7ffcb80b073c, 0x7ffcb80b0738; depth: 174530
Segmentation fault

我使用 gcc 编译了这两个代码，正如预期的那样，它们都会导致堆栈溢出。然而，我最初的预期是，鉴于代码片段二中的函数使用 2 倍内存，代码片段二的深度会浅得多。然而，虽然片段二早一点出现段错误，但两个堆栈的深度实际上非常接近...

如果一切都按照我天真的理论进行，代码片段一中的函数调用自身174,616次，需要占用4 Bytes * 174,616 / 1,024 = 682 KBytes； snippet 2中的函数调用自身174,539次，需要占用(4 + 4) Bytes * 174,539 = 1,363 KBytes.

为什么会这样？

片段三

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int function(int depth) {
  int tmp0 = rand() % 65536;
  int tmp1 = rand() % 65536;
  int tmp2 = rand() % 65536;
  int tmp3 = rand() % 65536;
  int tmp4 = rand() % 65536;
  int tmp5 = rand() % 65536;
  tmp0 = tmp0 - 1;
  tmp1 = tmp1 + 1;
  tmp2 = tmp2 - 2;
  tmp3 = tmp3 + 2;
  tmp4 = tmp4 - 3;
  tmp5 = tmp5 + 3;
  printf("val: %d, %d, %d; addr: %p, %p, %p; depth: %d\n", tmp0, tmp1, tmp2, (void*)&tmp0, (void*)&tmp1, (void*)&tmp2, depth);
  tmp1 = function(++depth);
  return tmp0 - tmp1 + tmp2 - tmp3 + tmp4;
}
int main() {
  srand(time(NULL));
  long res = function(0);
  printf("%d\n", res);
  return 0;
}

输出三个

val: 9366, 56113, 48970; addr: 0x7fff063fe830, 0x7fff063fe82c, 0x7fff063fe828; depth: 130920
val: 11924, 11633, 26004; addr: 0x7fff063fe7f0, 0x7fff063fe7ec, 0x7fff063fe7e8; depth: 130921
val: 13316, 42397, 45027; addr: 0x7fff063fe7b0, 0x7fff063fe7ac, 0x7fff063fe7a8; depth: 130922
val: 4285, 58053, 21693; addr: 0x7fff063fe770, 0x7fff063fe76c, 0x7fff063fe768; depth: 130923
Segmentation fault

Answer 1

So why is it like this?

好吧，你所描述的原则上是正确的，但是......你忘记了编译器优化。只要不改变程序的可观察行为，编译器就可以进行各种优化。

例如，编译器可以决定将所有 tmp 变量保存在 cpu 寄存器中。在那种情况下，不会为它们分配堆栈内存。

您可以尝试通过打印他们的地址来强制他们记忆：

printf("%p\n", (void*)&tmp);

另一件可能发生的事情是，编译器为两个函数更改了相同数量的堆栈指针。在我的系统上，编译器在两种情况下都保留 32 个字节。在编译器将其更改为 48 之前，我不得不使用 5 tmp 个变量。换句话说 - 不要指望该函数保留它所需要的。允许保留更多。在我的系统上，它似乎总是将堆栈指针更改 N x 16。

为了更好地理解，您需要查看生成的机器代码。为此，您可以使用 gcc -S

你也可以查看这个https://godbolt.org/z/x5c3bj7M9

两个函数都以：

开头

    push    rbp
    mov     rbp, rsp
    sub     rsp, 32   <------ Stack pointer change, i.e. reserving memory
    mov     DWORD PTR [rbp-20], edi

所以他们对两个调用使用相同数量的堆栈。

使用 -O2 编译的相同代码给出完全不同的结果 https://godbolt.org/z/f6jMEqaPd

第一个函数给出：

    push    rbx
    mov     ebx, edi
    sub     rsp, 48   <------ Stack pointer change, i.e. reserving memory

但第二个给出：

    push    rbx
    mov     ebx, edi
    sub     rsp, 16   <------ Stack pointer change, i.e. reserving memory

结论是：你不能只看 C 代码就知道会发生什么。您需要机器码。

Answer 2

请记住，局部变量并不是唯一存储在堆栈中的东西。还有参数和调用函数的 return 地址。因此，您更有可能看到至少 16 字节与 20 字节的差异，而不是 4 与 8 的差异。

如果您仔细查看每次迭代之间打印的地址，您会发现它们在两种情况下都相差 48 个字节，因此堆栈帧大约在同一时间达到顶峰是有意义的。

所以编译器似乎也插入了一些填充，在后一种情况下最终被额外变量占用。

Answer 3

另一个较小的实验：

#include <stdio.h>
void function(int depth) {
  if (depth==0) return;
  int tmp = 65536;
  printf("%p\n",&tmp);
  function(--depth);
}
void function2(int depth) {
  if (depth==0) return;
  int tmp = 65536;
  int tmp2 = 65536;
  printf("%p %p\n",&tmp,&tmp2);
  function2(--depth);
}
int main() {
  function(2);
  function2(2);
  return 0;
}

可以产生以下结果：

0x7ffee80f0988
0x7ffee80f0968
0x7ffee80f0988 0x7ffee80f0984
0x7ffee80f0968 0x7ffee80f0964

其中可以观察到两个局部变量在其自身调用中的距离对于两个函数是相同的。这可能意味着在这些情况下，堆栈分配的大小是恒定的，并且两者的大小相同。如果您在第二种情况 (4/5) 中添加更多局部变量，那将会发生变化。堆栈帧可能以四舍五入到某个值的大小分配。

为什么向函数中添加一个整数不会将递归堆栈深度减半

Why adding one integer to a function does not cut recursion stack depth in half

c

pointers

stack-memory