Apa kinerja Objek / Array di JavaScript? (khusus untuk Google V8)

Performa yang terkait dengan Array dan Objek dalam JavaScript (khususnya Google V8) akan sangat menarik untuk didokumentasikan. Saya tidak menemukan artikel komprehensif tentang topik ini di mana pun di Internet.

Saya memahami bahwa beberapa Objek menggunakan kelas sebagai struktur data yang mendasarinya. Jika ada banyak properti, terkadang diperlakukan sebagai tabel hash?

Saya juga memahami bahwa Array terkadang diperlakukan seperti C ++ Array (yaitu pengindeksan acak cepat, penghapusan lambat, dan pengubahan ukuran). Dan, di lain waktu, mereka diperlakukan lebih seperti Objek (pengindeksan cepat, penyisipan / penghapusan cepat, lebih banyak memori). Dan, mungkin terkadang mereka disimpan sebagai daftar tertaut (yaitu pengindeksan acak yang lambat, penghapusan / penyisipan cepat di awal / akhir)

Apa kinerja yang tepat dari pengambilan dan manipulasi Array / Objek dalam JavaScript? (khusus untuk Google V8)

Lebih khusus lagi, apa dampak kinerja:

• Menambahkan properti ke Objek
• Menghapus properti dari Objek
• Mengindeks properti di Objek
• Menambahkan item ke Array
• Menghapus item dari Array
• Mengindeks item dalam Array
• Memanggil Array.pop ()
• Memanggil Array.push ()
• Memanggil Array.shift ()
• Memanggil Array.unshift ()
• Memanggil Array.slice ()

Artikel atau tautan apa pun untuk detail lebih lanjut akan dihargai juga. :)

EDIT: Saya benar-benar bertanya-tanya bagaimana array dan objek JavaScript bekerja di bawah tenda. Juga, dalam konteks apa mesin V8 "tahu" untuk "beralih" ke struktur data lain?

Misalnya, saya membuat array dengan ...

var arr = [];
arr[10000000] = 20;
arr.push(21);

Apa yang sebenarnya terjadi disini?

Atau ... bagaimana dengan ini ... ???

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

Untuk array konvensional, kinerjanya akan sangat buruk; sedangkan, jika LinkedList digunakan ... tidak terlalu buruk.

Saya membuat rangkaian pengujian, tepatnya untuk menjelajahi masalah ini (dan lebih banyak lagi) ( salinan yang diarsipkan ).

Dan dalam hal itu, Anda dapat melihat masalah kinerja dalam 50+ test case tester ini (ini akan memakan waktu lama).

Juga seperti yang disarankan oleh namanya, ini mengeksplorasi penggunaan menggunakan sifat daftar tertaut asli dari struktur DOM.

(Saat ini turun, sedang dibangun kembali) Lebih detail di blog saya tentang ini .

Ringkasannya adalah sebagai berikut

• V8 Array Cepat, SANGAT CEPAT
• Array push / pop / shift ~ kira-kira 20x + lebih cepat daripada objek yang setara.
• Anehnya Array.shift()adalah cepat ~ kira-kira 6x lebih lambat dari pop array, tetapi ~ kira-kira 100x lebih cepat daripada penghapusan atribut objek.
• Menariknya, Array.push( data );lebih cepat dari Array[nextIndex] = datahampir 20 (array dinamis) hingga 10 (array tetap) kali lipat.
• Array.unshift(data) lebih lambat seperti yang diharapkan, dan ~ kira-kira 5x lebih lambat dari penambahan properti baru.
• array[index] = nullMenghapus nilai lebih cepat daripada menghapusnya delete array[index](tidak ditentukan) dalam array dengan ~ kira-kira 4x ++ lebih cepat.
• Anehnya, membatalkan nilai dalam sebuah objek obj[attr] = null~ kira-kira 2x lebih lambat daripada hanya menghapus atributdelete obj[attr]
• Tidak mengherankan, mid array Array.splice(index,0,data)lambat, sangat lambat.
• Anehnya, Array.splice(index,1,data)telah dioptimalkan (tidak ada perubahan panjang) dan 100x lebih cepat dari sekedar sambunganArray.splice(index,0,data)
• tidak mengherankan, divLinkedList lebih rendah daripada array di semua sektor, kecuali dll.splice(index,1)penghapusan (Jika merusak sistem pengujian).
• KEJUTAN TERBESAR dari semuanya [seperti yang ditunjukkan jjrv], penulisan array V8 sedikit lebih cepat daripada pembacaan V8 = O

Catatan: Metrik ini hanya berlaku untuk larik / objek besar yang v8 tidak "sepenuhnya dioptimalkan". Ada kasus kinerja yang dioptimalkan sangat terisolasi untuk larik / ukuran objek kurang dari ukuran sewenang-wenang (24?). Detail selengkapnya dapat dilihat secara luas di beberapa video Google IO.

Catatan 2: Hasil kinerja luar biasa ini tidak dibagikan di seluruh browser, terutama *cough*IE. Tesnya juga sangat besar, oleh karena itu saya belum sepenuhnya menganalisis dan mengevaluasi hasilnya: silakan edit di =)

Catatan yang Diperbarui (des 2012): Perwakilan Google memiliki video di youtubes yang menjelaskan cara kerja chrome itu sendiri (seperti saat beralih dari larik daftar tertaut ke larik tetap, dll), dan cara mengoptimalkannya. Lihat GDC 2012: Dari Konsol ke Chrome untuk selengkapnya.

