Berapa biaya kinerja untuk memiliki metode virtual dalam kelas C ++?

Memiliki setidaknya satu metode virtual dalam kelas C ++ (atau salah satu kelas induknya) berarti bahwa kelas tersebut akan memiliki tabel virtual, dan setiap instance akan memiliki penunjuk virtual.

Jadi biaya memorinya cukup jelas. Yang paling penting adalah biaya memori pada instance (terutama jika instance berukuran kecil, misalnya jika mereka hanya dimaksudkan untuk berisi integer: dalam hal ini memiliki pointer virtual di setiap instance dapat menggandakan ukuran instance. Adapun ruang memori yang digunakan oleh tabel virtual, saya kira itu biasanya dapat diabaikan dibandingkan dengan ruang yang digunakan oleh kode metode yang sebenarnya.

Ini membawa saya ke pertanyaan saya: apakah ada biaya kinerja yang dapat diukur (yaitu dampak kecepatan) untuk membuat metode virtual? Akan ada pencarian di tabel virtual saat runtime, pada setiap panggilan metode, jadi jika ada panggilan yang sangat sering ke metode ini, dan jika metode ini sangat singkat, mungkin ada kinerja yang dapat diukur hit? Saya kira itu tergantung pada platformnya, tetapi adakah yang menjalankan beberapa tolok ukur?

Alasan saya bertanya adalah bahwa saya menemukan bug yang terjadi karena programmer lupa mendefinisikan metode virtual. Ini bukan pertama kalinya saya melihat kesalahan seperti ini. Dan saya berpikir: mengapa kita menambahkan kata kunci virtual saat diperlukan daripada menghapus kata kunci virtual padahal kita benar-benar yakin bahwa kata kunci tersebut tidak diperlukan? Jika biaya kinerja rendah, saya pikir saya hanya akan merekomendasikan yang berikut ini di tim saya: cukup buat setiap metode virtual secara default, termasuk destruktor, di setiap kelas, dan hanya hapus saat Anda perlu. Apakah itu terdengar gila bagi Anda?

Saya menjalankan beberapa pengaturan waktu pada prosesor PowerPC berurutan 3ghz. Pada arsitektur tersebut, biaya panggilan fungsi virtual 7 nanodetik lebih lama daripada panggilan fungsi langsung (non-virtual).

Jadi, tidak perlu khawatir tentang biaya kecuali fungsinya adalah sesuatu seperti aksesor Get () / Set () yang sepele, di mana apa pun selain inline agak boros. Overhead 7ns pada fungsi yang sejajar dengan 0,5ns sangat parah; overhead 7ns pada fungsi yang membutuhkan 500ms untuk dieksekusi tidak ada artinya.

Biaya besar dari fungsi virtual sebenarnya bukanlah pencarian function pointer di vtable (yang biasanya hanya satu siklus), tetapi lompatan tidak langsung biasanya tidak dapat diprediksi oleh cabang. Hal ini dapat menyebabkan gelembung pipa besar karena prosesor tidak dapat mengambil instruksi apa pun hingga lompatan tidak langsung (panggilan melalui penunjuk fungsi) dihentikan dan penunjuk instruksi baru dihitung. Jadi, biaya panggilan fungsi virtual jauh lebih besar daripada yang terlihat dari melihat perakitan ... tetapi masih hanya 7 nanodetik.

Sunting: Andrew, Not Sure, dan lainnya juga mengangkat poin yang sangat bagus bahwa panggilan fungsi virtual dapat menyebabkan cache instruksi hilang: jika Anda melompat ke alamat kode yang tidak ada di cache maka seluruh program akan berhenti sementara sementara instruksi diambil dari memori utama. Ini selalu merupakan penghentian yang signifikan: di Xenon, sekitar 650 siklus (menurut pengujian saya).

Namun ini bukan masalah khusus untuk fungsi virtual karena bahkan panggilan fungsi langsung akan menyebabkan kegagalan jika Anda beralih ke instruksi yang tidak ada dalam cache. Yang penting adalah apakah fungsi telah dijalankan sebelumnya baru-baru ini (membuatnya lebih mungkin berada dalam cache), dan apakah arsitektur Anda dapat memprediksi cabang statis (bukan virtual) dan mengambil instruksi tersebut ke dalam cache sebelumnya. PPC saya tidak, tapi mungkin perangkat keras terbaru Intel memilikinya.

Pengaturan waktu saya mengontrol pengaruh icache miss pada eksekusi (sengaja, karena saya mencoba memeriksa pipeline CPU secara terpisah), jadi mereka mendiskon biaya itu.

Pasti ada overhead yang terukur saat memanggil fungsi virtual - panggilan harus menggunakan vtable untuk menyelesaikan alamat fungsi untuk jenis objek tersebut. Instruksi tambahan adalah yang paling tidak Anda khawatirkan. Vtables tidak hanya mencegah banyak potensi pengoptimalan kompilator (karena tipe kompilernya bersifat polimorfik), vtables juga dapat merusak I-Cache Anda.

Tentu saja apakah penalti ini signifikan atau tidak tergantung pada aplikasi Anda, seberapa sering jalur kode tersebut dijalankan, dan pola warisan Anda.

Menurut pendapat saya, memiliki segala sesuatu sebagai virtual secara default adalah solusi menyeluruh untuk masalah yang dapat Anda selesaikan dengan cara lain.

Mungkin Anda bisa melihat bagaimana kelas dirancang / didokumentasikan / ditulis. Umumnya header untuk sebuah kelas harus menjelaskan fungsi mana yang dapat diganti oleh kelas turunan dan bagaimana mereka dipanggil. Meminta pemrogram menulis dokumentasi ini membantu memastikan bahwa mereka ditandai dengan benar sebagai virtual.

Saya juga akan mengatakan bahwa mendeklarasikan setiap fungsi sebagai virtual dapat menyebabkan lebih banyak bug daripada hanya lupa menandai sesuatu sebagai virtual. Jika semua fungsi virtual semuanya dapat diganti dengan kelas dasar - publik, dilindungi, pribadi - semuanya menjadi permainan yang adil. Dengan kecelakaan atau niat subclass kemudian dapat mengubah perilaku fungsi yang kemudian menyebabkan masalah saat digunakan dalam implementasi dasar.

Tergantung. :) (Apakah Anda mengharapkan hal lain?)

