Clever Geek Handbook

Comment j'ai accéléré le moteur de 13%

Un article récent sur l'importance d'utiliser des algorithmes linéaires m'a inspiré pour optimiser la fonction quadratique "chaude", comment je l'ai fait et à quels résultats cela a conduit - je vais vous le dire aujourd'hui. Préparez du Pu Er dans une tasse, asseyez-vous dans votre fauteuil :



▍ — JavaScript



… , , . , , .



© « »
Au début de cette année code (ou à la fin de l' année dernière), un nouveau joueur est apparu parmi les putout moteurs analyseur statique : le moteur du processeur . Maintenant, vérifiez et corrigez non seulement can js(x)



, ts(x)



et les flow



fichiers, mais markdown



, yaml



, ignore



, json



et tous les autres qui implémentent le moteur d'interface.



Le processeur prend le JavaScript



code des fichiers et recolle le tout, par exemple, dans le processeur Markdown .

Soit convertit json



, yaml



et ignore



dans JavaScript



pour trouver et corriger les erreurs de plugins .



L'interface du processeur ressemble à ceci :



  • process(rawSource, {fix}) -> [processedSource, processedPlaces]



    - renvoie le code source traité ou les erreurs trouvées conformément au flag fix



    ;
  • preProcess(processedSource) -> preProcessedList



    - se retire JavaScript



    de processedSource



    la vérification et de correction;
  • postProcess(processedSource, preProcessedList) -> processedSource



    - colle les corrigés JavaScript



    ;


Le cœur de Putout se compose de 4 parties (moteurs) :



  • L'analyseur traduit une chaîne en AST



    et en AST



    arrière dans une chaîne ;
  • Le chargeur trouve et charge les plugins (y compris pour Babel



    ) et les mods de codejscodeshift



  • L'interprète reconnaît et traite toutes sortes de plugins (il y en a maintenant 4);
  • Le processeur contrôle le fonctionnement de la trinité précédente ;




Le plan de travail peut ressembler à ceci:

image



▍Nous recherchons des fonctions "chaudes"



Le truc, c'est que nous sommes constamment en train de faire un voyage qui s'est terminé une seconde avant que nous ayons eu le temps de partir.



© Victor Pelevin "Flèche Jaune"
Conformément à la loi de Pareto : 20% d'efforts correctement dirigés nous donneront 80% du résultat, donc la première chose qu'il est toujours logique de trouver les fonctions les plus « chaudes » et de travailler avec elles.



Tout d'abord, récupérez le isolate



fichier à l' node v14



aide de la clé --prof , exécutez-le à partir de la racine du référentiel : 



node --prof packages/putout/bin/putout.mjs --fresh .


Ensuite, nous allons le traiter à l'aide de la clé --prof-process



: 



 node --prof-process isolate-0x1049e5000-86428-v8.log > processed.txt


En parcourant les informations relatives à engine-processor



in, processed.txt



nous remarquons la ligne : 



334   93.6%            LazyCompile: *module.exports.runProcessors /Users/coderaiser/putout/packages/engine-processor/lib/processor.js:26:32


Oui, le moteur du processeur réalise 334 cycles d'horloge et 93,6% des appels lorsque la fonction parent est appelée.



Un peu sur Big O



Le passé est la locomotive qui entraîne l'avenir avec lui. Il arrive que ce soit le passé, en plus de celui de quelqu'un d'autre. Vous roulez dos en avant et vous ne voyez que ce qui a déjà disparu. Et pour descendre du train, il faut un ticket. Vous le tenez entre vos mains, mais à qui allez-vous le présenter ?



© Victor Pelevin "Flèche Jaune"
Pour une fonction fn



qui prend en entrée data



et renvoie result



: 



const result = fn(data);


Big O fournit des informations sur le scénario le plus pessimiste.

Le temps d'exécution fn



peut être obtenu à l'aide d'une fonction complexity



, elle prend en entrée operationsCount



: 



const time = complexity(operationsCount);


Le temps est exprimé dans une lettre n



, c'est plus pratique que d'utiliser des chiffres, car il y en a beaucoup, mais leur signification n'est pas particulièrement importante (on coupe le rasoir d'Occam ) : la technologie change, de nouveaux ordinateurs plus productifs remplacent les ordinateurs faibles . Ce qui compte vraiment, c'est la possibilité de comparer les algorithmes . Et ça existe ! Voici Big O , et voici ses exemples les plus simples :



  • O(1) — , , . , , : 



    time = complexity(2 + n);
O(1);

const fn = (name) => {
    const str = `hello ${name}`;
    return str;
}


  • O(n) — , , . 10 , 100 : 



    time = complexity(n * 10);
O(n);

