PythonでLanguage Implementation Patternsのパーサと戯れる Packratパーサのメモリ効率化
前回まで見てきたBacktrackingパーサ、Packratパーサは「これまで見たすべてのトークン」をメモリ上のバッファに保持し続け、それらに対してのパース結果もすべてキャッシュに残し続ける実装になっていて、パース終了直前にはソースファイルのすべてのトークンがメモリに乗っている状態になってしまう。
実際にはバックトラックする予定がない場合、現在地以前にあるバッファのトークンを消してしまってもなんの問題もないし、それに対応するパース関数のキャッシュも削除できる。今回はその修正の話。
計測
まずparse関数をいじってパース終了時にtokens.bufferをプリントするようにする：
def parse(char_stream): _clear_caches() tokens = Backtrackable(xl.lex(char_stream), 2) _list(tokens) _match(tokens, t.Eof) print(tokens.buffer) # ここを追加
使ってみる：
>>> parse("[abc=xyz, [d, [e]=[x], f, g], x, [y=z]=[a,b]]") [Lbrack(), Ident(s='abc'), Equal(), Ident(s='xyz'), Comma(), Lbrack(), Ident(s='d'), Comma(), Lbrack(), Ident(s='e'), Rbrack(), Equal(), Lbrack(), Ident(s='x'), Rbrack(), Comma(), Ident(s='f'), Comma(), Ident(s='g'), Rbrack(), Comma(), Ident(s='x'), Comma(), Lbrack(), Ident(s='y'), Equal(), Ident(s='z'), Rbrack(), Equal(), Lbrack(), Ident(s='a'), Comma(), Ident(s='b'), Rbrack(), Rbrack(), Eof()]
先頭の(からEofまですべてのトークンが保持されているのがわかる。
パーサ関数のキャッシュも確認：
>>> _caches
[{1: 4, 6: 7, 9: 10, 13: 14, 8: 15, 16: 17, 18: 19, 5: 20, 21: 22, 24: 27, 30: 31, 32: 33, 23: 34}, {8: 11, 12: 15, 5: 20, 23: 28, 29: 34, 0: 35}, {9: 10, 13: 14, 6: 19, 24: 27, 30: 33, 1: 34}, {1: 4, 5: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 6: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 8: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 9: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>"), 13: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>"), 16: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 18: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>"), 21: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 24: 27, 30: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 32: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>")}, {8: 15, 5: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 23: 34}, {5: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 6: 7, 8: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 9: 10, 13: 14, 16: 17, 18: 19, 21: 22, 23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 30: 31, 32: 33}]
やはり最初の方からすべて保持されている。
Backtrackableのbuffer
Backtrackableは今までバッファとしてただのPython listを使っていたが、その代替として「クリアできるバッファ」クラスを定義する：
class ClearableBuffer: def __init__(self): self._buffer = [] self._start = 0 def __getitem__(self, key): if 0 <= key < self._start: raise IndexError(f"Invalid access of index {key} for ClearableBuffer starting at {self._start}") return self._buffer[key - self._start] def __len__(self): return self._start + len(self._buffer) def __repr__(self): return repr(self._buffer) def append(self, item): self._buffer.append(item) def clear(self): if not self._buffer: return self._start += len(self._buffer) - 1 self._buffer = self._buffer[-1:]
ほとんどListと同じAPIとなるが、x.clear()すると最後の要素だけ残して他の要素は消される。しかしアクセス用のインデックスはズレない。クリアされた要素のインデックスにアクセスしようとするとエラーになる。
使用例：
>>> xs = ClearableBuffer() >>> for x in range(10): ... xs.append(x) ... >>> xs [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] >>> xs[9] 9 >>> xs.clear() >>> xs [9] >>> for x in range(10, 20): ... xs.append(x) ... >>> xs [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] >>> xs[9] 9 >>> xs[8] Traceback (most recent call last): ... IndexError: Invalid access of index 8 for ClearableBuffer starting at 9
このClearableBufferをBacktrackableクラスに持たせ、try_clearメソッドを追加する：
class Backtrackable: def __init__(self, input_, sentinel=None): self._stream = iter(input_) self.sentinel = sentinel self.i = 0 self.buffer = ClearableBuffer() # ここを変更 self.backtrack_points = [] ... def try_clear(self): if self.backtrack_points or (self.i < len(self.buffer)-1) or (len(self.buffer) < 2): return False self.buffer.clear() return True
try_clearメソッドは「トークンストリームのバッファをクリアできる条件が整っているならする、そして成否を結果として返す」という関数。クリアできる条件というのは
- バックトラック予定ではない =
self.backtrack_pointsが空 - 現在のトークンストリームの位置がバッファの最後の要素を指している
- バッファに要素が２個以上含まれている
のすべてが満たされているというもの。
パーサ本体
この拡張を使って、パーサ関数側で折を見てバッファとキャッシュをクリアする処理を追加する。
例によってデコレータとして実装：
def _buffer_cache_clear(func): @functools.wraps(func) def f(tokens): if tokens.try_clear(): _clear_caches() func(tokens) return f
バッファがクリアされた場合、キャッシュに残っているデータも必要なくなっているので同時にクリアする。前回の記事ではparse関数が呼び出されるごとに使っていた_clear_caches()をパース中にも使うようになる。
このデコレータで各パース関数を修飾する：
@_buffer_cache_clear @_memo def _list(tokens): _match(tokens, t.Lbrack) _elements(tokens) _match(tokens, t.Rbrack)
例によって他のパース関数も同じくデコレータを追加。
これでパース関数が相互再帰的に呼び出されるたびに「バッファとキャッシュがクリアできるか調べて、条件が合えばクリア」という処理が走るようになる。
使ってみる
>>> parse("[abc=xyz, [d, [e]=[x], f, g], x, [y=z]=[a,b]]") [Comma(), Lbrack(), Ident(s='y'), Equal(), Ident(s='z'), Rbrack(), Equal(), Lbrack(), Ident(s='a'), Comma(), Ident(s='b'), Rbrack(), Rbrack(), Eof()] >>> _caches [{24: 27, 30: 31, 32: 33, 23: 34}, {23: 28, 29: 34, 0: 35}, {24: 27, 30: 33, 1: 34}, {23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 24: 27, 30: ValueError("Failed to match Comma() to type <class 'xtokens.Equal'>"), 32: ValueError("Failed to match Rbrack() to type <class 'xtokens.Equal'>")}, {23: 34}, {23: ValueError("Failed to match Lbrack() to type <class 'xtokens.Ident'>"), 30: 31, 32: 33}]
パース終了時のバッファもキャッシュも元々に比べて減っているのがわかる。
今回のコード
次回
未定
