(Statis) Pemilihan wadah optimal dalam program C ++

Halo Hari ini saya ingin berbicara lagi tentang analisis statis. Dan lagi tentang C ++. Hanya, tidak seperti PVS-Studio, kami tidak akan mencari kesalahan dalam program kami (meskipun mereka tidak hanya mencari kesalahan), tetapi untuk tempat-tempat yang tidak ditulis cukup optimal. Dan salah satu tempat ini memilih wadah untuk data dalam program. Jika saya menarik bagi Anda, selamat datang di kucing!

Masalah

Pada CoreHard 2018 Autumn (konferensi yang sangat bagus, ayo) saya berbicara tentang bagaimana kompiler C ++ tidak dioptimalkan dengan baik saat ini. Dan salah satu keluhan saya adalah bahwa penyusun tidak dapat mengoptimalkan penggunaan wadah dalam program kami. Mari kita lihat beberapa contoh kode.

void foo() { std::vector<int> v(42); } 

Tampaknya dalam kasus sederhana seperti itu, kompiler harus dapat mengoptimalkan fungsi ini dan cukup membuang deklarasi variabel dari tipe std :: vector, karena mulai dengan C ++ 14 kompiler diperbolehkan untuk menghapus alokasi memori dinamis, tetapi kompiler tidak. Alasan untuk ini adalah bahwa saat ini hanya satu kompiler C ++ mengimplementasikan optimasi untuk menghapus alokasi dinamis - Dentang. Semua kompiler lain sejauh ini tidak tahu bagaimana melakukan ini. Tetapi bahkan Dentang dapat melakukan ini dalam sejumlah kasus terbatas.

Dalam hal ini, kita bisa mengganti std :: vector dengan std :: array, asalkan ukuran vektor yang dipilih tidak terlalu besar, karena kita mungkin tidak memiliki cukup tumpukan untuk penggantian seperti itu. Penggantian seperti itu akan menghapus alokasi memori yang agak mahal ke heap, dan ditambah adalah ketika menggunakan std :: array, kompiler sudah dapat membuang std :: array dari fungsi sama sekali!

Jika kita berbicara tentang pengoptimalan kinerja, kami mengusulkan untuk mempertimbangkan contoh berikut:

 void foo() { std::vector<int> v; for(int i = 0; i < 42; ++i) { v.insert(v.begin(), 42); } for(const auto val : v) { std::cout << val << ' '; } } 

Dalam hal ini, kita melihat penggunaan operasi yang sangat tidak efektif dalam kasus std :: vector - insertion di awal wadah. Semua programmer C ++ tahu bahwa ini sangat buruk untuk dilakukan, karena menyebabkan semua elemen bergeser setiap waktu, yang menyebabkan biaya besar untuk menyalin / memindahkan. Dalam kasus ini akan jauh lebih baik untuk menggantinya dengan std :: list, yang tidak peduli di mana penyisipan berlangsung, atau std :: deque (meskipun dalam hal ini Anda dapat dengan jelas melihat bahwa Anda tidak hanya perlu menggunakan insert. Tapi ini hanya sebuah contoh, tidak lebih lanjut :)

Mari kita lihat contoh kode lain:

 void foo() { std::list<int> v; for(int i = 0; i < 3; ++i) { v.push_front(i); } for(const auto val : v) { std::cout << val << ' '; } } 

Dalam hal ini, kita dapat melihat bahwa kita dapat dengan mudah mengganti std :: list (ya, saya tahu bahwa beberapa orang menggunakannya) dengan std :: forward_list. Dalam hal ini, dalam hal ini, kami sama sekali tidak akan kehilangan apa pun, tetapi kami akan mendapatkan penghematan memori. Secara alami, kompiler tidak melakukan optimasi seperti itu sekarang.

Trik serupa dapat dilakukan dalam contoh berikut:

 void foo() { std::deque<int> v; for(int i = 0; i < 3; ++i) { v.push_back(i); } for(int i = 0; i < 3; ++i) { std::cout << v.back() << ' '; v.pop_back(); } } 

Di sini kita dapat melihat bahwa yang benar-benar kita butuhkan bukanlah std :: deque, tetapi std :: stack. Ini tidak dapat disebut optimasi, karena std :: stack adalah adaptor, dan secara default menggunakan std :: deque inside (kecuali pengguna menentukan sebaliknya). Di sini kita dapat berbicara lebih banyak tentang pengoptimalan semantik, mis. menyederhanakan kode untuk mengerti. Dari sudut pandang saya, ini juga penting. Jika Anda bertanya, "Mungkin penggantian seperti itu juga memberikan peningkatan kinerja?", Saya akan menjawab "Mungkin. Lihat detail implementasi di versi perpustakaan standar Anda. "

