Améliorer l'efficacité de la mémoire dans un interprète fonctionnel

Les durées de vie sont une caractéristique fascinante de Rust et de l'expérience humaine. Il s’agit d’un blog technique, alors concentrons-nous sur le premier. J'ai certes été un adepte lent à tirer parti des durées de vie pour emprunter des données en toute sécurité dans Rust. Dans l'implémentation treewalk de Memphis, mon interpréteur Python écrit en Rust, j'exploite à peine les durées de vie (en clonant sans cesse) et j'échappe à plusieurs reprises au vérificateur d'emprunt (en utilisant la mutabilité intérieure, également sans cesse) chaque fois que possible.

Mes chers Rustacés, je suis là aujourd'hui pour vous dire que cela se termine maintenant. Lisez mes lèvres… plus de raccourcis.

D’accord, d’accord, soyons réalistes. Qu’est-ce qu’un raccourci ou quelle est la bonne méthode est une question de priorités et de perspective. Nous avons tous commis des erreurs et je suis ici pour assumer la responsabilité des miennes.

J'ai commencé à écrire un interprète six semaines après avoir installé rustc pour la première fois parce que je n'ai pas froid aux yeux. Une fois ces harangues et ces postures écartées, commençons la conférence d'aujourd'hui sur la façon dont nous pouvons utiliser les vies comme bouée de sauvetage pour améliorer la base de code de mon interprète gonflé.

Identifier et éviter les données clonées

Une durée de vie Rust est un mécanisme qui fournit une garantie au moment de la compilation que les références ne survivent pas aux objets auxquels elles font référence. Ils nous permettent d'éviter le problème du « pointeur suspendu » de C et C.

Cela suppose que vous les exploitiez ! Le clonage est une solution de contournement pratique lorsque vous souhaitez éviter les complexités associées à la gestion des durées de vie, même si l'inconvénient est une utilisation accrue de la mémoire et un léger délai lié à chaque fois que les données sont copiées.

Utiliser des durées de vie vous oblige également à penser de manière plus idiomatique aux propriétaires et aux emprunts à Rust, ce que j'avais hâte de faire.

J'ai choisi mon premier candidat comme jetons à partir d'un fichier d'entrée Python. Mon implémentation originale, qui s'appuyait fortement sur les conseils de ChatGPT alors que j'étais assis sur Amtrak, utilisait ce flux :

1. nous transmettons notre texte Python à un Builder
2. le constructeur crée un Lexer, qui tokenise le flux d'entrée
3. le constructeur crée ensuite un analyseur, qui clone le flux de jetons pour conserver sa propre copie
4. le constructeur est utilisé pour créer un interprète, qui demande à plusieurs reprises à l'analyseur sa prochaine instruction analysée et l'évalue jusqu'à ce que nous atteignions la fin du flux de jetons

L'aspect pratique du clonage du flux de jetons est que le Lexer pouvait être supprimé librement après l'étape 3. En mettant à jour mon architecture pour que le Lexer soit propriétaire des jetons et que l'analyseur se contente de les emprunter, le Lexer devrait désormais rester vivre beaucoup plus longtemps. Les durées de vie de Rust nous le garantiraient : tant que l'analyseur existerait avec une référence à un jeton emprunté, le compilateur garantirait que le Lexer qui possède ces jetons existe toujours, garantissant une référence valide.

Comme toujours tout code, cela a fini par être un changement plus important que ce à quoi je m'attendais. Voyons pourquoi !

Le nouvel analyseur

Avant de mettre à jour l'analyseur pour emprunter les jetons du Lexer, cela ressemblait à ceci. Les deux domaines d’intérêt pour la discussion d’aujourd’hui sont les jetons et current_token. Nous n'avons aucune idée de la taille du Vec l'est, mais il nous appartient distinctement (c'est-à-dire que nous ne l'empruntons pas).

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

Après avoir emprunté les jetons au Lexer, cela semble assez similaire, mais maintenant nous voyons une VIE ! En connectant les jetons à la durée de vie 'a, le compilateur Rust ne permettra pas au propriétaire des jetons (qui est notre Lexer) et aux jetons eux-mêmes d'être supprimés pendant que notre analyseur les référence toujours. Cela semble sûr et sophistiqué !

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

Une autre petite différence que vous remarquerez peut-être est cette ligne :

static EOF: Token = Token::Eof;

Il s'agit d'une petite optimisation à laquelle j'ai commencé à réfléchir une fois que mon analyseur évoluait dans la direction d'une « mémoire efficace ». Plutôt que d'instancier un nouveau Token::Eof chaque fois que l'analyseur doit vérifier s'il se trouve à la fin du flux de texte, le nouveau modèle m'a permis d'instancier un seul jeton et de référencer &EOF à plusieurs reprises.

