Mengapa lebih cepat memproses array yang diurutkan daripada array yang tidak disortir?

Ini adalah bagian dari kode C ++ yang tampaknya sangat aneh. Untuk beberapa alasan aneh, mengurutkan data secara ajaib membuat kode hampir enam kali lebih cepat.

 import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // Generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } } 

Dengan hasil yang agak mirip, tetapi kurang ekstrim.


Pikiran pertama saya adalah penyortiran membawa data ke cache, tapi kemudian saya berpikir betapa bodohnya itu, karena array baru saja dihasilkan.

  • Apa yang terjadi
  • Mengapa array yang diurutkan diproses lebih cepat daripada array yang tidak disortir?
  • Kode ini merangkum beberapa istilah independen, dan urutannya tidak masalah.
22512
27 июня '12 в 16:51 2012-06-27 16:51 GManNickG ditetapkan pada 27 Juni '12 pada 4:51 2012-06-27 16:51
@ 26 jawaban

Anda adalah korban penyimpangan dari percabangan .


Apa itu prediksi cabang?

Pertimbangkan persimpangan kereta:

2019

Prediksi cabang.

Dengan array yang diurutkan, data[c] >= 128 kondisi adalah false pertama untuk string nilai, dan kemudian menjadi true untuk semua nilai berikutnya. Mudah diprediksi. Dengan array yang tidak disortir, Anda membayar biaya percabangan.

3815
27 июня '12 в 16:54 2012-06-27 16:54 jawabannya diberikan oleh Daniel Fischer 27 Juni '12 pada pukul 16.54 2012-06-27 16:54

Alasan bahwa kinerja meningkat secara dramatis ketika mengurutkan data adalah bahwa hukuman untuk prediksi cabang dihi>Mysticial dengan sempurna.

Sekarang, jika kita melihat kodenya

 if (data[c] >= 128) sum += data[c]; 

kita dapat menemukan bahwa arti dari cabang khusus ini if... else... adalah untuk menambahkan sesuatu ketika kondisi terpenuhi. Jenis cabang ini dapat dengan mudah dikonversi ke operator bersyarat , yang akan dikompilasi menjadi instruksi gerakan bersyarat: cmovl , dalam sistem x86 . Cabang dan, oleh karena itu, potensi penalti untuk memprediksi cabang dihi>

Dalam C , oleh karena itu, C++ , operator yang akan >x86 adalah operator ternary ...?... :... ...?... :... Oleh karena itu, kami menulis u>

 sum += data[c] >=128 ? data[c] : 0; 

Dengan mempertahankan keterbacaan, kita dapat memeriksa faktor akselerasi.

Untuk Intel Core i7 -2600K @ 3.4 GHz dan uji referensi mode rilis Visual Studio 2010 (format disalin dari Mysticial):

x86

 // Branch - Random seconds = 8.885 // Branch - Sorted seconds = 1.528 // Branchless - Random seconds = 3.716 // Branchless - Sorted seconds = 3.71 

x64

 // Branch - Random seconds = 11.302 // Branch - Sorted seconds = 1.830 // Branchless - Random seconds = 2.736 // Branchless - Sorted seconds = 2.737 

Hasilnya dapat diandalkan dalam beberapa tes. Kami mendapatkan akselerasi yang signifikan ketika hasil percabangan tidak dapat diprediksi, tetapi kami sedikit menderita ketika itu dapat diprediksi. Bahkan, saat menggunakan gerakan bersyarat, kinerja tetap sama terlepas dari pola data.

Sekarang mari kita lihat lebih dekat, menjelajahi build x86 mereka hasilkan. Untuk kesederhanaan, kami menggunakan dua fungsi max1 dan max2 .

max1 menggunakan cabang kondisional, if... else... :

 int max1(int a, int b) { if (a > b) return a; else return b; } 

max2 menggunakan operator ternary ...?... :... ...?... :... :

 int max2(int a, int b) { return a > b ? a : b; } 

Pada komputer x86-64, GCC -S membangun unit di bawah ini.

 :max1 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jle .L2 movl -4(%rbp), %eax movl %eax, -12(%rbp) jmp .L4 .L2: movl -8(%rbp), %eax movl %eax, -12(%rbp) .L4: movl -12(%rbp), %eax leave ret :max2 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl %eax, -8(%rbp) cmovge -8(%rbp), %eax leave ret 

max2 menggunakan kode jauh lebih sedikit karena penggunaan instruksi cmovge . Tetapi keuntungan sebenarnya adalah bahwa max2 tidak termasuk transisi pada max2 , jmp , yang dapat menyebabkan kinerja max2 signifikan jika hasil yang diprediksi adalah max2 .

Jadi mengapa >

