エンジンを13％高速化した方法

線形アルゴリズムを使用することの重要性に関する最近の記事 は、「ホット」な2次関数を最適化するように促し、それをどのように行ったか、そしてそれがどのような結果につながったかを示します。今日お話しします。プーアル茶をカップに入れ、椅子に腰を下ろします。

▍すべて-JavaScript

…本質的に、幸福はなく、幸福の意識だけがあります。言い換えれば、意識しかないのです。



©VictorPelevin「イエローアロー」

このの初めに 今年のコード（あるいは昨年の終わりに）、新しいプレーヤーが登場間で刺殺静的アナライザエンジン ： プロセッサエンジン。今すぐチェックし、正しくできるだけでなく js(x)



、 ts(x)



および flow



ファイル、しかし markdown



、 yaml



、 ignore



、 json



およびインタフェース・エンジンを実装して他のもの。



プロセッサは JavaScript



ファイルから-codeを取得し、たとえばMarkdownプロセッサですべてを接着します 。

どちらの変換 json



、 yaml



および ignore



中 JavaScript



のエラーの発見と修正するための プラグインを。



プロセッサインターフェイスは次のようになります。

• process(rawSource, {fix}) -> [processedSource, processedPlaces]
  
  
  
  -フラグに従って、処理されたソースコードまたは検出されたエラーを返しますfix
  
  
  
  。
• preProcess(processedSource) -> preProcessedList
  
  
  
  -検証と修正のために撤退JavaScript
  
  
  
  しprocessedSource
  
  
  
  ます。
• postProcess(processedSource, preProcessedList) -> processedSource
  
  
  
  -修正されたものを接着しJavaScript
  
  
  
  ます;

Putoutの心臓部は、4つの部分（エンジン）で構成されています。

• パーサは、文字列に変換AST
  
  
  
  し、AST
  
  
  
  バック文字列にします。
• ローダーはプラグイン（forを含むBabel
  
  
  
  ）とコードmodを見つけてロードしますjscodeshift
  
  
  
  
• パフォーマーはあらゆる種類のプラグインを認識して処理します（現在は4つあります）。
• プロセッサは、前の三位一体の動作を制御します。

作業のスキームは次のようになります。

▍「ホット」な機能を探しています

問題は、私たちが出発する時間の前に1秒で終わった旅を絶えず行っているということです。



©VictorPelevin「イエローアロー」

パレートの法則によれば 、正しく指示された作業の20％で結果の80％が得られるため、最初に「最もホットな」関数を見つけて操作することが常に理にかなっています。



まず、-profキーを使用し てisolate



-fileを 取得し 、リポジトリのルートから実行します。 node v14

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

次に、キーを使用して処理します --prof-process



。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

関連する情報を見 engine-processor



て、 processed.txt



私たちはラインに気づきます：

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

ええ、プロセッサエンジンは、親関数が呼び出されたときに334クロックサイクルと93.6％の呼び出しを実行します。

▍BigOについて少し

過去は未来を引っ張る機関車です。他の誰かに加えて、これは過去であることが起こります。背中を前に向けて乗ると、すでに消えたものだけが見えます。電車を降りるには切符が必要です。手に持っていますが、誰にプレゼントしますか？



©VictorPelevin「イエローアロー」

fn



入力として受け取り data



、返す 関数の場合 result



：

const result = fn(data);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Big Oは、最も悲観的なシナリオに関する情報を提供します。

実行時間 fn



は関数を使用して取得できます。 complexity



入力として使用します operationsCount



。

const time = complexity(operationsCount);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

時間は文字n



で表され ます。数字はたくさんあるので、数字を使うよりも便利ですが、その意味は特に重要ではありません（OccamのRazorを切り離しました ）：テクノロジーは変化し、新しい、より生産的なコンピューターが弱いコンピューターに取って代わります。本当に重要なのは、 アルゴリズムを比較する機能です。そしてそれは存在します！これは BigOであり、最も簡単な例を次に示します。

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

  
  
  

▍最適化

-人が車輪の音を聞くのをやめて、さらに進むことに同意すると、彼は乗客になることを忘れないでください。

-同意するかどうかは誰にも聞かれません。どうやってここにたどり着いたのかさえ覚えていません。運転するだけで、それだけです。何も残っていません。

-人生で最も難しいことが残っています。電車に乗って、乗客ではありません。



©VictorPelevin「イエローアロー」

プロセッサエンジンを起動する簡略化されたバージョンに は、ループ内にループが含まれています。つまり



、次のようになります。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

簡略化 された改訂版には、2つの連続したループが含まれており、



次のようになり ます。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

そして 理想的には、ループのある関数が取り出され、メイン関数から呼び出されます。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

▍測定を行います

この全世界はあなたを襲った黄色い矢であり、あなたが破壊された橋に行く列車です。



©VictorPelevin「イエローアロー」

測定には、を使用しました time



。これは最も正確な方法ではありません。実行時間はコンピューターによって大きく異なる可能性があるためですが、同じシステム内では+時間は同じであり、ほとんどの実行の違いはそれほど重要ではありません。たとえば、Macの場合、実行時間はリモートLinuxの2分の1ですが、特性によっては時間が異なる場合があります。



私が書くとき、私は putout



しばしば1800ファイル（すでに以上）のチェックを実行し、1分半はそれほど多くないように見えるかもしれませんが、15秒で3000テストの実行時間と比較すると 、次のことが明らかになります。成長する余地です！したがって、タグを選択し、 redrunv17.5.0



を使用して新しいlintを 起動します：

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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

最初の行に関心があります：分33秒、分20秒-13秒速くなりました。これは約12 ％です。最適化後に測定値を理想的なバリアントに追加すると、 すべて13％になります。



「ホット」関数の検索を繰り返すと、次の数値が得られます。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

稼働サイクル数は4分の1になり、割合は93％から54％に減少しましたが、それ自体は悪いことではありません。コメントの誰かがプロファイラーがファイルに保存するデータに関する情報を拡張してくれれば幸いです。

▍広範囲にわたる結論

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



© « »

最適化の結果、コードの処理が高速になるだけでなく、理解しやすくなり、保守性と拡張性が向上しました。したがって、私は大胆に宣言します。「ホット」スポットの最適化はすべての祝福の根源です！



更新 どうやら私はアルゴリズムの複雑さを計算するのに間違いを犯しました、そして私が線形アルゴリズムと呼ぶものはO（n * m）です、どうもありがとう@Yavanosta、ファイワー、 nvgordeev    !  ,  , , Big O - . , V8.

▍

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



© « »