Clever Geek Handbook

Bagaimana saya mempercepat mesin sebesar 13%

Sebuah artikel baru-baru ini tentang pentingnya menggunakan algoritma linier mengilhami saya untuk mengoptimalkan fungsi kuadrat "panas", bagaimana saya melakukannya, dan apa hasilnya - saya akan memberi tahu Anda hari ini. Seduh Pu Er dalam cangkir, duduk kembali di kursi Anda:



Semuanya - JavaScript



… , , . , , .



© « »
Pada awal kode tahun ini (atau pada akhir tahun lalu), pemain baru muncul di antara mesin penganalisis statis yang dikeluarkan : mesin Prosesor . Sekarang periksa dan perbaiki tidak hanya can js(x)



, ts(x)



dan flow



file, tetapi markdown



, yaml



, ignore



, json



dan lainnya yang mengimplementasikan mesin antarmuka.



Prosesor mengambil JavaScript



kode -dari file, dan merekatkan semuanya kembali, misalnya, di prosesor Penurunan harga .

Baik mengkonversi json



, yaml



dan ignore



di JavaScript



untuk menemukan dan memperbaiki kesalahan plugin .



Antarmuka prosesor terlihat seperti ini:



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



    - mengembalikan kode sumber yang diproses atau menemukan kesalahan sesuai dengan tanda fix



    ;
  • preProcess(processedSource) -> preProcessedList



    - menarik diri JavaScript



    dari processedSource



    untuk verifikasi dan koreksi;
  • postProcess(processedSource, preProcessedList) -> processedSource



    - merekatkan yang dikoreksi JavaScript



    ;


Jantung Putout terdiri dari 4 bagian (mesin):



  • Parser menerjemahkan string ke dalam AST



    dan AST



    kembali ke string;
  • Pemuat menemukan dan memuat plugin (termasuk for Babel



    ), dan mod kodejscodeshift



  • Pelaku mengenali dan memproses semua jenis plugin (sekarang ada 4 plugin);
  • Prosesor mengontrol pengoperasian trinitas sebelumnya;




Skema kerja mungkin terlihat seperti ini:

gambar



Kami mencari fungsi "panas"



Masalahnya adalah kita terus-menerus melakukan perjalanan yang berakhir sedetik sebelum kita punya waktu untuk pergi.



© Victor Pelevin "Panah Kuning"
Sesuai dengan hukum Pareto : 20% dari upaya yang diarahkan dengan benar akan memberi kita 80% dari hasil, jadi hal pertama yang selalu masuk akal adalah menemukan fungsi "terpanas" dan bekerja dengannya.



Pertama, dapatkan isolate



-file node v14



menggunakan kunci --prof , jalankan dari root repositori: 



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


Kemudian kami akan memprosesnya menggunakan kunci --prof-process



: 



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


Melihat melalui informasi yang berhubungan dengan engine-processor



in, processed.txt



kita perhatikan baris: 



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


Ya, mesin Prosesor memenuhi 334 siklus clock dan 93,6% panggilan saat fungsi induk dipanggil.



Sedikit tentang Big O



Masa lalu adalah lokomotif yang menarik masa depan bersamanya. Kebetulan ini adalah masa lalu, selain milik orang lain. Anda naik dengan punggung ke depan dan Anda hanya melihat apa yang telah hilang. Dan untuk turun dari kereta, Anda membutuhkan tiket. Anda memegangnya di tangan Anda, tetapi kepada siapa Anda akan memberikannya?



© Victor Pelevin "Panah Kuning"
Untuk fungsi fn



yang mengambil sebagai input data



dan mengembalikan result



: 



const result = fn(data);


Big O memberikan informasi tentang skenario paling pesimistis.

Waktu eksekusi fn



dapat diperoleh dengan menggunakan fungsi complexity



, dibutuhkan sebagai input operationsCount



: 



const time = complexity(operationsCount);


Waktu dinyatakan dalam huruf n



