C ++ tips optimasi tingkat rendah [ditutup]

Dengan asumsi Anda sudah memiliki algoritma pilihan terbaik, solusi tingkat rendah apa yang dapat Anda tawarkan untuk memeras beberapa tetes terakhir frame rate manis dari kode C ++?

Tak perlu dikatakan bahwa tips ini hanya berlaku untuk bagian kode kritis yang sudah Anda sorot di profiler Anda, tetapi mereka harusnya merupakan perbaikan non-struktural tingkat rendah. Saya sudah memberi contoh.

Optimalkan tata letak data Anda! (Ini berlaku untuk lebih banyak bahasa daripada hanya C ++)

Anda dapat melakukannya dengan sangat mendalam, membuat ini secara khusus disesuaikan untuk data Anda, prosesor Anda, penanganan multi-core dengan baik, dll. Tetapi konsep dasarnya adalah ini:

Saat Anda memproses hal-hal dalam loop ketat, Anda ingin membuat data untuk setiap iterasi sekecil mungkin, dan sedekat mungkin dalam memori. Itu berarti ideal adalah array atau vektor objek (bukan pointer) yang hanya berisi data yang diperlukan untuk perhitungan.

Dengan cara ini, ketika CPU mengambil data untuk iterasi pertama dari loop Anda, beberapa iterasi selanjutnya dari data akan dimuat ke dalam cache dengannya.

Benar-benar CPU cepat dan kompilernya bagus. Tidak banyak yang dapat Anda lakukan dengan menggunakan instruksi yang lebih sedikit dan lebih cepat. Koherensi cache adalah tempatnya (itu adalah artikel acak I Googled - berisi contoh yang bagus untuk mendapatkan koherensi cache untuk suatu algoritma yang tidak hanya dijalankan melalui data secara linear).

Tip yang sangat, sangat level rendah, tetapi tip yang berguna:

Sebagian besar penyusun mendukung beberapa bentuk petunjuk kondisional eksplisit. GCC memiliki fungsi yang disebut __builtin_expect yang memungkinkan Anda memberi tahu kompilator berapa nilai hasil mungkin. GCC dapat menggunakan data itu untuk mengoptimalkan persyaratan untuk melakukan secepat mungkin dalam kasus yang diharapkan, dengan eksekusi yang sedikit lebih lambat dalam kasus yang tidak terduga.

if(__builtin_expect(entity->extremely_unlikely_flag, 0)) {
  // code that is rarely run
}

Saya telah melihat speedup 10-20% dengan penggunaan yang tepat dari ini.

Hal pertama yang perlu Anda pahami adalah perangkat keras yang Anda jalankan. Bagaimana cara menangani percabangan? Bagaimana dengan caching? Apakah ada set instruksi SIMD? Berapa banyak prosesor yang dapat digunakan? Apakah harus berbagi waktu prosesor dengan yang lain?

Anda dapat memecahkan masalah yang sama dengan cara yang sangat berbeda - bahkan pilihan algoritme Anda harus bergantung pada perangkat keras. Dalam beberapa kasus O (N) dapat berjalan lebih lambat dari O (NlogN) (tergantung pada implementasi).

Sebagai gambaran umum optimasi, hal pertama yang akan saya lakukan adalah melihat masalah apa dan data apa yang Anda coba selesaikan. Kemudian optimalkan untuk itu. Jika Anda menginginkan kinerja ekstrem, lupakan solusi generik - Anda dapat membuat case khusus yang tidak cocok dengan case yang paling sering Anda gunakan.

Lalu profil. Profil, profil, profil. Lihatlah penggunaan memori, lihat hukuman percabangan, Lihatlah overhead panggilan fungsi, lihat pemanfaatan pipa. Cari tahu apa yang memperlambat kode Anda. Ini mungkin akses data (saya menulis sebuah artikel yang disebut "The Latency Elephant" tentang overhead akses data - google. Saya tidak dapat memposting 2 tautan di sini karena saya tidak memiliki "reputasi" yang cukup), jadi periksalah dan kemudian optimalkan tata letak data Anda ( array homogen datar besar yang bagus bagus ) dan akses data (siapkan jika memungkinkan).

