在研究罗伯特·奈斯特罗姆的《构建解释器》第14章的挑战时，我遇到了这个问题。注意：生产虚拟机更为复杂，不过我会在本文的末尾分享这与JVM和Lua等其他虚拟机的相似之处。背景本书的前半部分从上到下实现了玩具语言jlox，从词法分析和语法分析构建AST开始，然后进行解释。后半部分从下到上重新实现相同的语言，从字节码结构开始。来源：《构建解释器》第14章它在一个块中存储字节码，块包含一系列字节。每个字节要么是操作码，要么是属于操作码的操作数。因此，指令可以占用不同数量的字节。例如，OP_RETURN是一个字节，而OP_CONSTANT后面跟着一个包含常量池索引的操作数：偏移量 0 1 2 字节 OP_CONSTANT 常量索引 OP_RETURN \___________________/ | 一条指令 另一条指令当一条指令导致运行时错误时，虚拟机需要一种方法将字节码偏移量转换回产生该错误的源代码行。因此，块需要存储行号。一个简单的解决方案是在字节码并行存储第二个数组lines，使每个字节都有一个对应的源代码行：偏移量：0 1 2 3 4 5 6 7 代码：00 01 00 02 01 00 03 01 行：1 1 1 1 1 2 2 2这种设计简单，并且为我们提供了O(1)的查找效率。然而，它占用了O(n)的内存，用于n字节的字节码。从上面的行数组来看，我们可以利用几个连续字节可以来自同一源行的事实。运行长度编码运行长度编码将每个行号一次存储，并带有属于它的连续字节的数量：每个字节的行：1 1 1 1 1 | 2 2 2 编码运行：(5, 1) | (3, 2) 计数，行n表示字节码字节的数量。r是连续行运行的数量。在这里，n = 8，r = 2。一般来说，1 <= r <= n。最佳情况是整个块来自一条源行，其中r = 1。最坏情况是每个字节后都改变源行，其中r = n。运行长度编码将行表的内存从O(n)减少到O(r)。线性搜索为了查找任意偏移量的行，我们可以遍历运行，同时累积它们的长度。对于偏移量6：(5, 1) -> 涵盖偏移量0..4 (3, 2) -> 涵盖偏移量5..7 <- 偏移量6在这里因此，随机查找在最坏情况下需要O(r)的时间。如果我们在反汇编一个块时对每个字节执行新的线性扫描，总成本是O(nr)。由于r可能等于n，最坏情况是O(n²)。一次遍历然而，运行长度编码本身并不是二次的。如果反汇编器按照递增顺序访问偏移量，它可以保持一个游标指向当前运行。然后，每个字节和每个运行只需访问一次，给出O(n + r)，这简化为O(n)，因为r <= n。这种方法非常适合顺序遍历，但它并没有改善任意查找，任然是O(r)。如果错误给我们一个在块中间的偏移量，我们仍然需要从头扫描运行，除非我们存储更多信息。前驱问题与记录运行长度相比，我们可以记录运行的起始偏移量：偏移量：0 1 2 | 3 4 | 5 行：1 1 1 | 2 2 | 3 起始对：(0, 1) (3, 2) (5, 3) 每对意味着从这个字节码偏移量开始，这个数量的后续字节属于这个源行。本质上，这现在是一个静态前驱问题。1 二分查找因为对是根据它们的起始偏移量排序的，我们可以通过修改后的二分查找解决静态前驱问题。考虑：起始对：(0, 1) (3, 2) (5, 3) 给定目标偏移量4，我们找到小于或等于4的最大起始偏移量， 即(3, 2)。在二分查找过程中，左和右限制了仍可能包含准确匹配的区域。如果没有准确匹配，它们最终会交叉：目标4 v 起始偏移量：0 3 | 5 ^ ^ 右左如果不存在准确匹配，pair[right]指向小于目标的最大起始偏移量。结合准确匹配情况，这可以找到小于或等于目标的最大起始偏移量。fn get_line (chunk: & Chunk, offset: usize) -> usize { let mut left = 0; let mut right = chunk.line_starts.len() - 1; while left <= right { let mid = left + (right - left) / 2; let (mid_offset, mid_line) = chunk.line_starts[mid]; if offset < mid_offset { right = mid - 1; } else if offset > mid_offset { left = mid + 1; } else { return mid_line; } } let (_, line) = chunk.line_starts[right]; line } 这段代码依赖于不变式：get_line仅在有效的字节码偏移量上调用。line_starts保持排序，因为字节码是按顺序附加的。通过起始偏移量的一次遍历二分查找对于任意查找非常有用。在顺序反汇编期间，游标可以指向当前起始对。每当...