Bytecode-to-Source Mapping
3 hours ago
- 字节码块存储操作码和操作数，需要一种方式将字节码偏移量映射回源代码行号，以便在运行时错误报告中使用。
- 朴素的方法使用一个并行数组，将每个字节映射到一个行号，占用O(n)内存但提供O(1)查找。
- 游程编码通过存储（计数，行号）游程来压缩行信息，将内存减少到O(r)，但随机查找变为O(r)，且不经优化时完整遍历为O(n²)。
- 使用游标对游程编码进行单次遍历可实现O(n)顺序访问，但不改进任意查找。
- 使用起始偏移量代替游程长度，将问题转化为静态前驱问题，可通过二分查找实现O(log r)的随机查找。
- 起始偏移量结构既支持用于随机访问的二分查找，也支持用于顺序遍历的游标，具有灵活性。
- JVM的LineNumberTable使用起始偏移量对（start_pc, line_number），并通过线性搜索进行查找，而Lua则存储行增量并使用检查点来加速查找。