Dalam hal apa kenaikan elemen
std :: vector lebih cepat - jika bertipe
uint8_t atau
uint32_t ?
Agar tidak beralasan secara abstrak, kami mempertimbangkan dua implementasi spesifik:
void vector8_inc(std::vector<uint8_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } } void vector32_inc(std::vector<uint32_t>& v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } }
Mari kita coba tebak
Mudah untuk menjawab pertanyaan ini menggunakan tolok ukur, dan beberapa saat kemudian kami akan melakukannya, tetapi pertama-tama kami akan mencoba menebak (ini disebut "penalaran berdasarkan prinsip-prinsip dasar" - ini terdengar lebih seperti aroma).
Pertama, ada baiknya mengajukan pertanyaan:
Berapa ukuran vektor ini ?
Baiklah, mari kita pilih beberapa nomor. Biarkan ada 20.000 elemen di masing-masing.
Lebih lanjut, diketahui bahwa kita akan menguji pada prosesor Intel Skylake - kita akan melihat karakteristik perintah tambahan untuk operan
8-bit dan
32-bit dengan pengalamatan langsung. Ternyata indikator utamanya sama: 1 operasi per siklus dan penundaan 4 siklus per akses memori (1). Dalam hal ini, penundaan tidak menjadi masalah, karena setiap operasi penambahan dilakukan secara independen, sehingga kecepatan yang dihitung adalah 1 elemen per siklus, dengan ketentuan bahwa semua sisa pekerjaan pada loop akan dilakukan secara paralel.
Anda juga dapat melihat bahwa 20.000 item sesuai dengan dataset 20 Kbyte untuk versi dengan
uint8_t dan sebanyak 80 Kbytes untuk versi dengan
uint32_t . Dalam kasus pertama, mereka secara ideal sesuai dengan cache level L1 dari komputer berbasis x86 modern, dan yang kedua - tidak. Ternyata versi 8-bit akan mendapatkan kemajuan karena caching yang efisien?
Akhirnya, kami mencatat bahwa tugas kami sangat mirip dengan kasus klasik
vektorisasi otomatis : dalam satu lingkaran dengan jumlah iterasi yang diketahui, operasi aritmatika dilakukan pada elemen-elemen yang secara berurutan terletak di memori. Dalam hal ini, versi 8-bit harus memiliki keunggulan luar biasa dibandingkan versi 32-bit, karena satu operasi vektor akan memproses elemen empat kali lebih banyak dan, secara umum, prosesor Intel melakukan operasi vektor pada elemen byte tunggal pada kecepatan yang sama dengan lebih dari 32 elemen bit.
Baiklah, berhenti mengomel. Saatnya beralih ke ujian.
Tolok ukur
Saya mendapatkan pewaktuan berikut untuk vektor dari 20.000 elemen pada
kompiler gcc 8 dan
clang 8 dengan tingkat optimisasi yang berbeda:
Ternyata, dengan pengecualian tingkat
-O1 , versi dengan
uint32_t lebih cepat daripada versi dengan
uint8_t , dan dalam beberapa kasus ini penting: 5,4 kali pada gcc di tingkat
-O3 dan tepat 8 kali dentang di kedua tingkat,
-O2 dan
- O3 . Ya, peningkatan bilangan bulat 32-bit dalam
std :: vector hingga delapan kali lebih cepat daripada peningkatan bilangan bulat 8-bit pada kompiler populer dengan pengaturan optimalisasi standar.
Seperti biasa, mari kita beralih ke daftar assembler dengan harapan akan menjelaskan apa yang terjadi.
Berikut adalah daftar untuk gcc 8 pada level
-O2 , di mana versi 8-bit "hanya" 1,5 kali lebih lambat dari versi 32-bit (2):
8-bit: .L3: inc BYTE PTR [rdx+rax] mov rdx, QWORD PTR [rdi] inc rax mov rcx, QWORD PTR [rdi+8] sub rcx, rdx cmp rax, rcx jb .L3
32-bit: .L9: inc DWORD PTR [rax] add rax, 4 cmp rax, rdx jne .L9
Versi 32-bit terlihat persis seperti yang kita harapkan dari loop (3) undeveloped: increment (4) dengan alamat, lalu tiga perintah kontrol loop:
add rax ,
4 - kenaikan variabel inductive (5) dan beberapa perintah
cmp dan
jne untuk memeriksa kondisi untuk keluar dari loop dan melompat bersyarat di atasnya. Semuanya tampak hebat - penyebaran akan mengimbangi biaya penambahan penghitung dan memeriksa kondisinya, dan kode kami akan hampir mencapai kecepatan maksimum yang mungkin dari 1 elemen per siklus clock (6), tetapi untuk aplikasi open-source itu akan dilakukan. Dan bagaimana dengan versi 8-bit? Selain perintah
inc dengan alamat, dua perintah tambahan untuk membaca dari memori dieksekusi, serta perintah
sub , yang diambil entah dari mana.
Berikut adalah daftar dengan komentar:
8-bit: .L3: inc BYTE PTR [rdx+rax] ; v[i] mov rdx, QWORD PTR [rdi] ; v.begin inc rax ; i++ mov rcx, QWORD PTR [rdi+8] ; v.end sub rcx, rdx ; end - start (.. vector.size()) cmp rax, rcx ; i < size() jb .L3 ; . i < size()
Di sini
vector :: begin dan
vector :: end adalah pointer internal
std :: vector , yang digunakan untuk menunjukkan awal dan akhir dari urutan elemen yang terkandung dalam area yang dipilih untuk itu (7), ini pada dasarnya adalah nilai yang sama yang digunakan untuk mengimplementasikan
vector :: begin () dan
vector :: end () (walaupun mereka bertipe berbeda). Ternyata semua perintah tambahan hanyalah konsekuensi dari perhitungan
vector.size () . Sepertinya tidak ada yang aneh? Tetapi setelah semua, dalam versi 32-bit, tentu saja,
size () juga dihitung, namun, perintah ini tidak ada dalam daftar itu. Perhitungan
ukuran () terjadi hanya sekali - di luar loop.
Jadi ada apa? Jawaban singkatnya adalah
pointer alias . Saya akan memberikan jawaban terinci di bawah ini.
Jawaban terinci
Vektor dilewatkan ke fungsi dengan referensi, yang, pada kenyataannya, adalah pointer bertopeng. Compiler harus pergi ke anggota
v :: begin dan
v :: end of vector untuk menghitung ukuran
ukurannya () , dan dalam contoh kita,
ukuran () dihitung
pada setiap iterasi. Tetapi kompiler tidak diwajibkan untuk secara buta mematuhi kode sumber: itu mungkin membawa hasil memanggil fungsi
size () di luar loop, tetapi hanya jika ia tahu pasti bahwa semantik program
tidak akan berubah . Dari sudut pandang ini, satu-satunya tempat yang bermasalah dalam loop adalah kenaikan
v [i] ++ . Rekaman berlangsung di alamat yang tidak dikenal. Bisakah operasi seperti itu mengubah nilai ukuran ()?
Jika catatan terjadi di
std :: vector <uint32_t> (mis. Oleh pointer
uint32_t * ), maka tidak, itu tidak dapat mengubah nilai
size () . Menulis ke objek tipe
uint32_t hanya dapat memodifikasi objek tipe
uint32_t , dan pointer yang terlibat dalam menghitung
ukuran () memiliki tipe yang berbeda (8).
Namun, dalam kasus
uint8_t , setidaknya pada kompiler populer (9), jawabannya adalah: ya, secara teoritis, nilai
ukuran () dapat berubah , karena
uint8_t adalah alias untuk
char unsigned , dan array tipe
char unsigned (dan
char ) bisa
Alias dengan tipe lain . Ini berarti bahwa, menurut kompiler, menulis ke
pointer uint8_t dapat mengubah isi memori yang tidak diketahui asalnya di alamat mana pun (10). Oleh karena itu, diasumsikan bahwa setiap operasi kenaikan
v [i] ++ dapat mengubah nilai
size () , dan karena itu dipaksa untuk menghitung ulang pada setiap iterasi dari loop.
Kita semua tahu bahwa menulis ke memori yang ditunjuk oleh
std :: vector tidak akan pernah mengubah ukurannya sendiri
() , karena ini berarti bahwa vektor itu sendiri entah bagaimana dialokasikan di dalam tumpukannya sendiri, dan itu praktis mustahil dan mirip dengan masalah ayam dan telur (11). Namun sayangnya ini tidak diketahui oleh kompiler!
Bagaimana dengan sisa hasilnya?
Yah, kami menemukan mengapa versi dengan
uint8_ sedikit lebih lambat dari versi
uint32_t pada gcc di level
-O2 . Tapi mengapa menjelaskan perbedaan besar - hingga 8 kali - pada dentang atau gcc yang sama pada
-O3 ?
Semuanya sederhana di sini: dalam kasus
uint32_t, dentang dapat melakukan loop otomatis vektorisasi:
.LBB1_6: ; =>This Inner Loop Header: Depth=1 vmovdqu ymm1, ymmword ptr [rax + 4*rdi] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 32] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 64] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 96] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 32], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 64], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 96], ymm4 vmovdqu ymm1, ymmword ptr [rax + 4*rdi + 128] vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 160] vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 192] vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 224] vpsubd ymm1, ymm1, ymm0 vpsubd ymm2, ymm2, ymm0 vpsubd ymm3, ymm3, ymm0 vpsubd ymm4, ymm4, ymm0 vmovdqu ymmword ptr [rax + 4*rdi + 128], ymm1 vmovdqu ymmword ptr [rax + 4*rdi + 160], ymm2 vmovdqu ymmword ptr [rax + 4*rdi + 192], ymm3 vmovdqu ymmword ptr [rax + 4*rdi + 224], ymm4 add rdi, 64 add rsi, 2 jne .LBB1_6
Siklus ini digunakan 8 kali, dan ini secara umum adalah kinerja maksimum yang bisa Anda dapatkan: satu vektor (8 elemen) per siklus clock untuk cache L1 (ini tidak akan lagi berfungsi karena keterbatasan satu operasi tulis per siklus clock (12)).
Vektorisasi tidak dilakukan untuk
uint8_t , karena terhambat oleh kebutuhan untuk menghitung
ukuran () untuk memeriksa kondisi loop pada setiap iterasi. Alasan lag masih sama, tetapi lag itu sendiri jauh lebih besar.
Pengaturan waktu terendah dijelaskan oleh auto-vektorisasi: gcc hanya menerapkannya pada level
-O3 , dan dentang berlaku pada level
-O2 dan
-O3 secara default. Compiler level -cc gcc menghasilkan kode yang sedikit lebih lambat daripada dentang karena tidak memperluas loop yang di-autovektorat.
Perbaiki situasi
Kami menemukan apa masalahnya - bagaimana kami bisa memperbaikinya?
Pertama, mari kita coba satu cara yang, bagaimanapun, tidak akan berhasil, yaitu, kita akan menulis siklus yang lebih idiomatis berdasarkan iterator:
for (auto i = v.begin(); i != v.end(); ++i) { (*i)++; }
Kode yang dihasilkan
gcc pada level
-O2 akan sedikit lebih baik daripada opsi dengan
ukuran () :
.L17: add BYTE PTR [rax], 1 add rax, 1 cmp QWORD PTR [rdi+8], rax jne .L17
Dua operasi baca tambahan berubah menjadi satu, karena
saya sekarang kita bandingkan dengan pointer
akhir vektor, dan jangan menghitung ulang
ukuran () , kurangi pointer ke awal vektor dari pointer akhir. Dengan jumlah instruksi, kode ini menyusul
uint32_t , karena operasi baca ekstra digabungkan dengan operasi perbandingan. Namun, masalahnya belum hilang dan auto-vektorisasi masih belum tersedia, jadi
uint8_t masih signifikan di belakang
uint32_t - lebih dari 5 kali pada gcc dan dentang pada level di mana auto-vektorisasi disediakan.
Mari kita coba yang lain. Kami tidak akan berhasil lagi, atau lebih tepatnya, kami akan menemukan metode
lain yang tidak beroperasi.
Dalam versi ini, kami menghitung
ukuran () hanya sekali sebelum loop dan menempatkan hasilnya dalam variabel lokal:
for (size_t i = 0, s = v.size(); i < s; i++) { v[i]++; }
Tampaknya bisa berfungsi? Masalahnya adalah
size () , dan sekarang kami memerintahkan compiler untuk melakukan hasil
size () ke variabel lokal di awal loop, dan variabel lokal, seperti yang Anda tahu, tidak berpotongan dengan data lain. Kami benar-benar melakukan apa yang tidak dapat dilakukan oleh kompiler. Dan kode yang akan dihasilkannya sebenarnya akan lebih baik (dibandingkan dengan yang asli):
.L9: mov rdx, QWORD PTR [rdi] add BYTE PTR [rdx+rax], 1 add rax, 1 cmp rax, rcx jne .L9
Hanya ada satu operasi baca tambahan dan tidak ada perintah
sub . Tapi apa yang dilakukan perintah tambahan ini (
rdx, QWORD PTR [rdi] ) jika tidak terlibat dalam perhitungan ukuran? Bunyinya pointer
data () dari
v !
Ekspresi
v [i] diimplementasikan sebagai
* (v.data () + i) , dan anggota dikembalikan oleh
data () (dan, pada kenyataannya, pointer
awalan reguler) menimbulkan masalah yang sama dengan
size () . Benar, saya tidak melihat operasi ini dalam versi asli, karena itu ada "gratis", karena masih harus dilakukan untuk menghitung ukuran.
Beruang dengan sedikit lagi, kami hampir menemukan solusi. Anda hanya perlu menghapus dari loop kami
semua dependensi pada konten
std :: vector . Cara termudah untuk melakukannya adalah dengan memodifikasi idiom kami dengan iterator sedikit:
for (auto i = v.begin(), e = v.end(); i != e; ++i) { (*i)++; }
Sekarang semuanya telah berubah secara dramatis (di sini kita hanya membandingkan versi dengan
uint8_t - di satu kita menyimpan iterator
akhir dalam variabel lokal
sebelum loop, yang lain - tidak):
Perubahan kecil ini memberi kami peningkatan kecepatan 20 kali lipat pada level dengan auto-vektorisasi. Selain itu, kode dengan
uint8_t tidak hanya mengejar kode dengan
uint32_t - itu menyalip hampir tepat 4 kali oleh gcc
-O3 dan dentang
-O2 dan
-O3 , seperti yang kami harapkan di awal, mengandalkan vektorisasi: pada akhirnya, tepat empat kali lebih banyak elemen dapat diproses oleh operasi vektor dan kita membutuhkan bandwidth empat kali lebih sedikit - terlepas dari tingkat cache (13).
Jika Anda membaca ke tempat ini, maka Anda harus berseru kepada diri sendiri selama ini:
Tapi bagaimana dengan for-loop dengan band traversal yang diperkenalkan di C ++ 11?Saya cepat-cepat menyenangkan Anda: itu berhasil! Ini, pada kenyataannya, adalah gula sintaksis, di belakang yang bersembunyi versi kita dengan iterator dalam bentuk yang hampir sama, di mana kita memperbaiki pointer
akhir dalam variabel lokal sebelum dimulainya loop. Jadi kecepatannya sama.
Jika kami tiba-tiba memutuskan untuk kembali ke zaman gua purba dan menulis fungsi mirip-C, kode seperti itu akan berfungsi juga:
void array_inc(uint8_t* a, size_t size) { for (size_t i = 0; i < size; i++) { a[i]++; } }
Di sini, pointer ke array
a dan
ukuran variabel dilewatkan ke fungsi dengan nilai, sehingga mereka tidak dapat diubah sebagai hasil dari penulisan ke pointer
a (14) - sama seperti variabel lokal. Kinerja kode ini sama dengan opsi sebelumnya.
Akhirnya, pada kompiler di mana opsi ini tersedia, Anda dapat mendeklarasikan vektor dengan
__restrict (15):
void vector8_inc_restrict(std::vector<uint8_t>& __restrict v) { for (size_t i = 0; i < v.size(); i++) { v[i]++; } }
Kata kunci terbatas __ bukan bagian dari standar C ++, tetapi bagian dari standar
C sejak C99 (sebagai
batasan ). Jika ini diterapkan sebagai ekstensi C ++ di kompiler, maka kemungkinan besar ia akan mematuhi semantik C. Tentu saja, tidak ada tautan di C, sehingga Anda dapat secara mental mengganti tautan ke vektor dengan penunjuk ke vektor.
Perhatikan bahwa pembatasan tidak memiliki
properti transitif: aksi specifier
__restrict , dengan mana tautan ke
std :: vector dideklarasikan, hanya berlaku untuk anggota vektor itu sendiri, dan tidak ke heap region yang dirujuk oleh
v.data () . Dalam kasus kami, lebih banyak tidak diperlukan, karena (seperti dalam kasus variabel lokal) cukup meyakinkan kompiler bahwa istilah itu sendiri, menunjuk ke awal dan akhir vektor, tidak berpotongan dengan apa pun. Klausa tentang
pembatasan , bagaimanapun, masih relevan, karena menulis melalui
v.data () masih dapat menyebabkan objek lain di fungsi Anda berubah karena alias.
Kekecewaan
Di sini kita sampai pada kesimpulan terakhir - dan sangat mengecewakan -. Faktanya adalah bahwa semua solusi yang ditunjukkan di atas hanya berlaku untuk kasus khusus ini, ketika vektor secara teoritis dapat mengganggu dengan sendirinya. Solusinya adalah keluar dari loop atau mengisolasi hasil memanggil
ukuran () atau
end () dari vektor, dan
tidak memberi tahu kompiler bahwa menulis ke data vektor tidak mempengaruhi data lain. Kode seperti itu akan sulit untuk skala ketika fungsinya bertambah.
Masalah aliasing belum hilang, dan perintah tulis masih bisa pergi "ke mana saja" - tidak ada data lain dalam fungsi ini yang dapat terpengaruh ... untuk saat ini. Begitu kode baru muncul di dalamnya, semuanya akan diulang. Berikut ini
contohnya begitu saja . Jika dalam loop kecil Anda menulis ke array elemen dari tipe
uint8_t , Anda harus bertarung dengan kompiler sampai akhir (16).
Komentar
Saya akan dengan senang hati menerima umpan balik. Saya belum memiliki sistem komentar (17), jadi, seperti biasa, kita akan membahas di
utas ini tentang HackerNews .
- Dengan mengakses memori di sini, dapat dipahami bahwa rantai dependensi melewati memori: perintah tulis pada alamat yang sama harus membaca nilai terakhir yang ditulis di sana, oleh karena itu operasi tersebut tergantung (dalam praktiknya, pengalihan untuk memuat (STLF) akan digunakan jika perekaman sudah cukup. sering). Ketergantungan perintah add ketika mengakses memori dapat terjadi dengan cara lain, misalnya, dengan menghitung alamat, tetapi untuk kasus kami ini tidak relevan.
- Hanya siklus kecil yang ditampilkan di sini; Kode instalasi sederhana dan berfungsi cepat. Untuk melihat daftar lengkap, unggah kode ke godbolt .
- Mungkin itu harus disebut "diminimalkan"? Meskipun demikian, kompiler gcc biasanya tidak membuka gulungan bahkan pada level -O2 dan -O3 , kecuali dalam kasus-kasus khusus ketika jumlah iterasi kecil dan diketahui pada tahap kompilasi . Karena itu, gcc menunjukkan hasil tes yang lebih rendah dibandingkan dengan dentang, tetapi menghemat banyak pada ukuran kode. Anda dapat memaksa gcc untuk membuka gulungan dengan menerapkan optimasi profil atau dengan mengaktifkan flag -funroll-loop .
- Sebenarnya, perintah DWORD PTR [rax] inc di gcc adalah optimasi yang terlewatkan: hampir selalu lebih baik menggunakan perintah add [rax], 1 , karena hanya terdiri dari 2 operasi mikro gabungan versus 3 untuk inc . Dalam hal ini, perbedaannya hanya sekitar 6%, tetapi jika siklusnya sedikit diperluas sehingga hanya operasi penulisan yang diulang, perbedaannya akan signifikan (ekspansi lebih lanjut tidak lagi berperan, karena kita akan mencapai batas 1) merekam operasi per siklus, yang tidak tergantung pada jumlah total operasi mikro).
- Saya menyebut variabel ini induktif , dan bukan hanya saya , seperti dalam kode sumber, karena kompiler mengubah operasi unit kenaikan i menjadi peningkatan 4-byte dari penunjuk yang disimpan dalam register rax , dan karenanya memperbaiki kondisi loop. Dalam bentuk aslinya, loop kami membahas elemen-elemen vektor, dan setelah konversi ini, ia menambah pointer / iterator, yang merupakan salah satu cara untuk mengurangi biaya operasi .
- Bahkan, jika Anda mengaktifkan -funroll-loop , pada gcc kecepatannya akan menjadi 1,08 langkah per elemen dengan 8x roll- out. Tetapi bahkan dengan flag ini, ia tidak akan memperluas loop untuk versi dengan elemen 8-bit, sehingga kelambatan dalam kecepatan akan lebih terlihat!
- Anggota-anggota ini memiliki pengubah pribadi , dan nama-nama mereka bergantung pada implementasi, tetapi dalam stdlibc ++ mereka tidak benar-benar disebut mulai dan selesai , seperti dalam gcc. Mereka disebut _Vector_base :: _ Vector_impl :: _ M_start dan _Vector_base :: _ Vector_impl :: _ M_finish masing-masing , mis. masukkan struktur _Vector_impl , yang merupakan anggota _M_impl (dan satu-satunya) dari kelas _Vector_base , dan itu, pada gilirannya, adalah kelas dasar untuk std :: vector . Baik, baik! Untungnya, kompiler dengan mudah mengatasi tumpukan abstraksi ini.
- Standar tidak menentukan apa yang seharusnya menjadi tipe internal std :: vector members, tetapi di libstdc ++ library mereka hanya didefinisikan sebagai Alloc :: pointer (di mana Alloc adalah pengalokasi untuk vektor), dan untuk std :: dialokasikan objek default mereka hanya akan pointer tipe T * , yaitu pointer reguler ke objek - dalam hal ini uint32_t * .
- Saya membuat reservasi ini karena suatu alasan. Ada kecurigaan bahwa uint8_t dapat dianggap sebagai tipe selain char , char yang ditandatangani , dan char yang tidak ditandatangani . Karena aliasing bekerja dengan tipe karakter , ini pada prinsipnya tidak berlaku untuk uint8_t dan harus berperilaku seperti tipe non-karakter lainnya. Namun, tidak ada dari kompiler yang saya tahu berpikir demikian: di semua dari mereka mengetik uint8_t adalah alias dari unsigned char , sehingga kompiler tidak melihat perbedaan di antara mereka, bahkan jika mereka ingin menggunakannya.
- Maksud "asal tidak diketahui" Maksud saya di sini hanya bahwa kompiler tidak tahu di mana isi dari memori menunjuk atau bagaimana tampilannya. Ini termasuk pointer arbitrer yang diteruskan ke fungsi, serta variabel global dan statis. , , , , , ( - ). , malloc new , , , , : , , . , malloc new .
- , std::vector - ? , std::vector<uint8_t> a a.data() placement new b . std::swap(a, b) , – , b ? , b . : - (, ), , .
- 8 , .. 32 . , std::vector .
- - 4 : , , – . : 8- L1, 32- – L2 , .
- , – : . , , «».
- v[i] , .
- . , «» , uint8_t . , , , uint8_t , . , clang, gcc , , uint8_t . - gcc , . , , - __restrict .
- - , , ( Disqus), ( ), .
. : Travis Downs. Incrementing vectors .