5 hours ago
- The bytecode chunk stores opcodes and operands, requiring a way to map bytecode offsets back to source lines for runtime error reporting.
- A naive approach stores a parallel array mapping every byte to a line number, using O(n) memory but offering O(1) lookup.
- Run-length encoding compresses line info by storing (count, line) runs, reducing memory to O(r) but making random lookup O(r) and full traversal O(n²) without optimization.
- One-pass traversal with a cursor on run-length encoding achieves O(n) sequential access but does not improve arbitrary lookups.
- Using starting offsets instead of run lengths transforms the problem into a static predecessor problem, solvable with binary search for O(log r) random lookup.
- The starting-offset structure supports both binary search for random access and a cursor for sequential traversal, offering flexibility.
- JVM's LineNumberTable uses starting-offset pairs (start_pc, line_number) and performs linear search for lookup, while Lua stores line deltas with checkpoints to bound scan time.