Encore une fois, il s'agit d'une petite optimisation, mais elle témoigne de l'état d'esprit plus large de chaque élément de données n'existant qu'une seule fois en mémoire et chaque consommateur y faisant simplement référence en cas de besoin, ce que Rust vous encourage à faire et vous tient confortablement la main. le chemin.

En parlant d'optimisation, j'aurais vraiment dû comparer l'utilisation de la mémoire avant et après. Comme je ne l'ai pas fait, je n'ai plus rien à dire à ce sujet.

Comme je l'ai mentionné plus tôt, lier la durée de vie de mon Lexer et de mon Parser a un impact important sur mon modèle Builder. Voyons à quoi cela ressemble !

Le nouveau constructeur : MemphisContext

Dans le flux que j'ai décrit ci-dessus, vous vous souvenez de la façon dont j'ai mentionné que le Lexer pouvait être supprimé dès que l'analyseur créait sa propre copie des jetons ? Cela avait involontairement influencé la conception de mon Builder, qui était destiné à être le composant prenant en charge l'orchestration des interactions Lexer, Parser et Interpreter, que vous commenciez par un flux de texte Python ou un chemin vers un fichier Python.

Comme vous pouvez le voir ci-dessous, il y a quelques autres aspects non idéaux dans cette conception :

1. besoin d'appeler une méthode dangereuse de downcast pour obtenir l'interprète.
2. pourquoi ai-je pensé qu'il était acceptable de renvoyer un analyseur à chaque test unitaire juste pour ensuite le renvoyer directement dansinterpreter.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()))
            );
        }
    }
}

Ci-dessous se trouve la nouvelle interface MemphisContext. Ce mécanisme gère la durée de vie de Lexer en interne (pour garder nos références actives suffisamment longtemps pour que notre analyseur soit heureux !) et n'expose que ce qui est nécessaire pour exécuter ce test.

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() est encore un peu maladroit et parle d'un autre problème de conception que je pourrais résoudre plus tard : lorsque vous exécutez l'interpréteur, souhaitez-vous renvoyer uniquement la valeur de retour finale ou quelque chose qui vous permet d'accéder à des valeurs arbitraires de la table des symboles ? Cette méthode opte pour cette dernière approche. En fait, je pense qu'il y a lieu de faire les deux, et je continuerai à peaufiner mon API pour permettre cela au fur et à mesure.

Soit dit en passant, ce changement a amélioré ma capacité à évaluer un morceau arbitraire de code Python. Si vous vous souvenez de ma saga WebAssembly, je devais compter sur mon recoupement TreewalkAdapter pour le faire à l'époque. Désormais, notre interface Wasm est beaucoup plus propre.

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

L'interface context.evaluate_oneshot() renvoie le résultat de l'expression plutôt qu'une table de symboles complète. Je me demande s'il existe un meilleur moyen de garantir que l'une des méthodes « oneshot » ne peut fonctionner qu'une seule fois sur un contexte, garantissant ainsi qu'aucun consommateur ne les utilise dans un contexte avec état. Je vais continuer à mijoter là-dessus !

Est-ce que cela en valait la peine ?

Memphis est avant tout un exercice d'apprentissage, donc cela en valait vraiment la peine !

En plus de partager les jetons entre le Lexer et le Parser, j'ai créé une interface pour évaluer le code Python avec beaucoup moins de passe-partout. Bien que le partage de données ait introduit une complexité supplémentaire, ces changements apportent des avantages évidents : une utilisation réduite de la mémoire, des garanties de sécurité améliorées grâce à une gestion plus stricte de la durée de vie et une API rationalisée, plus facile à maintenir et à étendre.

Je choisis de croire que c’était la bonne approche, principalement pour maintenir mon estime de soi. En fin de compte, mon objectif est d'écrire du code qui reflète clairement les principes du génie logiciel et informatique. Nous pouvons désormais ouvrir la source Memphis, désigner l'unique propriétaire des jetons et dormir tranquille la nuit !

Abonnez-vous et économisez [sur rien]

Si vous souhaitez recevoir plus de messages comme celui-ci directement dans votre boîte de réception, vous pouvez vous abonner ici !

Autre part

En plus d'encadrer des ingénieurs logiciels, j'écris également sur mon expérience de travail indépendant et d'autisme diagnostiqué tardivement. Moins de code et le même nombre de blagues.

• Café effet lac, chapitre 1 - From Scratch dot org

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!