Pada prosesor x86 biasa, eksekusi x86 dibagi menjadi beberapa tahap. Secara kasar, kami memiliki perangkat keras yang berbeda untuk tahapan yang berbeda. Karena itu, kita tidak perlu menunggu akhir satu instruksi untuk memulai yang baru. Ini disebut pipelining .

Dalam hal percabangan, instruksi selanjutnya ditentukan oleh yang sebelumnya, jadi kami tidak bisa melakukan pipelining. Kita harus menunggu atau memprediksi.

Dalam kasus >Fetch dan Decode , tidak bergantung pada hasil instruksi sebelumnya; hanya tahap akhir yang membutuhkan hasil. Dengan demikian, kami menunggu sebagian waktu eksekusi dari satu instruksi. Inilah sebabnya mengapa versi pemindahan bersyarat lebih lambat daripada cabang saat prediksi mudah.

Buku Computer Systems: A Prospect for a Programmer, edisi kedua, menjelaskan hal ini secara terperinci. Anda dapat memeriksa Bagian 3.6.6 untuk Instruksi Gerakan Bersyarat, seluruh Bab 4 untuk Arsitektur Prosesor, dan Bagian 5.11.2 untuk penanganan khusus untuk Denda Prediksi dan Prediksi yang Salah.

Terkadang beberapa kompiler modern dapat mengoptimalkan kode kami untuk membangun dengan kinerja yang lebih tinggi, kadang-kadang beberapa kompiler tidak dapat (kode ini menggunakan kompiler Visual Studio sendiri). Mengetahui perbedaan kinerja antara percabangan dan gerakan kondisional, ketika tidak dapat diprediksi, dapat membantu kami menulis kode dengan kinerja yang lebih baik ketika skrip menjadi sangat kompleks sehingga kompiler tidak dapat secara otomatis mengoptimalkannya.

3064
28 июня '12 в 5:14 2012-06-28 05:14 jawabannya diberikan oleh WiSaGaN 28 Juni '12 pada 5:14 am 2012-06-28 05:14

Jika Anda tertarik pada lebih banyak optimasi yang dapat dilakukan dengan kode ini, pertimbangkan hal berikut:

Mulai dari siklus awal:

 for (unsigned i = 0; i < 100000; ++i) { for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) sum += data[j]; } } 

Dengan permutasi siklus, kita dapat dengan aman mengubah siklus ini ke:

 for (unsigned j = 0; j < arraySize; ++j) { for (unsigned i = 0; i < 100000; ++i) { if (data[j] >= 128) sum += data[j]; } } 

Maka Anda dapat melihat bahwa kondisi if konstan selama eksekusi loop i , sehingga Anda dapat menariknya if keluar:

 for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { for (unsigned i = 0; i < 100000; ++i) { sum += data[j]; } } } 

Kemudian Anda akan melihat bahwa loop dalam dapat diciutkan menjadi satu ekspresi, dengan asumsi bahwa model floating point memungkinkan (misalnya, / fp: fast)

 for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { sum += data[j] * 100000; } } 

Ini 100.000 kali lebih cepat dari sebelumnya.

2105
03 июля '12 в 5:25 2012-07-03 05:25 jawabannya diberikan kepada gagak vulcan 3 Juli '12 pukul 5:25 2012-07-03 05:25

Tidak diragukan lagi, sebagian dari kita akan tertarik pada cara mengidentifikasi kode yang bermasalah untuk prosesor prediktor CPU. Alat cachegrind Valgrind memiliki sintaksis cabang prediktor cabang yang diaktifkan menggunakan --branch-sim=yes . Menjalankannya dengan contoh-contoh dalam pertanyaan ini, jumlah loop eksternal, dikurangi menjadi 10.000 dan dikompilasi dengan g++ , memberikan hasil berikut:

Urutkan berdasarkan:

 ==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind) ==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind) ==32551== Mispred rate: 0.0% ( 0.0% + 1.2% ) 

Tidak disortir:

 ==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind) ==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind) ==32555== Mispred rate: 25.0% ( 25.0% + 1.2% ) 

Beralih ke output linear yang dibuat oleh cg_annotate , kita melihat siklus yang dimaksud:

Urutkan berdasarkan:

  Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 10,006 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . } 

Tidak disortir:

  Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 164,050,007 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . } 

Ini memungkinkan Anda untuk dengan mudah mengidentifikasi garis masalah - dalam versi yang tidak disortir, garis if (data[c] >= 128) menyebabkan Bcm cabang bersyarat yang diprediksi salah ( Bcm ) sebagai bagian dari model prediktor cabang cachegrind, sementara hanya menyebabkan 10.006 diurutkan versi.


