Secara umum, apakah layak menggunakan fungsi virtual untuk menghindari percabangan?

Tampaknya ada setara kasar instruksi untuk menyamakan dengan biaya kehilangan fungsi virtual cabang memiliki tradeoff yang sama:

• instruksi vs. kehilangan cache data
• hambatan optimasi

Jika Anda melihat sesuatu seperti:

if (x==1) {
   p->do1();
}
else if (x==2) {
   p->do2();
}
else if (x==3) {
   p->do3();
}
...

Anda bisa memiliki larik fungsi anggota, atau jika banyak fungsi bergantung pada kategorisasi yang sama, atau kategorisasi yang lebih kompleks ada, gunakan fungsi virtual:

p->do()

Tapi, secara umum, seberapa mahal fungsi virtual vs percabangan Sulit untuk menguji pada platform yang cukup untuk digeneralisasi, jadi saya bertanya-tanya apakah ada yang punya aturan praktis (bagus jika sesederhana 4 ifdetik adalah breakpoint)

Secara umum fungsi virtual lebih jelas dan saya akan condong ke arah mereka. Tetapi, saya memiliki beberapa bagian yang sangat kritis di mana saya dapat mengubah kode dari fungsi virtual ke cabang. Saya lebih suka memikirkan hal ini sebelum melakukan ini. (ini bukan perubahan sepele, atau mudah diuji di berbagai platform)

Saya ingin masuk ke sini di antara jawaban-jawaban yang sudah sangat bagus ini dan mengakui bahwa saya telah mengambil pendekatan yang jelek untuk benar-benar bekerja mundur ke anti-pola mengubah kode polimorfik menjadi switchesatau if/elsecabang dengan keuntungan yang terukur. Tapi saya tidak melakukan grosir ini, hanya untuk jalur paling kritis. Tidak harus hitam dan putih.

_{Sebagai penafian, saya bekerja di bidang-bidang seperti raytracing di mana kebenaran tidak begitu sulit untuk dicapai (dan seringkali fuzzy dan didekati pula) sementara kecepatan sering menjadi salah satu kualitas paling kompetitif yang dicari. Pengurangan waktu render seringkali merupakan salah satu permintaan pengguna yang paling umum, dengan kami terus-menerus menggaruk-garuk kepala kami dan mencari cara untuk mencapainya untuk jalur terukur yang paling kritis.}

Refactoring Polimorfik Kondisional

Pertama, perlu dipahami mengapa polimorfisme lebih disukai dari aspek rawatan daripada percabangan bersyarat ( switchatau banyak if/elsepernyataan). Manfaat utama di sini adalah ekstensibilitas .

Dengan kode polimorfik, kami dapat memperkenalkan subtipe baru ke basis kode kami, menambahkan contohnya ke beberapa struktur data polimorfik, dan memiliki semua kode polimorfik yang ada yang masih bekerja secara otomatis tanpa modifikasi lebih lanjut. Jika Anda memiliki banyak kode yang tersebar di seluruh basis kode besar yang menyerupai bentuk, "Jika jenis ini adalah 'foo', lakukan itu" , Anda mungkin menemukan diri Anda dengan beban yang mengerikan untuk memperbarui 50 bagian kode yang berbeda untuk memperkenalkan jenis hal baru, dan akhirnya hilang beberapa.

Manfaat rawatan polimorfisme secara alami berkurang di sini jika Anda hanya memiliki pasangan atau bahkan satu bagian dari basis kode Anda yang perlu melakukan pemeriksaan jenis tersebut.

Penghalang Pengoptimalan

Saya sarankan untuk tidak melihat ini dari sudut pandang percabangan dan pipelining begitu banyak, dan melihatnya lebih dari pola pikir desain kompiler dari hambatan optimasi. Ada beberapa cara untuk meningkatkan prediksi cabang yang berlaku untuk kedua kasus, seperti mengurutkan data berdasarkan sub-tipe (jika cocok dengan urutan).

