『解釈器の設計』第 14 章：行番号情報のメモリ効率化と高速検索

ロバート・ニストロムの『解釈器の設計』第 14 章の問題集に取り組む際に出会う課題です。
注釈: 実際の仮想機械（VM）はより高度な機能を持ちますが、本稿の末尾では JVM や Lua などの実装における同様の手法について触れます。

背景

本書前半ではトップダウンアプローチで言語

jlox

を実装し、後半ではバイトコード構造から始めるボトムアップアプローチで再実装します。
実行時のエラーハンドリングにおいて、VM はバイトコードのオフセットをソースコードの行番号に変換する必要があります。そのため、チャンクに線形情報（行番号情報）を格納する必要があります。

単純な解法とその課題

バイトコードと並列に第 2 の配列

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) の検索が可能。
• 欠点: n バイトのコードに対して O(n) のメモリを必要とする。

改善案：連続行番号の活用

上記の例から、「連続する複数のバイトが同じソース行に属する」という事実を活用できます。

ランレングス符号化（Run-length encoding）

各行番号を 1 つだけ格納しつつ、その行に属する連続するバイト数も記録します。

バイトあたりの行番号: 1  1  1  1  1 | 2  2  2
符号化された走査区間:          (5, 1) |   (3, 2)
                           回数、行番号

• ( n ): バイトコードのバイト数
• ( r ): 連続する行番号区間の数
• メモリ使用量は O(n) から O(r) に削減されます。

アクセス方法と性能分析

ランダムなオフセット検索を行う際の方法論とその計算コストです。

1. 線形探索（新しい走査区間を生成）

各区間の長さを累積しながら走査します。

• ランダム検索: O(r)
• 全走査: O(nr)、最悪で O(n²) に発散する可能性あり。

2. 単一通り走査（カーソル保持）

ディスアセンブラが昇順にオフセットを訪れる場合、現在の走査区間を示すカーソルを保持します。

• メリット: 各区間と各バイトは最大 1 回ずつしか訪れず、処理時間は O(n) と同値になります。
• デメリット: ランダムなオフセット検索への対応は改善せず、依然として O(r) です。エラー発生時に先頭から探索せざるを得ない場合があるためです。

前驱者問題（Predecessor problem）へのアプローチ

走査区間の長さを記録する代わりに、各区間の開始オフセットを記録します。

オフセット:          0  1  2 | 3  4 | 5
行番号:            1  1  1 | 2  2 | 3
開始ペア:           (0, 1)    (3, 2) (5, 3)

これは静的な**前驱者問題（Static Predecessor Problem）**と等価です。

解法 A: バイナリ検索

ソートされた開始オフセット配列

line_starts

を使用します。

• 原理: ターゲットオフセットより「小さく、または等しい最大の開始オフセット」を探す。
• 計算量: O(log r)
• 実装例（Rust）:

  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;
          }
      }
      // 完全一致がない場合、right が指すペアが答え（ターゲット未満の最大オフセット）
      let (_, line) = chunk.line_starts[right];
      line
  }
  

解法 B: 開始オフセットを用いた単一通り走査

バイナリ検索と同様にソートされたデータを保持しつつ、順次走査時はカーソルを使用します。

• ランダム検索: O(log r)（バイナリ検索を活用）
• 全走査: O(n)（カーソルを前方のみ進めるため）

結論: このデータ構造は、ランダムアクセスと順次走査の両方の要求事項を満たします。

実行時間分析まとめ

アプローチ	メモリ	ランダム検索	全走査
バイトごとの行番号	O(n)	O(1)	O(n)
ランレングス + 線形探索	O(r)	O(r)	O(nr), 最悪 O(n²)
ランレングス + カーソル	O(r)	O(r)	O(n)
開始オフセット + バイナリ検索	O(r)	O(log r)	O(n log r)
開始オフセット + カーソル	O(r)	*O(log r) **	O(n)

* 任意のオフセットへの検索が必要な場合のみ。順次走査時は O(n) を維持します。

他の VM がこの問題を取り扱う方法

JVM

• LineNumberTable

  は、本質的に開始オフセット形式を使用しています。
• HotSpot VM は仕様でソートを要求せず、検索時に線形探索を行いますが、実装上の最適化が加えられています。

Lua

Lua は並列配列で情報を格納しますが、アプローチが異なります（Writer/Reader パターン）。

• 方式: 命令ごとに正確な行番号を保存するのではなく、**前の行からの差分（デルタ）**を保存します。
• 例外: 稀に絶対的なチェックポイント (

  source

  ) を配置して、検索走査の長さを有界に保ちます。

動作例:

命令:      0    1     2     3     4
ソース行:  10   10   300   310    314
lineinfo:  0    0   ABS   +10     +4

• ABS

  が絶対チェックポイント

  (pc 2, line 300)

  です。
• 命令 4 の行番号は、チェックポイントからデルタを加算して計算します：
  ( 300 + 10 + 4 = 314 )

参考文献と補足

この研究の過程で、ハーバード大学の CS224「Advanced Algorithms」で**静的な前驱者問題（Static Predecessor Problem）**という正式な名称を知りました。動的な前驱者問題や Word RAM モデルについても考察されていますが、ここでは概要のみを参照しています。

補足: ソートされたキー配列に対し、与えられた値より小さくまたは等しい最大のキーを見つける問題を指します。データ構造の変更を伴わない点が動的な問題との違いです。