Verbesserung der Gedächtniseffizienz in einem funktionierenden Dolmetscher

Lebenszeiten sind ein faszinierendes Merkmal von Rust und der menschlichen Erfahrung. Da dies ein technischer Blog ist, konzentrieren wir uns auf ersteres. Zugegebenermaßen war ich ein langsamer Anwender, wenn es darum ging, Lebenszeiten zu nutzen, um Daten in Rust sicher auszuleihen. In der Treewalk-Implementierung von Memphis, meinem in Rust geschriebenen Python-Interpreter, nutze ich die Lebensdauern kaum aus (durch ununterbrochenes Klonen) und entgehe dem Borrow-Checker immer wieder (indem ich innere Veränderlichkeit verwende, ebenfalls ununterbrochen), wann immer es möglich ist.

Meine Rustaceaner, ich bin heute hier, um Ihnen zu sagen, dass dies jetzt endet. Lies von meinen Lippen … keine Abkürzungen mehr.

Okay, okay, seien wir ehrlich. Was eine Abkürzung ist und was der richtige Weg ist, ist eine Frage der Prioritäten und der Perspektive. Wir haben alle Fehler gemacht und ich bin hier, um die Verantwortung für meine zu übernehmen.

Ich habe sechs Wochen nach der ersten Installation von rustc angefangen, einen Dolmetscher zu schreiben, weil ich keine Gänsehaut habe. Nachdem wir dieses Reden und Gehabe hinter uns haben, beginnen wir mit der heutigen Vorlesung darüber, wie wir Lebenszeiten als Lebensader nutzen können, um meine aufgeblähte Interpreter-Codebasis zu verbessern.

Identifizieren und Vermeiden geklonter Daten

Eine Rust-Lebensdauer ist ein Mechanismus, der zur Kompilierungszeit garantiert, dass Referenzen die Objekte, auf die sie verweisen, nicht überleben. Sie ermöglichen es uns, das Problem des „baumelnden Zeigers“ von C und C zu vermeiden.

Dies setzt voraus, dass Sie sie überhaupt nutzen! Das Klonen ist eine praktische Problemumgehung, wenn Sie die Komplexität vermeiden möchten, die mit der Verwaltung von Lebensdauern verbunden ist. Der Nachteil ist jedoch eine erhöhte Speichernutzung und eine leichte Verzögerung bei jedem Kopieren von Daten.

Die Verwendung von Lebenszeiten zwingt Sie auch dazu, idiomatischer über Eigentümer und Kreditaufnahme in Rust nachzudenken, was ich unbedingt tun wollte.

Meinen ersten Kandidaten habe ich als Token aus einer Python-Eingabedatei ausgewählt. Meine ursprüngliche Implementierung, die sich während meiner Zeit bei Amtrak stark auf die ChatGPT-Anleitung stützte, verwendete diesen Ablauf:

1. Wir übergeben unseren Python-Text an einen Builder
2. Der Builder erstellt einen Lexer, der den Eingabestream tokenisiert
3. Der Builder erstellt dann einen Parser, der den Token-Stream klont, um eine eigene Kopie zu enthalten
4. Der Builder wird verwendet, um einen Interpreter zu erstellen, der den Parser wiederholt nach seiner nächsten geparsten Anweisung fragt und diese auswertet, bis wir das Ende des Token-Streams erreichen

Der praktische Aspekt des Klonens des Token-Streams besteht darin, dass der Lexer nach Schritt 3 gelöscht werden konnte. Durch die Aktualisierung meiner Architektur, sodass der Lexer die Token besitzt und der Parser sie nur ausleiht, müsste der Lexer nun bleiben viel länger am Leben. Rust-Lebenszeiten würden dies für uns garantieren: Solange der Parser existierte, der eine Referenz auf ein geliehenes Token hielt, würde der Compiler garantieren, dass der Lexer, dem diese Token gehören, noch existierte, was eine gültige Referenz gewährleistete.

Wie bei jedem Code war dies letztendlich eine größere Änderung, als ich erwartet hatte. Mal sehen warum!

Der neue Parser

Bevor der Parser aktualisiert wurde, um die Token vom Lexer auszuleihen, sah es so aus. Die beiden Interessengebiete für die heutige Diskussion sind Token und current_token. Wir haben keine Ahnung, wie groß der Vec ist, aber es gehört eindeutig uns (d. h. wir leihen es uns nicht aus).

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,
        }
    }
}

Nachdem wir uns die Token vom Lexer geliehen haben, sieht es ziemlich ähnlich aus, aber jetzt sehen wir ein LEBENSLANGES! Durch die Verknüpfung von Token mit der Lebensdauer 'a verhindert der Rust-Compiler, dass der Eigentümer der Token (unser Lexer) und die Token selbst gelöscht werden, während unser Parser noch auf sie verweist. Das fühlt sich sicher und schick an!

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,
        }
    }
}

Ein weiterer kleiner Unterschied, der Ihnen vielleicht auffällt, ist diese Zeile:

static EOF: Token = Token::Eof;

Dies ist eine kleine Optimierung, über die ich nachzudenken begann, als sich mein Parser in Richtung „speichereffizient“ bewegte. Anstatt jedes Mal ein neues Token::Eof zu instanziieren, wenn der Parser prüfen muss, ob es sich am Ende des Textstroms befindet, konnte ich mit dem neuen Modell nur ein einzelnes Token instanziieren und wiederholt auf &EOF verweisen.