Apa yang lebih berbeda antara kedua strategi ini adalah jumlah informasi yang dimiliki pengoptimal sebelumnya. Panggilan fungsi yang diketahui menyediakan lebih banyak informasi, panggilan fungsi tidak langsung yang memanggil fungsi yang tidak dikenal pada waktu kompilasi mengarah ke penghalang optimasi.

Ketika fungsi yang dipanggil diketahui, kompiler dapat melenyapkan struktur dan memadatkannya menjadi berkeping-keping, menyatukan panggilan, menghilangkan potensi overhead aliasing, melakukan pekerjaan yang lebih baik dengan alokasi instruksi / register, bahkan mungkin menata ulang loop dan bentuk cabang lainnya, menghasilkan hard LUT miniatur yang disandikan bila diperlukan (sesuatu yang GCC 5.3 baru-baru ini mengejutkan saya dengan switchpernyataan dengan menggunakan LUT kode-data untuk hasil daripada tabel lompatan).

Beberapa manfaat tersebut hilang ketika kami mulai memperkenalkan waktu kompilasi yang tidak diketahui ke dalam campuran, seperti halnya pemanggilan fungsi tidak langsung, dan di situlah percabangan bersyarat kemungkinan besar menawarkan keunggulan.

Optimalisasi Memori

Ambil contoh gim video yang terdiri dari pemrosesan urutan makhluk berulang kali dalam satu lingkaran yang ketat. Dalam kasus seperti itu, kita mungkin memiliki beberapa wadah polimorfik seperti ini:

vector<Creature*> creatures;

_{Catatan: untuk kesederhanaan saya hindari di unique_ptrsini.}

... di mana Creatureadalah tipe dasar polimorfik. Dalam hal ini, salah satu kesulitan dengan wadah polimorfik adalah bahwa mereka sering ingin mengalokasikan memori untuk setiap subtipe secara terpisah / individual (mis: menggunakan lemparan default operator newuntuk setiap makhluk individu).

Itu akan sering membuat prioritas pertama untuk optimasi (jika kita membutuhkannya) berbasis memori daripada percabangan. Salah satu strategi di sini adalah menggunakan pengalokasi tetap untuk setiap sub-jenis, mendorong representasi yang berdekatan dengan mengalokasikan dalam potongan besar dan menyatukan memori untuk setiap sub-jenis yang dialokasikan. Dengan strategi seperti itu, pasti dapat membantu untuk menyortir creatureswadah ini menurut sub-jenis (dan juga alamat), karena hal itu tidak hanya mungkin meningkatkan prediksi cabang tetapi juga meningkatkan lokalitas referensi (memungkinkan beberapa makhluk dengan subtipe yang sama untuk diakses dari satu baris cache sebelum penggusuran).

Devirtualisasi Parsial Struktur Data dan Loop

Katakanlah Anda melakukan semua gerakan ini dan Anda masih menginginkan kecepatan yang lebih. Perlu dicatat bahwa setiap langkah yang kami lakukan di sini menurunkan tingkat perawatan, dan kami akan berada pada tahap penggilingan logam dengan pengembalian kinerja yang semakin berkurang. Jadi perlu ada permintaan kinerja yang cukup signifikan jika kita melangkah ke wilayah ini, di mana kami bersedia mengorbankan pemeliharaan lebih jauh untuk keuntungan kinerja yang lebih kecil dan lebih kecil.

Namun langkah selanjutnya untuk mencoba (dan selalu dengan kemauan untuk mendukung perubahan kita jika tidak membantu sama sekali) mungkin adalah devirtualization manual.

_{Kiat kendali versi: kecuali Anda jauh lebih mengerti optimasi daripada saya, ada baiknya membuat cabang baru pada saat ini dengan kemauan untuk membuangnya jika upaya optimasi kami kehilangan yang mungkin terjadi. Bagi saya itu semua coba-coba setelah titik-titik semacam ini bahkan dengan profiler di tangan.}