Yah, saya pikir ada cukup banyak contoh. Anda masing-masing juga dapat menghasilkan banyak dari mereka.

Alat bekas

Untuk mengimplementasikan analisa statis, saya menggunakan Clang Static Analzyer (CSA) dan Clang Tidy, yang merupakan bagian dari paket LLVM. Saya memilih alat ini, karena saya menganggapnya alat yang paling menjanjikan di antara alat terbuka untuk analisis statis. Selain itu, Clang menyediakan salah satu parser C ++ berkualitas tinggi yang tidak dapat dibanggakan oleh analisis statis lainnya (kecuali tentu saja mereka menggunakan libclang).

Baik CSA dan Clang Tidy adalah penganalisa statis, keduanya merupakan bagian dari LLVM. Apa bedanya? Perbedaannya adalah bahwa Clang Tidy dirancang untuk menulis cek sederhana, yang pada dasarnya terdiri dari menemukan semacam pola pada pohon sintaksis abstrak, menampilkan semacam peringatan, dan mungkin menggantinya secara otomatis dengan yang lain. Anda dapat mempelajari lebih lanjut tentang Clang Tidy di sini .

CSA dirancang untuk menulis pemeriksaan yang lebih "serius" dan intensif sumber daya (baik dari sudut pandang implementasi, dan dari sudut pandang waktu eksekusi / memori yang dihabiskan). Di sana, misalnya, mekanisme eksekusi simbolis tersedia.

Saya memutuskan untuk mengimplementasikan cek di CSA, karena sepertinya tidak lazim bagi saya, apalagi di masa depan akan semakin sulit. Dan diputuskan untuk dijalankan melalui Clang Tidy, karena analisa statis ini memiliki banyak integrasi dengan berbagai IDE.

Bagaimana kita akan (mencoba) menyelesaikan masalah

Untuk memulainya, ada baiknya memperkenalkan beberapa pembatasan yang cukup kuat, yang terutama terkait dengan fakta bahwa ini hanyalah sebuah prototipe:

• Analisis hanya pada tingkat fungsi; Batasan ini berarti bahwa tidak akan ada analisis antara fungsi, serta antara unit terjemahan. Pembatasan analisis antar fungsi diberlakukan untuk menyederhanakan implementasi analisis ini dan di masa depan dapat relatif mudah diperbaiki dengan menjalankan analisis statis untuk seluruh unit terjemahan, dan tidak hanya untuk setiap fungsi. Pembatasan analisis antar unit terjemahan diberlakukan oleh pembatasan yang ada dalam CSA, yang akan segera diperbaiki (komitmen sudah mengalir ke hulu);
• Dukungan hanya untuk sejumlah kontainer. Ini relatif mudah diperbaiki di masa mendatang dengan menambahkan aturan baru untuk wadah baru.
• Gunakan untuk analisis hanya pohon sintaksis abstrak. Karena untuk membuat prototipe ini adalah jenis analisis yang paling sederhana. Untuk hasil yang lebih akurat, tentu saja, Anda dapat mencoba menggunakan setidaknya eksekusi simbolis, tetapi metode ini memiliki kekurangan. Anda dapat membaca lebih lanjut tentang metode di sini .

Sekarang prototipe mengimplementasikan algoritma sederhana berikut:

• Pertama, pada pohon sintaksis abstrak, kami menemukan simpul yang bertanggung jawab untuk mendeklarasikan variabel tipe wadah yang kami dukung.
• Kemudian kami menemukan operasi yang terkait dengan wadah ini, mengklasifikasikannya dan menyimpan informasi ini dalam cache sementara.
• Setelah mencapai akhir fungsi, kami menganalisis statistik yang dikumpulkan dan, berdasarkan aturan yang telah ditentukan, mengeluarkan rekomendasi tentang penggunaan wadah.

Klasifikasi operasi kontainer saat ini adalah sebagai berikut (akan diperluas di masa depan):

• Tambahkan item ke bagian atas wadah.
• Menambahkan item ke tengah wadah.
• Menambahkan item ke ujung wadah.
• Menghapus item dari awal wadah.
• Menghapus item dari tengah wadah.
• Menghapus item dari ujung wadah.

Klasifikasi saat ini tidak lengkap dan bahkan pada daftar ini tidak berfungsi dengan benar. Misalnya, operasi penyisipan, bahkan jika itu dilakukan di awal, penganalisis mengklasifikasikan sebagai menyisipkan ke tengah, meskipun pada kenyataannya tidak sama sekali.

Melawan positif palsu

