作業中のインタープリタでのメモリ効率の向上

ライフタイムは、Rust と人間の経験の魅力的な機能です。これは技術的なブログなので、前者に焦点を当てましょう。確かに私は、Rust でデータを安全に借用するためにライフタイムを活用するのが遅かったです。 Rust で書かれた私の Python インタプリタである Memphis のツリーウォーク実装では、(絶え間なくクローンを作成することによって) ライフタイムをほとんど利用せず、可能な限り (これも絶え間なく内部可変性を使用することによって) 借用チェッカーを繰り返し回避しています。

Rustacean の皆さん、私は今日ここに来て、これがもう終わったことをお伝えします。私の唇を読んでください……もう近道はありません。

わかりました、わかりました、本当のことを言いましょう。何が近道であり、何が正しい方法であるかは、優先順位と視点の問題です。私たちは皆、間違いを犯したことがあります。私は自分の責任を取るためにここにいます。

私は、rustc を最初にインストールしてから 6 週間後にインタープリタを書き始めました。寒気がしなかったからです。そのような嫌がらせや態度はさておき、肥大化したインタープリターのコードベースを改善するためにライフラインをライフラインとして使用する方法について、今日の講義を始めましょう。

クローンデータの特定と回避

Rust のライフタイムは、参照が参照先のオブジェクトより長く存続しないことをコンパイル時に保証するメカニズムです。これらにより、 C と C の「ダングリング ポインター」問題を回避できます。

これは、それらを活用することを前提としています。クローン作成は、ライフタイムの管理に伴う複雑さを回避したい場合に便利な回避策ですが、メモリ使用量が増加し、データがコピーされるたびに若干の遅延が発生するという欠点があります。

ライフタイムを使用すると、Rust での所有者と借入についてより慣用的に考える必要があります。これは私が熱望していたことです。

最初の候補を Python 入力ファイルからのトークンとして選択しました。私の元の実装では、アムトラックに乗っていたときに ChatGPT ガイダンスに大きく依存しており、次のフローを使用していました。

1. Python テキストをビルダーに渡します
2. ビルダーは入力ストリームをトークン化するレクサーを作成します
3. その後、ビルダーはパーサーを作成し、トークン ストリームのクローンを作成して独自のコピーを保持します
4. ビルダーはインタープリターを作成するために使用されます。インタープリターは、パーサーに次の解析済みステートメントを繰り返し要求し、トークン ストリームの最後に到達するまでそれを評価します

トークン ストリームのクローン作成の便利な点は、ステップ 3 の後にレクサーを自由に削除できることです。レクサーがトークンを所有し、パーサーがトークンを借用するようにアーキテクチャを更新すると、レクサーはそのままにしておく必要があります。もっと長く生きています。 Rust のライフタイムはこれを保証します。借用したトークンへの参照を保持するパーサーが存在する限り、コンパイラーはそれらのトークンを所有するレクサーがまだ存在していることを保証し、有効な参照を保証します。

すべてのコードと同様に、これも予想よりも大きな変更となりました。その理由を見てみましょう!

新しいパーサー

レクサーからトークンを借用するためにパーサーを更新する前は、次のようになっていました。今日の議論で関心のある 2 つのフィールドは、token と current_token です。 Vec がどれほどの大きさであるかはわかりません。ですが、それは明らかに私たちのものです（つまり、私たちが借りているわけではありません）。

pub struct Parser {
    state: Container<State>,
    tokens: Vec<Token>,
    current_token: Token,
    position: usize,
    line_number: usize,
    delimiter_depth: usize,
}

impl Parser {
    pub fn new(tokens: Vec<Token>, state: Container<State>) -> Self {
        let current_token = tokens.first().cloned().unwrap_or(Token::Eof);
        Parser {
            state,
            tokens,
            current_token,
            position: 0,
            line_number: 1,
            delimiter_depth: 0,
        }
    }
}

レクサーからトークンを借りた後はかなり似ていますが、今度は LIFETIME! が表示されます。トークンをライフタイム 'a に接続することで、Rust コンパイラは、パーサーがまだトークンを参照している間、トークンの所有者 (レクサー) とトークン自体を削除することを許可しません。これは安全でおしゃれな感じです!

static EOF: Token = Token::Eof;

/// A recursive-descent parser which attempts to encode the full Python grammar.
pub struct Parser<'a> {
    state: Container<State>,
    tokens: &'a [Token],
    current_token: &'a Token,
    position: usize,
    line_number: usize,
    delimiter_depth: usize,
}

impl<'a> Parser<'a> {
    pub fn new(tokens: &'a [Token], state: Container<State>) -> Self {
        let current_token = tokens.first().unwrap_or(&EOF);
        Parser {
            state,
            tokens,
            current_token,
            position: 0,
            line_number: 1,
            delimiter_depth: 0,
        }
    }
}

もう 1 つの小さな違いに気づくかもしれませんが、次の行です。

static EOF: Token = Token::Eof;

これは、パーサーが「メモリ効率の高い」方向に進んでから検討し始めた小さな最適化です。パーサーがテキスト ストリームの最後にあるかどうかを確認する必要があるたびに新しい Token::Eof をインスタンス化するのではなく、新しいモデルでは 1 つのトークンのみをインスタンス化し、&EOF を繰り返し参照することができました。

繰り返しになりますが、これは小さな最適化ですが、各データはメモリ内に 1 回だけ存在し、すべてのコンシューマは必要なときにそれを参照するだけであるという、より大きな考え方を物語っています。Rust は、これを実行することを奨励し、しっかりとサポートします。