Namun demikian, kita tidak harus menerapkan pola pikir ini secara grosir. Melanjutkan contoh kita, katakanlah video game ini sebagian besar terdiri dari makhluk manusia, sejauh ini. Dalam kasus seperti itu, kita hanya dapat mendevirtualisasi makhluk manusia dengan mengangkatnya dan membuat struktur data terpisah hanya untuk mereka.

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures

Ini menyiratkan bahwa semua area dalam basis kode kami yang perlu memproses makhluk membutuhkan loop kasus khusus untuk makhluk manusia. Namun itu menghilangkan overhead pengiriman dinamis (atau mungkin, lebih tepat, penghalang optimasi) bagi manusia yang, sejauh ini, adalah jenis makhluk yang paling umum. Jika area ini besar jumlahnya dan kami mampu membelinya, kami mungkin melakukan ini:

vector<Human> humans;               // common case
vector<Creature*> other_creatures;  // additional rare-case creatures
vector<Creature*> creatures;        // contains humans and other creatures

... jika kita mampu melakukan ini, jalur yang kurang kritis dapat tetap seperti itu dan hanya memproses semua jenis makhluk secara abstrak. Jalur kritis dapat memproses humansdalam satu loop dan other_creaturesdalam loop kedua.

Kami dapat memperluas strategi ini sesuai kebutuhan dan berpotensi memeras beberapa keuntungan dengan cara ini, namun perlu dicatat seberapa banyak kami merendahkan kemampuan pemeliharaan dalam proses tersebut. Menggunakan templat fungsi di sini dapat membantu menghasilkan kode untuk manusia dan makhluk tanpa menduplikasi logikanya secara manual.

Devirtualization Sebagian Kelas

Sesuatu yang saya lakukan bertahun-tahun lalu yang benar-benar menjijikkan, dan saya bahkan tidak yakin itu bermanfaat lagi (ini di era C ++ 03), adalah devirtualisasi parsial suatu kelas. Dalam hal ini, kami sudah menyimpan ID kelas dengan setiap instance untuk tujuan lain (diakses melalui accessor di kelas dasar yang non-virtual). Di sana kami melakukan sesuatu yang analog dengan ini (ingatanku agak kabur):

switch (obj->type())
{
   case id_common_type:
       static_cast<CommonType*>(obj)->non_virtual_do_something();
       break;
   ...
   default:
       obj->virtual_do_something();
       break;
}

... di mana virtual_do_somethingditerapkan untuk memanggil versi non-virtual dalam subkelas. Ini kotor, saya tahu, melakukan downcast statis eksplisit untuk mendevirtualize panggilan fungsi. Saya tidak tahu betapa bermanfaatnya ini sekarang karena saya belum pernah mencoba hal semacam ini selama bertahun-tahun. Dengan paparan desain berorientasi data, saya menemukan strategi di atas memecah struktur data dan loop dalam mode panas / dingin menjadi jauh lebih berguna, membuka lebih banyak pintu untuk strategi optimasi (dan jauh lebih jelek).

Devirtualisasi Grosir

Saya harus mengakui bahwa saya tidak pernah sejauh ini menerapkan pola pikir optimasi, jadi saya tidak tahu manfaatnya. Saya telah menghindari fungsi tidak langsung dalam tinjauan ke masa depan dalam kasus-kasus di mana saya tahu hanya akan ada satu set kondisional sentral (mis: pemrosesan acara dengan hanya satu acara pemrosesan tempat sentral), tetapi tidak pernah memulai dengan pola pikir polimorfik dan dioptimalkan sepanjang jalan. sampai sini.

Secara teoritis, manfaat langsung di sini mungkin merupakan cara yang berpotensi lebih kecil untuk mengidentifikasi jenis daripada penunjuk virtual (mis: satu byte jika Anda dapat berkomitmen pada gagasan bahwa ada 256 jenis unik atau kurang) selain benar-benar menghilangkan hambatan pengoptimalan ini. .