Atau, di Linux, Anda dapat menggunakan subsistem penghitung kinerja untuk melakukan tugas yang sama, tetapi dengan kinerjanya sendiri menggunakan penghitung CPU.

 perf stat ./sumtest_sorted 

Urutkan berdasarkan:

  Performance counter stats for './sumtest_sorted': 11808.095776 task-clock # 0.998 CPUs utilized 1,062 context-switches # 0.090 K/sec 14 CPU-migrations # 0.001 K/sec 337 page-faults # 0.029 K/sec 26,487,882,764 cycles # 2.243 GHz 41,025,654,322 instructions # 1.55 insns per cycle 6,558,871,379 branches # 555.455 M/sec 567,204 branch-misses # 0.01% of all branches 11.827228330 seconds time elapsed 

Tidak disortir:

  Performance counter stats for './sumtest_unsorted': 28877.954344 task-clock # 0.998 CPUs utilized 2,584 context-switches # 0.089 K/sec 18 CPU-migrations # 0.001 K/sec 335 page-faults # 0.012 K/sec 65,076,127,595 cycles # 2.253 GHz 41,032,528,741 instructions # 0.63 insns per cycle 6,560,579,013 branches # 227.183 M/sec 1,646,394,749 branch-misses # 25.10% of all branches 28.935500947 seconds time elapsed 

Itu juga dapat membuat anotasi kode sumber dengan pembongkaran.

 perf record -e branch-misses ./sumtest_unsorted perf annotate -d sumtest_unsorted 
  Percent | Source code  Disassembly of sumtest_unsorted ------------------------------------------------ ... : sum += data[c]; 0.00 : 400a1a: mov -0x14(%rbp),%eax 39.97 : 400a1d: mov %eax,%eax 5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax 4.60 : 400a26: cltq 0.00 : 400a28: add %rax,-0x30(%rbp) ... 

Untuk detailnya, lihat manual kinerja .

1758
12 окт. jawab diberikan kaf 12 Oktober. 2012-10-12 08:53 '12 pada 8:53 2012-10-12 08:53

Saya baru saja membaca pertanyaan ini dan jawabannya, dan saya merasa bahwa jawabannya tidak ada.

Cara biasa untuk menghi>

Pendekatan ini bekerja secara umum jika:

  1. ini adalah meja kecil dan kemungkinan besar akan di-cache di prosesor, dan
  2. Anda bekerja dalam lingkaran yang agak sempit dan / atau prosesor dapat melakukan pramuat data.

Latar belakang dan alasannya

Dari sudut pandang prosesor, memori Anda lambat. Untuk mengkompensasi perbedaan kecepatan, beberapa cache (cache L1 / L2) dimasukkan ke dalam prosesor Anda. Jadi bayangkan Anda melakukan perhitungan yang baik dan mencari tahu bahwa Anda perlu memori. Prosesor akan melakukan operasi pemuatan dan memuat bagian memori ke dalam cache, dan kemudian menggunakan cache untuk melakukan perhitungan yang tersisa. Karena memori relatif lambat, "memuat" ini akan memperlambat program Anda.

Seperti prediksi cabang, prosesor ini dioptimalkan dalam prosesor Pentium: prosesor memperkirakan bahwa ia perlu memuat beberapa data, dan mencoba memuatnya ke dalam cache sebelum operasi benar-benar masuk ke dalam cache. Seperti yang telah kita lihat, prediksi cabang terkadang salah besar - dalam kasus terburuk, Anda harus kembali dan benar-benar menunggu beban memori yang akan bertahan selamanya ( dengan kata lain: prediksi cabang yang gagal adalah buruk, beban memori setelah kegagalan prediksi cabang buruk! ).

Untungnya bagi kami, jika skema akses memori dapat diprediksi, prosesor akan memuatnya ke dalam cache yang cepat, dan semuanya baik-baik saja.

Hal pertama yang perlu kita ketahui adalah bahwa ada sedikit? Meskipun ukuran yang lebih kecil biasanya lebih baik, aturan praktisnya adalah tetap berpegang pada tabel pencarian <= 4096 byte. Sebagai batas atas: jika tabel referensi Anda lebih besar dari 64 KB, mungkin harus direvisi.

Bangun meja

Jadi, kami mengetahui bahwa kami dapat membuat tabel kecil. Hal selanjutnya yang harus dilakukan adalah mengganti fungsi pencarian. Fungsi pencarian biasanya merupakan fungsi kecil yang menggunakan beberapa operasi integer dasar (dan, atau, xor, shift, tambah, hapus, dan mungkin penggandaan). Вы хотите, чтобы ваш ввод был переведен с помощью функции поиска в какой-то "уникальный ключ" в вашей таблице, который затем просто дает вам ответ на всю работу, которую вы хотели, чтобы он делал.