Setelah kelas mendapatkan fungsi virtual, itu tidak bisa lagi menjadi tipe data POD, (mungkin juga belum pernah ada sebelumnya, dalam hal ini tidak akan membuat perbedaan) dan itu membuat berbagai macam pengoptimalan menjadi tidak mungkin.

std :: copy () pada jenis POD biasa dapat menggunakan rutinitas memcpy sederhana, tetapi jenis non-POD harus ditangani lebih hati-hati.

Konstruksi menjadi jauh lebih lambat karena vtabel harus diinisialisasi. Dalam kasus terburuk, perbedaan kinerja antara tipe data POD dan non-POD dapat menjadi signifikan.

Dalam kasus terburuk, Anda mungkin melihat eksekusi 5x lebih lambat (nomor itu diambil dari proyek universitas yang saya lakukan baru-baru ini untuk menerapkan ulang beberapa kelas perpustakaan standar. Penampung kami membutuhkan waktu sekitar 5x lebih lama untuk dibuat segera setelah jenis data yang disimpan mendapat vtable)

Tentu saja, dalam banyak kasus, Anda tidak mungkin melihat perbedaan kinerja yang dapat diukur, ini hanya untuk menunjukkan bahwa dalam beberapa kasus perbatasan, ini bisa mahal.

Namun, performa seharusnya tidak menjadi pertimbangan utama Anda di sini. Menjadikan segalanya virtual bukanlah solusi sempurna karena alasan lain.

Mengizinkan segala sesuatu untuk diganti dalam kelas turunan membuat lebih sulit untuk mempertahankan invarian kelas. Bagaimana sebuah kelas menjamin bahwa ia tetap dalam status yang konsisten ketika salah satu metodenya dapat didefinisikan ulang kapan saja?