Pada tingkat dasar yang tetap dalam ranah JavaScript, properti pada objek adalah entitas yang jauh lebih kompleks. Anda dapat membuat properti dengan setter / getter, dengan enumerabilitas, kemampuan menulis, dan konfigurasi yang berbeda. Item dalam larik tidak dapat dikustomisasi dengan cara ini: item itu ada atau tidak. Pada tingkat mesin yang mendasarinya, hal ini memungkinkan pengoptimalan yang lebih banyak dalam hal mengatur memori yang mewakili struktur.

Dalam hal mengidentifikasi array dari sebuah objek (kamus), mesin JS selalu membuat garis eksplisit di antara keduanya. Itulah mengapa ada banyak artikel tentang metode mencoba membuat objek semi-palsu mirip Array yang berperilaku seperti satu tetapi memungkinkan fungsionalitas lain. Alasan pemisahan ini bahkan ada adalah karena mesin JS sendiri menyimpan keduanya secara berbeda.

Properti dapat disimpan pada objek array, tetapi ini hanya menunjukkan bagaimana JavaScript bersikeras membuat semuanya menjadi objek. Nilai yang diindeks dalam larik disimpan secara berbeda dari properti apa pun yang Anda putuskan untuk disetel pada objek larik yang mewakili data larik yang mendasarinya.

Setiap kali Anda menggunakan objek array yang sah dan menggunakan salah satu metode standar untuk memanipulasi array itu, Anda akan mencapai data array yang mendasarinya. Khususnya di V8, ini pada dasarnya sama dengan array C ++ sehingga aturan tersebut akan berlaku. Jika karena alasan tertentu Anda bekerja dengan array yang mesin tidak dapat menentukan dengan percaya diri adalah array, maka Anda berada di tempat yang jauh lebih goyah. Dengan versi terbaru V8, ada lebih banyak ruang untuk bekerja. Misalnya, dimungkinkan untuk membuat kelas yang memiliki Array.prototype sebagai prototipe dan masih mendapatkan akses efisien ke berbagai metode manipulasi larik asli. Tapi ini adalah perubahan terkini.

Tautan khusus ke perubahan terkini untuk manipulasi larik mungkin berguna di sini:

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

Sebagai tambahan, inilah Array Pop dan Array Push langsung dari sumber V8, keduanya diterapkan di JS itu sendiri:

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}


function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

Saya ingin melengkapi jawaban yang ada dengan penyelidikan atas pertanyaan tentang bagaimana implementasi berperilaku terkait dengan larik yang berkembang: Jika menerapkannya dengan cara "biasa", orang akan melihat banyak dorongan cepat dengan dorongan lambat yang jarang dan diselingi pada titik mana salinan implementasi representasi internal array dari satu buffer ke buffer yang lebih besar.

Anda dapat melihat efek ini dengan sangat baik, ini dari Chrome:

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

Meskipun setiap push diprofilkan, outputnya hanya berisi push yang membutuhkan waktu di atas ambang tertentu. Untuk setiap pengujian saya menyesuaikan ambang untuk mengecualikan semua dorongan yang tampaknya mewakili dorongan cepat.

Jadi angka pertama mewakili elemen mana yang telah dimasukkan (baris pertama untuk elemen ke-17), angka kedua adalah berapa lama waktu yang dibutuhkan (untuk banyak array, benchmark dilakukan secara paralel), dan nilai terakhir adalah pembagian dari nomor pertama dengan yang ada di baris sebelumnya.

Semua baris yang memiliki waktu eksekusi kurang dari 2 md dikecualikan untuk Chrome.

Anda dapat melihat bahwa Chrome meningkatkan ukuran array dalam kekuatan 1.5, ditambah beberapa offset untuk memperhitungkan array kecil.

Untuk Firefox, ini adalah kekuatan dua:

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

Saya harus menaikkan ambang cukup sedikit di Firefox, itulah mengapa kami mulai dari # 126.

Dengan IE, kami mendapatkan campuran:

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

Ini adalah kekuatan dua pada awalnya dan kemudian berpindah ke kekuatan lima pertiga.

Jadi semua implementasi umum menggunakan cara "normal" untuk array (alih-alih menjadi gila dengan tali , misalnya).

Ini kode patokan dan biolanya .

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

Saat berjalan di bawah node.js 0.10 (dibangun di atas v8) saya melihat penggunaan CPU yang tampak berlebihan untuk beban kerja. Saya menelusuri satu masalah kinerja ke fungsi yang memeriksa keberadaan string dalam array. Jadi saya menjalankan beberapa tes.

• memuat 90.822 host
• memuat konfigurasi membutuhkan 0,087 detik (larik)
• memuat konfigurasi membutuhkan waktu 0,152 detik (objek)

Memuat 91k entri ke dalam larik (dengan validasi & push) lebih cepat daripada menyetel obj [key] = nilai.

Pada tes berikutnya, saya mencari setiap nama host dalam daftar satu kali (iterasi 91k, untuk rata-rata waktu pencarian):

• konfigurasi pencarian membutuhkan 87,56 detik (array)
• konfigurasi pencarian membutuhkan waktu 0,21 detik (objek)

Aplikasi di sini adalah Haraka (server SMTP) dan memuat host_list sekali saat startup (dan setelah perubahan) dan kemudian melakukan pencarian ini jutaan kali selama operasi. Beralih ke suatu objek adalah kemenangan kinerja yang besar.