, lebih nyaman daripada menggunakan angka, karena jumlahnya banyak, tetapi artinya tidak terlalu penting (kami memotong Occam's Razor ): teknologi berubah, komputer baru yang lebih produktif menggantikan komputer yang lemah . Yang benar-benar penting adalah kemampuan untuk membandingkan algoritma . Dan itu ada! Ini Big O , dan ini adalah contoh paling sederhana:



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






Optimalkan



- Ingat, ketika seseorang berhenti mendengar suara roda dan setuju untuk melangkah lebih jauh, dia menjadi penumpang.

- Tidak ada yang bertanya apakah kami setuju atau tidak. Kami bahkan tidak ingat bagaimana kami sampai di sini. Kami hanya mengemudi dan hanya itu. Tidak ada yang tersisa.

- Hal tersulit dalam hidup tetap ada. Naik kereta api dan tidak menjadi penumpang.



© Victor Pelevin "Panah Kuning"
Versi sederhana untuk memulai Mesin Prosesor berisi loop dalam satu loop, yaitu



, terlihat seperti ini: 



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


Versi revisi yang disederhanakan berisi dua loop berturut-turut, dan



terlihat seperti ini: 



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


Dan idealnya , fungsi dengan loop dikeluarkan dan dipanggil dari fungsi utama: 



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


Kami melakukan pengukuran



Seluruh dunia ini adalah panah kuning yang mengenai Anda, sebuah kereta di mana Anda pergi ke jembatan yang hancur.



© Victor Pelevin "Panah Kuning"
Untuk melakukan pengukuran, saya menggunakan time



. Ini bukan metode yang paling akurat, karena waktu eksekusi dapat sangat bervariasi pada komputer yang berbeda, namun, dalam sistem yang sama, waktu + sama dan perbedaan antara sebagian besar proses tidak terlalu signifikan. Misalnya, di Mac, waktu eksekusi dua kali lebih sedikit daripada di Linux jarak jauh, sesuai dengan karakteristiknya, waktu Anda mungkin berbeda.



Ketika saya menulis, saya putout



sering menjalankan pemeriksaan (sudah lebih dari) 1800 file, dan satu setengah menit mungkin tidak terlalu banyak, tetapi jika Anda membandingkannya dengan waktu eksekusi 3000 tes dalam 15 detik, menjadi jelas: ada adalah ruang untuk tumbuh! Jadi, kami akan memilih tag v17.5.0



dan meluncurkan lint baru menggunakan 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


Kami tertarik pada baris pertama: menit 33 detik, dan menit 20 detik - menjadi lebih cepat 13 detik, ini sekitar 12% untuk mereka, kami menambahkan pengukuran setelah pengoptimalan ke varian ideal dan kami mendapatkan semua 13%.



Mengulangi pencarian untuk fungsi "panas", kami mendapatkan angka-angka berikut: 



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


Jumlah siklus yang bekerja 4 kali lebih sedikit, dan persentasenya menurun dari 93% menjadi 54%, yang bukan merupakan hal yang buruk. Saya akan berterima kasih jika seseorang di komentar memperluas informasi tentang data yang disimpan oleh profiler ke file.



Kesimpulan yang jauh jangkauannya



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



© « »


Sebagai hasil dari pengoptimalan, kode tidak hanya menjadi lebih cepat untuk diproses, tetapi juga lebih mudah dipahami, dan karenanya lebih dapat dipelihara dan diperluas. Oleh karena itu, saya dengan berani menyatakan: optimalisasi titik-titik "panas" adalah akar dari semua berkah!



UPDATE Rupanya saya melakukan kesalahan dalam menghitung kompleksitas algoritmik dan yang saya sebut sebagai algoritme linier adalah O (n * m) , terima kasih banyak @Yavanosta,lebih lemah, nvgordeev    !  ,  , , Big O - . , V8.



▍

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



© « »






More articles:


All Articles