Setelah Anda meminimalkan overhead dari subsistem memori, coba dan tentukan apakah instruksi sekarang menjadi hambatan (semoga saja demikian), lalu lihat implementasi SIMD dari algoritma Anda - Implementasi Structure-of-Array (SoA) bisa sangat data dan cache instruksi yang efisien. Jika SIMD tidak cocok untuk masalah Anda maka pengkodean tingkat intrinsik dan assembler mungkin diperlukan.

Jika Anda masih membutuhkan kecepatan lebih maka lakukan paralel. Jika Anda mendapat manfaat menjalankan PS3 maka SPU adalah teman Anda. Gunakan mereka, cintai mereka. Jika Anda sudah menulis solusi SIMD maka Anda akan mendapatkan manfaat besar pindah ke SPU.

Dan kemudian, profil lagi. Uji dalam skenario permainan - apakah kode ini masih menjadi hambatan? Bisakah Anda mengubah cara kode ini digunakan pada tingkat yang lebih tinggi untuk meminimalkan penggunaannya (sebenarnya, ini harus menjadi langkah pertama Anda)? Bisakah Anda menunda penghitungan beberapa bingkai?

Apa pun platform Anda, pelajari sebanyak mungkin tentang perangkat keras dan profiler yang tersedia. Jangan berasumsi bahwa Anda tahu apa hambatannya - temukan itu dengan profiler Anda. Dan pastikan Anda memiliki heuristik untuk menentukan apakah Anda benar-benar membuat game Anda berjalan lebih cepat.

Dan kemudian profil lagi.

Langkah pertama: Pikirkan baik-baik tentang data Anda terkait dengan algoritme Anda. O (log n) tidak selalu lebih cepat dari O (n). Contoh sederhana: Tabel hash dengan hanya beberapa tombol seringkali lebih baik diganti dengan pencarian linier.

Langkah kedua: Lihatlah perakitan yang dihasilkan. C ++ membawa banyak generasi kode implisit ke tabel. Kadang-kadang, itu menyelinap pada Anda tanpa Anda sadari.

Tapi dengan asumsi itu benar-benar waktu pedal-ke-the-metal: Profil. Serius. Menerapkan "trik-trik kinerja" secara acak kemungkinan akan melukai seperti halnya membantu.

Kemudian, semuanya tergantung pada apa yang menjadi hambatan Anda.

cache data ketinggalan => optimalkan tata letak data Anda. Inilah titik awal yang baik: http://gamesfromwithin.com/data-oriented-design

kode cache misses => Lihat panggilan fungsi virtual, kedalaman callstack yang berlebihan, dll. Penyebab umum untuk kinerja yang buruk adalah keyakinan keliru bahwa kelas dasar harus virtual.

Kinerja C ++ umum lainnya tenggelam:

• Alokasi / deokasiasi yang berlebihan. Jika kinerjanya kritis, jangan panggil ke runtime. Pernah.
• Salin konstruksi. Hindari dimanapun Anda bisa. Jika itu bisa menjadi referensi const, buat satu.

Semua hal di atas langsung terlihat jelas ketika Anda melihat majelis, jadi lihat di atas;)

Hapus cabang yang tidak perlu

Pada beberapa platform dan dengan beberapa kompiler, cabang dapat membuang seluruh pipa Anda, jadi bahkan tidak signifikan jika () blok bisa mahal.

Arsitektur PowerPC (PS3 / x360) menawarkan instruksi pilih titik-mengambang fsel,. Ini dapat digunakan di tempat cabang jika blok adalah tugas sederhana:

float result = 0;
if (foo > bar) { result = 2.0f; }
else { result = 1.0f; }

Menjadi:

float result = fsel(foo-bar, 2.0f, 1.0f);

Ketika parameter pertama lebih besar dari atau sama dengan 0, parameter kedua dikembalikan, atau yang ketiga.

Harga kehilangan cabang adalah bahwa jika {} dan yang lain {} blok akan dieksekusi, jadi jika salah satu adalah operasi yang mahal atau dereferensi pointer NULL optimasi ini tidak cocok.