最適化と言えば、その前後でメモリ使用量のベンチマークを行うべきでした。私はそうしなかったので、この件に関してはこれ以上言うことはありません。

前にほのめかしたように、レクサーとパーサーの存続期間を結びつけることは、ビルダー パターンに大きな影響を与えます。それがどのようなものか見てみましょう!

新しいビルダー: MemphisContext

上で説明したフローで、パーサーがトークンの独自のコピーを作成するとすぐにレクサーが削除される可能性があると述べたことを覚えていますか?これは、Python テキスト ストリームから始めるか Python ファイルへのパスから始めるかに関係なく、レクサー、パーサー、およびインタープリターの相互作用の調整をサポートするコンポーネントになることを目的とした私のビルダーの設計に意図せず影響を与えていました。

以下に示すように、この設計には他にも理想的ではない側面がいくつかあります。

1. インタプリタを取得するには危険なダウンキャスト メソッドを呼び出す必要があります。
2. なぜ私は、すべての単体テストにパーサーを返して、すぐにinterpreter.run(&mut parser) に戻すだけで問題ないと思ったのでしょうか?!

fn downcast<T: InterpreterEntrypoint + 'static>(input: T) -> Interpreter {
    let any_ref: &dyn Any = &input as &dyn Any;
    any_ref.downcast_ref::<Interpreter>().unwrap().clone()
}

fn init(text: &str) -> (Parser, Interpreter) {
    let (parser, interpreter) = Builder::new().text(text).build();

    (parser, downcast(interpreter))
}


#[test]
fn function_definition() {
     let input = r#"
def add(x, y):
    return x + y

a = add(2, 3)
"#;
    let (mut parser, mut interpreter) = init(input);

    match interpreter.run(&mut parser) {
        Err(e) => panic!("Interpreter error: {:?}", e),
        Ok(_) => {
            assert_eq!(
                interpreter.state.read("a"),
                Some(ExprResult::Integer(5.store()))
            );
        }
    }
}

以下は新しい MemphisContext インターフェースです。このメカニズムは、レクサーの有効期間を内部で管理し (パーサーを満足させるのに十分な長さの参照を存続させるため)、このテストの実行に必要なもののみを公開します。

pub struct Parser {
    state: Container<State>,
    tokens: Vec<Token>,
    current_token: Token,
    position: usize,
    line_number: usize,
    delimiter_depth: usize,
}

impl Parser {
    pub fn new(tokens: Vec<Token>, state: Container<State>) -> Self {
        let current_token = tokens.first().cloned().unwrap_or(Token::Eof);
        Parser {
            state,
            tokens,
            current_token,
            position: 0,
            line_number: 1,
            delimiter_depth: 0,
        }
    }
}

context.run_and_return_interpreter() はまだ少し不格好で、今後取り組む可能性のある別の設計上の問題について話します。インタープリタを実行するときに、最終的な戻り値のみを返しますか、それとも任意の値にアクセスできるものを返しますか。シンボルテーブルから?この方法では後者のアプローチを選択します。実際には両方を行うケースもあると考えており、今後もこれを可能にするために API を微調整し続けます。

ちなみに、この変更により、Python コードの任意の部分を評価する能力が向上しました。私の WebAssembly 物語を思い出していただけると思いますが、当時、それを行うにはクロスチェック TreewalkAdapter に依存する必要がありました。 Wasm インターフェースがよりクリーンになりました。

static EOF: Token = Token::Eof;

/// A recursive-descent parser which attempts to encode the full Python grammar.
pub struct Parser<'a> {
    state: Container<State>,
    tokens: &'a [Token],
    current_token: &'a Token,
    position: usize,
    line_number: usize,
    delimiter_depth: usize,
}

impl<'a> Parser<'a> {
    pub fn new(tokens: &'a [Token], state: Container<State>) -> Self {
        let current_token = tokens.first().unwrap_or(&EOF);
        Parser {
            state,
            tokens,
            current_token,
            position: 0,
            line_number: 1,
            delimiter_depth: 0,
        }
    }
}

インターフェイス context.evaluate_oneshot() は、完全なシンボル テーブルではなく式の結果を返します。 「ワンショット」メソッドがコンテキスト上で 1 回だけ動作し、コンシューマがステートフル コンテキストでメソッドを使用しないようにする、より良い方法はないのだろうか。これからも煮詰めていきます！

これには価値がありましたか?

メンフィスは何よりも学習の場であるため、これは絶対に価値がありました!

レクサーとパーサーの間でトークンを共有することに加えて、ボイラープレートを大幅に減らして Python コードを評価するインターフェイスを作成しました。データの共有によりさらに複雑さが増しましたが、これらの変更により、メモリ使用量の削減、厳格なライフタイム管理による安全性保証の向上、保守と拡張が容易になった合理化された API など、明らかなメリットがもたらされました。

私は、主に自尊心を維持するために、これが正しいアプローチだったと信じることにしました。最終的には、ソフトウェアとコンピューター エンジニアリングの原則を明確に反映したコードを書くことを目指しています。これで、メンフィスのソースを開き、トークンの単一所有者を指定して、夜はぐっすり眠ることができるようになりました!

定期購入して [何もせずに] 節約しましょう

このような投稿をさらに直接受信トレイに受け取りたい場合は、ここから購読できます!

他の場所

私はソフトウェア エンジニアの指導に加えて、自営業や晩期に診断された自閉症を乗り越えた経験についても書いています。コードは減り、ジョークの数は同じです。

• Lake-Effect Coffee、第 1 章 - ゼロから作る dot org

以上が作業中のインタープリタでのメモリ効率の向上の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。