const fn = (files) => {
    const results = [];

    for (const file of files) {
       results.push(processFile(file));
    }

    return results;
}


  • O(n^2) — , , . , n



    . runners



    5 , run



    10 , : 



    time = complexity(5 * 10);
O(n * n);

function process(runners) {
    const processed = [];

    for (const run of runners) {
        const files = run();

        for (const file of files) {
            processed.push(processFile(file));
        }

     return processed;
}






Optimiser



- Souvenez-vous, lorsqu'une personne cesse d'entendre le bruit des roues et accepte d'aller plus loin, elle devient passager.

- Personne ne nous demande si nous sommes d'accord ou non. Nous ne nous souvenons même pas comment nous sommes arrivés ici. Nous roulons juste et c'est tout. Rien ne subsiste.

- La chose la plus difficile dans la vie reste. Montez dans un train et ne soyez pas un passager.



© Victor Pelevin "Flèche Jaune"
Une version simplifiée du démarrage du Processor Engine contient une boucle dans une boucle, c'est-à-



dire qu'elle ressemble à ceci : 



function process(runners) {
    const processed = [];
    
    for (const run of runners) {
        const processed = run();
  
        for (const file of files) {
            processed.push(processFile(file));
        }
     
     return processed;
}


La version simplifiée et révisée contient deux boucles consécutives et



ressemble à ceci : 



function process(runners) {
    const processed = [];
  
    for (const run of runners) {
        files.push(...run());
    }
    
    for (const file of files) {
        processed.push(processFile(file));
    }
     return processed;
}


Et idéalement , les fonctions avec des boucles sont extraites et appelées à partir de la fonction principale : 



function process(runners) {
    const files = getFiles(runners);
    const linted = lintFiles(files);
    
    return linted;
}

function getFiles(runners) {
    const files = [];
    
    for (const run of runners) {
        files.push(...run());
    }
    
    return files;
}

function lintFiles(files) {
    const linted = [];
    
    for (const file of files) {
        linted.push(processFile(file));
    }
   
    return linted;
}


Nous prenons des mesures



Tout ce monde est une flèche jaune qui vous touche, un train sur lequel vous vous dirigez vers le pont détruit.



© Victor Pelevin "Flèche Jaune"
Pour prendre les mesures, j'ai utilisé time



. Ce n'est pas la méthode la plus précise, car le temps d'exécution peut varier considérablement sur différents ordinateurs, cependant, au sein d'un même système, le temps + est le même et la différence entre la plupart des exécutions n'est pas très significative. Par exemple, sur un Mac, le temps d'exécution est deux fois moins que sur un Linux distant, conformément aux caractéristiques, votre temps peut différer.



Quand j'écris, j'exécute putout



souvent des contrôles (déjà plus de) 1800 fichiers, et une minute et demie peut sembler peu, mais si vous le comparez au temps d'exécution de 3000 tests en 15 secondes, cela devient clair : il est de la place pour grandir! Ainsi, nous sélectionnerons une étiquette v17.5.0



et lancerons une nouvelle peluche à l'aide de redrun: 



git checkout v17.5.0 && time redrun fresh:lint
> putout . --fresh

real	1m32.712s
user	1m25.502s
sys	0m6.542s

git checkout master && time redrun fresh:lint
> putout . --fresh

real	1m20.898s
user	1m13.502s
sys	0m6.542s


Nous nous intéressons aux premières lignes : minute 33 secondes, et minute 20 secondes - c'est devenu plus rapide de 13 secondes, cela fait environ 12% à elles, nous ajoutons une mesure après optimisation à une variante idéale et nous obtenons tous 13%.



En répétant la recherche des fonctions "chaudes", on obtient les nombres suivants : 



   73   54.9%            LazyCompile: *module.exports.runProcessors /Users/coderaiser/putout/packages/engine-processor/lib/processor.js:26:32


Le nombre de cycles travaillés est 4 fois moindre, et les pourcentages sont passés de 93% à 54%, ce qui n'est pas une mauvaise chose en soi. Je serais reconnaissant si quelqu'un dans les commentaires développe les informations sur les données que le profileur enregistre dans le fichier.



Des conclusions de grande portée



, , , , , , “Fleetwood Mac”. , , . , , .



© « »


Grâce à l'optimisation, le code est devenu non seulement plus rapide à traiter, mais aussi plus facile à comprendre, et donc plus maintenable et extensible. Par conséquent, je déclare hardiment : l'optimisation des points « chauds » est la racine de toutes les bénédictions !



MISE À JOUR Apparemment, j'ai fait une erreur dans le calcul de la complexité algorithmique et ce que j'appelle l'algorithme linéaire est O (n * m) , merci beaucoup @Yavanosta,moins, nvgordeev    !  ,  , , Big O - . , V8.



▍

, , . , . : , , , . ? . , – ? , ».



© « »






More articles:


All Articles