浅谈计算机中的“栈”

 

提示:本文会出现大量汇编相关内容,阅读前建议先了解汇编相关知识(本博文使用的汇编架构主要为 x86_64)

提示2:以下对 MB 与 MiB 不作区分,可能出现混淆情况,欢迎指正

栈是什么

先摘录一段定义吧(来自维基百科

堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象资料类型,只允许在有序的线性资料集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。 堆栈的基本特点:先入后出,后入先出;除头尾节点之外,每个元素有一个前驱,一个后继。

简单来说,栈是一种具有先进后出特性的抽象数据结构,具体机制如图(来源):

栈的示意图

汇编

栈帧

在 Java 中的e.printStacks()、gdb 中的bt相关内容中,会出现“栈帧”这个词,由于找不到定义直接上图(来源 ):

栈帧的示意图

如图,每个栈帧代表的是单次执行函数的参数、临时变量、父函数地址等,上述的调试指令也就是将这些内容打印出来以获知函数调用情况

由于函数的调用显然也遵循“先进后出”原则,因此形象化地称其为“调用栈”

常说的“爆栈”也就是此栈总大小超过栈内存,默认情况下,该值在 Windows 下为2 MB1 MB(需要确认),在 Linux 下为8 MB

至于手动扩充栈大小,既可以在文件开头添加#pragma comment(linker,"/STACK:1024000000,1024000000"),也可以在编译选项中添加-Wl,--stack=134217728-Wl表示将后续参数交给链接器);

又或者,在 Linux 下可以通过ulimit -s 102400临时修改默认栈大小(如此处修改为 100 MB),永久修改请参见这篇博文

C++ STL

C++ 函数传参

从 STL 中的栈迁移到汇编中的栈

该部分内容只为图一乐,认真你就输了

众所周知,STL 中的栈开销极大!实现同样的pushtoppop,使用汇编仅需 6 条指令,而 STL 中的 stack 除去函数调用都至少需要 19 条指令,那为什么不从 stack 迁移到汇编里的栈呢?

再次警告,该代码只供图一乐,永远不要真正使用

#include <iostream>
using namespace std;
int main(){
    long long n = 1234;
    long long k = 4321; // x86_64 环境下,push & pop 都需要 64位的数
    asm ("push %0"::"r" (n):"memory");
//    cout<<n<<endl;
//    cout<<k<<endl; // 不注释会怎样?boom啦!栈是会被其他函数/指令使用的
    asm("pop %0":"=r"(k)::"memory");
    // 稍微对 asm 进行一下解释:四个部分均以半角冒号分隔;第一项为汇编代码(其中的 %0 表示第一个参数;第二项为输出列表;第三项为输入列表;第四项为特殊标识(此处用于说明内存会被更改))
    cout << k << endl; // 输出 1234
}

参考资料

x86 和 x64 汇编调用C 函数参数传递规则(GCC)

x86-64 下函数调用及栈帧原理 - 知乎

std::stack - cppreference.com

数据结构-栈(Stack) - 知乎

Compiler Explorer

asm declaration - cppreference.com

C/C++ keyword: asm