Mengapa <= lebih lambat dari <menggunakan cuplikan kode ini di V8?

Saya membaca slide Melanggar Batas Kecepatan Javascript dengan V8 , dan ada contoh seperti kode di bawah ini. Saya tidak tahu mengapa <=lebih lambat daripada <dalam kasus ini, adakah yang bisa menjelaskan hal itu? Setiap komentar dihargai.

Lambat:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

(Petunjuk: primes adalah array dengan panjang prime_count)

Lebih cepat:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i < this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

[Info Lebih Lanjut] peningkatan kecepatannya signifikan, dalam uji lingkungan lokal saya, hasilnya adalah sebagai berikut:

V8 version 7.3.0 (candidate) 

Lambat:

 time d8 prime.js
 287107
 12.71 user 
 0.05 system 
 0:12.84 elapsed 

Lebih cepat:

time d8 prime.js
287107
1.82 user 
0.01 system 
0:01.84 elapsed

Saya bekerja di V8 di Google, dan ingin memberikan beberapa wawasan tambahan di atas jawaban dan komentar yang ada.

Untuk referensi, inilah contoh kode lengkap dari slide :

var iterations = 25000;

function Primes() {
  this.prime_count = 0;
  this.primes = new Array(iterations);
  this.getPrimeCount = function() { return this.prime_count; }
  this.getPrime = function(i) { return this.primes[i]; }
  this.addPrime = function(i) {
    this.primes[this.prime_count++] = i;
  }
  this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
      if ((candidate % this.primes[i]) == 0) return true;
    }
    return false;
  }
};

function main() {
  var p = new Primes();
  var c = 1;
  while (p.getPrimeCount() < iterations) {
    if (!p.isPrimeDivisible(c)) {
      p.addPrime(c);
    }
    c++;
  }
  console.log(p.getPrime(p.getPrimeCount() - 1));
}

main();

Pertama dan terpenting, perbedaan kinerja tidak ada hubungannya dengan operator <dan <=secara langsung. Jadi tolong jangan melompat melalui lingkaran hanya untuk menghindari <=dalam kode Anda karena Anda membaca di Stack Overflow bahwa itu lambat --- tidak!

Kedua, orang-orang menunjukkan bahwa array itu "berlubang". Ini tidak jelas dari cuplikan kode di pos OP, tetapi jelas ketika Anda melihat kode yang menginisialisasi this.primes:

this.primes = new Array(iterations);

Hasil ini dalam sebuah array dengan sebuah HOLEYelemen jenis di V8, bahkan jika array berakhir sepenuhnya diisi / dikemas / berdekatan. Secara umum, operasi pada array berlubang lebih lambat daripada operasi pada array dikemas, tetapi dalam kasus ini perbedaannya dapat diabaikan: itu berjumlah 1 tambahan Smi ( bilangan bulat kecil ) cek (untuk menjaga terhadap lubang) setiap kali kita menekan this.primes[i]dalam loop isPrimeDivisible. Bukan masalah besar!

TL; DR Makhluk array HOLEYbukan masalah di sini.

Lainnya menunjukkan bahwa kode tersebut dibaca di luar batas. Ini umumnya direkomendasikan untuk menghindari membaca melampaui panjang array , dan dalam hal ini memang akan menghindari penurunan kinerja yang besar. Tapi mengapa? V8 dapat menangani beberapa skenario tidak terikat ini hanya dengan dampak kinerja kecil. Apa yang istimewa dari kasus khusus ini?

The out-of-bounds membaca hasil this.primes[i]berada undefineddi baris ini:

if ((candidate % this.primes[i]) == 0) return true;

Dan itu membawa kita ke masalah sebenarnya : %operator sekarang sedang digunakan dengan operan non-integer!

• integer % someOtherIntegerdapat dihitung dengan sangat efisien; Mesin JavaScript dapat menghasilkan kode mesin yang sangat dioptimalkan untuk kasus ini.

• integer % undefineddi sisi lain jumlah cara yang kurang efisien Float64Mod, karena undefineddirepresentasikan sebagai ganda.