Membuat segala sesuatu menjadi virtual dapat menghilangkan beberapa potensi bug, tetapi juga memperkenalkan yang baru.

Jika Anda memerlukan fungsionalitas pengiriman virtual, Anda harus membayar harganya. Keuntungan dari C ++ adalah Anda dapat menggunakan implementasi pengiriman virtual yang sangat efisien yang disediakan oleh compiler, daripada versi yang mungkin tidak efisien yang Anda implementasikan sendiri.

Namun, membebani diri sendiri dengan overhead jika Anda tidak membutuhkannya mungkin akan terlalu berlebihan. Dan sebagian besar kelas tidak dirancang untuk diwariskan - untuk membuat kelas dasar yang baik memerlukan lebih dari sekadar membuat fungsinya virtual.

Pengiriman virtual adalah urutan besarnya lebih lambat daripada beberapa alternatif - bukan karena tipu muslihat melainkan pencegahan sebaris. Di bawah ini, saya mengilustrasikan bahwa dengan membandingkan pengiriman virtual dengan implementasi yang menyematkan "tipe (-identifying) number" di objek dan menggunakan pernyataan switch untuk memilih kode tipe-spesifik. Ini menghindari overhead panggilan fungsi sepenuhnya - hanya melakukan lompatan lokal. Ada potensi biaya untuk pemeliharaan, ketergantungan rekompilasi, dll. Melalui lokalisasi paksa (dalam sakelar) dari fungsionalitas jenis khusus.

PENERAPAN

#include <iostream>
#include <vector>

// virtual dispatch model...

struct Base
{
    virtual int f() const { return 1; }
};

struct Derived : Base
{
    virtual int f() const { return 2; }
};

// alternative: member variable encodes runtime type...

struct Type
{
    Type(int type) : type_(type) { }
    int type_;
};

struct A : Type
{
    A() : Type(1) { }
    int f() const { return 1; }
};

struct B : Type
{
    B() : Type(2) { }
    int f() const { return 2; }
};

struct Timer
{
    Timer() { clock_gettime(CLOCK_MONOTONIC, &from); }
    struct timespec from;
    double elapsed() const
    {
        struct timespec to;
        clock_gettime(CLOCK_MONOTONIC, &to);
        return to.tv_sec - from.tv_sec + 1E-9 * (to.tv_nsec - from.tv_nsec);
    }
};

int main(int argc)
{
  for (int j = 0; j < 3; ++j)
  {
    typedef std::vector<Base*> V;
    V v;

    for (int i = 0; i < 1000; ++i)
        v.push_back(i % 2 ? new Base : (Base*)new Derived);

    int total = 0;

    Timer tv;

    for (int i = 0; i < 100000; ++i)
        for (V::const_iterator i = v.begin(); i != v.end(); ++i)
            total += (*i)->f();

    double tve = tv.elapsed();

    std::cout << "virtual dispatch: " << total << ' ' << tve << '\n';

    // ----------------------------

    typedef std::vector<Type*> W;
    W w;

    for (int i = 0; i < 1000; ++i)
        w.push_back(i % 2 ? (Type*)new A : (Type*)new B);

    total = 0;

    Timer tw;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
        {
            if ((*i)->type_ == 1)
                total += ((A*)(*i))->f();
            else
                total += ((B*)(*i))->f();
        }

    double twe = tw.elapsed();

    std::cout << "switched: " << total << ' ' << twe << '\n';

    // ----------------------------

    total = 0;

    Timer tw2;

    for (int i = 0; i < 100000; ++i)
        for (W::const_iterator i = w.begin(); i != w.end(); ++i)
            total += (*i)->type_;

    double tw2e = tw2.elapsed();

    std::cout << "overheads: " << total << ' ' << tw2e << '\n';
  }
}

HASIL KINERJA

Di sistem Linux saya:

~/dev  g++ -O2 -o vdt vdt.cc -lrt
~/dev  ./vdt                     
virtual dispatch: 150000000 1.28025
switched: 150000000 0.344314
overhead: 150000000 0.229018
virtual dispatch: 150000000 1.285
switched: 150000000 0.345367
overhead: 150000000 0.231051
virtual dispatch: 150000000 1.28969
switched: 150000000 0.345876
overhead: 150000000 0.230726