Auch hier handelt es sich um eine kleine Optimierung, aber sie spiegelt die übergeordnete Denkweise wider, dass jedes Datenelement nur einmal im Speicher vorhanden ist und jeder Verbraucher bei Bedarf nur darauf verweist, wozu Rust Sie sowohl ermutigt als auch freundlich mitnimmt der Weg.

Apropos Optimierung: Ich hätte die Speichernutzung vorher und nachher wirklich vergleichen sollen. Da ich dies nicht getan habe, kann ich dazu nichts mehr sagen.

Wie ich bereits erwähnt habe, hat die Verknüpfung der Lebensdauer meines Lexers und Parsers einen großen Einfluss auf mein Builder-Muster. Mal sehen, wie das aussieht!

Der neue Builder: MemphisContext

Erinnern Sie sich daran, wie ich in dem oben beschriebenen Ablauf erwähnt habe, dass der Lexer gelöscht werden könnte, sobald der Parser seine eigene Kopie der Token erstellt hat? Dies hatte unbeabsichtigt Einfluss auf das Design meines Builders, der die Komponente sein sollte, die die Orchestrierung von Lexer-, Parser- und Interpreter-Interaktionen unterstützt, unabhängig davon, ob Sie mit einem Python-Textstream oder einem Pfad zu einer Python-Datei beginnen.

Wie Sie unten sehen können, gibt es bei diesem Design noch ein paar andere nicht ideale Aspekte:

1. Sie müssen eine gefährliche Downcast-Methode aufrufen, um den Interpreter zu erhalten.
2. Warum dachte ich, dass es in Ordnung sei, einen Parser zu jedem Unit-Test zurückzugeben, um ihn dann direkt wieder an interpreter.run(&mut parser) weiterzuleiten?!

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()))
            );
        }
    }
}

Unten finden Sie die neue MemphisContext-Schnittstelle. Dieser Mechanismus verwaltet die Lexer-Lebensdauer intern (um unsere Referenzen lange genug am Leben zu halten, damit unser Parser zufrieden ist!) und stellt nur das bereit, was zum Ausführen dieses Tests erforderlich ist.

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() ist immer noch etwas umständlich und weist auf ein weiteres Designproblem hin, das ich vielleicht später angehen werde: Wenn Sie den Interpreter ausführen, möchten Sie nur den endgültigen Rückgabewert zurückgeben oder etwas, das Ihnen den Zugriff auf beliebige Werte ermöglicht? aus der Symboltabelle? Diese Methode wählt den letztgenannten Ansatz. Ich denke tatsächlich, dass beides sinnvoll ist, und werde meine API weiterhin optimieren, um dies zu ermöglichen.

Übrigens hat diese Änderung meine Fähigkeit verbessert, einen beliebigen Teil des Python-Codes auszuwerten. Wenn Sie sich an meine WebAssembly-Saga erinnern, musste ich mich damals auf meinen Crosscheck-TreewalkAdapter verlassen, um das zu tun. Jetzt ist unsere Wasm-Schnittstelle viel sauberer.

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,
        }
    }
}

Die Schnittstelle context.evaluate_oneshot() gibt das Ausdrucksergebnis anstelle einer vollständigen Symboltabelle zurück. Ich frage mich, ob es eine bessere Möglichkeit gibt, sicherzustellen, dass eine der „Oneshot“-Methoden nur einmal auf einen Kontext angewendet werden kann, um sicherzustellen, dass kein Verbraucher sie in einem zustandsbehafteten Kontext verwendet. Daran werde ich weiter brodeln!

Hat sich das gelohnt?

Memphis ist in erster Linie eine Lernübung, das hat sich also absolut gelohnt!

Zusätzlich zur gemeinsamen Nutzung der Token zwischen Lexer und Parser habe ich eine Schnittstelle erstellt, um Python-Code mit deutlich weniger Boilerplate auszuwerten. Während das Teilen von Daten zu zusätzlicher Komplexität führte, bringen diese Änderungen klare Vorteile mit sich: geringere Speichernutzung, verbesserte Sicherheitsgarantien durch strengeres Lifetime-Management und eine optimierte API, die einfacher zu warten und zu erweitern ist.

Ich glaube, dass dies der richtige Ansatz war, vor allem, um mein Selbstwertgefühl zu bewahren. Letztendlich möchte ich Code schreiben, der die Prinzipien der Software- und Computertechnik klar widerspiegelt. Wir können jetzt die Memphis-Quelle öffnen, auf den einzelnen Besitzer der Token verweisen und nachts tief und fest schlafen!

Abonnieren und sparen [bei nichts]

Wenn Sie weitere Beiträge wie diesen direkt in Ihrem Posteingang erhalten möchten, können Sie sich hier anmelden!

Anderswo

Neben der Betreuung von Softwareentwicklern schreibe ich auch über meine Erfahrungen beim Umgang mit der Selbstständigkeit und spät diagnostiziertem Autismus. Weniger Code und die gleiche Anzahl an Witzen.

• Kaffee mit Seeeffekt, Kapitel 1 – Von Scratch dot org

Das obige ist der detaillierte Inhalt vonVerbesserung der Gedächtniseffizienz in einem funktionierenden Dolmetscher. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!