Dalam beberapa kasus mungkin juga membantu untuk menulis kode yang lebih mudah dirawat (dibandingkan contoh devirtualisasi manual yang dioptimalkan di atas) jika Anda hanya menggunakan satu switchpernyataan pusat tanpa harus membagi struktur data dan loop berdasarkan subtipe, atau jika ada pesanan -dependensi dalam kasus ini di mana hal-hal harus diproses dalam urutan yang tepat (bahkan jika itu menyebabkan kami bercabang di semua tempat). Ini akan menjadi kasus di mana Anda tidak memiliki terlalu banyak tempat yang perlu dilakukan switch.

Saya umumnya tidak akan merekomendasikan ini bahkan dengan pola pikir yang sangat kritis terhadap kinerja kecuali ini cukup mudah untuk dipertahankan. "Mudah dirawat" cenderung bergantung pada dua faktor dominan:

• Tidak memiliki kebutuhan ekstensibilitas yang nyata (mis: mengetahui dengan pasti bahwa Anda memiliki 8 jenis hal yang harus diproses, dan tidak pernah lagi).
• Tidak memiliki banyak tempat dalam kode Anda yang perlu memeriksa jenis ini (mis: satu tempat sentral).

... namun saya merekomendasikan skenario di atas dalam banyak kasus dan beralih ke solusi yang lebih efisien dengan devirtualization parsial sesuai kebutuhan. Ini memberi Anda lebih banyak ruang bernapas untuk menyeimbangkan kebutuhan perpanjangan dan pemeliharaan dengan kinerja.

Fungsi Virtual vs. Function Pointer

Untuk melengkapi ini, saya perhatikan di sini bahwa ada beberapa diskusi tentang fungsi virtual vs fungsi pointer. Memang benar bahwa fungsi virtual memerlukan sedikit kerja ekstra untuk memanggil, tetapi itu tidak berarti mereka lebih lambat. Kontra-intuitif, bahkan mungkin membuat mereka lebih cepat.

Ini kontra-intuitif di sini karena kita terbiasa mengukur biaya dalam hal instruksi tanpa memperhatikan dinamika hierarki memori yang cenderung memiliki dampak yang jauh lebih signifikan.

Jika kita membandingkan a classdengan 20 fungsi virtual vs. structyang menyimpan 20 fungsi pointer, dan keduanya instantiated beberapa kali, overhead memori dari setiap classinstance dalam hal ini 8 byte untuk pointer virtual pada mesin 64-bit, sedangkan memori overhead structadalah 160 byte.

Biaya praktis bisa ada jauh lebih banyak cache wajib dan non-wajib dengan tabel pointer fungsi vs kelas menggunakan fungsi virtual (dan mungkin kesalahan halaman pada skala input yang cukup besar). Biaya itu cenderung membuat pekerjaan pengindeksan tabel virtual sedikit lebih kecil.

Saya juga telah berurusan dengan basis kode C warisan (lebih tua dari saya) di mana mengubah structsdiisi dengan pointer fungsi, dan dipakai berkali-kali, benar-benar memberikan keuntungan kinerja yang signifikan (lebih dari 100% peningkatan) dengan mengubahnya menjadi kelas dengan fungsi virtual, dan hanya karena pengurangan besar dalam penggunaan memori, peningkatan cache-keramahan, dll.

Di sisi lain, ketika perbandingan menjadi lebih tentang apel ke apel, saya juga telah menemukan pola pikir yang berlawanan dari menerjemahkan dari pola pikir fungsi virtual C ++ ke pola fungsi pointer gaya C untuk menjadi berguna dalam jenis skenario ini:

class Functionoid
{
public:
    virtual ~Functionoid() {}
    virtual void operator()() = 0;
};