Dalam analisis statis apa pun, positif palsu adalah sakit kepala utama. Jika jumlah mereka terlalu banyak, maka pesan-pesan berguna hilang di sampah. Oleh karena itu, dalam hal ini, Anda harus bertindak sangat konservatif dan mengeluarkan peringatan hanya dalam kasus di mana kami benar-benar yakin dengan diagnostik kami dan dapat mengatakan bahwa ada sesuatu yang salah di beberapa tempat dalam kode.

Jika kita berbicara tentang pengoptimalan kompiler, maka itu masih lebih menyedihkan di sana - pengoptimalan yang tepat tidak dapat mengubah perilaku program menurut Standar C ++ (jika tidak, pengoptimal seperti itu tidak berharga). Dan optimasi juga tidak boleh menimbulkan pesimisasi :) Jadi di sini Anda harus lebih berhati-hati dalam mengambil keputusan.

Dalam penganalisa ini, perjuangan ini menghasilkan fakta bahwa jika penganalisa melihat bahwa beberapa operasi yang tidak didukung saat ini sedang dilakukan, maka analisis untuk wadah ini dimatikan.

Kekurangan dan kemungkinan solusi

Ada beberapa masalah dengan metode ini.

Masalah pertama adalah bahwa untuk penganalisa saat ini semua cabang kode sama kemungkinannya. Lebih tepatnya, dia bahkan tidak tahu tentang hal seperti cabang berbeda dari eksekusi kode.
Ini diterjemahkan ke dalam masalah dengan analisis untuk sesuatu seperti kode ini:

 void foo(int* ptr, std::vector<int>& v) { if(ptr == nullptr) { v.insert(v.begin(), 42); } else { v.push_back(84); } } 

Kemungkinan besar, dalam aplikasi kita, cabang kode ini tidak memiliki probabilitas eksekusi yang sama, karena di dunia nyata pointer biasanya menunjukkan sesuatu yang normal, dan bukan nullptr. Dalam LLVM yang sama ada heuristik statis pada skor ini. Sebagai contoh, ini mempertimbangkan kasus di atas dengan membandingkan pointer dengan nullptr, dan membandingkan satu sama lain persamaan nilai dua variabel dengan floating point, dan beberapa kasus menarik lainnya. Tapi ini lebih dan lebih mirip kruk, dan dari sudut pandang saya, solusi nyata untuk masalah ini adalah menambahkan analisis atau instrumentasi yang dinamis.

Masalah kedua adalah kurangnya dukungan untuk wadah khusus. Kita hidup di dunia C ++, mereka suka naik di sini (mari kita tinggalkan diskusi tentang alasan untuk fenomena tidak selalu buruk ini di luar ruang lingkup artikel ini) semuanya, termasuk wadah kami. Contohnya termasuk LLVM yang sama, LibreOffice, dan banyak lainnya. Dalam hal ini, muncul pertanyaan - bagaimana menganalisis wadah bukan dari perpustakaan STL? Lagi pula, saya ingin memasukkan analisis untuk wadah sebanyak mungkin.

Ada berbagai cara untuk menyelesaikan masalah.

Yang pertama adalah bahwa pengguna membubuhi keterangan wadah mereka dalam beberapa cara (semacam komentar khusus, atribut C ++, sesuatu yang lain). Masalah dengan metode ini adalah bahwa kita perlu memahami bagaimana membuat anotasi secara umum, informasi apa yang kita butuhkan untuk analisis kualitatif. Masalah lain mungkin adalah modifikasi kode wadah itu sendiri, yang tidak selalu memungkinkan.

Metode kedua menawarkan pengguna mekanisme untuk menulis aturan mereka sendiri. Saat ini, aturan dalam alat analisis dijahit ke dalam kode sumber alat analisis itu sendiri, dan jika pengguna ingin menambahkan aturan mereka sendiri, maka ia perlu mengunduh kode sumber alat analisis, menyusunnya, mencari cara menulis cek, menulis, membangun kembali, dan sebagainya. Anda dapat memberi pengguna cara untuk mengatur ceknya pada beberapa DSL, di mana pengguna hanya menulis cek untuk wadahnya, dan penganalisa terlibat dalam seluruh rutinitas. Saya menganggap metode ini lebih menjanjikan daripada yang sebelumnya.

Juga, penggantian wadah otomatis tidak didukung, karena fungsi ini tidak ada dalam CSA (tetapi ada di Clang Tidy). Tetapi dalam kasus-kasus sulit, melakukan AutoCorrect tidak selalu merupakan tugas yang sepele, dan penganalisa bekerja lebih mungkin dalam mode semi-manual.

Kemungkinan aplikasi

