Pengindeks dalam C # di bawah tenda: pengindeksan lebih baik dari Dow Jones

Hari yang baik Dalam artikel ini, saya mengusulkan untuk berkenalan dengan pengindeks dalam berbagai jenis. Mari kita lihat kode bahasa assembler untuk pengindeks ini dan karakteristik masing-masing instruksi dalam kecepatannya. Saya juga akan menawarkan beberapa kesimpulan yang jelas. Tetapi apa sebenarnya yang harus digunakan dalam situasi khusus Anda bergantung pada Anda apakah akan mengorbankan kenyamanan untuk kecepatan atau sebaliknya.

Metrik

Kode bahasa assembly diberikan untuk sistem 64 bit. Metrik berikut dipilih sebagai metrik untuk setiap instruksi: jumlah operasi mikro yang digabungkan, jumlah total operasi mikro, penundaan, throughput, dan, tentu saja, jumlah instruksi. Saya tidak memberikan angka apa pun secara keseluruhan untuk pengindeks, karena situasinya dapat bervariasi tergantung pada bagaimana Anda bekerja dengan tipe yang diindeks dan mempengaruhi cache secara berbeda.

Di bawah ini adalah ringkasan singkat dari terminologi, tanpa menggali lebih dalam, hanya konsep konseptual. Tujuan saya adalah menggambarkan segala sesederhana mungkin, untuk pemahaman bersama.

Operasi mikro (uop) adalah operasi tertentu yang terdiri dari setiap instruksi. Konsep operasi mikro digunakan untuk optimisasi seperti penggabungan, caching, dan pemesanan ulang. Jadi, misalnya, instruksi MOV terdiri dari 1 operasi mikro, sedangkan instruksi XCHG pada dua register terdiri dari 3 operasi mikro (pendekatannya adalah melalui "variabel sementara", yaitu, register internal, terima kasih leotsarev untuk pembaruan), instruksi XCHG atas register dan memori terdiri dari 8 operasi mikro.

Operasi mikro gabungan (fusi uops) - sebagaimana disebutkan di atas, menggabungkan operasi mikro adalah salah satu optimisasi. Ini terdiri dari mengganti dua operasi mikro dengan satu lagi yang kompleks.

Latensi adalah jumlah tindakan setelah data yang digunakan dalam instruksi ini akan tersedia untuk digunakan oleh instruksi lain.

Throughput (Reciprocal throughput) - jumlah siklus jam yang diperlukan untuk menjalankan satu instruksi, asalkan urutan instruksi yang identik dijalankan dan mereka beroperasi dengan data independen.

Berdasarkan indikator-indikator ini, Anda dapat mengevaluasi kinerja seperangkat instruksi tertentu. Harap perhatikan bahwa kami hanya dapat "mengevaluasi", kinerja sebenarnya tergantung pada banyak faktor, seperti hit atau miss cache, ketergantungan data, dll.

Angka-angka ini untuk arsitektur prosesor Intel Skylake-X. Ini sesuai dengan prosesor Intel Core i7-6700 saya.

Perlu diingat juga bahwa fastcall untuk sistem 64 bit menyediakan transfer bukan 2, tetapi 4 parameter dalam register (rcx, rdx, r8, r9).

Pengindeks dalam angka

1. Array indexer

Kami akan mempertimbangkan metode berikut sebagai contoh:

public int IndexerArray(int index, int[] array) { return array[index]; } 

Pertimbangkan kode bahasa assembler untuk cuplikan ini.

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07288c78 3. movsxd rax,edx 4. mov eax,dword ptr [r8+rax*4+10h] 

Baris pertama memeriksa apakah indeks melampaui batas array. Baris kedua melempar pengecualian jika keluar. Selanjutnya, kita menghitung posisi elemen dalam array. Kolom pertama dalam array adalah informasi layanan, jadi kita perlu melewati mereka (tambahan 10 jam = 16 byte).

2. Daftar Favorit <>

Kode Tinta:

 public int IndexerList(int index, List<int> list) { return list[index]; } 