... di mana kelas menyimpan fungsi tunggal yang sangat dapat dikesampingkan (atau dua jika kita menghitung destruktor virtual). Dalam kasus-kasus itu, pasti dapat membantu dalam jalur kritis untuk mengubahnya menjadi ini:

void (*func_ptr)(void* instance_data);

... idealnya di belakang antarmuka tipe-aman untuk menyembunyikan gips berbahaya ke / dari void*.

Dalam kasus-kasus di mana kita tergoda untuk menggunakan kelas dengan fungsi virtual tunggal, dapat dengan cepat membantu menggunakan pointer fungsi sebagai gantinya. Alasan besar bahkan belum tentu mengurangi biaya dalam memanggil fungsi pointer. Itu karena kita tidak lagi menghadapi godaan untuk mengalokasikan masing-masing functionoid terpisah pada daerah tumpukan yang tersebar jika kita menggabungkannya ke dalam struktur yang persisten. Pendekatan semacam ini dapat membuatnya lebih mudah untuk menghindari heap-related dan fragmentasi memori overhead jika data instance homogen, misalnya, dan hanya perilaku yang bervariasi.

Jadi pasti ada beberapa kasus di mana menggunakan pointer fungsi dapat membantu, tetapi sering saya menemukannya sebaliknya jika kita membandingkan sekelompok tabel pointer fungsi ke satu vtable yang hanya memerlukan satu pointer disimpan per instance kelas. . Vtable itu akan sering duduk di satu atau lebih baris cache L1 juga dalam loop ketat.

Kesimpulan

Jadi, itu adalah putaran kecil saya tentang topik ini. Saya sarankan bertualang di area ini dengan hati-hati. Pengukuran kepercayaan, bukan insting, dan mengingat cara optimasi ini sering menurunkan rawatan, hanya sejauh yang Anda mampu (dan rute yang bijaksana adalah untuk berbuat salah di sisi rawatan).

Pengamatan:

• Dengan banyak kasus, fungsi virtual lebih cepat karena pencarian vtable adalah O(1)operasi sedangkan else if()tangga adalah O(n)operasi. Namun, ini hanya berlaku jika distribusi kasusnya rata.

• Untuk satu if() ... else, kondisional lebih cepat karena Anda menyimpan overhead panggilan fungsi.

• Jadi, ketika Anda memiliki distribusi kasus yang rata, titik impas harus ada. Satu-satunya pertanyaan adalah di mana letaknya.

• Jika Anda menggunakan switch()alih - alih else if()fungsi panggilan tangga atau virtual, kompiler Anda dapat menghasilkan kode yang lebih baik: ia dapat melakukan cabang ke lokasi yang terlihat dari tabel, tetapi yang bukan panggilan fungsi. Artinya, Anda memiliki semua properti panggilan fungsi virtual tanpa semua panggilan fungsi overhead.

• Jika seseorang jauh lebih sering daripada yang lain, memulai if() ... elsedengan kasing akan memberi Anda kinerja terbaik: Anda akan menjalankan cabang kondisional tunggal yang diprediksi dengan benar di sebagian besar kasing.

• Kompiler Anda tidak memiliki pengetahuan tentang distribusi kasus yang diharapkan dan akan menganggap distribusi yang rata.

Sejak compiler Anda mungkin memiliki beberapa heuristik yang baik di tempat kapan untuk kode switch()sebagai else if()tangga atau sebagai lookup table. Saya akan cenderung memercayai penilaiannya kecuali Anda tahu bahwa distribusi kasusnya bias.

Jadi, saran saya adalah ini:

• Jika salah satu kasing mengecilkan sisanya dalam hal frekuensi, gunakan else if()tangga yang diurutkan .

• Kalau tidak gunakan switch()pernyataan, kecuali salah satu metode lain membuat kode Anda jauh lebih mudah dibaca. Pastikan Anda tidak membeli perolehan kinerja yang dapat diabaikan dengan tingkat keterbacaan yang berkurang secara signifikan.