Saya melihat beberapa aplikasi untuk jenis analisis ini:

1. Seperti analisa statis. Semuanya sederhana di sini - tes analisis statis lainnya, yang Anda jalankan sesuai keinginan hati Anda (dengan tangan Anda, dalam IDE secara otomatis selama pengembangan, pada CI, dll.), Di mana Anda mungkin akan diberi petunjuk bahwa di suatu tempat Anda bisa ambil wadah dan lebih baik.
2. Seperti pengoptimalan dalam kompiler. Dalam beberapa kasus, kami dapat menjamin bahwa mengganti wadah tidak akan memengaruhi kinerja secara negatif. Misalnya, mengganti std :: vektor untuk ukuran kecil yang diketahui pada waktu kompilasi dengan std :: array atau mengganti std :: daftar dengan std :: forward_list ketika kita tidak membutuhkan koneksi dan kita tidak mengambil ukuran dari daftar. Kompilator dapat mengganti wadah dengan yang lebih optimal tanpa sepengetahuan kami, seperti yang telah dilakukan untuk sejumlah hal yang sangat besar.
3. Seperti analisa dinamis. Ini adalah arah yang menurut saya paling menjanjikan untuk jenis analisis ini. Memang, dengan bantuan pengetahuan tentang profil eksekusi program, kami, misalnya, dapat memperoleh informasi penting bagi kami seperti probabilitas setiap eksekusi kode cabang. Dan ini diperlukan untuk penilaian yang lebih akurat. Dan dengan analisis seperti itu, Anda sudah bisa berpikir ke arah integrasi dengan PGO ...

Perlu juga dicatat bahwa metode ini berlaku tentu saja tidak hanya untuk program C ++. Saya benar-benar ingin melihat analisis / optimasi statis semacam ini di kompiler dan untuk bahasa pemrograman lain. Misalnya, penganalisa statis SAP untuk ABAP sudah tahu bagaimana melakukan analisis optimalitas statis pada tingkat dasar, yang merupakan kabar baik. Jika Anda tahu proyek serupa untuk bahasa pemrograman lain - tulis di komentar dan saya akan menambah artikel!

Bekerja dalam arah yang serupa

Untuk dunia C ++, saya belum menemukan analisa seperti itu di mana pun. Untuk dunia ABAP, saya menyebutkan alat analisa di atas, yang dapat menemukan operasi yang tidak efisien untuk beberapa bagian kontainer standar, tetapi sejauh yang saya tahu, analisis statis yang sangat sederhana diterapkan di sana.

Karya yang jauh lebih menarik adalah Chameleon - penganalisis dinamis untuk Java, yang dilakukan dengan sangat cerdik. Mereka sedikit mengubah JVM, dan selama operasi mereka mengumpulkan berbagai statistik tentang penggunaan kontainer, dan tergantung pada profil muatan saat ini, mereka memilih wadah tertentu dan menggantinya secara otomatis selama operasi. Sayangnya, sumber ditutup dan tidak ada kesempatan untuk mendapatkannya (saya mencoba).

Saya juga merekomendasikan melihat berbagai karya (ada banyak) di SETL . Di dalamnya, penulis juga sering mengajukan pertanyaan tentang pemilihan otomatis wadah.

Referensi

1. Implementasi saat ini di github
2. C ++ Rusia 2017: Yuri Efimochev, clang-rapi: perjalanan di dalam C ++ Abstrak Sintaksis Pohon
3. Bunglon: Seleksi Koleksi yang Adaptif
4. Bunyikan panduan analisa statis
5. Obrolan berbahasa Rusia tentang pengembangan kompiler di Telegram. Jika Anda tertarik, masuklah, itu sangat menarik di sana. Berhati-hatilah dengan banjir - mereka akan segera menghukumnya :)

Alih-alih kesimpulan, saya ingin fokus pada kenyataan bahwa itu hanya prototipe sejauh ini dan memiliki terlalu banyak "lubang" dalam implementasi. Dalam artikel ini, saya hanya ingin berbagi dengan Anda gagasan tentang analisis seperti itu dan mempopulerkannya. Yah, mungkin seseorang akan tertarik pada topik ini dan akan ada keinginan untuk terhubung ke proyek - Saya hanya akan senang! Selain itu, Anda selalu dapat mengumpulkan analisa ini di tempat Anda sendiri untuk mencobanya pada contoh pengujian Anda.

Jika Anda memiliki sesuatu untuk melengkapi materi, mengalami tugas yang serupa, atau sekadar memiliki beberapa informasi yang mungkin berguna pada topik ini - jangan ragu untuk membagikan informasi ini di komentar.

Terima kasih atas perhatian anda!