Terkadang kompiler Anda telah melakukan pekerjaan ini, jadi periksa perakitan Anda terlebih dahulu.

Berikut informasi lebih lanjut tentang percabangan dan fsel:

http://assemblyrequired.crashworks.org/tag/intrinsics/

Hindari akses memori dan terutama yang acak di semua biaya.

Itulah satu-satunya hal terpenting untuk dioptimalkan pada CPU modern. Anda dapat melakukan shitload aritmatika dan bahkan banyak cabang prediksi yang salah pada saat Anda menunggu data dari RAM.

Anda juga dapat membaca aturan ini sebaliknya: Lakukan sebanyak mungkin perhitungan di antara akses memori.

Gunakan Compiler Intrinsics.

Pastikan bahwa kompiler menghasilkan rakitan paling efisien untuk operasi tertentu dengan menggunakan intrinsik - konstruksi yang terlihat seperti panggilan fungsi yang kompiler berubah menjadi rakitan yang dioptimalkan:

Ini referensi untuk Visual Studio , dan ini satu untuk GCC

Hapus panggilan fungsi virtual yang tidak perlu

Pengiriman fungsi virtual bisa sangat lambat. Artikel ini memberikan penjelasan yang bagus tentang alasannya. Jika memungkinkan, untuk fungsi yang dipanggil berkali-kali per frame, hindari.

Anda dapat melakukan ini dalam beberapa cara. Kadang-kadang Anda hanya dapat menulis ulang kelas untuk tidak membutuhkan warisan - mungkin ternyata MachineGun adalah satu-satunya subkelas Senjata, dan Anda dapat menggabungkannya.

Anda dapat menggunakan templat untuk menggantikan polimorfisme run-time dengan polimorfisme kompilasi. Ini hanya berfungsi jika Anda mengetahui subtipe objek Anda saat runtime, dan dapat menjadi penulisan ulang utama.

Prinsip dasar saya adalah: jangan melakukan apa pun yang tidak perlu .

Jika Anda telah menemukan bahwa fungsi tertentu adalah hambatan, Anda dapat mengoptimalkan fungsi - atau Anda bisa mencoba agar tidak dipanggil terlebih dahulu.

Ini tidak berarti Anda menggunakan algoritma yang buruk. Ini mungkin berarti bahwa Anda menjalankan perhitungan setiap frame yang bisa di-cache untuk sementara waktu (atau seluruhnya dihitung sebelumnya), misalnya.

Saya selalu mencoba pendekatan ini sebelum ada upaya optimasi tingkat rendah.

Gunakan SIMD (oleh SSE), jika Anda belum melakukannya. Gamasutra memiliki artikel yang bagus tentang ini . Anda dapat mengunduh kode sumber dari pustaka yang disajikan di akhir artikel.

Minimalkan rantai ketergantungan untuk memanfaatkan pipa CPU dengan lebih baik.

Dalam kasus sederhana kompiler dapat melakukan ini untuk Anda jika Anda mengaktifkan loop membuka gulungan. Namun sering tidak akan melakukannya, terutama ketika ada float yang terlibat saat menata ulang ekspresi mengubah hasilnya.

Contoh:

float *data = ...;
int length = ...;

// Slow version
float total = 0.0f;
int i;
for (i=0; i < length; i++)
{
  total += data[i]
}

// Fast version
float total1, total2, total3, total4;
for (i=0; i < length-3; i += 4)
{
  total1 += data[i];
  total2 += data[i+1];
  total3 += data[i+2];
  total4 += data[i+3];
}
for (; i < length; i++)
{
  total += data[i]
}
total += (total1 + total2) + (total3 + total4);

Jangan mengabaikan kompiler Anda - jika Anda menggunakan gcc pada Intel, Anda bisa dengan mudah mendapatkan keuntungan kinerja dengan beralih ke Kompiler Intel C / C ++, misalnya. Jika Anda menargetkan platform ARM, lihat kompiler komersial ARM. Jika Anda menggunakan iPhone, Apple hanya mengizinkan Dentang digunakan dimulai dengan iOS 4.0 SDK.

