Latar Belakang:
Sambil mengoptimalkan beberapa kode Pascal dengan bahasa assembly yang tertanam, saya melihat MOVinstruksi yang tidak perlu , dan menghapusnya.
Yang mengejutkan saya, menghapus instruksi yang tidak perlu menyebabkan program saya melambat .
Saya menemukan bahwa menambahkan MOVinstruksi yang sewenang-wenang dan tidak berguna meningkatkan kinerja lebih jauh.
Efeknya tidak menentu, dan perubahan berdasarkan urutan eksekusi: instruksi sampah yang sama dipindahkan ke atas atau ke bawah dengan satu baris menghasilkan pelambatan .
Saya mengerti bahwa CPU melakukan semua jenis optimasi dan perampingan, tetapi, ini lebih seperti ilmu hitam.
Data:
Versi kode saya secara kompilasi mengkompilasi tiga operasi sampah di tengah-tengah loop yang berjalan 2**20==1048576kali. (Program sekitarnya hanya menghitung hash SHA-256 ).
Hasil pada mesin saya yang agak lama (Intel (R) Core (TM) 2 CPU 6400 @ 2.13 GHz):
avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without: 1836.44 msProgram dijalankan 25 kali dalam satu lingkaran, dengan urutan berjalan berubah secara acak setiap kali.
Kutipan:
{$asmmode intel}
procedure example_junkop_in_sha256;
var s1, t2 : uint32;
begin
// Here are parts of the SHA-256 algorithm, in Pascal:
// s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
// s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
// Here is how I translated them (side by side to show symmetry):
asm
MOV r8d, a ; MOV r9d, e
ROR r8d, 2 ; ROR r9d, 6
MOV r10d, r8d ; MOV r11d, r9d
ROR r8d, 11 {13 total} ; ROR r9d, 5 {11 total}
XOR r10d, r8d ; XOR r11d, r9d
ROR r8d, 9 {22 total} ; ROR r9d, 14 {25 total}
XOR r10d, r8d ; XOR r11d, r9d
// Here is the extraneous operation that I removed, causing a speedup
// s1 is the uint32 variable declared at the start of the Pascal code.
//
// I had cleaned up the code, so I no longer needed this variable, and
// could just leave the value sitting in the r11d register until I needed
// it again later.
//
// Since copying to RAM seemed like a waste, I removed the instruction,
// only to discover that the code ran slower without it.
{$IFDEF JUNKOPS}
MOV s1, r11d
{$ENDIF}
// The next part of the code just moves on to another part of SHA-256,
// maj { r12d } := (a and b) xor (a and c) xor (b and c)
mov r8d, a
mov r9d, b
mov r13d, r9d // Set aside a copy of b
and r9d, r8d
mov r12d, c
and r8d, r12d { a and c }
xor r9d, r8d
and r12d, r13d { c and b }
xor r12d, r9d
// Copying the calculated value to the same s1 variable is another speedup.
// As far as I can tell, it doesn't actually matter what register is copied,
// but moving this line up or down makes a huge difference.
{$IFDEF JUNKOPS}
MOV s1, r9d // after mov r12d, c
{$ENDIF}
// And here is where the two calculated values above are actually used:
// T2 {r12d} := S0 {r10d} + Maj {r12d};
ADD r12d, r10d
MOV T2, r12d
end
end;Cobalah sendiri:
Kode ini online di GitHub jika Anda ingin mencobanya sendiri.
Pertanyaan saya:
- Mengapa tidak berguna menyalin konten register ke RAM yang pernah meningkatkan kinerja?
- Mengapa instruksi yang tidak berguna yang sama memberikan percepatan pada beberapa baris, dan perlambatan pada yang lain?
- Apakah perilaku ini sesuatu yang dapat dieksploitasi dapat diprediksi oleh kompiler?
sumber
Jawaban:
Penyebab peningkatan kecepatan yang paling mungkin adalah:
Core2 Anda tidak menyimpan catatan riwayat terpisah untuk setiap lompatan bersyarat. Alih-alih itu menyimpan sejarah bersama dari semua lompatan bersyarat. Salah satu kelemahan prediksi cabang global adalah bahwa sejarah diencerkan oleh informasi yang tidak relevan jika lompatan bersyarat yang berbeda tidak berkorelasi.
Tutorial prediksi cabang kecil ini menunjukkan cara kerja buffer prediksi cabang. Cache buffer diindeks oleh bagian bawah dari alamat instruksi cabang. Ini bekerja dengan baik kecuali dua cabang tidak berkorelasi penting berbagi bit yang lebih rendah yang sama. Dalam hal ini, Anda berakhir dengan alias yang menyebabkan banyak cabang salah duga (yang menghentikan jalur instruksi dan memperlambat program Anda).
Jika Anda ingin memahami bagaimana misprediksi cabang mempengaruhi kinerja, lihat jawaban yang sangat bagus ini: https://stackoverflow.com/a/11227902/1001643
Compiler biasanya tidak memiliki informasi yang cukup untuk mengetahui cabang mana yang akan alias dan apakah alias itu akan signifikan. Namun, informasi itu dapat ditentukan saat runtime dengan alat-alat seperti Cachegrind dan VTune .
sumber
Anda mungkin ingin membaca http://research.google.com/pubs/pub37077.html
TL; DR: memasukkan instruksi nop secara acak ke dalam program dapat dengan mudah meningkatkan kinerja sebesar 5% atau lebih, dan tidak, kompiler tidak dapat dengan mudah mengeksploitasinya. Ini biasanya kombinasi dari prediktor cabang dan perilaku cache, tetapi bisa juga menjadi mis. Kios stasiun reservasi (bahkan dalam kasus tidak ada rantai ketergantungan yang rusak atau sumber daya yang jelas langganan berlebihan).
sumber
Saya percaya pada CPU modern instruksi perakitan, sementara menjadi lapisan terakhir yang terlihat oleh seorang programmer untuk memberikan instruksi eksekusi ke CPU, sebenarnya adalah beberapa lapisan dari eksekusi aktual oleh CPU.
CPU modern adalah hibrida RISC / CISC yang menerjemahkan instruksi CISC x86 ke dalam instruksi internal yang lebih banyak perilaku RISC. Selain itu ada analisis eksekusi out-of-order, prediktor cabang, "fusi op-mikro" Intel yang mencoba untuk mengelompokkan instruksi ke dalam sejumlah besar pekerjaan simultan (seperti titanic VLIW / Itanium ). Bahkan ada batas cache yang bisa membuat kode berjalan lebih cepat untuk dewa-tahu-mengapa jika lebih besar (mungkin cache controller menempatkannya lebih cerdas, atau menyimpannya lebih lama).
CISC selalu memiliki lapisan terjemahan assembly-to-microcode, tetapi intinya adalah bahwa dengan CPU modern, banyak hal yang jauh lebih rumit. Dengan semua transistor real estat tambahan di pabrik fabrikasi semikonduktor modern, CPU mungkin dapat menerapkan beberapa pendekatan pengoptimalan secara paralel dan kemudian memilih satu di akhir yang memberikan kecepatan terbaik. Instruksi tambahan mungkin bias CPU untuk menggunakan satu jalur optimasi yang lebih baik daripada yang lain.
Efek dari instruksi tambahan mungkin tergantung pada model / generasi / pabrikan CPU, dan sepertinya tidak dapat diprediksi. Mengoptimalkan bahasa rakitan dengan cara ini akan membutuhkan eksekusi terhadap banyak generasi arsitektur CPU, mungkin menggunakan jalur eksekusi khusus CPU, dan hanya akan diinginkan untuk bagian kode yang sangat sangat penting, meskipun jika Anda melakukan perakitan, Anda mungkin sudah tahu itu.
sumber
Mempersiapkan cache
Memindahkan operasi ke memori dapat menyiapkan cache dan membuat operasi pemindahan berikutnya lebih cepat. CPU biasanya memiliki dua unit muat dan satu unit toko. Unit muat dapat membaca dari memori menjadi register (satu baca per siklus), unit toko menyimpan dari register ke memori. Ada juga unit lain yang melakukan operasi antar register. Semua unit bekerja secara paralel. Jadi, pada setiap siklus, kami dapat melakukan beberapa operasi sekaligus, tetapi tidak lebih dari dua beban, satu toko, dan beberapa operasi register. Biasanya hingga 4 operasi sederhana dengan register biasa, hingga 3 operasi sederhana dengan register XMM / YMM dan 1-2 operasi kompleks dengan segala jenis register. Kode Anda memiliki banyak operasi dengan register, jadi satu operasi penyimpanan memori dummy gratis (karena ada lebih dari 4 operasi register), tetapi ia menyiapkan cache memori untuk operasi penyimpanan berikutnya. Untuk mengetahui cara kerja penyimpanan memori, silakan merujuk keManual Referensi Optimasi Arsitektur Intel 64 dan IA-32 .
Memutus ketergantungan salah
Meskipun ini tidak persis merujuk ke kasing Anda, tetapi kadang-kadang menggunakan operasi mov 32-bit di bawah prosesor 64-bit (seperti dalam kasing Anda) digunakan untuk menghapus bit yang lebih tinggi (32-63) dan memutus rantai ketergantungan.
Diketahui bahwa pada x86-64, menggunakan operan 32-bit membersihkan bit yang lebih tinggi dari register 64-bit. Mohon baca bagian yang relevan - 3.4.1.1 - dari Manual Pengembang Perangkat Lunak Arsitektur Intel® 64 dan IA-32 Volume 1 :
Jadi, instruksi mov, yang mungkin tampak tidak berguna pada pandangan pertama, menghapus bit yang lebih tinggi dari register yang sesuai. Apa yang memberi kita? Ini memecah rantai ketergantungan dan memungkinkan instruksi untuk dieksekusi secara paralel, dalam urutan acak, oleh algoritma Out-of-Order diimplementasikan secara internal oleh CPU sejak Pentium Pro pada tahun 1995.
Kutipan dari Manual Referensi Optimasi Arsitektur Intel® 64 dan IA-32 , Bagian 3.5.1.8:
MOVZX dan MOV dengan operan 32-bit untuk x64 adalah sama - mereka semua memutus rantai ketergantungan.
Itu sebabnya kode Anda dieksekusi lebih cepat. Jika tidak ada dependensi, CPU secara internal dapat mengganti nama register, meskipun pada pandangan pertama mungkin tampak bahwa instruksi kedua memodifikasi register yang digunakan oleh instruksi pertama, dan keduanya tidak dapat dieksekusi secara paralel. Tetapi karena mendaftar mengubah nama mereka bisa.
Pengubahan nama register adalah teknik yang digunakan secara internal oleh CPU yang menghilangkan ketergantungan data palsu yang timbul dari penggunaan kembali register dengan instruksi berturut-turut yang tidak memiliki ketergantungan data nyata di antara mereka.
Saya pikir Anda sekarang melihat bahwa itu terlalu jelas.
sumber