Cuplikan kode memang dapat ditingkatkan dengan mengubah <=menjadi <pada baris ini:

for (var i = 1; i <= this.prime_count; ++i) {

... bukan karena <=entah bagaimana operator yang unggul daripada <, tetapi hanya karena ini menghindari out-of-bounds yang dibaca dalam kasus khusus ini.

Jawaban dan komentar lain menyebutkan bahwa perbedaan antara dua loop adalah bahwa yang pertama mengeksekusi satu iterasi lebih dari yang kedua. Ini benar, tetapi dalam array yang tumbuh hingga 25.000 elemen, satu iterasi lebih atau kurang hanya akan membuat perbedaan kecil. Sebagai perkiraan kasarnya, jika kita mengasumsikan panjang rata-rata saat tumbuh adalah 12.500, maka perbedaan yang kita harapkan seharusnya sekitar 1 / 12.500, atau hanya 0,008%.

Perbedaan kinerja di sini jauh lebih besar daripada yang akan dijelaskan oleh satu iterasi tambahan, dan masalahnya dijelaskan pada akhir presentasi.

this.primes adalah array yang bersebelahan (setiap elemen memiliki nilai) dan elemen adalah semua angka.

Mesin JavaScript dapat mengoptimalkan array seperti itu menjadi array sederhana dari angka aktual, bukan array objek yang kebetulan mengandung angka tetapi bisa mengandung nilai lain atau tidak ada nilai. Format pertama jauh lebih cepat untuk diakses: dibutuhkan lebih sedikit kode, dan array jauh lebih kecil sehingga lebih sesuai dalam cache. Tetapi ada beberapa kondisi yang dapat mencegah penggunaan format yang dioptimalkan ini.

Salah satu syaratnya adalah jika beberapa elemen array hilang. Sebagai contoh:

let array = [];
a[0] = 10;
a[2] = 20;

Sekarang apa nilainya a[1]? Tidak memiliki nilai . (Bahkan tidak benar untuk mengatakan memiliki nilai undefined- elemen array yang mengandung undefinednilai berbeda dari elemen array yang hilang seluruhnya.)

Tidak ada cara untuk merepresentasikan ini hanya dengan angka, jadi mesin JavaScript terpaksa menggunakan format yang kurang dioptimalkan. Jika a[1]berisi nilai numerik seperti dua elemen lainnya, array berpotensi dapat dioptimalkan menjadi array angka saja.

Alasan lain untuk array yang akan dipaksa ke dalam format deoptimisasi bisa jika Anda mencoba mengakses elemen di luar batas array, seperti yang dibahas dalam presentasi.

Loop pertama dengan <=upaya untuk membaca elemen melewati akhir array. Algoritma masih bekerja dengan benar, karena dalam iterasi tambahan terakhir:

• this.primes[i]mengevaluasi undefinedkarena imelewati akhir array.
• candidate % undefined(untuk nilai apa pun candidate) dievaluasi menjadi NaN.
• NaN == 0mengevaluasi ke false.
• Karena itu, return truetidak dieksekusi.

Jadi seolah-olah iterasi ekstra tidak pernah terjadi - itu tidak berpengaruh pada sisa logika. Kode menghasilkan hasil yang sama seperti tanpa iterasi tambahan.

Tetapi untuk sampai ke sana, ia mencoba membaca elemen yang tidak ada melewati akhir array. Ini memaksa array keluar dari optimasi - atau setidaknya lakukan pada saat pembicaraan ini.

Loop kedua dengan <hanya membaca elemen yang ada dalam array, sehingga memungkinkan array dan kode yang dioptimalkan.

Masalahnya dijelaskan di halaman 90-91 dari pembicaraan, dengan diskusi terkait di halaman sebelum dan sesudah itu.

Saya kebetulan menghadiri presentasi Google I / O yang sangat ini dan berbicara dengan pembicara (salah satu penulis V8) sesudahnya. Saya telah menggunakan teknik dalam kode saya sendiri yang melibatkan membaca melewati akhir array sebagai upaya yang salah arah (di belakang) untuk mengoptimalkan satu situasi tertentu. Dia mengonfirmasi bahwa jika Anda mencoba untuk bahkan membaca melewati akhir array, itu akan mencegah format sederhana yang dioptimalkan digunakan.

Jika apa yang dikatakan penulis V8 masih benar, maka membaca melewati akhir array akan mencegahnya dioptimalkan dan harus kembali ke format yang lebih lambat.

Sekarang mungkin V8 telah diperbaiki sementara itu untuk menangani kasus ini secara efisien, atau bahwa mesin JavaScript lainnya menanganinya secara berbeda. Saya tidak tahu satu atau lain cara dalam hal itu, tetapi deoptimisasi ini adalah apa yang dibicarakan presentasi.

TL; DR Loop yang lebih lambat adalah karena mengakses Array 'out-of-bounds', yang memaksa engine untuk mengkompilasi ulang fungsi dengan sedikit atau bahkan tanpa optimasi ATAU untuk tidak mengkompilasi fungsi dengan salah satu dari optimasi ini untuk memulai dengan ( jika (JIT-) Compiler mendeteksi / mencurigai kondisi ini sebelum 'versi' kompilasi pertama), baca di bawah mengapa;

Contoh 1:
a Dense Array(bersebelahan (berarti tidak ada kesenjangan antara indeks) DAN sebenarnya elemen pada setiap indeks) dari 5 elemen menggunakan pengindeksan berbasis 0 (selalu dalam ES262).

var arr_five_char=['a', 'b', 'c', 'd', 'e']; // arr_five_char.length === 5
//  indexes are:    0 ,  1 ,  2 ,  3 ,  4    // there is NO index number 5

Dengan demikian kita tidak benar-benar berbicara tentang perbedaan kinerja antara <vs <=(atau 'satu iterasi ekstra'), tetapi kita berbicara:
'mengapa snipet yang benar (b) berjalan lebih cepat daripada snipet yang salah (a)'?

Jawabannya adalah 2 kali lipat (meskipun dari perspektif pelaksana bahasa ES262 keduanya adalah bentuk optimasi):

1. Representasi Data: bagaimana merepresentasikan / menyimpan Array secara internal dalam memori (objek, hashmap, array numerik 'nyata', dll.)
2. Fungsional Mesin-kode: cara mengkompilasi kode yang mengakses / menangani (baca / modifikasi) 'Array' ini

Butir 1 cukup (dan benar IMHO) dijelaskan oleh jawaban yang diterima , tetapi itu hanya menghabiskan 2 kata ('kode') pada Butir 2: kompilasi .

Lebih tepatnya: JIT-Kompilasi dan bahkan yang lebih penting JIT- RE- Kompilasi!

Spesifikasi bahasa pada dasarnya hanyalah deskripsi dari serangkaian algoritma ('langkah-langkah untuk melakukan untuk mencapai hasil akhir yang ditentukan'). Yang ternyata adalah cara yang sangat indah untuk menggambarkan suatu bahasa. Dan itu meninggalkan metode aktual yang digunakan mesin untuk mencapai hasil yang ditentukan terbuka untuk para pelaksana, memberikan banyak peluang untuk menghasilkan cara yang lebih efisien untuk menghasilkan hasil yang ditentukan. Mesin yang memenuhi spesifikasi harus memberikan hasil yang sesuai dengan spesifikasi untuk setiap input yang ditentukan.

Sekarang, dengan kode javascript / perpustakaan / penggunaan meningkat, dan mengingat berapa banyak sumber daya (waktu / memori / dll) yang digunakan kompiler 'nyata', jelas kami tidak dapat membuat pengguna yang mengunjungi halaman web menunggu selama itu (dan membutuhkannya untuk memiliki banyak sumber daya yang tersedia).

Bayangkan fungsi sederhana berikut:

function sum(arr){
  var r=0, i=0;
  for(;i<arr.length;) r+=arr[i++];
  return r;
}

Jelas sempurna, bukan? Tidak memerlukan klarifikasi tambahan APAPUN, Benar? Jenis kembali adalah Number, kan?
Ya .. tidak, tidak & tidak ... Itu tergantung pada argumen apa yang Anda berikan ke parameter fungsi bernama arr...

sum('abcde');   // String('0abcde')
sum([1,2,3]);   // Number(6)
sum([1,,3]);    // Number(NaN)
sum(['1',,3]);  // String('01undefined3')
sum([1,,'3']);  // String('NaN3')
sum([1,2,{valueOf:function(){return this.val}, val:6}]);  // Number(9)
var val=5; sum([1,2,{valueOf:function(){return val}}]);   // Number(8)

Lihat masalahnya? Kalau begitu anggap ini hanyalah permutasi besar yang nyaris mustahil ... Kita bahkan tidak tahu jenis TIPE fungsi KEMBALI sampai kita selesai ...

Sekarang bayangkan kode fungsi yang sama ini benar-benar digunakan pada tipe yang berbeda atau bahkan variasi input, keduanya secara harfiah (dalam kode sumber) dijelaskan dan secara dinamis dalam program 'array' dihasilkan.

Dengan demikian, jika Anda mengkompilasi fungsi sumJUST ONCE, maka satu-satunya cara yang selalu mengembalikan hasil yang ditentukan oleh spesifikasi untuk setiap dan semua jenis input, tentu saja, hanya dengan melakukan SEMUA langkah utama DAN sub-resep yang ditentukan spesifik yang dapat menjamin hasil yang sesuai dengan spesifikasi (seperti browser pra-y2k yang tidak disebutkan namanya). Tidak ada optimasi (karena tidak ada asumsi) dan bahasa scripting lambat ditafsirkan lambat.

Kompilasi JIT (JIT seperti dalam Just In Time) adalah solusi populer saat ini.

Jadi, Anda mulai mengkompilasi fungsi menggunakan asumsi tentang apa yang dilakukannya, kembali dan menerima.
Anda datang dengan pemeriksaan sesederhana mungkin untuk mendeteksi jika fungsi tersebut mungkin mulai mengembalikan hasil yang tidak spesifik (seperti karena ia menerima input yang tidak terduga). Kemudian, buang hasil kompilasi sebelumnya dan kompilasi ulang ke sesuatu yang lebih rumit, putuskan apa yang harus dilakukan dengan hasil parsial yang sudah Anda miliki (apakah valid untuk dipercaya atau dihitung lagi untuk memastikan), ikat fungsi kembali ke dalam program dan coba lagi. Akhirnya jatuh kembali ke penafsiran naskah bertahap seperti dalam spec.

Semua ini membutuhkan waktu!

Semua browser bekerja pada mesin mereka, untuk masing-masing dan setiap sub-versi Anda akan melihat semuanya membaik dan mundur. String pada suatu saat dalam string benar-benar abadi (maka array.join lebih cepat dari penggabungan string), sekarang kita menggunakan tali (atau serupa) yang meringankan masalah. Keduanya mengembalikan hasil yang sesuai dengan spesifikasi dan itulah yang penting!

Singkatnya: hanya karena semantik bahasa javascript sering kali mendukung kita (seperti bug diam ini dalam contoh OP) tidak berarti bahwa kesalahan 'bodoh' meningkatkan peluang kompiler mengeluarkan kode mesin cepat. Diasumsikan kita menulis 'biasanya' instruksi yang benar: mantra saat ini yang kita 'pengguna' (dari bahasa pemrograman) harus miliki adalah: membantu kompiler, menggambarkan apa yang kita inginkan, mendukung idiom umum (mengambil petunjuk dari asm.js untuk pemahaman dasar browser apa yang bisa dioptimalkan dan mengapa).

Karena itu, berbicara tentang kinerja sama pentingnya, TETAPI JUGA sebuah ladang ranjau (dan karena ladang ranjau itu, saya benar-benar ingin mengakhiri dengan menunjuk ke (dan mengutip) beberapa materi yang relevan:

Akses ke properti objek yang tidak ada dan elemen array di luar batas mengembalikan undefinednilai alih-alih menaikkan pengecualian. Fitur dinamis ini membuat pemrograman dalam JavaScript nyaman, tetapi mereka juga membuatnya sulit untuk mengkompilasi JavaScript ke dalam kode mesin yang efisien.

...

Premis penting untuk optimalisasi JIT yang efektif adalah bahwa pemrogram menggunakan fitur dinamis JavaScript secara sistematis. Sebagai contoh, kompiler JIT mengeksploitasi fakta bahwa properti objek sering ditambahkan ke objek dengan tipe tertentu dalam urutan tertentu atau jarang diakses oleh array array. Kompiler JIT mengeksploitasi asumsi keteraturan ini untuk menghasilkan kode mesin yang efisien saat runtime. Jika suatu blok kode memenuhi asumsi, mesin JavaScript mengeksekusi kode mesin yang efisien dan dihasilkan. Kalau tidak, mesin harus kembali ke kode lebih lambat atau menafsirkan program.

Sumber:
"JITProf: Penentuan Kode JavaScript JIT-tidak ramah"
publikasi Berkeley, 2014, oleh Liang Gong, Michael Pradel, Koushik Sen.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (juga tidak suka keluar dari akses array terikat):

Kompilasi Sebelumnya

Karena asm.js adalah subset ketat dari JavaScript, spesifikasi ini hanya mendefinisikan logika validasi — semantik pelaksanaannya hanyalah JavaScript. Namun, asm.js yang divalidasi dapat menerima kompilasi sebelumnya (AOT). Selain itu, kode yang dihasilkan oleh kompiler AOT bisa sangat efisien, menampilkan:

• representasi bilangan bulat dan angka floating-point tanpa kotak;
• tidak adanya pemeriksaan tipe runtime;
• tidak adanya pengumpulan sampah; dan
• tumpukan dan toko yang efisien (dengan strategi implementasi berbeda-beda berdasarkan platform).

Kode yang gagal divalidasi harus kembali ke eksekusi dengan cara tradisional, mis. Kompilasi interpretasi dan / atau just-in-time (JIT).

http://asmjs.org/spec/latest/

dan akhirnya https://blogs.windows.com/msedgedev/2015/05/07/membawa-asm-js-to-chakra-microsoft-edge/
jika ada subbagian kecil tentang peningkatan kinerja internal mesin ketika melepas batas- check (sementara hanya mengangkat batas-periksa di luar loop sudah memiliki peningkatan 40%).

EDIT:
perhatikan bahwa banyak sumber berbicara tentang berbagai tingkat JIT-Rekompilasi hingga interpretasi.

Contoh teoritis berdasarkan informasi di atas, mengenai cuplikan OP:

• Panggil ke isPrimeDivisible
• Kompilasi isPrimeDivisible menggunakan asumsi umum (seperti tidak ada akses di luar batas)
• Bekerja
• BAM, tiba-tiba array mengakses di luar batas (tepat di akhir).
• Omong-omong, kata engine, mari kita kompilasi ulang yaituPrimeDivisible menggunakan berbagai asumsi (kurang), dan mesin contoh ini tidak mencoba mencari tahu apakah ia dapat menggunakan kembali hasil parsial saat ini, jadi
• Hitung ulang semua pekerjaan menggunakan fungsi lebih lambat (mudah-mudahan selesai, jika tidak ulangi dan kali ini hanya menafsirkan kode).
• Hasil kembali

Karenanya waktu adalah:
Jalankan pertama (gagal pada akhirnya) + melakukan semua pekerjaan lagi menggunakan kode mesin lebih lambat untuk setiap iterasi + kompilasi dll. Jelas membutuhkan> 2 kali lebih lama dalam contoh teoritis ini !

EDIT 2: (penafian: dugaan berdasarkan fakta-fakta di bawah)
Semakin saya memikirkannya, semakin saya berpikir bahwa jawaban ini sebenarnya dapat menjelaskan alasan yang lebih dominan untuk 'hukuman' ini pada cuplikan yang salah (atau bonus kinerja pada cuplikan) , tergantung pada bagaimana Anda memikirkannya), tepatnya mengapa saya adament dalam menyebutnya (snippet a) kesalahan pemrograman:

Cukup menggoda untuk menganggap bahwa itu this.primesadalah numerik murni 'array padat' yang juga

• Hard-code literal dalam source-code (kandidat yang dikenal unggul untuk menjadi array 'nyata' karena semuanya sudah diketahui oleh kompiler sebelum waktu kompilasi) ATAU
• kemungkinan besar dihasilkan menggunakan fungsi numerik mengisi pra-ukuran ( new Array(/*size value*/)) dalam urutan berurutan (kandidat lama yang dikenal untuk menjadi array 'nyata').

Kita juga tahu bahwa primespanjang array di- cache sebagai prime_count! (menunjukkan niat dan ukuran tetap).

Kita juga tahu bahwa kebanyakan mesin pada awalnya mengeluarkan Array sebagai copy-on-modifikasi (bila perlu) yang membuat penanganannya jauh lebih cepat (jika Anda tidak mengubahnya).

Oleh karena itu masuk akal untuk mengasumsikan bahwa Array primeskemungkinan besar sudah merupakan array yang dioptimalkan secara internal yang tidak berubah setelah penciptaan (mudah diketahui untuk kompiler jika tidak ada kode yang memodifikasi array setelah penciptaan) dan oleh karena itu sudah (jika berlaku untuk mesin) disimpan dengan cara yang dioptimalkan, cukup banyak seolah-olah itu adalah Typed Array.

Seperti yang saya coba jelaskan dengan sumcontoh fungsi saya , argumen yang dilewati sangat mempengaruhi apa yang sebenarnya perlu terjadi dan bagaimana kode tertentu dikompilasi ke kode mesin. Melewati a Stringke sumfungsi seharusnya tidak mengubah string tetapi mengubah bagaimana fungsi dikompilasi JIT! Melewati Array untuk summengkompilasi versi mesin-kode yang berbeda (mungkin bahkan tambahan untuk jenis ini, atau 'bentuk').

Karena sepertinya sedikit bonkus untuk mengonversi primesArray Typed_Array-like on-the-fly ke something_else sementara kompiler tahu fungsi ini bahkan tidak akan memodifikasinya!

Di bawah asumsi ini, ada 2 opsi:

1. Kompilasi sebagai pengurai angka dengan asumsi tidak ada batas, mengalami masalah di luar batas, kompilasi ulang dan ulangi pekerjaan (seperti diuraikan dalam contoh teoretis dalam edit 1 di atas)
2. Kompiler telah mendeteksi (atau diduga?) Keluar dari akses terikat di muka dan fungsinya dikompilasi JIT seolah argumen yang dilewati adalah objek yang jarang menghasilkan kode mesin fungsional yang lebih lambat (karena akan memiliki lebih banyak pemeriksaan / konversi / pemaksaan) dll.) Dengan kata lain: fungsi tidak pernah memenuhi syarat untuk optimisasi tertentu, itu dikompilasi seolah-olah ia menerima argumen '(seperti) array jarang.

Saya sekarang benar-benar bertanya-tanya yang mana dari 2 ini!

Untuk menambahkan sedikit keilmiahan padanya, inilah jsperf

https://jsperf.com/ints-values-in-out-of-array-bounds

Ini menguji kasus kontrol dari array yang diisi dengan int dan perulangan melakukan aritmatika modular sambil tetap dalam batas. Ini memiliki 5 kasus uji:

• 1. Looping di luar batas
• 2. Array berlubang
• 3. Aritmatika modular terhadap NaNs
• 4. Nilai yang sama sekali tidak terdefinisi
• 5. Menggunakan a new Array()

Ini menunjukkan bahwa 4 kasus pertama sangat buruk untuk kinerja. Looping di luar batas sedikit lebih baik daripada 3 lainnya, tetapi semua 4 kira-kira 98% lebih lambat dari kasus terbaik.
The new Array()kasus hampir sama baiknya dengan array baku, hanya beberapa persen lebih lambat.