一文梳理"Stack"一词的多重含义
来源标题:The Many Meanings of "Stack"
技术博客梳理了"stack"在计算机领域的多种含义:既指后进先出的数据结构,也指图遍历中实现深度优先搜索的方式,还指操作系统为进程分配的、存放局部变量和函数参数的内存区域。作者称写此文是为帮读者省去自己曾花费数小时的困惑。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
作者注:Hacker News 上的评论在这里。 说到“同一个词,不同含义”,stack(栈)这个词首当其冲(双关意在)。本文并不追求面面俱到,但希望能提供足够的细节,帮你省下我当初困惑好几个小时的时间。 栈是一种数据结构,从中删除最近加入集合的元素很方便(后进先出,即 LIFO)。可以想象一摞煎饼,拿走最上面那张很容易。这与队列形成对比:队列中删除集合里存在时间最长的元素很方便(先进先出,即 FIFO)。 当用这些数据结构来遍历图时,一个很好的对比就出现了。如果用栈,你会进行深度优先遍历(DFS);如果用队列,则是广度优先遍历(BFS)。 为了支持代码执行,操作系统会为运行中的进程在内存中分配一块区域。栈用于存放局部变量、函数参数和返回地址——这些对象的大小在编译时已知。这与堆形成对比,堆用于存放动态分配的数据,比如列表和字典。 就性能而言,使用栈更快,因为开销很小——栈的管理只需改动一个计数器(栈指针)。在堆上分配则要费更多功夫:需要找到一块大小合适的空闲连续内存块,更新空闲块列表,并在不再需要时释放该块。 如需进一步了解,Operating Systems: Three Easy Pieces 在第 4.3 节讨论了进程的内存分配。Computer Systems: A Programmer's Perspective 在第 9.9 节讲解了动态内存分配。如果想更直观(或者说,不那么反直觉)地理解 x86 上的栈增长,Eli Bendersky 有一篇很有帮助的文章。 虚拟机这个词同样被赋予了多重含义。就本文而言,我们指的是进程虚拟机,它让你能在不同的操作系统或不同的处理器上运行相同的指令。例如,你可以在任何支持 JVM 的平台上运行 Java 字节码,在任何网页浏览器中运行 WebAssembly。这与系统虚拟机形成对比,后者让你能在 Linux 机器上玩 Windows 游戏(例子出自 Bob Nystrom)。 基于栈的虚拟机会使用上文“栈 vs 队列”意义上的栈,通过 push(入栈)和 pop(出栈)操作来执行指令。事实上,JVM 和 WebAssembly 都使用基于栈的虚拟机。这与基于寄存器的虚拟机形成对比,后者使用虚拟寄存器,能更自然地映射到物理寄存器。 Crafting Interpreters 的第二部分涉及实现一个基于栈的虚拟机。Lua 在从 4.0 升级到 5.0 时,从基于栈的虚拟机转向了基于寄存器的虚拟机。该论文描述了升级中的多项语言优化,但仅虚拟机这一项改动就带来了显著的性能提升。Linus Lee 基于该论文写了一篇关于 Lua 内部实现的思考文章。 调用约定定义了编程语言中的函数调用在机器码层面如何运作。在基于栈的调用约定中,函数参数和返回值通过上文“栈 vs 堆”意义上的栈来传递。这与基于寄存器的调用约定形成对比,后者使用物理寄存器,并允许在函数调用之间将状态保留在寄存器中。 Go 在从 1.16 升级到 1.17 时,从基于栈的调用约定转向了基于寄存器的调用约定。基于栈的调用约定的好处是简单——所有平台使用相同的约定,因此不需要处理器特定的寄存器细节。然而,基于寄存器的调用约定受益于更高的吞吐量,因为在寄存器中访问参数比在栈上更快。 有关此次升级的细节可以在提案中找到,Menno Finlay-Smits 就此写了一篇通俗易懂的文章(附有汇编代码和基准测试!)。同样值得一读的是为支持这一变更而并行采用的多 ABI 机制。
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。