• Jika Anda menggunakan switch()dan masih belum puas dengan kinerja, lakukan perbandingan, tetapi bersiaplah untuk mengetahui bahwa switch()itu sudah kemungkinan tercepat.

Secara umum, apakah layak menggunakan fungsi virtual untuk menghindari percabangan?

Secara umum, ya. Manfaat untuk pemeliharaan sangat signifikan (pengujian pemisahan, pemisahan kekhawatiran, peningkatan modularitas dan ekstensibilitas).

Tetapi, secara umum, seberapa mahal fungsi virtual vs percabangan Sulit untuk menguji pada platform yang cukup untuk digeneralisasi, jadi saya bertanya-tanya apakah ada orang yang memiliki aturan praktis (bagus jika sesederhana 4 jika ada breakpoint)

Kecuali Anda telah membuat profil kode Anda dan mengetahui pengiriman antar cabang ( evaluasi kondisi ) membutuhkan waktu lebih lama daripada perhitungan yang dilakukan ( kode di cabang ), optimalkan perhitungan yang dilakukan.

Yaitu, jawaban yang benar untuk "seberapa mahal fungsi virtual vs percabangan" adalah mengukur dan mencari tahu.

Aturan praktis : kecuali memiliki situasi di atas (diskriminasi cabang lebih mahal daripada perhitungan cabang), optimalkan bagian kode ini untuk upaya pemeliharaan (gunakan fungsi virtual).

Anda mengatakan bahwa Anda ingin bagian ini berjalan secepat mungkin; Seberapa cepat itu? Apa kebutuhan konkret Anda?

Secara umum fungsi virtual lebih jelas dan saya akan condong ke arah mereka. Tetapi, saya memiliki beberapa bagian yang sangat kritis di mana saya dapat mengubah kode dari fungsi virtual ke cabang. Saya lebih suka memikirkan hal ini sebelum melakukan ini. (ini bukan perubahan sepele, atau mudah diuji di berbagai platform)

Gunakan fungsi virtual. Ini bahkan akan memungkinkan Anda untuk mengoptimalkan per platform jika perlu, dan tetap menjaga kode klien tetap bersih.

Jawaban lain sudah memberikan argumen teoretis yang bagus. Saya ingin menambahkan hasil percobaan yang telah saya lakukan baru-baru ini untuk memperkirakan apakah itu akan menjadi ide yang baik untuk mengimplementasikan mesin virtual (VM) menggunakan besar di switchatas kode-op atau lebih tepatnya menafsirkan kode-op sebagai indeks menjadi array pointer fungsi. Meskipun ini tidak persis sama dengan virtualpemanggilan fungsi, saya pikir itu cukup dekat.

Saya telah menulis skrip Python untuk secara acak menghasilkan kode C ++ 14 untuk VM dengan ukuran set instruksi yang dipilih secara acak (meskipun tidak seragam, pengambilan sampel rentang rendah lebih padat) antara 1 dan 10000. VM yang dihasilkan selalu memiliki 128 register dan tidak ada RAM Instruksi tidak bermakna dan semua memiliki formulir berikut.

inline void
op0004(machine_state& state) noexcept
{
  const auto c = word_t {0xcf2802e8d0baca1dUL};
  const auto r1 = state.registers[58];
  const auto r2 = state.registers[69];
  const auto r3 = ((r1 + c) | r2);
  state.registers[6] = r3;
}

Script juga menghasilkan rutin pengiriman menggunakan switchpernyataan ...

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  switch (opcode)
  {
  case 0x0000: op0000(state); return 0;
  case 0x0001: op0001(state); return 0;
  // ...
  case 0x247a: op247a(state); return 0;
  case 0x247b: op247b(state); return 0;
  default:
    return -1;  // invalid opcode
  }
}

... dan berbagai fungsi pointer.