Salah satu masalah yang Anda mungkin akan datang dengan optimasi, terutama pada x86, adalah bahwa banyak hal intuitif akhirnya bekerja melawan Anda pada implementasi CPU modern. Sayangnya bagi kebanyakan dari kita, kemampuan untuk mengoptimalkan kompiler sudah lama hilang. Kompiler dapat menjadwalkan instruksi dalam aliran berdasarkan pada pengetahuan internal CPU itu sendiri. Selain itu, CPU juga dapat menjadwalkan ulang instruksi berdasarkan kebutuhannya sendiri. Bahkan jika Anda memikirkan cara optimal untuk mengatur suatu metode, kemungkinan kompiler atau CPU telah datang dengan itu sendiri dan telah melakukan optimasi itu.

Saran terbaik saya adalah mengabaikan optimasi level rendah dan fokus pada level yang lebih tinggi. Kompiler dan CPU tidak dapat mengubah algoritma Anda dari algoritma O (n ^ 2) menjadi algoritma O (1), tidak peduli seberapa bagus mereka. Itu akan mengharuskan Anda untuk melihat dengan tepat apa yang Anda coba lakukan dan menemukan cara yang lebih baik untuk melakukannya. Biarkan kompiler dan CPU khawatir tentang level rendah dan Anda fokus pada level menengah ke atas.

The membatasi kata kunci berpotensi berguna, terutama dalam kasus di mana Anda perlu memanipulasi objek dengan pointer. Hal ini memungkinkan kompiler untuk menganggap objek menunjuk-ke ​​tidak akan bisa dimodifikasi dengan cara lain yang pada gilirannya memungkinkannya untuk melakukan optimasi yang lebih agresif seperti menjaga bagian-bagian dari objek dalam register atau menyusun ulang membaca dan menulis lebih efektif.

Satu hal yang baik tentang kata kunci adalah itu adalah petunjuk yang dapat Anda terapkan sekali dan melihat manfaat dari tanpa mengatur ulang algoritma Anda. Sisi buruknya adalah jika Anda menggunakannya di tempat yang salah, Anda mungkin melihat data rusak. Tetapi biasanya cukup mudah untuk menemukan di mana itu sah untuk menggunakannya - itu adalah salah satu dari sedikit contoh di mana programmer dapat diharapkan untuk mengetahui lebih banyak daripada yang dapat diasumsikan oleh kompiler, itulah sebabnya kata kunci telah diperkenalkan.

Secara teknis 'batasan' tidak ada dalam standar C ++, tetapi setara platform khusus tersedia untuk sebagian besar kompiler C ++, jadi perlu dipertimbangkan.

Lihat juga: http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

Semuanya!

Semakin banyak informasi yang Anda berikan kepada kompiler tentang data, semakin baik optimasinya (setidaknya menurut pengalaman saya).

void foo(Bar * x) {...;}

menjadi;

void foo(const Bar * const x) {...;}

Kompiler sekarang tahu bahwa pointer x tidak akan berubah dan bahwa data yang ditunjuknya juga tidak akan berubah.

Manfaat tambahan lainnya adalah Anda dapat mengurangi jumlah bug yang tidak disengaja, menghentikan diri sendiri (atau orang lain) memodifikasi hal-hal yang seharusnya tidak mereka lakukan.

Paling sering, cara terbaik untuk mendapatkan kinerja adalah dengan mengubah algoritma Anda. Semakin tidak umum implementasinya, semakin dekat Anda dengan logam.

Dengan asumsi bahwa telah dilakukan ....

Jika benar-benar kode kritis, cobalah untuk menghindari pembacaan memori, cobalah untuk menghindari menghitung hal-hal yang dapat dihitung sebelumnya (meskipun tidak ada tabel pencarian karena mereka melanggar aturan nomor 1). Ketahuilah apa yang dilakukan oleh algoritma Anda dan tulislah dengan cara yang juga diketahui oleh kompiler. Periksa unit untuk memastikannya.

Hindari kesalahan cache. Proses batch sebanyak yang Anda bisa. Hindari fungsi virtual dan tipuan lainnya.

