프로그램이 실행 중 오류를 내면, 사용자는 "몇 번째 줄에서 문제가 생겼는지"를 알고 싶어 한다. 그런데 컴파일된 바이트코드는 이미 원본 소스 코드의 구조를 잃어버린 바이트 나열일 뿐이다. 각 바이트는 명령어(opcode)이거나 그 명령어에 딸린 피연산자(operand)이며, 명령어마다 차지하는 바이트 수도 제각각이다. 예컨대 반환 명령은 1바이트로 끝나지만, 상수를 다루는 명령은 상수 풀의 인덱스를 담은 피연산자가 뒤따른다. 이 상황에서 특정 바이트코드 위치(offset)를 원래의 소스 줄 번호로 되돌리는 매핑을 어떻게 저장할 것인가는, 겉보기와 달리 자료구조 설계의 좋은 연습 문제가 된다. 이 글은 Robert Nystrom의 『Crafting Interpreters』 14장을 실습하며 정리된 접근을 따라간다.
가장 단순한 해법과 그 대가
가장 직관적인 방법은 바이트코드 배열과 나란히 같은 길이의 줄 번호 배열을 하나 더 두는 것이다. n바이트의 바이트코드가 있으면 n개짜리 줄 배열을 만들어, 임의의 위치를 O(1)에 조회한다. 조회 속도만 보면 더 바랄 것이 없지만, 메모리를 O(n)으로 통째로 소비한다는 점이 걸린다. 실제 코드에서는 연속된 여러 바이트가 같은 소스 줄에서 나오는 경우가 압도적으로 많기 때문에, 이 배열에는 같은 값이 지루하게 반복된다. 낭비가 눈에 보이는 구조인 셈이다.
여기서 자연스럽게 떠오르는 것이 런 렝스 인코딩(run-length encoding)이다. 같은 줄 번호가 이어지는 구간을 (줄 번호, 반복 횟수) 쌍 하나로 묶어 저장하면, 전체 바이트 수 n이 아니라 서로 다른 구간의 수 r에 비례하는 메모리만 쓴다. 청크 전체가 한 줄에서 나온 최선의 경우 r은 1까지 줄고, 매 바이트마다 줄이 바뀌는 최악의 경우에만 r이 n과 같아진다. 메모리를 O(n)에서 O(r)로 낮춘 것이다. 다만 대가가 있다. 임의의 위치가 어느 줄에 속하는지 알려면 앞에서부터 구간 길이를 누적하며 걸어가야 하므로 조회가 O(r)로 느려진다.
순차 접근과 임의 접근을 가르는 지점
이 지점에서 흔한 오해가 하나 있다. 런 렝스 인코딩이 본질적으로 O(n²)이라는 생각이다. 실제로 모든 바이트를 조회할 때마다 매번 처음부터 선형 탐색을 하면 총비용은 O(nr)이 되고, r이 n과 같은 최악에는 O(n²)까지 치솟는다. 그러나 디스어셈블러처럼 위치를 오름차순으로 방문하는 상황이라면 이야기가 다르다. 현재 구간을 가리키는 커서 하나를 유지하면서 앞으로만 전진시키면, 각 바이트와 각 구간을 정확히 한 번씩만 훑게 되어 전체가 O(n + r), 즉 O(n)으로 정리된다. 문제는 순차 접근이 아니라 임의 접근이다. 런타임 오류가 청크 한가운데의 위치를 던져 줄 때는 여전히 처음부터 구간을 세어야 하고, 조회는 O(r)에 머문다.
구간 길이 대신 시작 위치를 저장하기
해법의 전환점은 저장하는 정보를 바꾸는 데 있다. 반복 횟수 대신 각 구간의 시작 위치를 (시작 offset, 줄 번호) 형태로 기록하는 것이다. 각 쌍은 "이 바이트코드 위치부터 이어지는 바이트들이 이 소스 줄에 속한다"는 뜻이 된다. 쌍들이 시작 위치 기준으로 정렬되어 있으므로, 이제 문제는 "목표 위치보다 작거나 같은 시작 위치 중 가장 큰 것을 찾는" 정적 선행자(static predecessor) 문제로 바뀐다. 정렬된 배열에서의 선행자 탐색은 변형된 이진 탐색으로 풀 수 있다. 이진 탐색의 좌우 경계는 정확히 일치하는 값이 있을 수 있는 구간을 좁혀 가고, 일치가 없으면 경계가 교차하는 순간 오른쪽 인덱스가 목표 이하의 가장 큰 시작 위치를 가리키게 된다.
이 표현의 진짜 이점은 두 가지 접근 방식을 모두 열어 준다는 데 있다. 오류 처리처럼 예측 불가능한 임의 위치를 조회할 때는 이진 탐색으로 O(log r)에 답을 얻고, 디스어셈블처럼 위치를 순차적으로 훑을 때는 앞으로만 움직이는 커서로 각 쌍을 한 번씩만 방문해 O(n)에 전체를 순회한다. 둘 중 하나를 미리 고를 필요 없이, 상황에 맞춰 골라 쓸 수 있다는 유연성이 핵심이다.
실제 VM들은 어떻게 하는가
이 설계는 교과서 속 장난감 언어에만 머무는 아이디어가 아니다. JVM의 LineNumberTable은 사실상 동일한 시작 위치 표현을 쓴다. 각 메서드의 Code 속성에 선택적으로 붙는 이 테이블은 (start_pc, line_number) 항목으로 소스 줄이 시작되는 지점을 표시한다. 다만 명세가 쌍의 정렬을 강제하지 않기 때문에, HotSpot은 줄 번호를 찾을 때 선형 탐색으로 선행자를 구한다. 이론상 이진 탐색이 가능한 구조라도 실제 구현은 제약과 단순성에 따라 다른 선택을 한다는 점을 보여 주는 대목이다.
Lua는 또 다른 절충안을 택한다. 책의 원래 구현처럼 병렬 배열을 쓰되, 명령마다 정확한 줄 번호를 전부 담는 대신 직전 줄과의 1바이트 델타값을 저장하고 간간이 절대 체크포인트를 끼워 넣는다. 예를 들어 (pc 2, 줄 300)이라는 절대 체크포인트가 있고 이후 델타가 이어진다면, 명령 4의 줄은 300에서 시작해 델타를 더해 314로 계산된다. 체크포인트를 주기적으로 심어 두는 이유는 델타를 되짚는 스캔이 무한정 길어지지 않도록 상한을 두기 위해서다. 세 방식 모두 결국 같은 질문—메모리와 조회 속도의 균형—에 대한 서로 다른 답이며, 실무자가 자료구조를 고를 때 접근 패턴을 먼저 따져야 한다는 교훈을 공유한다. 무엇을 저장하느냐보다, 어떻게 읽힐 것이냐가 설계를 결정한다.