栈机如何高效存储不同大小的数据类型？

Question

假设我有以下虚拟机的原始堆栈实现：

unsigned long stack[512];
unsigned short top = 0;

void push(unsigned long qword) {
    stack[top] = qword;
    top++;
}

void pop() {
    top--;
}

unsigned long get() {
    return top-1;
}

这个堆栈实际上工作正常（除了它不检查溢出）但我现在遇到以下问题：效率很低。

这是一个例子：假设我想将一个字节压入堆栈。我现在必须将它转换为 long，然后将其压入堆栈。但是现在整整 7 个字节都没有被使用。感觉有点不对。

所以现在我有以下问题： 栈机如何高效存储不同大小的数据类型？他们做的和这个实现一样吗？

Answer 1

没有“唯一正确”的方法可以做到这一点，Java 虚拟机使用了几种不同的策略。大小小于 32 位的所有类型都扩展为 32 位。将 1 个字节压入堆栈实际上是将 4 个字节压入堆栈。当要处理的本机值大小较少时，好处是简单。

另一种策略用于 64 位值。它们占用两个堆栈槽而不是一个。 JVM 有特定的操作码，指示他们期望堆栈上的值类型，验证器确保没有操作码试图访问堆栈外的变量，该变量与应存在的类型不匹配。

第三种策略用于对象引用。实际指针大小可以是 32 位或 64 位，这取决于 CPU 能力，JVM 是否是运行 64 位模式等。JVM 有特定的操作码来处理对象引用，并且验证者也检查这个。

Answer 2

有不同的效率指标。使用八个字节 long 存储单个字节会增加内存消耗。另一方面，内存并不是当今大多数机器的主要关注点。此外，堆栈通常是预先分配的内存量。所以只要没有用完整个内存块，未使用的七个字节是在 long 内还是在 top.[=18= 标记的位置的另一侧是完全无关的。 ]

就 CPU 时间而言，传输小于硬件总线大小的数量没有任何优势。在最好的情况下，它没有区别。在最坏的情况下，传输单个字节归结为从内存中读取 long，操作其中的一个字节并将 long 写回。在后一种情况下，将字节扩展为长字节以显式覆盖所有八个字节会更有效。

例如，Java 字节码的设计反映了这一点。它不仅放弃了对小于 32 位的推入和弹出数量的支持，甚至不支持它们的算术指令¹。因此对于大多数用例，在推送之前您甚至不知道数量可能是 byte。只有形参类型和数组类型可以参考byte.

但请注意，JVM 甚至不是最狭义的堆栈引擎。不支持推送和弹出任意数量的项目。如中所述，使用堆栈表达意图允许非常紧凑的指令。但是 Java 字节码不允许分支到堆栈上具有不同数量项目的代码位置。所以它不支持在循环中推送或弹出项目。换句话说，对于每条指令，堆栈中的实际偏移量是可预测的，并且操作数类型也是已知的。因此，不直接使用堆栈就可以将 Java 字节码转换为 IR。这种转换后的代码可以使用具有任意操作数大小的指令，如果这对特定的目标体系结构有好处的话。

¹ 这是四分之一个世纪前使用的硬件

栈机如何高效存储不同大小的数据类型？

How do stack machines efficiently store data types of different sizes?

stack

bytecode

virtual-machine