Baru-baru ini proposal untuk kernel Linux dirilis, di mana diusulkan untuk menyertakan satu set tambalan dengan a implementasi yang dioptimalkan dari fungsi memchr() digunakan untuk mencari karakter dalam array.
Fungsi memchr() memindai n byte terdepan dari area memori yang ditunjuk oleh s untuk instance pertama dari c. Baik c dan byte di area memori yang ditunjuk oleh s ditafsirkan sebagai karakter yang tidak ditandatangani.
Proposal menjanjikan lebih cepat untuk menemukan karakter dalam blok memori. Dalam pengujian pengembang, implementasi baru bisa hampir empat kali lebih cepat pada pencarian besar
Berbeda dengan versi sebelumnya, yang menggunakan perbandingan byte demi byte, implementasi yang diusulkan dibuat dengan mempertimbangkan penggunaan penuh register CPU 64-bit dan 32-bit. Alih-alih byte, perbandingan dilakukan dengan menggunakan kata-kata mesin, yang memungkinkan setidaknya 4 byte untuk dibandingkan pada satu waktu.
Rangkaian tambalan ini mengoptimalkan "memchr()" dan menambahkan makro untuk
"memchr_inv()" sehingga kedua fungsi dapat menggunakannya untuk menghasilkan bitmask.Implementasi asli dari "memchr()" didasarkan pada perbandingan byte,
yang tidak sepenuhnya menggunakan register 64 atau 32 bit di CPU. Kami menerapkan
perbandingan dengan kata-kata sehingga setidaknya 4 byte dapat dibandingkan dengan yang sama
cuaca. Memchr() yang dioptimalkan hampir 4 kali lebih cepat dari aslinya
untuk rantai panjang. Di Kernel Linux, kami menemukan bahwa panjang string
dicari oleh "memchr()" hingga 512 byte di driver/misc/lkdtm/heap.c.
Saat mencari di string besar, versi baru ternyata sekitar 4 kali lebih cepat dari yang lama (misalnya, untuk string 1000 karakter). Untuk rantai kecil, efisiensi implementasi baru tidak terlalu signifikan, tetapi masih lebih tinggi dari versi aslinya.
Hal yang menarik dari proposal baru adalah peningkatan untuk rantai besar, yang meningkatkan waktu secara signifikan. Perlu disebutkan bahwa di kernel Linux, ukuran string yang diproses dalam memchr() mencapai 512 byte. Dalam pengujian kami, peningkatan kinerja untuk string 512-byte, dalam situasi di mana karakter pencarian di ujung tali, itu adalah 20%.
Perlu disebutkan bahwa versi asli memchr() diimplementasikan dengan teknik perbandingan byte-bijaksana, yang tidak sepenuhnya menggunakan register pada CPU 64-bit atau 32-bit.
Kami menggunakan perbandingan seluruh kata sehingga 8 karakter dapat dibandingkan pada waktu yang sama pada CPU. Kode ini didasarkan pada implementasi David Light.
Kami membuat dua file untuk mengukur kinerja file pertama yang berisi rata-rata 10 karakter di depan karakter tujuan. File kedua berisi setidaknya 1000 karakter sebelum karakter sasaran.
Implementasi "memchr()" kami sedikit lebih baik pada tes pertama dan hampir 4 kali lebih cepat dari aslinya implementasi pada tes kedua.
Pengujian kernel 5.18 dengan varian "memchr()" baru untuk arsitektur 32-bit dan 64-bit tidak mengungkapkan masalah.
Apa yang terjadi jika p tidak sejajar dengan 8 (atau 4 pada target 32 bit)? Tidak semua target mendukung beban yang tidak selaras (efisien), bukan?
Saya pikir itu berfungsi jika p tidak selaras 8 atau 4 byte. Katakanlah string adalah 10 byte. Perulangan for di sini akan mencari 8 byte pertama. Jika karakter tujuan dalam 2 byte terakhir, loop for kedua akan menemukannya. Ini juga berfungsi seperti ini pada mesin 32-bit.
Keuntungan kinerja keseluruhan belum dievaluasi subsistem kernel saat menggunakan varian "memchr()" yang dioptimalkan, juga belum dibahas apakah akan menimpa implementasi (panggilan fungsi memchr() terjadi 129 kali dalam kode kernel, termasuk driver dan sistem file).
Akhirnya Jika Anda tertarik untuk mengetahui lebih banyak tentang itu, Anda dapat memeriksa detailnya Di tautan berikut.