我对C语言下的内存结构的理解是，程序的内存是由堆栈和堆分开的，每个堆栈都从块的两端开始扩展，可以想象分配了所有ram，但显然抽象为某种OS内存片段管理器。
设计用于处理局部变量的堆栈（自动存储）和用于内存分配的堆（动态存储）。
（编者注：有些C实现中的自动存储不使用“调用栈”，但是这个问题假设普通的现代C实现是在普通的CPU上，如果本地人不能仅仅生活在寄存器中，它们就会使用调用栈。 ）
假设我想为某些数据解析算法实现堆栈数据结构。它的寿命和范围仅限于一种功能。
我可以想到3种方法来做这样的事情，但是在我看来，没有一种方法是解决此问题的最干净的方法。
我的第一个方法是在堆中构造一个堆栈，例如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并导致不规则的速度降低。对于该算法，这些都不是问题，但是这种构造似乎更适合必须在多个上下文中维护堆栈的应用程序。这里不是这种情况。堆栈是此功能专用的，并且在退出之前会被删除，就像自动存储类一样。
我的下一个想法是递归。因为递归使用内置堆栈，所以这似乎更接近我想要的。
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);
}
}
}
这种方法使我不必编写和维护堆栈。在我看来，该代码似乎更难遵循，对我而言并不重要。
我的主要问题是这会占用更多空间。
在堆栈框架中保存此Extra构造的副本（基本上包含Some data要在堆栈中保留的实际位的加号），并在每一帧中使用完全相同的迭代器指针的不必要的副本：因为这样“安全”，然后引用一些静态全局变量（并且我不知道怎么不这样做。如果编译器进行了一些巧妙的尾部递归之类的事情，这不会有问题，但是我不知道我是否喜欢用手指指望并希望编译器很棒。
我能想到的第三种方式涉及某种可以在堆栈上增长的动态数组，这是使用我不知道的某种C语言编写的最后一件事。
或外部asm块。
考虑到这一点，这就是我要寻找的东西，但是除非我的想法很简单，否则我不会看到我自己写的asm版本，并且尽管看起来更简单，但我看不出它更容易编写或维护。显然，它不能跨ISA移植。
我不知道我是否忽略了某些功能，是否需要寻找另一种语言，还是应该重新考虑自己的生活选择。一切都可能是真的...我希望这只是第一个。
我不反对使用某些库。有没有，如果是这样，它如何工作？我没有在搜索中找到任何东西。
我最近了解了可变长度数组，但我并不真正理解为什么不能利用它们来增加堆栈引用，但是我也无法想象它们会以这种方式工作。
在实践中，如果不能为小于1kiB的可能大小设置硬上限，通常应该动态分配。如果可以确定大小很小，则可以考虑将其alloca用作堆栈的容器。
（您不能有条件地使用VLA，它必须在范围内。尽管您可以通过在后面声明它的大小使其为零if()，然后将指针变量设置为VLA地址或malloc。但是alloca会更容易）
在C ++中，您通常会这样做std::vector，但是它很笨，因为它不能/不使用realloc（在容量增加时std :: vector *必须*是否移动对象？或者分配器可以“重新分配”吗？）。因此，在C ++中，尽管仍要分摊O（1）时间，但要在更有效的增长与重新发明轮子之间进行权衡。您可以通过相当大的reserve()预付款来减轻大部分负担，因为您分配但从不接触的内存通常不会花费任何费用。
无论如何，在C中，您都必须编写自己的堆栈，并且realloc可用。（而且所有C类型都是可复制的，因此没有什么可以阻止您使用realloc）。因此，当您确实需要增长时，可以重新分配存储。但是，如果您不能在函数入口上设置一个合理且绝对足够大的上限，并且可能需要增长，那么您仍然应该分别跟踪容量与使用中的大小，例如std :: vector。不要realloc在每次推送/弹出时都打电话。
在纯汇编语言中，将调用堆栈直接用作堆栈数据结构是很容易的（对于使用调用堆栈的ISA和ABI，即x86，ARM，MIPS等“常规” CPU）。是的，在ASM值得做的堆栈数据结构，你知道会很小，不值得的开销malloc/ free。
使用asmpush或pop指令（或对于没有单指令推入/弹出操作的ISA的等效序列）。您甚至可以通过与保存的堆栈指针值进行比较来检查大小/查看堆栈数据结构是否为空。（或者只是在您的推/弹出旁边保持一个整数计数器）。
一个非常简单的示例是某些人编写int-> string函数的低效方式。对于非2的幂的基数，例如10，您可以用除以10的方式一次删除最低有效位的数字，一次取一个，即digit =余数。您可以将其存储在缓冲区中并减少指针的大小，但是有些人会push在除法循环中编写函数，然后pop在第二个循环中编写函数，以按打印顺序显示它们（最重要的是第一个）。例如，关于如何在不使用c库的printf的情况下在汇编级编程中打印整数的问题，Ira的回答是？（我对同一问题的回答显示了一种有效的方法，一旦您使用它，它也会变得更简单。）
堆栈向着堆增长并不重要，只需要使用一些空间即可。而且该堆栈内存已被映射，并且通常在高速缓存中处于热状态。这就是我们可能要使用它的原因。
例如，在GNU / Linux下，堆之上堆栈确实是正确的，这通常会将主线程的用户空间堆栈放在用户空间虚拟地址空间的顶部附近。（例如0x7fff...）通常，堆栈增长限制比堆栈到堆的距离小得多。您希望意外的无限递归尽早出错，例如在消耗了8MiB的堆栈空间之后，不要驱动系统进行交换，因为它使用了千兆字节的堆栈。根据操作系统的不同，您可以增加堆栈限制，例如ulimit -s。而且线程堆栈通常使用分配mmap，与其他动态分配相同，因此无法确定它们相对于其他动态分配的位置。
（无论如何，都不安全。下面的示例显示了您必须像在asm中那样用C编写代码，这是多么邪恶。它基本上证明了现代C不是可移植的汇编语言。）
你不能只是包装push和pop在GNU C内联汇编语句，因为没有办法告诉编译器您正在修改堆栈指针。内联asm语句更改它后，它可能会尝试引用相对于堆栈指针的其他局部变量。
可能的是，如果您知道可以安全地强制编译器为该函数创建框架指针（它将用于所有局部变量访问），则可以无需修改堆栈指针。但是，如果要进行函数调用，许多现代的ABI都要求在调用之前将堆栈指针过度对齐。例如x86-64系统V在a之前需要16字节堆栈对齐call，但是push/pop以8字节为单位工作。OTOH，32位ARM（以及某些32位x86调用约定，例如Windows）没有该功能，因此，任意数量的4字节压入将使堆栈正确对齐以进行函数调用。
不过，我不建议这样做；如果您需要那种优化水平（并且您知道如何针对目标CPU优化asm），则在asm中编写整个函数可能更安全。
可变长度数组，我不太明白为什么不能利用它们作为增加堆栈引用的方法
VLA不可调整大小。完成后，int VLA[n];您将无法适应该大小。您在C中无法做的任何事情都可以保证您有更多与该数组相邻的内存。
同样的问题alloca(size)。这是一个特殊的编译器内置函数，该函数（在“常规”实现中）将size字节指针递减字节（四舍五入为堆栈宽度的倍数）并返回该指针。在实践中，您可以alloca拨打多个电话，并且它们很可能是连续的，但是这并不能保证为零，因此如果没有UB，您将无法安全地使用它。尽管如此，至少在目前，您可能会在某些实现上避免使用它，直到将来的优化注意到UB并假定您的代码无法访问为止。
（这可能会破坏某些调用约定，例如x86-64 System V，在该约定中，VLA保证是16字节对齐的。alloca那里的8字节可能会舍入为16。）
但是，如果您确实想完成这项工作，则可以使用long *base_of_stack = alloca(sizeof(long));（最高地址：大多数（但不是全部）ISA / ABI上的堆栈向下生长-这是您必须做的另一个假设）。
另一个问题是，alloca除非离开函数作用域，否则无法释放内存。因此，您pop必须增加一些top_of_stack C指针变量，而不实际移动真正的体系结构“堆栈指针”寄存器。并且push必须查看top_of_stack标记是在高水位线之上还是之下，您也分别维护它们。如果是这样，您将alloca有更多的内存。
那时，您可能还需要alloca更大的块，sizeof(long)因此通常情况是您不需要分配更多的内存，只需移动C变量栈顶指针即可。例如128字节的块。这也解决了一些ABI使堆栈指针过度对齐的问题。并且它使堆栈元素比推/弹出宽度更窄，而不会浪费填充空间。
这确实意味着我们最终需要更多的寄存器来对体系结构堆栈指针进行重复排序（除了SP不会在弹出时增加）。
请注意，这类似于std::vector的push_back逻辑，其中您有一个分配大小和一个正在使用的大小。区别在于，std::vector总是在需要更多空间时进行复制（因为实现甚至无法尝试realloc这样做），因此必须通过成倍增长来摊销。当我们通过移动堆栈指针知道增长为O（1）时，我们可以使用固定的增量。像128个字节，或者说半个页面会更有意义。我们不会立即触及分配底部的内存；我没有尝试针对需要堆栈探针的目标进行编译，以确保在不接触中间页面的情况下，将RSP移动不超过1页。MSVC可能为此插入了堆栈探针。
这主要是为了表明它有多邪恶，并且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] != '\0' ; 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（在Godbolt上），gcc -O1适用于x86-64（但在更高的优化级别上却不行）。clang -O1并gcc -O3优化if(top<high_water) alloca(128)指针比较，因此在实践中无法使用。
<从不同对象派生的指针的指针比较是UB，而且似乎强制转换uintptr_t也并不安全。也许GCC只是alloca(128)根据high_water = alloca()从未取消引用的事实来优化。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如果分配后有可用的虚拟地址空间，也可以提高效率）。C ++选择不realloc为其分配器提供接口，因此std::vector当需要更多内存时，总是愚蠢地分配+副本。（对于new尚未被覆盖并使用私有重新分配的情况，AFAIK没有实现可优化）。如果您可以选择绝对足够大的大小，则可以使用该大小的VLA。
我建议从顶部开始向下移动，以免将内存移到调用堆栈当前正在使用的区域以下。这样，在不需要“堆栈探针”来将堆栈增加一页以上的OS上，您可以避免将内存远压到堆栈指针下方。因此，您实际上在实践中最终使用的少量内存可能全部都在调用栈的一个已映射页面内，甚至可能是缓存行，如果最近的一些更深层的函数调用已经使用了它们，那么这些行已经很热。
如果您确实使用堆，则可以通过进行相当大的分配来最大程度地减少重新分配的成本。除非在空闲列表上有一个块，您可能会得到较小的分配，否则通常，如果您从未接触过不需要的部分，则过度分配的成本非常低，尤其是在执行任何操作之前释放或缩小它的情况下更多分配。
即不要memset对任何东西。如果您希望将内存清零，请使用calloc，它可能会为您从操作系统获取被清零的页面。
现代操作系统使用懒惰的虚拟内存进行分配，因此，第一次触摸页面时，它通常必须发生页面故障，并实际上连接到硬件页面表中。同样，必须将物理内存页面清零以支持此虚拟页面。（除非访问是读取的，否则Linux将在写时复制将页面映射到共享的零物理页面。）
在内核中的扩展簿记数据结构中，您甚至从未接触过的虚拟页面将更大。（并且在用户空间malloc分配器中）。这不会增加分配，释放或使用您接触过的早期页面的任何成本。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句