堆栈的目的是什么？我们为什么需要它？

6 回答

• 84

  更新：我非常喜欢这个问题，我做了the subject of my blog on November 18th 2011 . 谢谢你这个好问题！

  我一直想知道：堆栈的目的是什么？

  我假设您的意思是MSIL语言的评估堆栈，而不是运行时的实际每线程堆栈 .

  为什么从内存转移到堆栈或“加载？”另一方面，为什么会从堆栈转移到内存或“存储”？为什么不将它们全部放在内存中？

  MSIL是一种"virtual machine"语言 . 像C＃编译器这样的编译器生成CIL，然后在运行时，另一个名为JIT（Just In Time）编译器的编译器将IL转换为可以执行的实际机器代码 .

  首先让我们回答“为什么要使用MSIL？”的问题 . 为什么不让C＃编译器写出机器代码？

  因为这样做比较便宜 . 假设我们没有这样做;假设每种语言都必须有自己的机器代码生成器 . 你有20种不同的语言：C＃，JScript .NET，Visual Basic，IronPython，F# ......假设你有十种不同的处理器 . 你需要编写多少代码生成器？ 20 x 10 = 200代码生成器 . 这是很多工作 . 现在假设您要添加新处理器 . 你必须为它编写代码生成器二十次，每种语言一个 .

  此外，这是困难和危险的工作 . 为您不是专家的芯片编写高效的代码生成器是一项艰苦的工作！编译器设计人员是他们语言语义分析的专家，而不是新芯片组的有效寄存器分配 .

  现在假设我们采用CIL方式 . 你需要编写多少个CIL生成器？每种语言一种 . 你需要编写多少个JIT编译器？每个处理器一个 . 总计：20 10 = 30代码生成器 . 此外，语言到CIL生成器易于编写，因为CIL是一种简单的语言，并且CIL到机器代码生成器也很容易编写，因为CIL是一种简单的语言 . 我们摆脱了所有复杂的C＃和VB以及诸如此类的东西，并将所有内容“降低”为易于编写抖动的简单语言 .

  使用中间语言可以显着降低生成新语言编译器的成本 . 它还大大降低了支持新芯片的成本 . 你想支持一个新的芯片，你找到了那个芯片上的一些专家，让他们写一个CIL抖动，你就完成了;然后，您可以在芯片上支持所有这些语言 .

  好的，所以我们已经确定了为什么我们有MSIL;因为使用中间语言会降低成本 . 为什么语言是“堆栈机器”？

  因为堆栈机器在概念上对于语言编译器编写者来说非常简单 . 堆栈是用于描述计算的简单易懂的机制 . 对于JIT编译器编写者来说，堆栈机器在概念上也很容易处理 . 使用堆栈是一种简化的抽象，因此它再次降低了我们的成本 .

  你问“为什么要堆叠？”为什么不直接用内存做所有事情？好吧，让我们考虑一下 . 假设您要为以下内容生成CIL代码：

  int x = A() + B() + C() + 10;
  

  假设我们有“添加”，“调用”，“存储”等约定总是从堆栈中取出它们的参数并将它们的结果（如果有的话）放在堆栈上 . 要为此C＃生成CIL代码，我们只需说：

  load the address of x // The stack now contains address of x
  call A()              // The stack contains address of x and result of A()
  call B()              // Address of x, result of A(), result of B()
  add                   // Address of x, result of A() + B()
  call C()              // Address of x, result of A() + B(), result of C()
  add                   // Address of x, result of A() + B() + C()
  load 10               // Address of x, result of A() + B() + C(), 10
  add                   // Address of x, result of A() + B() + C() + 10
  store in address      // The result is now stored in x, and the stack is empty.
  

  现在假设我们没有堆栈就做到了 . 我们将按照您的方式执行操作，其中每个操作码都获取其操作数的地址以及存储其结果的地址：

  Allocate temporary store T1 for result of A()
  Call A() with the address of T1
  Allocate temporary store T2 for result of B()
  Call B() with the address of T2
  Allocate temporary store T3 for the result of the first addition
  Add contents of T1 to T2, then store the result into the address of T3
  Allocate temporary store T4 for the result of C()
  Call C() with the address of T4
  Allocate temporary store T5 for result of the second addition
  ...
  

  你看这是怎么回事？我们的代码变得越来越大，因为我们必须显式地分配通常按惯例进入堆栈的所有临时存储 . 更糟糕的是，我们的操作码本身都变得非常庞大，因为他们现在都必须将他们要写入结果的地址和每个操作数的地址作为参数 . 一条"add"指令知道它将从堆栈中取出两个东西并放置一个东西就可以是一个字节 . 采用两个操作数地址和结果地址的add指令将是巨大的 .

  我们使用基于堆栈的操作码，因为堆栈解决了常见问题 . 即： I want to allocate some temporary storage, use it very soon and then get rid of it quickly when I'm done . 通过假设我们有一个堆栈，我们可以使操作码非常小，代码非常简洁 .

  更新：一些额外的想法

  顺便提一下，这种通过（1）指定虚拟机，（2）编写编译器来大幅降低成本的想法针对VM语言，以及（3）在各种硬件上编写VM的实现，根本不是一个新想法 . 它不是源自MSIL，LLVM，Java字节码或任何其他现代基础架构 . 我所知道的最早实施这一策略的是1966年的pcode machine .

  我个人第一次听说这个概念的时候，我才知道Infocom的实现者如何设法在如此多的不同机器上运行 . 他们指定了一个名为Z-machine的虚拟机，然后为他们想要运行游戏的所有硬件制作了Z机器模拟器 . 这为他们在原始8位系统上实现虚拟内存管理带来了额外的巨大好处;游戏可能比内存更大，因为他们可以在需要时从磁盘中分页代码，并在需要加载新代码时将其丢弃 .

  回复于 2024-04-25T03:16:02+08:00