Hal ini menunjukkan bahwa pendekatan tipe-nomor-switched inline adalah sekitar (1,28 - 0,23) / (0,344 - 0,23) = 9,2 kali lebih cepat. Tentu saja, itu khusus untuk sistem yang diuji / compiler flags & version dll, tetapi umumnya bersifat indikatif.

KOMENTAR RE VIRTUAL DISPATCH

Harus dikatakan bahwa overhead panggilan fungsi virtual adalah sesuatu yang jarang signifikan, dan kemudian hanya untuk fungsi yang sering disebut trivial (seperti getter dan setter). Meski begitu, Anda mungkin bisa menyediakan satu fungsi untuk mendapatkan dan menyetel banyak hal sekaligus, meminimalkan biaya. Orang-orang terlalu khawatir tentang pengiriman virtual - jadi lakukan pembuatan profil sebelum menemukan alternatif yang canggung. Masalah utama dengan mereka adalah mereka melakukan panggilan fungsi out-of-line, meskipun mereka juga mendelokalisasi kode yang dieksekusi yang mengubah pola pemanfaatan cache (menjadi lebih baik atau (lebih sering) lebih buruk).

Biaya tambahan hampir tidak ada dalam kebanyakan skenario. (maafkan permainan kata). ejakulasi telah memposting tindakan relatif yang masuk akal.

Hal terbesar yang Anda berikan adalah kemungkinan pengoptimalan karena penyebarisan. Mereka bisa sangat baik jika fungsinya dipanggil dengan parameter konstan. Ini jarang membuat perbedaan nyata, tetapi dalam beberapa kasus, ini bisa sangat besar.

Mengenai pengoptimalan:
Penting untuk mengetahui dan mempertimbangkan biaya relatif konstruksi bahasa Anda. Notasi Big O hanya setengah dari cerita - bagaimana skala aplikasi Anda . Separuh lainnya adalah faktor konstanta di depannya.

Sebagai aturan praktis, saya tidak akan berusaha keras untuk menghindari fungsi virtual, kecuali ada indikasi yang jelas dan spesifik bahwa itu adalah leher botol. Desain yang bersih selalu didahulukan - tetapi hanya satu pemangku kepentingan yang tidak boleh terlalu merugikan pihak lain.

Contoh yang dibuat-buat: Penghancur virtual kosong pada larik berisi satu juta elemen kecil dapat membajak setidaknya 4MB data, merusak cache Anda. Jika destruktor itu dapat disingkirkan, data tidak akan disentuh.

Saat menulis kode perpustakaan, pertimbangan seperti itu jauh dari prematur. Anda tidak pernah tahu berapa banyak loop yang akan ditempatkan di sekitar fungsi Anda.

Sementara semua orang benar tentang kinerja metode virtual dan semacamnya, saya pikir masalah sebenarnya adalah apakah tim mengetahui tentang definisi kata kunci virtual dalam C ++.

Perhatikan kode ini, apa hasilnya?

#include <stdio.h>

