使用callstack在C中实现堆栈数据结构？
Using the callstack to implement a stack data structure in C?
我对 C 下的内存结构的理解是程序的内存被堆栈和堆分开，每个内存从块的两端增长，可以想象分配所有 ram 但显然抽象为某种 OS内存碎片管理器。
为处理局部变量（自动存储）而设计的堆栈和为内存分配（动态存储）而设计的堆。
（编者注：有些 C 实现的自动存储不使用 "call stack"，但这个问题假设一个普通的现代 C 实现在一个普通的 CPU 上，本地人确实使用调用堆栈如果他们不能只住在寄存器中。）
假设我想为一些数据解析算法实现一个堆栈数据结构。它的生命周期和范围仅限于一个函数。
我可以想到 3 种方法来做这样的事情，但在我看来，其中 none 是给定场景的最干净的方法。
我的第一个想法是在堆中构造一个堆栈，就像 C++ std::vector:
Some algorithm(Some data)
{
Label *stack = new_stack(stack_size_estimate(data));
Iterator i = some_iterator(data);
while(i)
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
push_stack(stack,label);
}
else if(label_type_b(label))
{
some_process(&data,label,pop_stack(stack));
}
i = some_iterator_next(i);
}
some_stack_cleanup(&data,stack);
delete_stack(stack);
return data;
}
这个方法没问题，但它很浪费，因为堆栈大小是一个猜测，并且在任何时候 push_stack 都可能调用一些内部 malloc 或 realloc 并导致不规则的减速。 None 其中是此算法的问题，但此构造似乎更适合必须跨多个上下文维护堆栈的应用程序。这里不是这种情况；堆栈是这个函数私有的，在退出前被删除，就像自动存储一样 class.
我的下一个想法是递归。因为递归使用内置堆栈，所以这似乎更接近我想要的。
Some algorithm(Some data)
{
Iterator i = some_iterator(data);
return some_extra(algorithm_helper(extra_from_some(data),&i);
}
Extra algorithm_helper(Extra thing, Iterator* i)
{
if(!*i)
{return thing;}
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
*i = some_iterator_next(*i);
return algorithm_helper
( extra_process( algorithm_helper(thing,i), label), i );
}
else if(label_type_b(label))
{
*i = some_iterator_next(*i);
return extra_attach(thing,label);
}
}
}
这种方法让我不用编写和维护堆栈。对我来说，代码似乎更难遵循，但对我来说并不重要。
我的主要问题是使用方式更多 space。
堆栈帧保存此 Extra 构造的副本（它基本上包含 Some data 加上要保存在堆栈中的实际位）和每个帧中完全相同的迭代器指针的不必要副本：因为它是"safer" 然后引用一些静态全局变量（我不知道如何不这样做）。如果编译器做了一些聪明的尾递归之类的事情，这将不是问题，但我不知道我是否喜欢交叉手指并希望我的编译器很棒。
我能想到的第三种方法涉及某种可以在堆栈上增长的动态数组，这是使用某种我不知道的 C 语言编写的最后一件事。
或者一个 extern asm 块。
考虑到这一点，这就是我正在寻找的，但我没有看到我自己编写一个 asm 版本，除非它非常简单，而且我没有看到它更容易编写或维护，尽管它看起来更简单我的头。显然它不能跨 ISA 移植。
我不知道我是否忽略了某些功能，或者我是否需要寻找另一种语言，或者我是否应该重新考虑我的人生选择。一切都可能是真的...我希望这只是第一个。
我不反对使用某些库。有没有，如果有，它是如何工作的？我在搜索中没有找到任何内容。
我最近了解了可变长度数组，但我真的不明白为什么不能将它们用作增加堆栈引用的一种方式，而且我也无法想象它们会以这种方式工作。
不是一个真正的答案，但对于单纯的评论来说有点太长了。
事实上，堆栈和堆以及相互增长的形象过于简单化了。 8086 处理器系列（至少在某些内存模型中）曾经是这样，其中堆栈和堆共享一个内存段，但即使是旧的 Windows 3.1 系统也带有一些 API允许在堆外分配内存的函数（搜索与 LocalAlloc 相反的 GlobalAlloc），前提是处理器至少是 80286.
但是现代系统都使用虚拟内存。有了虚拟内存，就不再有堆和栈共享的漂亮的连续段，OS 可以随心所欲地提供内存（当然前提是它可以在某处找到空闲内存）。但是堆栈仍然必须是一个连续的段。因此，该段的大小在构建时确定并且是固定的，而堆的大小仅受系统可以分配给进程的最大内存的限制。这就是为什么许多人建议仅将堆栈用于小型数据结构并始终分配大型数据结构的原因。此外，我不知道让程序知道其堆栈大小的可移植方式，更不用说它的空闲堆栈大小了。
所以恕我直言，这里重要的是想知道你的堆栈大小是否足够小。如果它可以超过一个小的限制，就去分配内存，因为它会更容易也更健壮。因为您可以（并且应该）测试分配错误，但堆栈溢出总是致命的。
最后，我的建议是不要尝试将 system 堆栈用于您自己的专用用途，即使仅限于一个功能，除非您可以干净利落地要求一个堆栈中的内存数组，并在其上构建您自己的堆栈管理。使用汇编语言直接使用底层堆栈会增加很多复杂性（更不用说失去可移植性）以获得假设的最小收益。只是不要。即使您想使用汇编语言指令对堆栈进行低级优化，我的建议是使用专用内存段并将系统堆栈留给编译器。
我的经验表明，代码越复杂，维护起来就越困难，健壮性就越差。
因此，请遵循最佳实践，仅在无法避免的情况下使用低级优化。
tl;博士：使用 std::vector 或等价物。
（已编辑）
关于您的开场白：分段的时代结束了。现在进程有多个堆栈（每个线程一个），但都共享一个堆。
关于选项 1：与其编写和维护堆栈并猜测其大小，您应该直接使用 std::vector 或围绕它的 C 包装器，或者它的 C 克隆 - 在任何情况下，使用 'vector' 数据结构。
Vector's algorithm is generally quite efficient。不完美，但通常对许多现实世界的用例都有好处。
关于选项 2：你是对的，至少只要讨论仅限于 C。在 C 中，递归既浪费又不可扩展。在其他一些语言中，特别是在函数式语言中，递归是表达这些算法的方式，尾调用优化是语言定义的一部分。
关于选项 3：最接近您正在寻找的 C 东西是 alloca()。它允许你增长堆栈帧，如果堆栈没有足够的内存，OS 将分配它。然而，围绕它构建堆栈对象将非常困难，因为没有 realloca()，正如@Peter Cordes 所指出的那样。
另一个缺点是堆栈仍然有限。在 Linux，堆栈通常限制为 8 MB。这是与递归相同的可扩展性限制。
关于可变长度数组：VLA 基本上是语法糖，一种方便的表示法。除了语法之外，它们具有与数组完全相同的功能（实际上，甚至更少，即 sizeof() 不起作用），更不用说 std::vector.
的动态能力了
在实践中，如果您不能为小于 1kiB 左右的可能大小设置硬性上限，您通常应该动态分配。如果您可以确定尺寸很小，您可以考虑使用 alloca 作为堆栈的容器。
（您不能有条件地使用 VLA，它必须在范围内。尽管您可以通过在 if() 之后声明它来使其大小为零，并将指针变量设置为 VLA地址，或 malloc。但 alloca 会更容易。）
在 C++ 中，您通常会 std::vector，但它很愚蠢，因为它不能/不使用 realloc (Does std::vector *have* to move objects when growing capacity? Or, can allocators "reallocate"?)。所以在 C++ 中，它是更有效的增长与重新发明轮子之间的权衡，尽管它仍然是 O(1) 时间的摊销。您可以预先使用相当大的 reserve() 来缓解大部分问题，因为您分配但从未接触过的内存通常不会花费任何费用。
在C 中你无论如何都要自己编写堆栈，并且realloc 是可用的。 （而且所有 C 类型都可以轻松复制，因此没有什么可以阻止您使用 realloc）。因此，当您确实需要增长时，您可以重新分配存储空间。但是，如果您不能在函数入口上设置一个合理且绝对足够大的上限并且可能需要增长，那么您仍然应该分别跟踪容量与使用中的大小，例如 std::vector。不要在每个 push/pop.
上调用 realloc
直接使用调用堆栈作为堆栈数据结构在纯汇编语言中很容易（对于使用调用堆栈的 ISA 和 ABI，即"normal" CPU 如 x86、ARM、MIPS 等）。 是的，在 asm 中值得为您 知道的 堆栈数据结构做的事情将非常小，不值得开销malloc / free.
使用 asm push 或 pop 指令（或没有单指令推送/弹出的 ISA 的等效序列）。您甚至可以通过与保存的堆栈指针值进行比较来检查大小/查看堆栈数据结构是否为空。 （或者只是在 push/pop 旁边维护一个整数计数器）。
一个非常简单的例子是一些人编写 int->string 函数的低效方式。对于像 10 这样的非 2 次幂基数，您可以通过除以 10 来生成最低有效的一阶数字，一次删除一个数字，其中数字 = 余数。您可以只存储到缓冲区中并递减指针，但是有些人编写函数 push 在 divide 循环中，然后在第二个循环中编写 pop 以使它们按打印顺序排列（最重要的优先） .例如Ira 在 How do I print an integer in Assembly Level Programming without printf from the c library? 上的回答（我对同一个问题的回答显示了一种有效的方法，一旦你理解了它也更简单。）
栈向堆增长并不特别重要，只是有一些space你可以使用。而且那个栈内存已经被映射了，并且通常在缓存中很热。这就是我们可能想要使用它的原因。
例如，Stack above heap 恰好在 GNU/Linux 下为真，这通常将主线程的 user-space 堆栈放在 user-space 虚拟地址 [= 的顶部附近216=]。 （例如 0x7fff...）通常有一个堆栈增长限制远小于从堆栈到堆的距离。您希望意外的无限递归尽早出现故障，例如在消耗 8MiB 的堆栈 space 之后，而不是驱动系统进行交换，因为它使用了千兆字节的堆栈。根据 OS，您可以增加堆栈限制，例如ulimit -s。并且线程堆栈通常分配 mmap，与其他动态分配相同，因此无法说明它们相对于其他动态分配的位置。
据我所知，即使使用内联 asm，C 也不可能
（无论如何都不安全。下面的示例显示了您必须像在 asm 中那样在 C 中编写它是多么邪恶。它基本上证明了现代 C 不是一种可移植的汇编语言。）
您不能只将 push 和 pop 包装在 GNU C 内联 asm 语句中，因为没有办法告诉编译器您正在修改堆栈指针。在您的内联 asm 语句更改它之后，它可能会尝试引用与堆栈指针相关的其他局部变量。
如果您知道您可以安全地强制编译器为该函数创建一个帧指针（它将用于所有局部变量访问），那么您可能无需修改堆栈指针。但是如果你想进行函数调用，许多现代 ABI 要求堆栈指针在调用之前过度对齐。例如x86-64 System V 要求在 call 之前进行 16 字节堆栈对齐，但 push/pop 以 8 字节为单位工作。 OTOH，32 位 ARM（和一些 32 位 x86 调用约定，例如 Windows）没有该功能，因此任何数量的 4 字节推送都会使堆栈正确对齐以进行函数调用。
不过我不推荐它；如果你想要那个级别的优化（并且你知道如何为目标优化 asm CPU），用 asm 编写你的整个函数可能更安全。
Variable Length Arrays and I don't really understand why they couldn't be leveraged as a way to grow stack reference
VLA 不可调整大小。 在您执行 int VLA[n]; 之后，您将无法调整大小。您在 C 中所做的任何事情都不能保证您有更多与该数组连续的内存。
alloca(size) 也有同样的问题。这是一个特殊的编译器内置函数（在 "normal" 实现上）将堆栈指针递减 size 字节（四舍五入为堆栈宽度的倍数）和 returns 该指针。 在实践中，您可以进行多次 alloca 调用，它们很可能是连续的，但对此的保证为零，因此如果没有 UB，您将无法安全地使用它。不过，您 可能 在某些实现上逃避此问题，至少目前如此，直到未来的优化注意到 UB 并假设您的代码无法访问。
（它可能会破坏某些调用约定，例如 x86-64 System V，其中 VLA 保证为 16 字节对齐。8 字节 alloca 可能会向上取整为 16。）
但是如果你确实想让这个工作，你可能会使用 long *base_of_stack = alloca(sizeof(long));（最高地址：堆栈在大多数但不是所有的 ISA/ABI 上向下增长 - 这是您必须做出的另一个假设）。
另一个问题是，除了离开函数作用域之外，没有办法释放 alloca 内存。所以你的 pop 必须增加一些 top_of_stack C 指针变量，而不是实际移动真正的架构 "stack pointer" 寄存器。 push 将不得不查看 top_of_stack 是高于还是低于您也单独维护的高水位线。如果是这样，你 alloca 多一些内存。
那时候你可能 alloca 块大于 sizeof(long) 所以正常情况是你不需要分配更多内存，只需将 C 变量移到顶部-堆栈指针。例如也许是 128 字节的块。这也解决了一些 ABI 保持堆栈指针过度对齐的问题。它让堆栈元素比 push/pop 宽度更窄，而不会在填充上浪费 space。
这确实意味着我们最终需要更多的寄存器来复制架构堆栈指针（除了 SP 永远不会在弹出时增加）。
请注意，这类似于 std::vector 的 push_back 逻辑，其中您有分配大小和使用中大小。 区别在于std::vector 总是在需要更多 space 时复制（因为实现甚至无法尝试 realloc）所以它必须通过指数增长来摊销。当我们通过移动堆栈指针知道增长是 O(1) 时，我们可以使用固定增量。像 128 字节，或者半页可能更有意义。我们不会立即触及分配底部的内存；我还没有尝试为需要堆栈探测的目标编译它，以确保您不会在不触及中间页面的情况下将 RSP 移动超过 1 页。 MSVC 可能会为此插入堆栈探测。
在调用堆栈上破解了 alloca 堆栈：在实践中充满了 UB 和错误编译 gcc/clang
这主要是为了表明它是多么邪恶，C 不是一种可移植的汇编语言。有些东西你可以在 asm 中做你在 C 中做不到的事情。（还包括从一个函数有效地返回多个值，在不同的寄存器中，而不是一个愚蠢的结构。）
#include <alloca.h>
#include <stdlib.h>
void some_func(char);
// assumptions:
// stack grows down
// alloca is contiguous
// all the UB manages to work like portable assembly language.
// input assumptions: no mismatched { and }
// made up useless algorithm: if('}') total += distance to matching '{'
size_t brace_distance(const char *data)
{
size_t total_distance = 0;
volatile unsigned hidden_from_optimizer = 1;
void *stack_base = alloca(hidden_from_optimizer); // highest address. top == this means empty
// alloca(1) would probably be optimized to just another local var, not necessarily at the bottom of the stack frame. Like char foo[1]
static const int growth_chunk = 128;
size_t *stack_top = stack_base;
size_t *high_water = alloca(growth_chunk);
for (size_t pos = 0; data[pos] != '[=10=]' ; pos++) {
some_func(data[pos]);
if (data[pos] == '{') {
//push_stack(stack, pos);
stack_top--;
if (stack_top < high_water) // UB: optimized away by clang; never allocs more space
high_water = alloca(growth_chunk);
// assert(high_water < stack_top && "stack growth happened somewhere else");
*stack_top = pos;
}
else if(data[pos] == '}')
{
//total_distance += pop_stack(stack);
size_t popped = *stack_top;
stack_top++;
total_distance += pos - popped;
// assert(stack_top <= stack_base)
}
}
return total_distance;
}
令人惊讶的是，这似乎实际上编译成看起来正确的 asm (on Godbolt)，gcc -O1 用于 x86-64（但不是更高优化级别）。 clang -O1 和 gcc -O3 优化了 if(top<high_water) alloca(128) 指针比较，因此这在实践中不可用。
，似乎甚至强制转换为 uintptr_t 也不安全。或者 GCC 可能只是根据 high_water = alloca() 从未被取消引用的事实优化掉 alloca(128)。
https://godbolt.org/z/ZHULrK 显示 gcc -O3 输出，其中循环内没有 alloca。有趣的事实：使 volatile int growth_chunk 对优化器隐藏常量值使其不会被优化掉。所以我不确定是指针比较 UB 导致了这个问题，它更像是访问第一个 alloca 下面的内存，而不是取消引用从第二个 alloca 派生的指针，让编译器对其进行优化。
# gcc9.2 -O1 -Wall -Wextra
# note that -O1 doesn't include some loop and peephole optimizations, e.g. no xor-zeroing
# but it's still readable, not like -O1 spilling every var to the stack between statements.
brace_distance:
push rbp
mov rbp, rsp # make a stack frame
push r15
push r14
push r13 # save some call-preserved regs for locals
push r12 # that will survive across the function call
push rbx
sub rsp, 24
mov r12, rdi
mov DWORD PTR [rbp-52], 1
mov eax, DWORD PTR [rbp-52]
mov eax, eax
add rax, 23
shr rax, 4
sal rax, 4 # some insane alloca rounding? Why not AND?
sub rsp, rax # alloca(1) moves the stack pointer, RSP, by whatever it rounded up to
lea r13, [rsp+15]
and r13, -16 # stack_base = 16-byte aligned pointer into that allocation.
sub rsp, 144 # alloca(128) reserves 144 bytes? Ok.
lea r14, [rsp+15]
and r14, -16 # and the actual C allocation rounds to %16
movzx edi, BYTE PTR [rdi] # data[0] check before first iteration
test dil, dil
je .L7 # if (empty string) goto return 0
mov ebx, 0 # pos = 0
mov r15d, 0 # total_distance = 0
jmp .L6
.L10:
lea rax, [r13-8] # tmp_top = top-1
cmp rax, r14
jnb .L4 # if(tmp_top < high_water)
sub rsp, 144
lea r14, [rsp+15]
and r14, -16 # high_water = alloca(128) if body
.L4:
mov QWORD PTR [r13-8], rbx # push(pos) - the actual store
mov r13, rax # top = tmp_top completes the --top
# yes this is clunky, hopefully with more optimization gcc would have just done
# sub r13, 8 and used [r13] instead of this RAX tmp
.L5:
add rbx, 1 # loop condition stuff
movzx edi, BYTE PTR [r12+rbx]
test dil, dil
je .L1
.L6: # top of loop body proper, with 8-bit DIL = the non-zero character
movsx edi, dil # unofficial part of the calling convention: sign-extend narrow args
call some_func # some_func(data[pos]
movzx eax, BYTE PTR [r12+rbx] # load data[pos]
cmp al, 123 # compare against braces
je .L10
cmp al, 125
jne .L5 # goto loop condition check if nothing special
# else: it was a '}'
mov rax, QWORD PTR [r13+0]
add r13, 8 # stack_top++ (8 bytes)
add r15, rbx # total += pos
sub r15, rax # total -= popped value
jmp .L5 # goto loop condition.
.L7:
mov r15d, 0
.L1:
mov rax, r15 # return total_distance
lea rsp, [rbp-40] # restore stack pointer to point at saved regs
pop rbx # standard epilogue
pop r12
pop r13
pop r14
pop r15
pop rbp
ret
这就像您为动态分配的堆栈数据结构所做的，除了：
- 它像调用栈一样向下增长
- 我们从
alloca 而不是 realloc 获得更多内存。 （realloc 如果在分配 之后有可用的虚拟地址space 也可以是高效的。 C++ 选择不为其分配器提供 realloc 接口，因此 std::vector 总是在需要更多内存时愚蠢地分配 + 副本。 （据我所知，没有针对 new 未被覆盖并使用私有重新分配的情况进行优化的实现）。
- 它完全不安全并且充满了 UB，并且在现代优化编译器的实践中失败了
- 页面永远不会返回到 OS：如果您使用大量堆栈 space，这些页面将无限期地保持脏状态。
如果您可以选择 绝对 足够大的尺寸，则可以使用该尺寸的 VLA。
我建议从顶部开始向下移动，以避免接触远低于调用堆栈当前使用区域的内存。这样，在不需要 "stack probes" 将堆栈增加超过 1 页的 OS 上，您可能会避免接触远低于堆栈指针的内存。因此，您在实践中最终使用的少量内存可能都在调用堆栈的已映射页面内，如果最近的一些更深层次的函数调用已经使用它们，甚至可能已经很热的缓存行。
如果您确实使用堆，则可以通过进行相当大的分配来最小化重新分配成本。除非空闲列表上有一个块，你可以通过较小的分配获得，一般来说，如果你从不接触你不需要的部分，过度分配的成本非常低，特别是如果你在做更多分配之前释放或收缩它。
即不要 memset 它做任何事情。如果您想要归零内存，请使用 calloc，它可以为您从 OS 中获取归零页面。
现代 OSes 使用惰性虚拟内存进行分配，因此您第一次接触页面时，它通常必须出现页面错误并实际连接到 HW 页表中。此外，物理内存页面必须清零以支持此虚拟页面。 （除非访问是读取，然后 Linux 会将写时复制映射到零的共享物理页面。）
你甚至从未接触过的虚拟页面在内核中的范围簿记数据结构中只是更大的尺寸。 （并且在 user-space malloc 分配器中）。这不会增加分配它、释放它或使用您接触的较早页面的成本。
我对 C 下的内存结构的理解是程序的内存被堆栈和堆分开，每个内存从块的两端增长，可以想象分配所有 ram 但显然抽象为某种 OS内存碎片管理器。
为处理局部变量（自动存储）而设计的堆栈和为内存分配（动态存储）而设计的堆。
（编者注：有些 C 实现的自动存储不使用 "call stack"，但这个问题假设一个普通的现代 C 实现在一个普通的 CPU 上，本地人确实使用调用堆栈如果他们不能只住在寄存器中。）
假设我想为一些数据解析算法实现一个堆栈数据结构。它的生命周期和范围仅限于一个函数。
我可以想到 3 种方法来做这样的事情，但在我看来，其中 none 是给定场景的最干净的方法。
我的第一个想法是在堆中构造一个堆栈，就像 C++ std::vector:
Some algorithm(Some data)
{
Label *stack = new_stack(stack_size_estimate(data));
Iterator i = some_iterator(data);
while(i)
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
push_stack(stack,label);
}
else if(label_type_b(label))
{
some_process(&data,label,pop_stack(stack));
}
i = some_iterator_next(i);
}
some_stack_cleanup(&data,stack);
delete_stack(stack);
return data;
}
这个方法没问题，但它很浪费，因为堆栈大小是一个猜测，并且在任何时候 push_stack 都可能调用一些内部 malloc 或 realloc 并导致不规则的减速。 None 其中是此算法的问题，但此构造似乎更适合必须跨多个上下文维护堆栈的应用程序。这里不是这种情况；堆栈是这个函数私有的，在退出前被删除，就像自动存储一样 class.
我的下一个想法是递归。因为递归使用内置堆栈，所以这似乎更接近我想要的。
Some algorithm(Some data)
{
Iterator i = some_iterator(data);
return some_extra(algorithm_helper(extra_from_some(data),&i);
}
Extra algorithm_helper(Extra thing, Iterator* i)
{
if(!*i)
{return thing;}
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
*i = some_iterator_next(*i);
return algorithm_helper
( extra_process( algorithm_helper(thing,i), label), i );
}
else if(label_type_b(label))
{
*i = some_iterator_next(*i);
return extra_attach(thing,label);
}
}
}
这种方法让我不用编写和维护堆栈。对我来说，代码似乎更难遵循，但对我来说并不重要。
我的主要问题是使用方式更多 space。
堆栈帧保存此 Extra 构造的副本（它基本上包含 Some data 加上要保存在堆栈中的实际位）和每个帧中完全相同的迭代器指针的不必要副本：因为它是"safer" 然后引用一些静态全局变量（我不知道如何不这样做）。如果编译器做了一些聪明的尾递归之类的事情，这将不是问题，但我不知道我是否喜欢交叉手指并希望我的编译器很棒。
我能想到的第三种方法涉及某种可以在堆栈上增长的动态数组，这是使用某种我不知道的 C 语言编写的最后一件事。
或者一个 extern asm 块。
考虑到这一点，这就是我正在寻找的，但我没有看到我自己编写一个 asm 版本，除非它非常简单，而且我没有看到它更容易编写或维护，尽管它看起来更简单我的头。显然它不能跨 ISA 移植。
我不知道我是否忽略了某些功能，或者我是否需要寻找另一种语言，或者我是否应该重新考虑我的人生选择。一切都可能是真的...我希望这只是第一个。
我不反对使用某些库。有没有，如果有，它是如何工作的？我在搜索中没有找到任何内容。
我最近了解了可变长度数组，但我真的不明白为什么不能将它们用作增加堆栈引用的一种方式，而且我也无法想象它们会以这种方式工作。
不是一个真正的答案，但对于单纯的评论来说有点太长了。
事实上，堆栈和堆以及相互增长的形象过于简单化了。 8086 处理器系列（至少在某些内存模型中）曾经是这样，其中堆栈和堆共享一个内存段，但即使是旧的 Windows 3.1 系统也带有一些 API允许在堆外分配内存的函数（搜索与 LocalAlloc 相反的 GlobalAlloc），前提是处理器至少是 80286.
但是现代系统都使用虚拟内存。有了虚拟内存，就不再有堆和栈共享的漂亮的连续段，OS 可以随心所欲地提供内存（当然前提是它可以在某处找到空闲内存）。但是堆栈仍然必须是一个连续的段。因此，该段的大小在构建时确定并且是固定的，而堆的大小仅受系统可以分配给进程的最大内存的限制。这就是为什么许多人建议仅将堆栈用于小型数据结构并始终分配大型数据结构的原因。此外，我不知道让程序知道其堆栈大小的可移植方式，更不用说它的空闲堆栈大小了。
所以恕我直言，这里重要的是想知道你的堆栈大小是否足够小。如果它可以超过一个小的限制，就去分配内存，因为它会更容易也更健壮。因为您可以（并且应该）测试分配错误，但堆栈溢出总是致命的。
最后，我的建议是不要尝试将 system 堆栈用于您自己的专用用途，即使仅限于一个功能，除非您可以干净利落地要求一个堆栈中的内存数组，并在其上构建您自己的堆栈管理。使用汇编语言直接使用底层堆栈会增加很多复杂性（更不用说失去可移植性）以获得假设的最小收益。只是不要。即使您想使用汇编语言指令对堆栈进行低级优化，我的建议是使用专用内存段并将系统堆栈留给编译器。
我的经验表明，代码越复杂，维护起来就越困难，健壮性就越差。
因此，请遵循最佳实践，仅在无法避免的情况下使用低级优化。
tl;博士：使用 std::vector 或等价物。
（已编辑）
关于您的开场白：分段的时代结束了。现在进程有多个堆栈（每个线程一个），但都共享一个堆。
关于选项 1：与其编写和维护堆栈并猜测其大小，您应该直接使用 std::vector 或围绕它的 C 包装器，或者它的 C 克隆 - 在任何情况下，使用 'vector' 数据结构。
Vector's algorithm is generally quite efficient。不完美，但通常对许多现实世界的用例都有好处。
关于选项 2：你是对的，至少只要讨论仅限于 C。在 C 中，递归既浪费又不可扩展。在其他一些语言中，特别是在函数式语言中，递归是表达这些算法的方式，尾调用优化是语言定义的一部分。
关于选项 3：最接近您正在寻找的 C 东西是 alloca()。它允许你增长堆栈帧，如果堆栈没有足够的内存，OS 将分配它。然而，围绕它构建堆栈对象将非常困难，因为没有 realloca()，正如@Peter Cordes 所指出的那样。
另一个缺点是堆栈仍然有限。在 Linux，堆栈通常限制为 8 MB。这是与递归相同的可扩展性限制。
关于可变长度数组：VLA 基本上是语法糖，一种方便的表示法。除了语法之外，它们具有与数组完全相同的功能（实际上，甚至更少，即 sizeof() 不起作用），更不用说 std::vector.
在实践中，如果您不能为小于 1kiB 左右的可能大小设置硬性上限，您通常应该动态分配。如果您可以确定尺寸很小，您可以考虑使用 alloca 作为堆栈的容器。
（您不能有条件地使用 VLA，它必须在范围内。尽管您可以通过在 if() 之后声明它来使其大小为零，并将指针变量设置为 VLA地址，或 malloc。但 alloca 会更容易。）
在 C++ 中，您通常会 std::vector，但它很愚蠢，因为它不能/不使用 realloc (Does std::vector *have* to move objects when growing capacity? Or, can allocators "reallocate"?)。所以在 C++ 中，它是更有效的增长与重新发明轮子之间的权衡，尽管它仍然是 O(1) 时间的摊销。您可以预先使用相当大的 reserve() 来缓解大部分问题，因为您分配但从未接触过的内存通常不会花费任何费用。
在C 中你无论如何都要自己编写堆栈，并且realloc 是可用的。 （而且所有 C 类型都可以轻松复制，因此没有什么可以阻止您使用 realloc）。因此，当您确实需要增长时，您可以重新分配存储空间。但是，如果您不能在函数入口上设置一个合理且绝对足够大的上限并且可能需要增长，那么您仍然应该分别跟踪容量与使用中的大小，例如 std::vector。不要在每个 push/pop.
realloc
直接使用调用堆栈作为堆栈数据结构在纯汇编语言中很容易（对于使用调用堆栈的 ISA 和 ABI，即"normal" CPU 如 x86、ARM、MIPS 等）。 是的，在 asm 中值得为您 知道的 堆栈数据结构做的事情将非常小，不值得开销malloc / free.
使用 asm push 或 pop 指令（或没有单指令推送/弹出的 ISA 的等效序列）。您甚至可以通过与保存的堆栈指针值进行比较来检查大小/查看堆栈数据结构是否为空。 （或者只是在 push/pop 旁边维护一个整数计数器）。
一个非常简单的例子是一些人编写 int->string 函数的低效方式。对于像 10 这样的非 2 次幂基数，您可以通过除以 10 来生成最低有效的一阶数字，一次删除一个数字，其中数字 = 余数。您可以只存储到缓冲区中并递减指针，但是有些人编写函数 push 在 divide 循环中，然后在第二个循环中编写 pop 以使它们按打印顺序排列（最重要的优先） .例如Ira 在 How do I print an integer in Assembly Level Programming without printf from the c library? 上的回答（我对同一个问题的回答显示了一种有效的方法，一旦你理解了它也更简单。）
栈向堆增长并不特别重要，只是有一些space你可以使用。而且那个栈内存已经被映射了，并且通常在缓存中很热。这就是我们可能想要使用它的原因。
例如，Stack above heap 恰好在 GNU/Linux 下为真，这通常将主线程的 user-space 堆栈放在 user-space 虚拟地址 [= 的顶部附近216=]。 （例如 0x7fff...）通常有一个堆栈增长限制远小于从堆栈到堆的距离。您希望意外的无限递归尽早出现故障，例如在消耗 8MiB 的堆栈 space 之后，而不是驱动系统进行交换，因为它使用了千兆字节的堆栈。根据 OS，您可以增加堆栈限制，例如ulimit -s。并且线程堆栈通常分配 mmap，与其他动态分配相同，因此无法说明它们相对于其他动态分配的位置。
据我所知，即使使用内联 asm，C 也不可能
（无论如何都不安全。下面的示例显示了您必须像在 asm 中那样在 C 中编写它是多么邪恶。它基本上证明了现代 C 不是一种可移植的汇编语言。）
您不能只将 push 和 pop 包装在 GNU C 内联 asm 语句中，因为没有办法告诉编译器您正在修改堆栈指针。在您的内联 asm 语句更改它之后，它可能会尝试引用与堆栈指针相关的其他局部变量。
如果您知道您可以安全地强制编译器为该函数创建一个帧指针（它将用于所有局部变量访问），那么您可能无需修改堆栈指针。但是如果你想进行函数调用，许多现代 ABI 要求堆栈指针在调用之前过度对齐。例如x86-64 System V 要求在 call 之前进行 16 字节堆栈对齐，但 push/pop 以 8 字节为单位工作。 OTOH，32 位 ARM（和一些 32 位 x86 调用约定，例如 Windows）没有该功能，因此任何数量的 4 字节推送都会使堆栈正确对齐以进行函数调用。
不过我不推荐它；如果你想要那个级别的优化（并且你知道如何为目标优化 asm CPU），用 asm 编写你的整个函数可能更安全。
Variable Length Arrays and I don't really understand why they couldn't be leveraged as a way to grow stack reference
VLA 不可调整大小。 在您执行 int VLA[n]; 之后，您将无法调整大小。您在 C 中所做的任何事情都不能保证您有更多与该数组连续的内存。
alloca(size) 也有同样的问题。这是一个特殊的编译器内置函数（在 "normal" 实现上）将堆栈指针递减 size 字节（四舍五入为堆栈宽度的倍数）和 returns 该指针。 在实践中，您可以进行多次 alloca 调用，它们很可能是连续的，但对此的保证为零，因此如果没有 UB，您将无法安全地使用它。不过，您 可能 在某些实现上逃避此问题，至少目前如此，直到未来的优化注意到 UB 并假设您的代码无法访问。
（它可能会破坏某些调用约定，例如 x86-64 System V，其中 VLA 保证为 16 字节对齐。8 字节 alloca 可能会向上取整为 16。）
但是如果你确实想让这个工作，你可能会使用 long *base_of_stack = alloca(sizeof(long));（最高地址：堆栈在大多数但不是所有的 ISA/ABI 上向下增长 - 这是您必须做出的另一个假设）。
另一个问题是，除了离开函数作用域之外，没有办法释放 alloca 内存。所以你的 pop 必须增加一些 top_of_stack C 指针变量，而不是实际移动真正的架构 "stack pointer" 寄存器。 push 将不得不查看 top_of_stack 是高于还是低于您也单独维护的高水位线。如果是这样，你 alloca 多一些内存。
那时候你可能 alloca 块大于 sizeof(long) 所以正常情况是你不需要分配更多内存，只需将 C 变量移到顶部-堆栈指针。例如也许是 128 字节的块。这也解决了一些 ABI 保持堆栈指针过度对齐的问题。它让堆栈元素比 push/pop 宽度更窄，而不会在填充上浪费 space。
这确实意味着我们最终需要更多的寄存器来复制架构堆栈指针（除了 SP 永远不会在弹出时增加）。
请注意，这类似于 std::vector 的 push_back 逻辑，其中您有分配大小和使用中大小。 区别在于std::vector 总是在需要更多 space 时复制（因为实现甚至无法尝试 realloc）所以它必须通过指数增长来摊销。当我们通过移动堆栈指针知道增长是 O(1) 时，我们可以使用固定增量。像 128 字节，或者半页可能更有意义。我们不会立即触及分配底部的内存；我还没有尝试为需要堆栈探测的目标编译它，以确保您不会在不触及中间页面的情况下将 RSP 移动超过 1 页。 MSVC 可能会为此插入堆栈探测。
在调用堆栈上破解了 alloca 堆栈：在实践中充满了 UB 和错误编译 gcc/clang
这主要是为了表明它是多么邪恶，C 不是一种可移植的汇编语言。有些东西你可以在 asm 中做你在 C 中做不到的事情。（还包括从一个函数有效地返回多个值，在不同的寄存器中，而不是一个愚蠢的结构。）
#include <alloca.h>
#include <stdlib.h>
void some_func(char);
// assumptions:
// stack grows down
// alloca is contiguous
// all the UB manages to work like portable assembly language.
// input assumptions: no mismatched { and }
// made up useless algorithm: if('}') total += distance to matching '{'
size_t brace_distance(const char *data)
{
size_t total_distance = 0;
volatile unsigned hidden_from_optimizer = 1;
void *stack_base = alloca(hidden_from_optimizer); // highest address. top == this means empty
// alloca(1) would probably be optimized to just another local var, not necessarily at the bottom of the stack frame. Like char foo[1]
static const int growth_chunk = 128;
size_t *stack_top = stack_base;
size_t *high_water = alloca(growth_chunk);
for (size_t pos = 0; data[pos] != '[=10=]' ; pos++) {
some_func(data[pos]);
if (data[pos] == '{') {
//push_stack(stack, pos);
stack_top--;
if (stack_top < high_water) // UB: optimized away by clang; never allocs more space
high_water = alloca(growth_chunk);
// assert(high_water < stack_top && "stack growth happened somewhere else");
*stack_top = pos;
}
else if(data[pos] == '}')
{
//total_distance += pop_stack(stack);
size_t popped = *stack_top;
stack_top++;
total_distance += pos - popped;
// assert(stack_top <= stack_base)
}
}
return total_distance;
}
令人惊讶的是，这似乎实际上编译成看起来正确的 asm (on Godbolt)，gcc -O1 用于 x86-64（但不是更高优化级别）。 clang -O1 和 gcc -O3 优化了 if(top<high_water) alloca(128) 指针比较，因此这在实践中不可用。
uintptr_t 也不安全。或者 GCC 可能只是根据 high_water = alloca() 从未被取消引用的事实优化掉 alloca(128)。
https://godbolt.org/z/ZHULrK 显示 gcc -O3 输出，其中循环内没有 alloca。有趣的事实：使 volatile int growth_chunk 对优化器隐藏常量值使其不会被优化掉。所以我不确定是指针比较 UB 导致了这个问题，它更像是访问第一个 alloca 下面的内存，而不是取消引用从第二个 alloca 派生的指针，让编译器对其进行优化。
# gcc9.2 -O1 -Wall -Wextra
# note that -O1 doesn't include some loop and peephole optimizations, e.g. no xor-zeroing
# but it's still readable, not like -O1 spilling every var to the stack between statements.
brace_distance:
push rbp
mov rbp, rsp # make a stack frame
push r15
push r14
push r13 # save some call-preserved regs for locals
push r12 # that will survive across the function call
push rbx
sub rsp, 24
mov r12, rdi
mov DWORD PTR [rbp-52], 1
mov eax, DWORD PTR [rbp-52]
mov eax, eax
add rax, 23
shr rax, 4
sal rax, 4 # some insane alloca rounding? Why not AND?
sub rsp, rax # alloca(1) moves the stack pointer, RSP, by whatever it rounded up to
lea r13, [rsp+15]
and r13, -16 # stack_base = 16-byte aligned pointer into that allocation.
sub rsp, 144 # alloca(128) reserves 144 bytes? Ok.
lea r14, [rsp+15]
and r14, -16 # and the actual C allocation rounds to %16
movzx edi, BYTE PTR [rdi] # data[0] check before first iteration
test dil, dil
je .L7 # if (empty string) goto return 0
mov ebx, 0 # pos = 0
mov r15d, 0 # total_distance = 0
jmp .L6
.L10:
lea rax, [r13-8] # tmp_top = top-1
cmp rax, r14
jnb .L4 # if(tmp_top < high_water)
sub rsp, 144
lea r14, [rsp+15]
and r14, -16 # high_water = alloca(128) if body
.L4:
mov QWORD PTR [r13-8], rbx # push(pos) - the actual store
mov r13, rax # top = tmp_top completes the --top
# yes this is clunky, hopefully with more optimization gcc would have just done
# sub r13, 8 and used [r13] instead of this RAX tmp
.L5:
add rbx, 1 # loop condition stuff
movzx edi, BYTE PTR [r12+rbx]
test dil, dil
je .L1
.L6: # top of loop body proper, with 8-bit DIL = the non-zero character
movsx edi, dil # unofficial part of the calling convention: sign-extend narrow args
call some_func # some_func(data[pos]
movzx eax, BYTE PTR [r12+rbx] # load data[pos]
cmp al, 123 # compare against braces
je .L10
cmp al, 125
jne .L5 # goto loop condition check if nothing special
# else: it was a '}'
mov rax, QWORD PTR [r13+0]
add r13, 8 # stack_top++ (8 bytes)
add r15, rbx # total += pos
sub r15, rax # total -= popped value
jmp .L5 # goto loop condition.
.L7:
mov r15d, 0
.L1:
mov rax, r15 # return total_distance
lea rsp, [rbp-40] # restore stack pointer to point at saved regs
pop rbx # standard epilogue
pop r12
pop r13
pop r14
pop r15
pop rbp
ret
这就像您为动态分配的堆栈数据结构所做的，除了：
- 它像调用栈一样向下增长
- 我们从
alloca而不是realloc获得更多内存。 （realloc如果在分配 之后有可用的虚拟地址space 也可以是高效的。 C++ 选择不为其分配器提供realloc接口，因此std::vector总是在需要更多内存时愚蠢地分配 + 副本。 （据我所知，没有针对new未被覆盖并使用私有重新分配的情况进行优化的实现）。 - 它完全不安全并且充满了 UB，并且在现代优化编译器的实践中失败了
- 页面永远不会返回到 OS：如果您使用大量堆栈 space，这些页面将无限期地保持脏状态。
如果您可以选择 绝对 足够大的尺寸，则可以使用该尺寸的 VLA。
我建议从顶部开始向下移动，以避免接触远低于调用堆栈当前使用区域的内存。这样，在不需要 "stack probes" 将堆栈增加超过 1 页的 OS 上，您可能会避免接触远低于堆栈指针的内存。因此，您在实践中最终使用的少量内存可能都在调用堆栈的已映射页面内，如果最近的一些更深层次的函数调用已经使用它们，甚至可能已经很热的缓存行。
如果您确实使用堆，则可以通过进行相当大的分配来最小化重新分配成本。除非空闲列表上有一个块，你可以通过较小的分配获得，一般来说，如果你从不接触你不需要的部分，过度分配的成本非常低，特别是如果你在做更多分配之前释放或收缩它。
即不要 memset 它做任何事情。如果您想要归零内存，请使用 calloc，它可以为您从 OS 中获取归零页面。
现代 OSes 使用惰性虚拟内存进行分配，因此您第一次接触页面时，它通常必须出现页面错误并实际连接到 HW 页表中。此外，物理内存页面必须清零以支持此虚拟页面。 （除非访问是读取，然后 Linux 会将写时复制映射到零的共享物理页面。）
你甚至从未接触过的虚拟页面在内核中的范围簿记数据结构中只是更大的尺寸。 （并且在 user-space malloc 分配器中）。这不会增加分配它、释放它或使用您接触的较早页面的成本。