• 5

  要在堆栈问题中添加更多内容 . 堆栈概念源自CPU设计，其中算术逻辑单元（ALU）中的机器代码对位于堆栈上的操作数进行操作 . 例如，乘法运算可以从堆栈中取两个顶部操作数，将它们多个并将结果放回堆栈 . 机器语言通常有两个基本功能来添加和删除堆栈中的操作数;推和POP . 在许多cpu的dsp（数字信号处理器）和机器控制器（例如控制洗衣机的控制器）中，堆栈位于芯片本身上 . 这样可以更快地访问ALU，并将所需的功能整合到单个芯片中 .

  回复于 2024-04-25T03:16:02+08:00
• 20

  请记住，当您在讨论虚拟机的说明时 . .NET中使用的VM是基于堆栈的虚拟机 . 与基于寄存器的VM相反，Android操作系统中使用的Dalvik VM就是一个例子 .

  VM中的堆栈是虚拟的，由解释器或即时编译器将VM指令转换为在处理器上运行的实际代码 . 在.NET的情况下几乎总是一个抖动，MSIL指令集被设计为从一开始就被jitted . 例如，与Java字节码相反，它具有针对特定数据类型的操作的不同指令 . 这使得它被优化以进行解释 . 实际上存在MSIL解释器，它在.NET Micro Framework中使用 . 哪个在资源非常有限的处理器上运行，无法承受存储机器代码所需的RAM .

  实际的机器代码模型是混合的，具有堆栈和寄存器 . JIT代码优化器的一个重要工作是提出一种方法来存储寄存器中保存在堆栈中的变量，从而大大提高执行速度 . Dalvik抖动有相反的问题 .

  机器堆栈是一个非常基本的存储设施，已经在处理器设计中存在了很长时间 . 它具有非常好的参考局部性，这是现代CPU的一个非常重要的特性，它比RAM可以提供数据并且支持递归更快地咀嚼数据 . 语言设计受到堆栈的影响很大，可见支持局部变量，范围仅限于方法体 . 堆栈的一个重要问题是该站点的名称 .

  回复于 2024-04-25T03:16:02+08:00
• 8

  如果没有遵循堆栈/堆的概念并且数据被加载到随机存储器位置，或者数据是从随机存储器位置存储的......它将是非常非结构化的和非托管的 .

  这些概念用于在预定义的结构中存储数据，以提高性能，内存使用......因此称为数据结构 .

  回复于 2024-04-25T03:16:02+08:00
• 4

  有一篇非常有趣/详细的维基百科文章，Advantages of stack machine instruction sets . 我需要完全引用它，所以它只是引用子 Headers

  • 非常紧凑的目标代码

  • 简单的编译器/简单的解释器

  • 最小处理器状态

  回复于 2024-04-25T03:16:02+08:00
• 429

  通过使用continuation passing style编码，可以让系统在没有堆栈的情况下工作 . 然后调用帧成为垃圾收集堆中分配的延续（垃圾收集器需要一些堆栈） .

  请参阅Andrew Appel的旧着作：Compiling with Continuations和Garbage Collection can be faster than Stack Allocation

  （由于缓存问题，他今天可能有点不对劲）

  回复于 2024-04-25T03:16:02+08:00