inline int
dispatch(machine_state& state, const opcode_t opcode) noexcept
{
  typedef void (* func_type)(machine_state&);
  static const func_type table[VM_NUM_INSTRUCTIONS] = {
    op0000,
    op0001,
    // ...
    op247a,
    op247b,
  };
  if (opcode >= VM_NUM_INSTRUCTIONS)
    return -1;  // invalid opcode
  table[opcode](state);
  return 0;
}

Rutin pengiriman mana yang dipilih dipilih secara acak untuk setiap VM yang dihasilkan.

Untuk pembandingan, aliran op-kode dihasilkan oleh mesin acak acak ( std::random_device) Mersenne twister ( std::mt19937_64).

Kode untuk setiap VM dikompilasi dengan GCC 5.2.0 menggunakan -DNDEBUG, -O3dan -std=c++14switch. Pertama, itu dikompilasi menggunakan -fprofile-generateopsi dan data profil yang dikumpulkan untuk mensimulasikan 1000 instruksi acak. Kode kemudian dikompilasi ulang dengan -fprofile-useopsi yang memungkinkan optimasi berdasarkan data profil yang dikumpulkan.

VM kemudian dilaksanakan (dalam proses yang sama) empat kali selama 50.000 siklus dan waktu untuk setiap putaran diukur. Jalankan pertama dibuang untuk menghilangkan efek cache dingin. PRNG tidak diunggulkan kembali di antara run sehingga mereka tidak melakukan urutan instruksi yang sama.

Dengan menggunakan pengaturan ini, 1000 titik data untuk setiap rutin pengiriman dikumpulkan. Data dikumpulkan pada quad core AMD A8-6600K APU dengan 2048 KiB cache menjalankan 64 bit GNU / Linux tanpa desktop grafis atau program lain berjalan. Di bawah ini adalah plot waktu CPU rata-rata (dengan standar deviasi) per instruksi untuk setiap VM.

Dari data ini, saya bisa mendapatkan kepercayaan bahwa menggunakan tabel fungsi adalah ide yang bagus kecuali mungkin untuk sejumlah kecil op-kode. Saya tidak memiliki penjelasan untuk pencilan switchversi antara 500 dan 1000 instruksi.

Semua kode sumber untuk tolok ukur serta data eksperimental lengkap dan plot resolusi tinggi dapat ditemukan di situs web saya .

Selain jawaban cmaster yang bagus, yang saya undur, ingatlah bahwa pointer fungsi secara umum lebih cepat daripada fungsi virtual. Pengiriman fungsi virtual umumnya melibatkan pertama mengikuti pointer dari objek ke vtable, pengindeksan tepat, dan kemudian dereferencing pointer fungsi. Jadi langkah terakhirnya sama, tetapi awalnya ada langkah ekstra. Selain itu, fungsi virtual selalu menganggap "ini" sebagai argumen, pointer fungsi lebih fleksibel.

Hal lain yang perlu diingat: jika jalur kritis Anda melibatkan loop, akan sangat membantu untuk mengurutkan loop berdasarkan tujuan pengiriman. Jelas ini nlogn, sedangkan melintasi loop hanya n, tetapi jika Anda akan melintasi berkali-kali ini bisa sia-sia. Dengan mengurutkan berdasarkan tujuan pengiriman, Anda memastikan bahwa kode yang sama dijalankan berulang kali, menjaganya tetap panas di icache, meminimalkan kesalahan cache.

Strategi ketiga yang perlu diingat: jika Anda memutuskan untuk beralih dari fungsi virtual / fungsi pointer ke strategi if / switch, Anda mungkin juga dilayani dengan baik dengan beralih dari objek polimorfik ke sesuatu seperti boost :: varian (yang juga menyediakan switch kasus dalam bentuk abstraksi pengunjung). Objek polimorfik harus disimpan oleh basis pointer, sehingga data Anda ada di semua tempat dalam cache. Ini bisa dengan mudah menjadi pengaruh yang lebih besar pada jalur kritis Anda daripada biaya pencarian virtual. Sedangkan varian disimpan sebaris sebagai kesatuan yang didiskriminasi; ini memiliki ukuran yang sama dengan tipe data terbesar (ditambah konstanta kecil). Jika ukuran objek Anda tidak terlalu banyak, ini cara yang bagus untuk menanganinya.