class A
{
public:
    void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Tidak ada yang mengejutkan di sini:

A::Foo()
B::Foo()
A::Foo()

Karena tidak ada yang virtual. Jika kata kunci virtual ditambahkan ke depan Foo di kelas A dan B, kita mendapatkan ini untuk hasilnya:

A::Foo()
B::Foo()
B::Foo()

Hampir seperti yang diharapkan semua orang.

Sekarang, Anda menyebutkan bahwa ada bug karena seseorang lupa menambahkan kata kunci virtual. Jadi pertimbangkan kode ini (di mana kata kunci virtual ditambahkan ke A, tetapi bukan kelas B). Lalu apa hasilnya?

#include <stdio.h>

class A
{
public:
    virtual void Foo()
    {
        printf("A::Foo()\n");
    }
};

class B : public A
{
public:
    void Foo()
    {
        printf("B::Foo()\n");
    }
};

int main(int argc, char** argv)
{    
    A* a = new A();
    a->Foo();

    B* b = new B();
    b->Foo();

    A* a2 = new B();
    a2->Foo();

    return 0;
}

Jawaban: Sama seperti jika kata kunci virtual ditambahkan ke B? Alasannya adalah bahwa tanda tangan untuk B :: Foo sama persis dengan A :: Foo () dan karena Foo A virtual, begitu juga dengan B.

Sekarang pertimbangkan kasus di mana Foo B adalah virtual dan A tidak. Lalu apa hasilnya? Dalam hal ini, hasilnya adalah

A::Foo()
B::Foo()
A::Foo()

Kata kunci virtual bekerja ke bawah dalam hierarki, bukan ke atas. Itu tidak pernah membuat metode kelas dasar virtual. Pertama kali metode virtual ditemukan dalam hierarki adalah saat polimorfisme dimulai. Tidak ada cara untuk kelas selanjutnya untuk membuat kelas sebelumnya memiliki metode virtual.

Jangan lupa bahwa metode virtual berarti bahwa kelas ini memberikan kelas yang akan datang kemampuan untuk mengganti / mengubah beberapa perilakunya.

Jadi, jika Anda memiliki aturan untuk menghapus kata kunci virtual, itu mungkin tidak memiliki efek yang diinginkan.

Kata kunci virtual di C ++ adalah konsep yang ampuh. Anda harus memastikan bahwa setiap anggota tim benar-benar mengetahui konsep ini sehingga dapat digunakan sesuai desain.

Bergantung pada platform Anda, overhead panggilan virtual bisa sangat tidak diinginkan. Dengan mendeklarasikan setiap fungsi virtual, pada dasarnya Anda memanggil semuanya melalui penunjuk fungsi. Setidaknya ini adalah dereferensi tambahan, tetapi pada beberapa platform PPC akan menggunakan instruksi yang dikodekan atau lambat untuk mencapai ini.

Saya akan merekomendasikan terhadap saran Anda karena alasan ini, tetapi jika itu membantu Anda mencegah bug maka itu mungkin sepadan dengan pertukarannya. Saya tidak bisa tidak berpikir bahwa pasti ada jalan tengah yang layak ditemukan.

Ini hanya akan membutuhkan beberapa instruksi asm tambahan untuk memanggil metode virtual.

Tetapi saya tidak berpikir Anda khawatir bahwa kesenangan (int a, int b) memiliki beberapa instruksi 'push' ekstra dibandingkan dengan fun (). Jadi jangan khawatir tentang virtual juga, sampai Anda berada dalam situasi khusus dan melihat bahwa itu benar-benar mengarah pada masalah.

PS Jika Anda memiliki metode virtual, pastikan Anda memiliki destruktor virtual. Dengan cara ini Anda akan menghindari kemungkinan masalah

Menanggapi komentar 'xtofl' dan 'Tom'. Saya melakukan tes kecil dengan 3 fungsi:

1. Virtual
2. Normal
3. Normal dengan 3 parameter int

Tes saya adalah iterasi sederhana:

for(int it = 0; it < 100000000; it ++) {
    test.Method();
}

Dan berikut hasilnya:

1. 3,913 dtk
2. 3,873 dtk
3. 3,970 dtk

Itu dikompilasi oleh VC ++ dalam mode debug. Saya hanya melakukan 5 tes per metode dan menghitung nilai rata-rata (jadi hasilnya mungkin sangat tidak akurat) ... Bagaimanapun, nilainya hampir sama dengan asumsi 100 juta panggilan. Dan metode dengan 3 push / pop ekstra lebih lambat.

Poin utamanya adalah jika Anda tidak menyukai analogi dengan push / pop, pikirkan tambahan if / else dalam kode Anda? Apakah Anda berpikir tentang pipa CPU ketika Anda menambahkan tambahan if / else ;-) Selain itu, Anda tidak pernah tahu tentang CPU apa kode akan berjalan ... Kompiler biasa dapat menghasilkan kode yang lebih optimal untuk satu CPU dan kurang optimal untuk yang lain ( Intel Penyusun C ++ )