Pada akhirnya, ukur semuanya. Aturan berubah sepanjang waktu. Apa yang digunakan untuk mempercepat kode 3 tahun yang lalu sekarang memperlambatnya. Contoh yang bagus adalah 'gunakan fungsi matematika ganda alih-alih versi float'. Saya tidak akan menyadarinya jika saya tidak membacanya.

Saya lupa - tidak memiliki konstruktor default menginternalisasi variabel Anda, atau jika Anda bersikeras, setidaknya juga buat konstruktor yang tidak. Waspadai hal-hal yang tidak muncul di profil. Ketika Anda kehilangan satu siklus yang tidak perlu per baris kode, tidak ada yang akan muncul di profiler Anda, tetapi Anda akan kehilangan banyak siklus secara keseluruhan. Sekali lagi, ketahuilah apa yang dilakukan kode Anda. Jadikan fungsi inti Anda lebih ramping, bukan sangat mudah. Versi foolproof dapat dipanggil jika diperlukan, tetapi tidak selalu diperlukan. Fleksibilitas datang dengan harga - kinerja menjadi satu.

Diedit untuk menjelaskan mengapa tidak ada inisialisasi default: Banyak kode mengatakan: Vector3 bla; bla = DoSomething ();

Intialisasi dalam konstruktor adalah waktu yang terbuang. Juga, dalam hal ini waktu yang terbuang adalah kecil (mungkin membersihkan vektor), namun jika programmer Anda melakukan ini biasanya bertambah. Juga, banyak fungsi membuat sementara (pikirkan operator kelebihan beban), yang akan diinisialisasi ke nol dan ditugaskan setelah langsung. Tersembunyi siklus yang hilang yang terlalu kecil untuk melihat lonjakan profiler Anda, tetapi siklus berdarah seluruh basis kode Anda. Juga, beberapa orang melakukan lebih banyak hal dalam konstruktor (yang jelas tidak boleh). Saya telah melihat keuntungan multi-milidetik dari variabel yang tidak digunakan di mana konstruktor kebetulan berada di sisi yang berat. Segera setelah konstruktor menyebabkan efek samping, kompiler tidak akan dapat memperbaikinya, jadi kecuali Anda tidak pernah menggunakan kode di atas, saya lebih suka konstruktor yang tidak menginisialisasi, atau, seperti yang saya katakan,

Vector3 bla (noInit); bla = doSomething ();

Kurangi evaluasi ekspresi boolean

Yang ini benar-benar putus asa, karena itu perubahan yang sangat halus tapi berbahaya pada kode Anda. Namun jika Anda memiliki persyaratan yang dievaluasi beberapa kali, Anda dapat mengurangi overhead evaluasi boolean dengan menggunakan operator bitwise sebagai gantinya. Begitu:

if ((foo && bar) || blah) { ... } 

Menjadi:

if ((foo & bar) | blah) { ... }

Sebagai gantinya, gunakan bilangan bulat aritmatika. Jika foo dan bar Anda adalah konstanta atau dievaluasi sebelum if (), ini bisa lebih cepat daripada versi boolean normal.

Sebagai bonus, versi aritmatika memiliki cabang lebih sedikit daripada versi boolean biasa. Yang merupakan cara lain untuk mengoptimalkan .

Kelemahan besar adalah Anda kehilangan evaluasi malas - seluruh blok dievaluasi, jadi Anda tidak bisa melakukannya foo != NULL & foo->dereference(). Karena ini, dapat diperdebatkan bahwa ini sulit untuk dipertahankan, sehingga pertukaran mungkin terlalu besar.

Mengawasi penggunaan tumpukan Anda

Segala sesuatu yang Anda tambahkan ke tumpukan adalah dorongan dan konstruksi tambahan saat suatu fungsi dipanggil. Ketika sejumlah besar ruang stack diperlukan, terkadang dapat bermanfaat untuk mengalokasikan memori yang bekerja sebelumnya, dan jika platform yang Anda kerjakan memiliki RAM cepat yang tersedia untuk digunakan - semuanya lebih baik!