Sebenarnya, saya tidak akan terkejut jika meningkatkan koherensi cache data Anda akan memiliki dampak yang lebih besar daripada pertanyaan awal Anda, jadi saya pasti akan melihat lebih dalam.

Bolehkah saya menjelaskan mengapa saya pikir ini adalah masalah XY ? (Kamu tidak sendirian dalam bertanya kepada mereka.)

Saya berasumsi bahwa tujuan Anda sebenarnya adalah untuk menghemat waktu secara keseluruhan, bukan hanya untuk memahami poin tentang cache-miss dan fungsi virtual.

Berikut adalah contoh penyetelan kinerja nyata , dalam perangkat lunak nyata.

Dalam peranti lunak nyata, hal-hal yang dilakukan itu, tidak peduli seberapa berpengalaman programmer, dapat dilakukan dengan lebih baik. Orang tidak tahu apa itu sampai program ditulis dan penyesuaian kinerja dapat dilakukan. Hampir selalu ada lebih dari satu cara untuk mempercepat program. Lagi pula, untuk mengatakan suatu program optimal, Anda mengatakan bahwa dalam jajaran program yang mungkin untuk memecahkan masalah Anda, tidak ada dari mereka yang membutuhkan waktu lebih sedikit. Sangat?

Pada contoh yang saya tautkan, ini awalnya membutuhkan 2.700 mikrodetik per "pekerjaan". Serangkaian enam masalah telah diperbaiki, berlawanan arah jarum jam di sekitar pizza. Speedup pertama dihapus 33% dari waktu. Yang kedua dihapus 11%. Tetapi perhatikan, yang kedua bukan 11% pada saat ditemukan, itu 16%, karena masalah pertama hilang . Demikian pula, masalah ketiga diperbesar dari 7,4% menjadi 13% (hampir dua kali lipat) karena dua masalah pertama hilang.

Pada akhirnya, proses pembesaran ini memungkinkan semua kecuali 3,7 mikrodetik untuk dihilangkan. Itu 0,14% dari waktu aslinya, atau kecepatan 730x.

Menghapus masalah-masalah besar yang awalnya memberikan jumlah percepatan yang moderat, tetapi mereka membuka jalan untuk menghilangkan masalah-masalah selanjutnya. Masalah-masalah yang belakangan ini pada awalnya bisa menjadi bagian yang tidak signifikan dari total, tetapi setelah masalah awal dihilangkan, masalah-masalah kecil ini menjadi besar dan dapat menghasilkan percepatan besar. (Penting untuk memahami bahwa, untuk mendapatkan hasil ini, tidak ada yang dapat dilewatkan, dan pos ini menunjukkan betapa mudahnya mereka.)

Apakah program finalnya optimal? Mungkin tidak. Tidak ada speedup yang ada hubungannya dengan kesalahan cache. Apakah cache tidak penting sekarang? Mungkin.

EDIT: Saya mendapat downvotes dari orang-orang yang mengikuti "bagian yang sangat kritis" dari pertanyaan OP. Anda tidak tahu ada sesuatu yang "sangat kritis" sampai Anda tahu seberapa kecil waktu yang dibutuhkan untuk itu. Jika biaya rata-rata metode yang dipanggil adalah 10 siklus atau lebih, seiring waktu, metode pengiriman kepada mereka mungkin tidak "kritis", dibandingkan dengan apa yang sebenarnya mereka lakukan. Saya melihat ini berulang-ulang, di mana orang memperlakukan "membutuhkan setiap nanodetik" sebagai alasan untuk sen dolar dan bodoh.