Kode bahasa rakitan:

 1. cmp edx,dword ptr [r8+10h] 2. jae M00_L00 3. mov rax,qword ptr [r8+8] 4. cmp edx,dword ptr [rax+8] 5. jae 00007ff9`07268f56 6. movsxd rdx,edx 7. mov eax,dword ptr [rax+rdx*4+10h] ret M00_L00 call System.ThrowHelper.ThrowArgumentOutOfRange_IndexException() 

Jelas ada lebih banyak instruksi di sini. Jelas terlihat bahwa sheet indexer membungkus array indexer. Hal yang menarik adalah bahwa pengecekan untuk melampaui batas array dilakukan dua kali. Jadi, instruksi pertama memeriksa apakah indeks melampaui batas lembar. Jika ya, maka kita melompat (instruksi 2) ke panggilan yang sangat jelas, melempar pengecualian jika melampaui batas array. Pemeriksaan perbatasan ini menggunakan bidang bagian dalam lembar, yang merupakan urutan kedua (offset 10 jam (16) byte dari awal jenis, 8 ke penunjuk ke tabel metode dan 8 ke tautan ke larik internal - bidang pertama). Pada baris ketiga, kita masukkan rax register ke alamat array internal - field pertama (dengan analogi, offset 8 byte adalah pointer ke tabel metode). Ini diikuti oleh bagian yang sudah akrab - referensi indeks untuk array (baris 4 - 7). Di sini, untuk memeriksa batas-batas, bidang internal array digunakan.
Saya mencoba untuk menghapus hal-hal yang tidak terkait langsung dengan pengindeksan, tapi di sini ada baiknya untuk tetap ret sehingga tidak tampak bahwa pada akhir setiap panggilan ke elemen sheet akan ada pengecualian: D

Ngomong-ngomong, agar tidak menyiksa Anda dengan spekulasi, harap biasakan diri Anda dengan implementasi lembar dengan referensi . Jenis casting ke int unsigned digunakan untuk mengurangi jumlah perbandingan.

Sebagai hasilnya, kami mendapatkan 7 instruksi untuk berhasil mengakses indeks, yaitu 3 lebih banyak dari pada array.

Baru - Rentang <>

Disc:

 public int IndexerSpan(int index, Span<int> span) { return span[index]; } 

Dan dalam bahasa assembly:

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07278f69 3. mov rax,qword ptr [r8] 4. movsxd rdx,edx 5. mov eax,dword ptr [rax+rdx*4] 

Ketika bentang diumumkan, mereka berjanji kepada kami bahwa mereka dibuat dengan bijak, dengan dukungan runtime. Dan mereka tidak berbohong harus berkata apa. Bahkan, ini berbeda dari array klasik hanya dalam satu instruksi, langkah tambahan untuk mengakses alamat. Dilihat oleh kode ini, alamat lokasi memori disembunyikan di dalam rentang, di mana elemen berada, yang kita dapatkan di baris 3. Ini bisa menjadi alamat ke tempat tertentu dalam array, garis, atau sepotong memori pada tumpukan.
Klik di sini untuk pengantar Span pengindeks untuk bersenang-senang. Anda mungkin memperhatikan bahwa ada 2 implementasi yang berbeda, tergantung pada variabel lingkungan. PROJECTN adalah nama kode dari versi pertama .NET Native untuk UWP. Oleh karena itu, kami lebih tertarik pada versi kedua dari pengindeks. Dia ditandai [Intrinsik] . Selain itu, jika Anda melihat kelas Tidak Aman statis yang digunakan dalam implementasi pengindeks ini, Anda dapat menemukan informasi bahwa implementasi sebagian besar metode dalam file ini direpresentasikan sebagai Intrinsik .

Metode panggilan atau referensi ke bidang yang ditandai dengan atribut [Intrinsik] mendapat dukungan dari runtime.

Dalam CoreCLR , badan metode tersebut digantikan oleh EE (mesin Eksekusi) dengan kode tidak aman (tidak aman). Jika Anda membutuhkan detail lebih lanjut, Anda bisa mulai menggali dengan metode getILIntrinsicImplementationForUnsafe .

Informasi tentang bagaimana ini bekerja di CoreRT (yang menarik minat saya sedikit),
Anda dapat mulai melihat Internal.IL.Stubs.UnsafeIntrinsics .

Dengan dukungan dari raintime, untuk memahami apa yang sebenarnya akan terjadi di balik layar, masuk akal untuk melihat petunjuk dalam bahasa assembler, yang kami lakukan.


Semua pengindeks sangat tergantung pada data: instruksi menggunakan hasil yang sebelumnya. Tidak ada hasil yang tidak biasa di sini, dan seharusnya tidak ada. Tetapi sekarang overhead yang muncul dalam kasus ini atau itu sudah jelas. Beberapa temuan jelas. Jika algoritma melibatkan akses yang sangat sering dengan indeks, maka masuk akal untuk berpikir tentang mengganti sheet dengan array. Jika panggilan tidak terlalu sering, maka mungkin lebih nyaman menggunakan sheet yang menyediakan api yang sangat nyaman dan tidak memiliki overhead yang besar (saya ingatkan Anda untuk memantau ekstensi array internal).

Sekarang mari kita coba melihat cara-cara berbeda yang dengannya kita dapat menentukan array dua dimensi: array array (array bergerigi) dan array multidimensi (array multidimensi).

4. Array multidimensi

Kode Sharp:

 public int IndexerDimensionalArray(int index1, int index2, int[,] demensionalArray) { return demensionalArray[index1, index2]; } 

Bahasa majelis:

 1. mov eax,edx 2. sub eax,dword ptr [r9+18h] 3. cmp eax,dword ptr [r9+10h] 4. jae 00007ff9`00098fe6 5. mov edx,r8d 6. sub edx,dword ptr [r9+1Ch] 7. cmp edx,dword ptr [r9+14h] 8. jae 00007ff9`00098fe6 9. mov ecx,dword ptr [r9+14h] 10. imul rcx,rax 11. mov rax,rdx 12. add rax,rcx 13. mov eax,dword ptr [r9+rax*4+20h] 

Semuanya dapat dimengerti secara prinsip - 2 memeriksa batas array, kemudian menghitung indeks dan membalikkan. Array ini disimpan dalam memori dalam satu fragmen.

5. Array array (array bergerigi)

 public int IndexerJaggedArray(int index, int index2, int[][] jaggedArray) { return jaggedArray[index][index2]; } 

Assembler:

 1. cmp edx,dword ptr [r9+8] 2. jae 00007ff9`00098f95 3. movsxd rax,edx 4. mov rax,qword ptr [r9+rax*8+10h] 5. cmp r8d,dword ptr [rax+8] 6. jae 00007ff9`00098f95 7. movsxd rdx,r8d 8. mov eax,dword ptr [rax+rdx*4+10h] 

Dan yang paling menarik - kami memiliki lebih sedikit instruksi dibandingkan dengan tipe multidimensi yang dibuat khusus.


Tetapi tentang 2 contoh terakhir, saya menyarankan Anda untuk tidak terburu-buru mengambil kesimpulan. Karena kenyataan bahwa array dua dimensi adalah tipe tunggal, yang diinisialisasi 1 kali, memori untuk seluruh array dialokasikan dalam satu fragmen besar. Ini akan memberikan cache yang lebih baik, yang secara fundamental dapat mengubah situasi. Dalam array array, memori untuk setiap array akan dialokasikan secara terpisah, sehingga kemungkinan array akan dialokasikan dalam memori dan dimasukkan di tempat yang paling cocok untuk mereka.

Namun, mungkin bagi sebagian orang, perilaku ini akan lebih dapat diterima. Mungkin dalam beberapa situasi diketahui bahwa masa hidup spesimen ini akan berumur pendek. Dan agar tidak jatuh ke sekelompok benda besar (yang merupakan semacam generasi kedua untuk pengumpul sampah), di mana ada kesempatan untuk tinggal untuk waktu yang lama, jauh lebih banyak daripada yang kita inginkan. Atau setelah beberapa waktu kami hanya ingin bekerja dengan garis-garis tertentu, dan segala sesuatu yang lain dapat dihapus. Plus, ini direncanakan untuk bekerja dengan tipe yang mengacu pada elemen acak yang tidak konsisten, ketika cache tidak dapat bekerja secara normal.

Juga, ketika menggunakan array array, lebih cenderung tidak memprovokasi pengumpul sampah untuk dipadatkan, tetapi harus dilakukan dengan sapuan. Pengingat: saat memecah memori, jumlah total ruang kosong mungkin cukup untuk objek baru, tetapi tidak ada area bebas terus menerus dari jumlah yang diperlukan. Dalam hal ini, pemadatan dilakukan - menggerakkan objek dengan tujuan defragmentasi. Jika kita dapat mengambil rentangan terus menerus dari memori bebas untuk objek baru, kita cukup memasukkan objek ke ruang kosong ini. Ini disebut sapuan.

Saya harap informasi ini membantu Anda untuk menarik kesimpulan yang tepat dan mendukung pendapat Anda dalam diskusi tentang apa yang harus digunakan.