实际上,如果你不能对可能小于1kiB的大小设置硬上限,通常应该动态分配。如果你能确定大小很小,你可以考虑使用
alloca
作为堆栈的容器。
(你不能有条件地使用VLA,它必须在作用域内。虽然你可以通过在
if()
之后声明大小为零的VLA,并将指针变量设置为VLA地址或
malloc
来实现。但是使用alloca会更容易。)
在C++中,通常使用
std::vector
,但这很愚蠢,因为它不能/不使用
realloc
(
std::vector是否必须在增加容量时移动对象?或者说,分配器可以“重新分配”吗?)。因此,在C++中,这是更高效的增长与重复发明轮子之间的权衡,尽管仍然是摊销O(1)时间。你可以通过一个相当大的
reserve()
来减轻大部分问题,因为你分配但从未使用的内存通常不会产生成本。
在 C 语言中,你必须自己编写栈,并且可以使用
realloc
函数。此外,所有的 C 类型都是可平凡复制的,因此没有什么能阻止你使用 realloc。因此,当你需要增长时,可以重新分配存储空间。但如果无法对函数入口设置合理且足够大的上限,并且可能需要增长,则仍应像 std::vector 一样单独跟踪容量和使用大小,不要在每次 push/pop 时调用
realloc
。
直接使用调用栈作为堆栈数据结构在纯汇编语言中很容易(对于使用调用栈的ISA和ABI,即像x86、ARM、MIPS等“正常”的CPU)。而且,在汇编语言中值得做的是对于你知道将非常小且不值得malloc/free开销的堆栈数据结构。使用asm push或pop指令(或等效序列,针对没有单指令push/pop的ISA)。您甚至可以通过与保存的堆栈指针值进行比较来检查大小/查看堆栈数据结构是否为空。 (或只需在推入/弹出旁边维护整数计数器)。
一个非常简单的例子是一些人编写int->string函数的低效方式。对于像10这样的非2幂基数,您通过除以10来逐个删除数字,以最不重要的顺序生成数字,并将其存储到缓冲区中并递减指针,但有些人编写函数,在除法循环中使用push,然后在第二个循环中使用pop以按打印顺序(最重要的先)获取它们。例如,在
How do I print an integer in Assembly Level Programming without printf from the c library?上的Ira的答案。(我在同一问题上的答案显示了高效的方法,一旦你理解了它,也更简单。)
堆栈向堆增长并不特别重要,只要有一些可用空间即可。而且堆栈内存已经映射,并且通常在高速缓存中热。这就是为什么我们可能想要使用它的原因。
在GNU/Linux中,堆栈在堆之上是真实存在的,例如通常将主线程的用户空间堆栈放置在用户空间虚拟地址空间的顶部(例如
0x7fff...
)。通常有一个堆栈增长限制,该限制比堆栈到堆的距离小得多。您希望意外的无限递归尽早出错,例如在使用8MiB堆栈空间后,而不是在使用几GB堆栈时驱动系统进行交换。根据操作系统的不同,您可以增加堆栈限制,例如使用
ulimit -s
。线程堆栈通常使用
mmap
进行分配,与其他动态分配相同,因此无法确定它们相对于其他动态分配的位置。
据我所知,即使使用内联汇编,在 C 语言中也无法实现这一点。(无论如何,不安全。下面的示例说明了您必须如何才能像汇编语言那样在 C 语言中编写此代码。它基本上证明了现代 C 语言不是可移植的汇编语言。)您不能只是将
push
和
pop
包装在 GNU C 内联汇编语句中,因为没有办法告诉编译器您正在修改堆栈指针。在您的内联汇编语句更改堆栈指针后,它可能尝试相对于堆栈指针引用其他局部变量。
可能如果你知道可以安全地强制编译器为该函数创建一个框架指针(它将用于所有局部变量访问),那么你可以通过修改堆栈指针来解决问题。但如果你想进行函数调用,许多现代ABI要求在调用之前堆栈指针具有超对齐。例如,x86-64系统V在调用之前要求16字节的堆栈对齐,但
push
/
pop
以8字节为单位工作。另一方面,32位ARM(和一些32位x86调用约定,如Windows)没有这个特性,因此任意数量的4字节推入将使堆栈正确对齐以进行函数调用。
我不建议这样做;如果你想要那种级别的优化(并且你知道如何为目标CPU优化汇编代码),最好还是使用汇编语言编写整个函数。
可变长度数组(Variable Length Arrays,VLAs)并不可调整大小。在 C 语言中,一旦定义了
int VLA[n];
这样的 VLA 数组,它的大小就无法更改。C 语言中没有任何方法可以保证在这个数组之后能够获得更多与之连续的内存空间。
在使用
alloca(size)
函数时也存在同样的问题。该函数是编译器内置的一个特殊函数,在“正常”实现中会将栈指针减去
size
字节(按照栈宽度向上取整),然后返回指向该内存区域的指针。实际上,可能连续多次调用
alloca
函数得到的内存空间是相邻的,但不能保证如此,因此在没有 UB(未定义行为)的保护下,无法安全地使用该函数。虽然,在某些实现中可能会暂时避免触发 UB,但未来的优化可能会假设您的代码无法被访问。
(这可能会在某些调用约定上出现问题,例如x86-64 System V,其中VLAs保证为16字节对齐。在那里使用8字节的
alloca
可能会向上舍入到16个字节。)
但是,如果您确实想使其工作,您可能会使用
long *base_of_stack = alloca(sizeof(long));
(最高地址:
大多数ISA / ABI的堆栈向下增长 - 这是您必须做出的另一个假设)。
另一个问题是,没有办法释放
alloca
内存,除非离开函数范围。因此,您的
pop
必须增加一些top_of_stack C指针变量,而不是实际移动真正的架构“堆栈指针”寄存器。并且,
push
将必须查看
top_of_stack
是否在您单独维护的高水位标记之上或之下。如果是,您将
alloca
更多内存。
在这种情况下,最好一次性使用大于
sizeof(long)
的块进行
alloca
,这样正常情况下就不需要再分配更多的内存,只需移动C变量的栈顶指针。例如,可以使用128字节的块。这也解决了某些ABIs保持堆栈指针过度对齐的问题。并且它允许堆栈元素比推送/弹出宽度更窄,而不浪费填充空间。
这意味着我们最终需要更多的寄存器来复制体系结构堆栈指针(除了弹出时SP永远不会增加)。
请注意,这类似于std :: vector的push_back逻辑,其中您有一个分配大小和一个使用中的大小。不同之处在于,std :: vector在需要更多空间时总是进行复制(因为实现甚至没有尝试realloc),因此必须通过指数增长来摊销。当我们知道增长是O(1)时,只需移动堆栈指针即可,我们可以使用固定的增量。例如128字节,或者也许半页更有意义。我们不会立即触及分配底部的内存;我还没有尝试为需要堆栈探测以确保不在未经干预的页面上将RSP移动超过1页的目标编译此代码。 MSVC可能会为此插入堆栈探测。
hack up alloca stack-on-the-callstack:充满了UB和实际上与gcc / clang不兼容
这主要是为了展示它有多么邪恶,以及C不是一种可移植的汇编语言。在汇编中,你可以做一些在C中无法做到的事情。(还包括高效地从函数中返回多个值,以不同的寄存器而不是愚蠢的结构体。)
#include <alloca.h>
#include <stdlib.h>
void some_func(char);
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);
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] == '{') {
stack_top--;
if (stack_top < high_water)
high_water = alloca(growth_chunk);
*stack_top = pos;
}
else if(data[pos] == '}')
{
size_t popped = *stack_top;
stack_top++;
total_distance += pos - popped;
}
}
return total_distance;
}
惊人的是,这似乎实际上可以编译成正确的汇编代码(
on Godbolt),对于x86-64来说使用
gcc -O1
(但在更高的优化级别下不行)。
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
如果在分配后有空闲的虚拟地址空间也可能很高效)。C ++选择不为其分配器提供realloc
接口,因此std::vector
总是愚蠢地在需要更多内存时进行分配和复制。(据我所知,没有实现针对new
未被覆盖且使用私有realloc的情况进行优化)。
- 它完全不安全,充满未定义行为,并且在现代优化编译器中无法正常工作
- 页面永远不会返回到操作系统:如果您使用大量堆栈空间,则这些页面将永久保持脏状态。
如果你能选择一个足够大的大小,你可以使用该大小的VLA。我建议从顶部开始向下移动,以避免触及调用堆栈当前正在使用区域远下方的内存。这样,在不需要“堆栈探测”以增加堆栈超过1页的操作系统上,你可能会避免接触到堆栈指针远下方的内存。因此,你实际使用的少量内存可能全部位于调用堆栈的已映射页面内,甚至是最近某个更深层次的函数调用已经使用过的缓存行内。
如果您使用堆,可以通过进行相当大的分配来最小化realloc成本。 除非存在一个在free-list上的块可以通过较小的分配获得,在一般情况下过度分配如果您从未触及不需要的部分,则成本非常低,特别是如果您在进行任何其他分配之前释放或缩小它。
即不要对其使用memset。 如果您想要零内存,请使用calloc,它可以为您从操作系统获取零页。
现代操作系统对于分配使用延迟虚拟内存,因此第一次触摸页面时,通常必须出现页面错误并实际连接到HW页面表中。此外,物理内存页面必须被清零以支持此虚拟页面。(除非访问是读取,然后Linux将将页面复制到共享的零物理页面上。)
您甚至从未触摸的虚拟页面仅是内核中的一个范围簿记数据结构的更大尺寸。 (以及用户空间malloc分配器)。这不会增加分配它的成本,也不会增加释放它或使用您触及的早期页面的成本。
inline
函数。 - Jonathan Leffler