Сопоставление байт-кода с исходным кодом

Заметки по итогам решения задач из главы 14 книги Роберта Найстрома (Robert Nystrom) Crafting Interpreters. Задача: когда инструкция байт-кода падает во время выполнения, VM должна указать сгенерировавшую её строку исходного кода, поэтому чанку нужна таблица строк (line table). Самое интересное здесь в том, что очевидное сжатие ухудшает произвольный поиск (random lookup), а решением оказывается классическая задача из университетских курсов по алгоритмам.

Байт-код в книге хранится в чанке (chunk) - плоской последовательности байтов, где каждый байт является либо кодом операции (opcode), либо операндом. Инструкции имеют переменную длину: OP_RETURN занимает один байт, за OP_CONSTANT следует индекс в пуле констант чанка. Эта переменная длина принципиальна: ошибка во время выполнения сообщает именно смещение, а не индекс инструкции.

Параллельный массив

Хранить массив lines рядом с code, по одной записи на байт:

offset:       0  1  2  3  4  5  6  7
code:        00 01 00 02 01 00 03 01
line:         1  1  1  1  1  2  2  2

Поиск за O(1), расход памяти O(n). Избыточность очевидна: идущие подряд байты обычно относятся к одной и той же строке.

Кодирование длин серий (RLE)

Хранить каждую строку один раз вместе с количеством относящихся к ней байтов. Если обозначить количество байтов байт-кода как n, а число серий (runs) как r, пример выше превратится в (5, 1) (3, 2), где n = 8 и r = 2. В общем случае 1 <= r <= n: лучший сценарий - весь чанк относится к одной строке, худший - строка меняется после каждого байта. Память сокращается с O(n) до O(r).

Произвольный поиск теперь стоит O(r), поскольку для поиска серии, покрывающей смещение, нужно суммировать длины серий с самого начала. Если делать это для каждого байта при дизассемблировании, получается O(nr), а в худшем случае O(n²). Но эта квадратичная сложность - следствие реализации дизассемблера, а не самого кодирования: поскольку дизассемблер обходит смещения по возрастанию, хранение курсора на текущей серии позволяет обойти каждый байт и каждую серию ровно один раз, давая O(n + r) - то есть O(n), так как r <= n.

Курсор решает проблему последовательного обхода, но ничем не помогает в сценарии, ради которого таблица строк изначально создавалась. При ошибке выполнения мы получаем смещение в середине чанка, и добраться до него по-прежнему нельзя никак, кроме как сканированием с начала.

Начальные смещения и задача о статическом предшественнике

Записывать, где каждая серия начинается, вместо того сколько она длится:

offset:          0  1  2 | 3  4 | 5
line:            1  1  1 | 2  2 | 3
starting pairs: (0, 1)    (3, 2) (5, 3)

Поиск строки для смещения 4 означает поиск наибольшего начального смещения, меньшего или равного 4. Это задача о статическом предшественнике (static predecessor problem) - автор наткнулся на это название в первой лекции гарвардского курса CS224, где также рассматриваются динамический вариант и модель word RAM.

Поскольку пары отсортированы (байт-код добавляется последовательно), модифицированный двоичный поиск решает задачу за O(log r). Модификация заключается в поведении при отсутствии точного совпадения: left и right перекрещиваются, и 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 остаётся отсортированным - здесь несущие, а не декоративные. right имеет тип usize, а поиск выполняет right = mid - 1, поэтому для сообщения об отсутствии смещения меньше первого записанного начала переменная должна была бы переполниться снизу (underflow). Этого не происходит, поскольку первая пара всегда начинается со смещения 0, а корректное смещение не может быть меньше нуля, однако в самом коде нет никакой проверки между нарушением инварианта и багом.

В итоге оба паттерна доступа уживаются без необходимости выбирать что-то одно: двоичный поиск для произвольного смещения из отчёта об ошибке и сдвиг курсора для упорядоченного дизассемблирования - и всё это поверх одной и той же структуры данных.

Что делают промышленные VM

LineNumberTable в JVM представляет собой как раз вариант с начальными смещениями в виде опционального атрибута внутри атрибута Code каждого метода, где записи (start_pc, line_number) отмечают начало каждой строки исходного кода. Примечательно, что спецификация не требует сортировки этих записей, что исключает двоичный поиск: line_number_from_bci в HotSpot выполняет линейный поиск предшественника.

Lua хранит параллельный массив, как в первом варианте из книги, но вместо абсолютного номера строки записывает однобайтовую дельту относительно предыдущей строки, периодически вставляя абсолютные контрольные точки (checkpoints), когда дельта не помещается в один байт:

instruction:  0   1    2    3    4
source line: 10  10  300  310   314
lineinfo:     0   0  ABS   +10   +4

Чтение инструкции 4 означает начало с контрольной точки на строке 300 и суммирование вперёд: 300 + 10 + 4 = 314. Это профиль потребления памяти параллельного массива, сжатый до одного байта на инструкцию, где контрольные точки ограничивают глубину необходимого сканирования.

О контексте виртуальных машин байт-кода, в котором всё это работает: заметка retrofitting-jit-c-interpreters рассказывает, что происходит с интерпретатором подобного вида при добавлении под него JIT-компилятора. intro-compilers-language-design описывает классический путь по тому же конвейеру со стороны фронтенда, а virtual-machines-versatile-platforms даёт систематику виртуальных машин, внутри которых и живёт эта таблица строк.