Hari ini kita akan mengukur kinerja berbagai implementasi fungsi toupper, karena ini adalah apa yang mereka lakukan pada hari Selasa.
Sebenarnya, saya tidak peduli dengan fungsi
toupper , saya baru saja menulis posting lain baru-baru ini dan saya membutuhkan semacam inti plot yang umum, dan
toupper tampaknya menjadi kandidat benchmark yang cukup menarik dan tidak berbahaya. Saya mencoba untuk memilih sesuatu yang sesederhana mungkin yang tidak akan membuat saya kesamping, tetapi kebetulan dalam tes ini saya mengalami masalah yang aneh.
Posting ini akan menjadi kecil - artikel yang lebih komprehensif tentang aslinya, mungkin topik yang lebih menarik segera diharapkan. Jika Anda ingin mereproduksi hasil dengan saya, Anda
dapat mengambil kode sumber
di github .
Jadi, kita akan mempertimbangkan tiga implementasi fungsi
toupper , yang mengubah karakter array yang terdiri dari elemen tipe
char ke huruf besar - yaitu, mengambil array sebagai argumen dan langsung mengubah elemen-elemennya sehingga semua huruf kecil dikapitalisasi.
Dalam implementasi pertama, kita cukup memanggil
fungsi toupper [1]
dari pustaka standar C dan menjalankan loop gaya-C:
void toupper_rawloop(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { buf[i] = toupper(buf[i]); } }
Dalam implementasi kedua, kami menggunakan pendekatan yang
lebih modern dengan mengganti siklus mentah dengan
std :: transform :
void toupper_transform(char* buf, size_t size) { std::transform(buf, buf + size, buf, ::toupper); }
Akhirnya, dalam implementasi ketiga, kami menggunakan algoritma khusus yang berfungsi dengan karakter ASCII. Ia memeriksa apakah karakter berada dalam kisaran
a - z , dan jika berhasil, mengganti huruf yang sama dalam huruf besar, mengurangi angka 32 dari kode karakter [2]:
void toupper_branch(char* buf, size_t size) { for (size_t i = 0; i < size; i++) { char c = buf[i]; if (c >= 'a' && c <= 'z') { buf[i] = c - 32; } } }
Terlihat mudah, bukan?
Sekarang kita akan mengukur kecepatan implementasi ini di laptop saya dengan prosesor Skylake i7-6700HQ pada kompiler gcc 5.5 dengan pengaturan default. Hasilnya diberikan dalam bentuk grafik pencar [3]:
Kami akan segera menangani tiga pertanyaan yang tidak relevan dengan tugas kami.
Pertama, lihat grafik algoritma percabangan (ditunjukkan dalam warna hijau). Ini bervariasi secara signifikan tergantung pada ukuran data input - dua grafik lainnya tetap hampir datar. Ini sebenarnya hanya artefak pengujian. Input karakter ASCII dipilih secara acak [4], oleh karena itu, faktor penentu dalam kasus implementasi ketiga adalah pengoperasian algoritma prediksi cabang. Dengan sejumlah kecil data, itu benar-benar menghafal urutan elemen saat iterasi dilakukan, sehingga jumlah kesalahan kecil dan kecepatan tinggi,
seperti yang ditunjukkan dalam catatan ini . Ketika ukuran urutan data bertambah, algoritma prediksi mengingat semakin sedikit sampai akhirnya mulai hilang dengan setiap huruf kapital (0,27 meleset per karakter), dan kemudian grafik diratakan.
Kedua, perhatikan kelompok bintik-bintik hijau di kiri atas, yang sesuai dengan kecepatan varian yang jauh lebih rendah dengan percabangan
toupper_branch :
Ini bukan artefak yang terisolasi: bintik-bintik seperti itu muncul selama beberapa peluncuran. Pada saat yang sama, mereka tidak dapat direproduksi jika Anda menguji algoritma hanya secara khusus pada ukuran data ini - mereka muncul hanya ketika tes dijalankan di semua ukuran. Tetapi dalam kasus ini, mereka tidak selalu muncul. Saya tidak secara khusus menyelidiki hal itu, tetapi saya dapat berasumsi bahwa ini adalah karena beberapa konflik nama atau alias dalam algoritma prediksi cabang atau ketika memetakan halaman fisik dari memori 4 KB ke virtual (meskipun pengacakan ruang alamat virtual dimatikan).
Ketiga, implementasi
toupper_rawloop (diperlihatkan dengan warna biru) pada grafik terlihat seperti dua baris terpisah: satu sedikit di atas tanda 2 langkah per karakter, dan yang lain pada tingkat 1,5 langkah per karakter. Dua baris ini muncul di semua penguji. Opsi yang lebih cepat, dengan kecepatan 1,57 karakter per siklus, sebenarnya melambat pada port unduhan: membaca data pada port 2 dan 3 terjadi pada kecepatan 1,54 operasi mikro per siklus, sehingga mereka akan sibuk 98%. Saya tidak bisa menetapkan alasan untuk “rezim” yang lebih lambat.
Ketika saya sedang berurusan dengan masalah ini, "rezim" yang cepat tiba-tiba menghilang dan hanya lambat yang tersisa. Mungkin prosesor menyadari apa yang saya coba lakukan dan diam-diam mengunduh pembaruan untuk kode mikro untuk menghapus kontradiksi, tetapi saya (masih) punya bukti - gambar vektor dengan grafik.
Lalu apa yang menarik bagi kita dalam contoh ini?
Tetapi yang menarik bagi kami adalah bahwa versi dengan siklus mentah adalah 3-4 kali lebih cepat daripada versi dengan
std :: transform : 1,5-2 siklus per karakter dibandingkan 7 dengan beberapa siklus per karakter.
Ada apa di sini? Apakah algoritma standar gagal saya? Apakah
std :: transform memiliki kekurangan?
Tidak juga. Lebih tepatnya, tidak sama sekali.
Ternyata hasil tersebut muncul ketika fungsi dikompilasi dalam
file yang berbeda . Jika Anda meletakkannya di file yang sama, maka kinerjanya menjadi sama rendahnya.
Dan tidak, keberpihakan tidak ada hubungannya dengan itu.
Tapi itu tidak semua: versi cepat dengan siklus mentah, ketika dikompilasi dalam file terpisah, melambat jika Anda cukup melampirkan file header
<algorithm> ke dalamnya. Ya, itu benar: cukup sambungkan file ini, yang tidak pernah digunakan dan tidak menghasilkan kode apa pun dalam file objek akhir, dan kecepatan siklus "mentah" akan turun 3-4 kali. Sebaliknya, versi dengan
std :: transform dipercepat hingga batasnya jika Anda menyalin dan menempel implementasi
std :: transform dari file
<algorithm> , tetapi tidak menyertakan file ini.
Keanehan tidak berakhir di sana (tidak akan ada lagi, saya janji): termasuk file
<algorithm> tidak selalu mengarah ke efek yang dijelaskan. Penurunan kecepatan terjadi jika
<algorithm> terhubung lebih awal dari
<ctype.h> , tetapi jika Anda menukar mereka, maka tidak ada:
Kode lambat: #include <algorithm> #include <ctype.h>
Kode cepat: #include <ctype.h> #include <algorithm>
Sebenarnya, anomali ini muncul dalam diri saya (dalam proyek lain) ketika dentang-format secara otomatis mengurutkan file header yang disertakan dan menempatkan
<algorithm> di bagian paling awal daftar, di mana ia berada (maka header clickbait artikel).
Tentu, cepat atau lambat kita harus masuk ke daftar assembler. Kami tidak akan menunda momen tidak menyenangkan ini.
Versi fungsi
cepat dan lambat [5] ditunjukkan di bawah ini, loop kecil disediakan dengan anotasi:
<algorithm> terhubung terlebih dahulu: toupper_rawloop(char*, unsigned long): push rbp push rbx lea rbp, [rdi+rsi] sub rsp, 8 test rsi, rsi je .L1 mov rbx, rdi .L5: movsx edi, BYTE PTR [rbx] ; char- *buf add rbx, 1 ; buf++ call toupper ; toupper(c) mov BYTE PTR [rbx-1], al ; buf[-1] cmp rbp, rbx ; buf == buf_end jne .L5 ; .L1: add rsp, 8 pop rbx pop rbp ret
<algorithm> terhubung kedua: toupper_rawloop(char*, unsigned long): test rsi, rsi je .L7 push rbp push rbx mov rbp, rsi mov rbx, rdi sub rsp, 8 call __ctype_toupper_loc lea rsi, [rbx+rbp] mov rdi, rbx .L4: ; char- buf movsx rcx, BYTE PTR [rdi] ; toupper ; ( __ctype_toupper_loc) mov rdx, QWORD PTR [rax] ; buf++ add rdi, 1 ; toupper , ; mov edx, DWORD PTR [rdx+rcx*4] mov BYTE PTR [rdi-1], dl ; cmp rsi, rdi ; buf == end_buf jne .L4 ; add rsp, 8 pop rbx pop rbp .L7: rep ret
Perbedaan utama adalah bahwa dalam versi lambat fungsi toupper hanya dipanggil dalam satu lingkaran, sedangkan dalam versi cepat tidak ada panggilan fungsi sama sekali, dan hanya ada pencarian di tabel korespondensi [6], yaitu tubuh fungsi
std :: toupper diganti di tempat panggilan.
Jika Anda melihat
kode sumber pustaka glibc, kami menemukan implementasi fungsi
toupper di sana:
__extern_inline int
Seperti yang dapat kita lihat,
toupper didefinisikan sebagai fungsi
inline eksternal yang pertama kali memeriksa bahwa ukuran karakter char cocok dalam satu byte [7], dan kemudian mencari karakter dalam tabel korespondensi yang dikembalikan oleh fungsi
__ctype_toupper_loc () . Fungsi ini mengembalikan pointer aliran lokal (dari tipe
const int ** ), yang, pada gilirannya, menunjuk ke tabel korespondensi, dari mana, sebagai tanggapan atas permintaan simbol kami, versi huruf besarnya dikembalikan [8].
Sekarang jelas apa yang terjadi dalam daftar. Dalam versi cepat dari algoritma, kompiler menggantikan tubuh fungsi
toupper , tetapi tidak dapat menggantikan panggilan ke fungsi
__ctype_toupper_loc () [9]. Panggilan ini, bagaimanapun, dinyatakan sebagai
__attribute __ ((const)) , yang berarti bahwa nilai kembali hanya bergantung pada argumen (yang tidak ada di sini). Kompiler tahu bahwa fungsi ini mengembalikan nilai yang sama setiap kali, dan karenanya mengambil panggilannya di luar loop, dan dalam loop itu sendiri hanya ada beberapa operasi baca yang terkait dengan mengakses tabel korespondensi, menulis nilai baru ke buffer, dan kontrol loop.
Dalam versi lambat, panggilan ke
toupper () tetap di tubuh loop. Loop itu sendiri lebih pendek dengan satu perintah, tetapi, tentu saja, sekarang Anda masih harus menjalankan semua kode di dalam fungsi
toupper . Di sistem saya, tampilannya seperti ini:
lea edx,[rdi+0x80] ; edx = rdi + 0x80 movsxd rax,edi ; c cmp edx,0x17f ; , c -128 255 ja 2a ; , mov rdx,QWORD PTR [rip+0x395f30] ; ; mov rdx,QWORD PTR fs:[rdx] ; ; mov rdx,QWORD PTR [rdx] ; ; mov rdx,QWORD PTR [rdx+0x48] ; toupper mov eax,DWORD PTR [rdx+rax*4+0x200] ; c 2a: ret
Karena ini adalah panggilan yang tidak tertanam, program ini bekerja lebih banyak. Setidaknya ada lima operasi berturut-turut mengakses memori (yang disebut pengejaran pointer,
pengejaran pointer ). Dalam versi cepat, hanya dua yang tersisa, karena yang lainnya dikeluarkan dari loop. Penundaan antara memanggil suatu fungsi dan keluar darinya seharusnya sekitar 25 siklus, dan kami memiliki sekitar 7 siklus yang keluar - ini berarti bahwa prosesor mampu memaralelkan panggilan, yang cukup baik, mengingat keadaan.
Kenapa begitu?
Dalam rantai panjang file sertakan, file header C ++, seperti
<algorithm> , termasuk, pada gilirannya, file
<bits / os_defines.h> , yang berisi baris berikut:
Ketika file
<ctype.h> akhirnya terhubung, karena arahan ini, kode di mana
toupper didefinisikan sebagai
extern inline tidak dapat dimasukkan:
#if !defined __NO_CTYPE # ifdef __isctype_f __isctype_f (alnum)
Harap perhatikan bahwa ketika menghubungkan
<ctype.h> versi C ++ dari
toupper tidak pernah didefinisikan sebagai makro - maksimum sebagai
extern inline - karena definisi makro dilindungi oleh pemeriksaan
! Defined __cplusplus dan karenanya tidak akan pernah berlaku.
Secara umum, saya tidak tahu pasti apakah
__NO_CTYPE dalam kasus ini harus mengecualikan tubuh fungsi
tolower dan
toupper yang dinyatakan sebagai
eksternal inline , tetapi inilah yang sebenarnya terjadi - dan karenanya merupakan penurunan signifikan dalam kecepatan siklus kami. Sebagai kesimpulan, saya dapat mengatakan bahwa jika Anda memasukkan
<cctype> alih-alih
<ctype.h> (mis., C ++ adalah versi file header C yang menempatkan fungsi di
std :: namespace ), maka dalam hal ini kode akan bekerja lambat karena
<cctype> akhirnya termasuk
<bits / os_defines.h> .
Apakah semua itu penting? Tidak, tidak
Fungsi
toupper tidak cocok untuk pekerjaan serius dengan karakter bahasa yang berbeda, jadi jika Anda hanya perlu memproses karakter ASCII, Anda dapat menulis implementasi yang lebih cepat. Jika Anda memerlukan pekerjaan serius dengan teks, maka kemungkinan besar Anda akan menggunakan UTF-8 dan harus menggunakan semacam ICU untuk mendukung pengaturan regional, atau menunggu hingga dukungan Unicode muncul di C ++ (mungkin perlu waktu lama untuk menunggu) . Jadi pernyataan "format dentang dapat menyebabkan penurunan kinerja 4x" hanya cocok sebagai header clickbait.
Apakah efek ini diamati di semua versi libc? Ya, di hampir semua, tetapi bahkan di sini tidak sesederhana itu.
Hasil yang ditunjukkan di atas berlaku untuk gcc 5.5 dan glibc 2.23, karena saya menggunakan versi ini, tetapi sesuatu yang baru terjadi di versi baru (mulai dari tentang glibc 2.27). Di sana, menyalakan
<algorithm> sebelum
<ctype.h> masih memberikan efek yang sama, tetapi sekarang
<stdlib.h> [10] juga menciptakan masalah: jika Anda menyalakannya sebelum
<ctype.h> , kinerja juga akan turun, yang tidak diamati pada versi sebelumnya. Jelas, dalam versi yang lebih baru, file
<stdlib.h> juga mengandung definisi
__NO_CTYPE . Setidaknya, sekarang tidak mungkin menyalahkan format dentang untuk penyortiran - ini hanya dapat membantu menyelesaikan masalah (jika tidak ada file masalah lain dalam daftar file yang terhubung).
Saya memposting
laporan bug di libc , sehingga kemungkinan bug ini akan diperbaiki, tetapi tidak ada keraguan bahwa kesalahan terkait dengan urutan di mana file header terhubung akan mengganggu kita lebih lanjut.
Komentar
Saya tidak memiliki sistem komentar di situs saya, tetapi saya sedang mengusahakannya (yaitu, secara berkala mengeluh bahwa sulit untuk membuat komentar di situs statis).
Sementara itu, Anda dapat mendiskusikan artikel ini di situs web
Hacker News atau
lobste.rs .
Ucapan Terima Kasih
Terima kasih kepada pengguna ufo dengan Hacker News, yang
menunjukkan bahwa tidak perlu menggunakan fungsi lambda untuk mengadaptasi
std :: toupper untuk digunakan dalam
std :: transform , dan juga kepada Jonathan Muller yang
menjelaskan bahwa fungsi lambda masih diperlukan.
- Ya, fungsi toupper (3) dari file header <ctype.h> tidak cocok untuk bekerja dengan sebagian besar karakter non-ASCII, karena tidak dapat menangani karakter yang lebih besar dari satu byte, tetapi cocok untuk tugas kami, karena kami hanya akan meneruskan string karakter ASCII ke dalamnya.
- Dalam tabel ASCII, karakter huruf kecil dan huruf besar sangat mudah ditemukan - pada jarak 32 posisi dari satu sama lain, yang berarti bahwa Anda dapat mentransfer karakter dari satu kasus ke yang lain hanya dengan mengurangi atau menambahkan 32. Secara umum, jika kita tahu pasti bahwa semua input datanya adalah huruf ASCII, kita dapat mereset bit ke-5 tanpa pemeriksaan (misalnya, c & 0b11011111 ) untuk mengubah huruf besar menjadi huruf kecil, sementara ini tidak akan tercermin dalam huruf kecil. Tapi kami mungkin tidak tahu, jadi kami harus memeriksa apakah karakternya adalah huruf, agar tidak secara tidak sengaja memecah karakter non-huruf seperti char .
- Itu harus disebut sebaran plot dengan penambahan "noise" ke lokasi poin. Sebenarnya, ini adalah diagram sebar biasa di mana parameter yang menarik bagi kami (ukuran data input) diplot pada sumbu x, dan kecepatan kerja pada sumbu y (mengukur per simbol - semakin rendah nilainya, semakin tinggi kecepatan ). Fitur utama diagram ini adalah bahwa untuk setiap nilai parameter pada sumbu x, pengambilan sampel dilakukan beberapa kali: dalam kasus ini, pengujian diulang 10 kali untuk setiap ukuran array.
- Yaitu, karakter dipilih secara acak dan seragam dari kisaran [32, 127], sehingga kondisi dalam fungsi akan benar di sekitar 27% kasus.
- Kedua daftar merujuk pada implementasi siklus mentah dan hanya berbeda dalam urutan di mana file <algorithm> dan <ctype.h> dimasukkan . Kode sumber yang dihasilkan sama untuk semua implementasi - baik dalam versi cepat dan lambat. Misalnya, implementasi dengan std :: transform akan menghasilkan kode assembler lambat yang sama jika Anda menyertakan file <algorithm> , dan kode cepat yang sama jika Anda hanya menyalin definisi fungsi dan tidak menyertakan file.
- Namun, loop cepat ini lebih lambat daripada yang bisa karena pointer ke tabel korespondensi dibaca terlalu banyak ( mov rdx, QWORD PTR [rax] ) di dalam loop. Pointer ini mungkin berbeda tergantung pada pengaturan regional, tetapi tidak diperbarui selama pelaksanaan siklus dan oleh karena itu dapat dipindahkan di luar siklus. Pasti kompiler percaya bahwa tidak ada alasan yang cukup untuk ini, karena kita menulis ke array elemen tipe char , dan mereka pada prinsipnya dapat digunakan sebagai alias untuk [rax] yaitu arahkan ke tabel. Bagaimanapun, bahkan __restrict__ tidak akan membantu di sini. Tetapi dalam versi lain dari loop, di mana nilai toupper hanya ditambahkan dan tidak ada yang ditulis ke array, optimasi ini diterapkan - pointer dibaca di luar loop.
- Pemeriksaan ini tidak tercermin dalam kode assembler yang dapat disubstitusikan, karena kompiler sudah tahu bahwa nilai-nilai char selalu dalam kisaran [-128, 255] . Pemeriksaan ini diperlukan hanya karena API fungsi toupper © menerima nilai dari tipe int , bukan char , sehingga pengguna dapat memberikan jumlah tipe int yang dikenalinya, sementara tabel korespondensi dirancang hanya untuk nilai-nilai tipe char , jadi memeriksa membantu menghindari pembacaan di luar buffer .
- Ngomong-ngomong, ini menjelaskan mengapa prosedur std :: toupper tidak tergantung pada ukuran data input: mereka tidak menggunakan cabang (kecuali untuk pemeriksaan jangkauan, yang sangat diprediksi), tetapi menggunakan tabel korespondensi independen cabang. ↵
- Mengganti panggilan ini tidak akan berfungsi bahkan dengan keinginan yang sangat kuat: isi fungsi tidak tersedia di file header.
- Saya sama sekali tidak menemukan kesalahan dengan stdlib.h (atau <algorithm> , dalam hal ini) - sangat mungkin bahwa banyak file header C lainnya dan semua file header C ++ juga menyebabkan perilaku ini, saya hanya tidak mengujinya. Saya menghubungkan stdlib.h hanya untuk menentukan size_t .
Catatan Artikel ini pertama kali dipublikasikan di situs web
Performance Matters . Artikel yang diterjemahkan diposting di sini dengan izin dari penulis.