Clever Geek Handbook

Cómo aceleré el motor en un 13%

Un artículo reciente sobre la importancia de usar algoritmos lineales me inspiró a optimizar la función cuadrática "caliente", cómo lo hice y qué resultados obtuvo. Te lo diré hoy. Prepare Pu Er en una taza, siéntese en su silla:



▍Todo - JavaScript



… En esencia, no hay felicidad, solo existe la conciencia de la felicidad. O, en otras palabras, solo hay conciencia.



© Victor Pelevin "Flecha amarilla"
A principios de este año de código (o al final del año pasado), un nuevo jugador apareció entre los putout motores analizador estático : el motor del procesador . Ahora comprobar y corregir no sólo puede js(x)



, ts(x)



y flow



archivos, pero markdown



, yaml



, ignore



, json



y cualquier otro que implementan la interfaz del motor.



El procesador toma el JavaScript



código de los archivos y vuelve a unir todo, por ejemplo, en el procesador Markdown .

O se convierte json



, yaml



y ignore



in JavaScript



para encontrar y corregir errores de complementos .



La interfaz del procesador se ve así:



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



    - devuelve el código fuente procesado o los errores encontrados de acuerdo con la bandera fix



    ;
  • preProcess(processedSource) -> preProcessedList



    - se retira JavaScript



    de processedSource



    la verificación y corrección;
  • postProcess(processedSource, preProcessedList) -> processedSource



    - pega el corregido JavaScript



    ;


El corazón de Putout consta de 4 partes (motores):



  • El analizador traduce una cadena AST



    y AST



    vuelve a convertirla en una cadena;
  • El cargador busca y carga complementos (incluso para Babel



    ) y modificaciones de códigojscodeshift



  • El ejecutante reconoce y procesa todo tipo de complementos (ahora hay 4 de ellos);
  • El procesador controla el funcionamiento de la trinidad anterior;




El esquema de trabajo puede verse así:

imagen



▍Buscamos funciones "calientes"



El caso es que constantemente estamos en un viaje que terminó un segundo antes de que tuviéramos tiempo de irnos.



© Victor Pelevin "Flecha amarilla"
De acuerdo con la ley de Pareto : el 20% de los esfuerzos correctamente dirigidos nos dará el 80% del resultado, por lo que lo primero que siempre tiene sentido es encontrar las funciones “más calientes” y trabajar con ellas.



Primero, obtenga el isolate



-file node v14



usando la clave --prof , ejecútelo desde la raíz del repositorio: 



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


Luego lo procesaremos usando la clave --prof-process



: 



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


Al examinar la información relacionada con engine-processor



, processed.txt



notamos la línea: 



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


Sí, el motor del procesador cumple 334 ciclos de reloj y el 93,6% de las llamadas cuando se llama a la función principal.



▍Un poco sobre Big O



El pasado es la locomotora que arrastra al futuro. Sucede que este es el pasado, además del de otra persona. Conduces con la espalda hacia adelante y solo ves lo que ya ha desaparecido. Y para bajarse del tren, necesita un boleto. Lo tiene en sus manos, pero ¿a quién se lo presentará?



© Victor Pelevin "Flecha amarilla"
Para una función fn



que toma como entrada data



y devuelve result



: 



const result = fn(data);


Big O proporciona información sobre el escenario más pesimista.

El tiempo de ejecución fn



se puede obtener mediante una función complexity



, toma como entrada operationsCount



: 



const time = complexity(operationsCount);


El tiempo se expresa en una letra n



, es más conveniente que usar números, ya que hay muchos, pero su significado no es particularmente importante (cortamos la navaja de Occam ): la tecnología está cambiando, las computadoras nuevas y más productivas están reemplazando a las computadoras débiles . Lo que realmente importa es la capacidad de comparar algoritmos . ¡Y existe! Este es Big O , y aquí están sus ejemplos más 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;
}






▍Optimizar



- Recuerde, cuando una persona deja de escuchar el sonido de las ruedas y acepta ir más lejos, se convierte en pasajero.

- Nadie nos pregunta si estamos de acuerdo o no. Ni siquiera recordamos cómo llegamos aquí. Simplemente conducimos y eso es todo. No queda nada.

- Queda lo más difícil de la vida. Viaja en tren y no seas pasajero.



© Victor Pelevin "Flecha amarilla"
Una versión simplificada de iniciar Processor Engine contiene un bucle en un bucle, es decir



, se ve así: 



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 versión simplificada y revisada contiene dos bucles consecutivos y



tiene este aspecto: 



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


E idealmente , las funciones con bucles se eliminan y se llaman desde la función principal: 



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


▍ Tomamos medidas



Todo este mundo es una flecha amarilla que te golpeó, un tren en el que vas al puente destruido.



© Victor Pelevin "Flecha amarilla"
Para tomar medidas, usé time



. Este no es el método más preciso, ya que el tiempo de ejecución puede variar mucho en diferentes computadoras, sin embargo, dentro del mismo sistema, el tiempo + es el mismo y la diferencia entre la mayoría de las ejecuciones no es muy significativa. Por ejemplo, en una Mac, el tiempo de ejecución es dos veces menor que en un Linux remoto, de acuerdo con las características, su tiempo puede diferir.



Cuando escribo, a putout



menudo ejecuto comprobaciones (ya más de) 1800 archivos, y un minuto y medio puede no parecer mucho, pero si lo comparas con el tiempo de ejecución de 3000 pruebas en 15 segundos, queda claro: hay hay espacio para crecer! Por lo tanto, seleccionemos una etiqueta v17.5.0



y lancemos una pelusa nueva usando 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


Estamos interesados ​​en las primeras líneas: minuto 33 segundos y minuto 20 segundos: se hizo más rápido en 13 segundos, esto es aproximadamente un 12% para ellos, agregamos una medición después de la optimización a una variante ideal y obtenemos todo el 13%.



Repitiendo la búsqueda de funciones "calientes", obtenemos los siguientes números: 



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


El número de ciclos trabajados es 4 veces menor y los porcentajes han bajado del 93% al 54%, lo que no es nada malo en sí mismo. Agradecería que alguien en los comentarios amplíe la información sobre los datos que el generador de perfiles guarda en el archivo.



▍ Conclusiones de largo alcance



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



© « »


Como resultado de la optimización, el código se volvió no solo más rápido de procesar, sino también más fácil de entender y, por lo tanto, más fácil de mantener y extensible. Por lo tanto, declaro audazmente: ¡la optimización de los puntos "calientes" es la raíz de todas las bendiciones!



ACTUALIZAR Al parecer me equivoqué al calcular la complejidad algorítmica y lo que llamo el algoritmo lineal es O (n * m) , muchas gracias @Yavanosta,más justo, nvgordeev    !  ,  , , Big O - . , V8.



▍

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



© « »






More articles:


All Articles