Pertanyaan Apakah std :: vector lebih lambat dari array biasa?


Saya selalu berpikir itu adalah kebijaksanaan umum itu std::vector adalah "diimplementasikan sebagai array," bla bla bla. Hari ini saya turun dan mengujinya, dan tampaknya tidak demikian:

Berikut beberapa hasil tes:

UseArray completed in 2.619 seconds
UseVector completed in 9.284 seconds
UseVectorPushBack completed in 14.669 seconds
The whole thing completed in 26.591 seconds

Itu sekitar 3 - 4 kali lebih lambat! Tidak benar-benar membenarkan untuk "vector mungkin lebih lambat untuk beberapa komentar nanosecs.

Dan kode yang saya gunakan:

#include <cstdlib>
#include <vector>

#include <iostream>
#include <string>

#include <boost/date_time/posix_time/ptime.hpp>
#include <boost/date_time/microsec_time_clock.hpp>

class TestTimer
{
    public:
        TestTimer(const std::string & name) : name(name),
            start(boost::date_time::microsec_clock<boost::posix_time::ptime>::local_time())
        {
        }

        ~TestTimer()
        {
            using namespace std;
            using namespace boost;

            posix_time::ptime now(date_time::microsec_clock<posix_time::ptime>::local_time());
            posix_time::time_duration d = now - start;

            cout << name << " completed in " << d.total_milliseconds() / 1000.0 <<
                " seconds" << endl;
        }

    private:
        std::string name;
        boost::posix_time::ptime start;
};

struct Pixel
{
    Pixel()
    {
    }

    Pixel(unsigned char r, unsigned char g, unsigned char b) : r(r), g(g), b(b)
    {
    }

    unsigned char r, g, b;
};

void UseVector()
{
    TestTimer t("UseVector");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
        pixels.resize(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPushBack");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels;
            pixels.reserve(dimension * dimension);

        for(int i = 0; i < dimension * dimension; ++i)
            pixels.push_back(Pixel(255, 0, 0));
    }
}

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        Pixel * pixels = (Pixel *)malloc(sizeof(Pixel) * dimension * dimension);

        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }

        free(pixels);
    }
}

int main()
{
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();
    UseVectorPushBack();

    return 0;
}

Apakah saya melakukan kesalahan atau sesuatu? Ataukah saya baru saja merusak mitos kinerja ini?

Saya menggunakan mode Rilis di Visual Studio 2005.


Di Visual C ++, #define _SECURE_SCL 0 mengurangi UseVector setengahnya (menurunkannya menjadi 4 detik). Ini sangat besar, IMO.


192
2017-09-08 02:38


asal


Jawaban:


Menggunakan yang berikut:

g ++ -O3 Time.cpp -I <MyBoost>
  ./a.out
  UseArray selesai dalam 2,196 detik
  UseVector selesai dalam 4,412 detik
  UseVectorPushBack selesai dalam 8,017 detik
  Semuanya selesai dalam 14.626 detik

Jadi array dua kali lebih cepat dari vektor.

Tapi setelah melihat kode secara lebih rinci, ini diharapkan; saat Anda berlari melintasi vektor dua kali dan larik hanya sekali. Catatan: ketika Anda resize() vektor Anda tidak hanya mengalokasikan memori tetapi juga berjalan melalui vektor dan memanggil konstruktor pada setiap anggota.

Atur ulang kode sedikit sehingga vektor hanya menginisialisasi setiap objek satu kali:

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

Sekarang lakukan waktu yang sama lagi:

g ++ -O3 Time.cpp -I <MyBoost>
  ./a.out
  UseVector selesai dalam 2,216 detik

Vektor sekarang kinerja hanya sedikit lebih buruk daripada array. IMO perbedaan ini tidak signifikan dan dapat disebabkan oleh banyak hal yang tidak terkait dengan tes.

Saya juga akan mempertimbangkan bahwa Anda tidak benar menginisialisasi / Menghancurkan objek Pixel di UseArrray() metode tidak konstruktor / destruktor tidak disebut (ini mungkin bukan masalah untuk kelas sederhana ini, tetapi sesuatu yang sedikit lebih kompleks (yaitu dengan pointer atau anggota dengan pointer) akan menyebabkan masalah.


246
2017-09-08 03:00



Pertanyaan bagus. Saya datang ke sini berharap menemukan beberapa perbaikan sederhana yang akan mempercepat tes vektor. Itu tidak berhasil seperti yang saya harapkan!

Optimasi membantu, tetapi itu tidak cukup. Dengan optimasi pada saya masih melihat perbedaan kinerja 2X antara UseArray dan UseVector. Menariknya, UseVector secara signifikan lebih lambat daripada UseVectorPushBack tanpa optimasi.

# g++ -Wall -Wextra -pedantic -o vector vector.cpp
# ./vector
UseArray completed in 20.68 seconds
UseVector completed in 120.509 seconds
UseVectorPushBack completed in 37.654 seconds
The whole thing completed in 178.845 seconds
# g++ -Wall -Wextra -pedantic -O3 -o vector vector.cpp
# ./vector
UseArray completed in 3.09 seconds
UseVector completed in 6.09 seconds
UseVectorPushBack completed in 9.847 seconds
The whole thing completed in 19.028 seconds

Ide # 1 - Gunakan [] baru bukan malloc

Saya mencoba berubah malloc() untuk new[] di UseArray sehingga objek akan dibangun. Dan mengubah dari penugasan lapangan individual untuk menetapkan instance Pixel. Oh, dan ganti nama variabel loop batin menjadi j.

void UseArray()
{
    TestTimer t("UseArray");

    for(int i = 0; i < 1000; ++i)
    {   
        int dimension = 999;

        // Same speed as malloc().
        Pixel * pixels = new Pixel[dimension * dimension];

        for(int j = 0 ; j < dimension * dimension; ++j)
            pixels[j] = Pixel(255, 0, 0);

        delete[] pixels;
    }
}

Anehnya (bagi saya), tidak ada perubahan yang membuat perbedaan apa pun. Bahkan tidak berubah new[] yang akan membangun default semua Pixel. Tampaknya gcc dapat mengoptimalkan panggilan konstruktor default saat menggunakan new[], tetapi tidak saat menggunakan vector.

Ide # 2 - Hapus panggilan operator ulang []

Saya juga berusaha menyingkirkan ketiganya operator[] mencari dan menyimpan referensi ke cache pixels[j]. Itu benar-benar memperlambat UseVector! Ups.

for(int j = 0; j < dimension * dimension; ++j)
{
    // Slower than accessing pixels[j] three times.
    Pixel &pixel = pixels[j];
    pixel.r = 255;
    pixel.g = 0;
    pixel.b = 0;
}

# ./vector 
UseArray completed in 3.226 seconds
UseVector completed in 7.54 seconds
UseVectorPushBack completed in 9.859 seconds
The whole thing completed in 20.626 seconds

Ide # 3 - Hapus konstruktor

Bagaimana dengan menghapus konstruktor sepenuhnya? Maka mungkin gcc dapat mengoptimalkan konstruksi semua objek ketika vektor dibuat. Apa yang terjadi jika kita mengubah Pixel ke:

struct Pixel
{
    unsigned char r, g, b;
};

Hasil: sekitar 10% lebih cepat. Masih lebih lambat dari array. Hm.

# ./vector 
UseArray completed in 3.239 seconds
UseVector completed in 5.567 seconds

Ide # 4 - Gunakan iterator, bukan loop index

Bagaimana kalau menggunakan vector<Pixel>::iterator bukannya indeks loop?

for (std::vector<Pixel>::iterator j = pixels.begin(); j != pixels.end(); ++j)
{
    j->r = 255;
    j->g = 0;
    j->b = 0;
}

Hasil:

# ./vector 
UseArray completed in 3.264 seconds
UseVector completed in 5.443 seconds

Tidak, tidak berbeda. Setidaknya itu tidak lebih lambat. Saya pikir ini akan memiliki kinerja yang mirip dengan # 2 di mana saya menggunakan Pixel& referensi.

Kesimpulan

Bahkan jika beberapa cookie pintar mencari tahu bagaimana membuat vektor loop secepat satu array, ini tidak berbicara dengan baik tentang perilaku default dari std::vector. Begitu banyak untuk compiler yang cukup pintar untuk mengoptimalkan semua C ++ ness dan membuat kontainer STL secepat raw array.

Intinya adalah bahwa kompilator tidak dapat mengoptimalkan panggilan konstruktor default no-op ketika menggunakan std::vector. Jika Anda menggunakan polos new[] itu mengoptimalkan mereka dengan baik. Tapi tidak dengan std::vector. Bahkan jika Anda dapat menulis ulang kode Anda untuk menghilangkan panggilan konstruktor yang terbang di muka mantra di sini: "Kompiler lebih pintar dari Anda. STL sama cepatnya seperti biasa C. Jangan khawatir tentang itu."


52
2017-09-08 12:27



Agar adil, Anda tidak dapat membandingkan implementasi C ++ ke implementasi C, karena saya akan memanggil versi malloc Anda. malloc tidak membuat objek - hanya mengalokasikan memori mentah. Bahwa Anda kemudian memperlakukan memori itu sebagai objek tanpa memanggil konstruktor miskin C ++ (mungkin tidak valid - saya akan meninggalkan itu kepada pengacara bahasa).

Yang mengatakan, hanya mengubah malloc menjadi new Pixel[dimensions*dimensions] dan bebas delete [] pixels tidak membuat banyak perbedaan dengan implementasi sederhana Pixel yang Anda miliki. Inilah hasilnya di kotak saya (E6600, 64-bit):

UseArray completed in 0.269 seconds
UseVector completed in 1.665 seconds
UseVectorPushBack completed in 7.309 seconds
The whole thing completed in 9.244 seconds

Tetapi dengan sedikit perubahan, tabel berubah:

Pixel.h

struct Pixel
{
    Pixel();
    Pixel(unsigned char r, unsigned char g, unsigned char b);

    unsigned char r, g, b;
};

Pixel.cc

#include "Pixel.h"

Pixel::Pixel() {}
Pixel::Pixel(unsigned char r, unsigned char g, unsigned char b) 
  : r(r), g(g), b(b) {}

main.cc

#include "Pixel.h"
[rest of test harness without class Pixel]
[UseArray now uses new/delete not malloc/free]

Dikompilasi dengan cara ini:

$ g++ -O3 -c -o Pixel.o Pixel.cc
$ g++ -O3 -c -o main.o main.cc
$ g++ -o main main.o Pixel.o

kami mendapatkan hasil yang sangat berbeda:

UseArray completed in 2.78 seconds
UseVector completed in 1.651 seconds
UseVectorPushBack completed in 7.826 seconds
The whole thing completed in 12.258 seconds

Dengan konstruktor non-inlined untuk Pixel, std :: vector sekarang mengalahkan array mentah.

Tampaknya kerumitan alokasi melalui std :: vector dan std: allocator terlalu banyak untuk dioptimalkan seefektif mudah new Pixel[n]. Namun, kita dapat melihat bahwa masalahnya hanya dengan alokasi bukan akses vektor dengan mengutak-atik beberapa fungsi pengujian untuk membuat vektor / larik satu kali dengan memindahkannya di luar lingkaran:

void UseVector()
{
    TestTimer t("UseVector");

    int dimension = 999;
    std::vector<Pixel> pixels;
    pixels.resize(dimension * dimension);

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
}

dan

void UseArray()
{
    TestTimer t("UseArray");

    int dimension = 999;
    Pixel * pixels = new Pixel[dimension * dimension];

    for(int i = 0; i < 1000; ++i)
    {
        for(int i = 0 ; i < dimension * dimension; ++i)
        {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = 0;
        }
    }
    delete [] pixels;
}

Kami mendapatkan hasil ini sekarang:

UseArray completed in 0.254 seconds
UseVector completed in 0.249 seconds
UseVectorPushBack completed in 7.298 seconds
The whole thing completed in 7.802 seconds

Apa yang bisa kita pelajari dari ini adalah bahwa std :: vector sebanding dengan array mentah untuk akses, tetapi jika Anda perlu membuat dan menghapus vektor / array berkali-kali, membuat objek yang kompleks akan memakan waktu lebih banyak yang menciptakan susunan sederhana ketika konstruktor elemen tidak inlined. Saya tidak berpikir ini sangat mengejutkan.


33
2017-07-17 14:25



Ini pertanyaan lama tapi populer.

Pada titik ini, banyak programmer akan bekerja di C ++ 11. Dan dalam C ++ 11, kode OP yang ditulis berjalan sama cepatnya UseArray atau UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

Masalah mendasar adalah saat Anda Pixel struktur tidak diinisialisasi, std::vector<T>::resize( size_t, T const&=T() ) mengambil bawaan yang dibangun Pixel dan menyalinnya. Compiler tidak memperhatikan itu diminta untuk menyalin data terinisialisasi, jadi itu benar-benar dilakukan salinan.

Di C ++ 11, std::vector<T>::resize memiliki dua kelebihan beban. Yang pertama adalah std::vector<T>::resize(size_t), yang lainnya std::vector<T>::resize(size_t, T const&). Ini berarti ketika Anda memanggil resize tanpa argumen kedua, ia hanya membangun default, dan compiler cukup pintar untuk menyadari bahwa konstruksi default tidak melakukan apa-apa, sehingga melewatkan pass over buffer.

(Dua kelebihan beban di mana ditambahkan untuk menangani jenis yang dapat dipindahkan, dapat dikonstruksi dan tidak dapat dipinjamkan - peningkatan kinerja saat mengerjakan data yang tidak diinisialisasi adalah bonus).

Itu push_back Solusi juga melakukan pengecekan pagar, yang memperlambatnya, sehingga tetap lebih lambat daripada malloc versi.

contoh hidup (Saya juga mengganti timer dengan chrono::high_resolution_clock).

Perhatikan bahwa jika Anda memiliki struktur yang biasanya memerlukan inisialisasi, tetapi Anda ingin menanganinya setelah menumbuhkan buffer, Anda dapat melakukannya dengan custom std::vector alokator. Jika Anda ingin kemudian memindahkannya menjadi lebih normal std::vectorSaya percaya penggunaan hati-hati allocator_traits dan mengesampingkan == mungkin melakukan itu, tapi saya tidak yakin.


33
2017-09-08 13:00



Coba dengan ini:

void UseVectorCtor()
{
    TestTimer t("UseConstructor");

    for(int i = 0; i < 1000; ++i)
    {
        int dimension = 999;

        std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));
    }
}

Saya mendapatkan kinerja hampir persis sama dengan array.

Hal tentang vector adalah bahwa itu alat yang jauh lebih umum daripada array. Dan itu berarti Anda harus mempertimbangkan bagaimana kamu menggunakannya. Ini dapat digunakan dalam banyak cara yang berbeda, menyediakan fungsionalitas yang tidak dimiliki oleh array. Dan jika Anda menggunakannya "salah" untuk tujuan Anda, Anda mengeluarkan banyak overhead, tetapi jika Anda menggunakannya dengan benar, itu biasanya pada dasarnya struktur data nol-overhead. Dalam kasus ini, masalahnya adalah Anda secara terpisah menginisialisasi vektor (menyebabkan semua elemen memiliki ktor default yang disebut), dan kemudian menimpa setiap elemen secara individual dengan nilai yang benar. Itu jauh lebih sulit bagi kompiler untuk mengoptimalkan jauh daripada ketika Anda melakukan hal yang sama dengan array. Itulah mengapa vektor menyediakan konstruktor yang memungkinkan Anda melakukan hal itu: menginisialisasi N elemen dengan nilai X.

Dan ketika Anda menggunakannya, vektor hanya secepat array.

Jadi tidak, Anda belum memecahkan mitos kinerja. Tetapi Anda telah menunjukkan bahwa itu hanya benar jika Anda menggunakan vektor secara optimal, yang merupakan poin yang cukup bagus juga. :)

Sisi baiknya, itu benar-benar paling sederhana penggunaan yang ternyata paling cepat. Jika Anda membandingkan cuplikan kode saya (satu baris) dengan jawaban John Kugelman, yang berisi tumpukan dan tumpukan tweak dan optimisasi, yang masih belum cukup menghilangkan perbedaan kinerja, cukup jelas bahwa vector cukup dirancang dengan cerdik. Anda tidak harus melompat melalui lingkaran untuk mendapatkan kecepatan yang sama dengan sebuah array. Sebaliknya, Anda harus menggunakan solusi sederhan mungkin.


26
2017-09-01 10:34



Itu bukan perbandingan yang adil ketika saya pertama kali melihat kode Anda; Saya benar-benar berpikir Anda tidak membandingkan apel dengan apel. Jadi saya pikir, mari kita konstruktor dan destruktor dipanggil pada semua tes; lalu bandingkan.

const size_t dimension = 1000;

void UseArray() {
    TestTimer t("UseArray");
    for(size_t j = 0; j < dimension; ++j) {
        Pixel* pixels = new Pixel[dimension * dimension];
        for(size_t i = 0 ; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
        delete[] pixels;
    }
}

void UseVector() {
    TestTimer t("UseVector");
    for(size_t j = 0; j < dimension; ++j) {
        std::vector<Pixel> pixels(dimension * dimension);
        for(size_t i = 0; i < dimension * dimension; ++i) {
            pixels[i].r = 255;
            pixels[i].g = 0;
            pixels[i].b = (unsigned char) (i % 255);
        }
    }
}

int main() {
    TestTimer t1("The whole thing");

    UseArray();
    UseVector();

    return 0;
}

Pikiran saya, bahwa dengan pengaturan ini, mereka seharusnya persis sama. Ternyata, saya salah.

UseArray completed in 3.06 seconds
UseVector completed in 4.087 seconds
The whole thing completed in 10.14 seconds

Jadi mengapa 30% penurunan kinerja ini bahkan terjadi? STL memiliki segalanya di header, jadi seharusnya mungkin bagi compiler untuk memahami segala sesuatu yang diperlukan.

Pikiran saya adalah bahwa dalam cara loop menginisialisasi semua nilai ke konstruktor default. Jadi saya melakukan tes:

class Tester {
public:
    static int count;
    static int count2;
    Tester() { count++; }
    Tester(const Tester&) { count2++; }
};
int Tester::count = 0;
int Tester::count2 = 0;

int main() {
    std::vector<Tester> myvec(300);
    printf("Default Constructed: %i\nCopy Constructed: %i\n", Tester::count, Tester::count2);

    return 0;
}

Hasilnya seperti yang saya duga:

Default Constructed: 1
Copy Constructed: 300

Ini jelas merupakan sumber perlambatan, fakta bahwa vektor menggunakan konstruktor salin untuk menginisialisasi elemen dari objek bawaan bawaan.

Ini berarti, bahwa operasi pseudo-operasi berikut terjadi selama pembangunan vektor:

Pixel pixel;
for (auto i = 0; i < N; ++i) vector[i] = pixel;

Yang mana, karena konstruktor salin implisit yang dibuat oleh kompiler, diperluas ke yang berikut:

Pixel pixel;
for (auto i = 0; i < N; ++i) {
    vector[i].r = pixel.r;
    vector[i].g = pixel.g;
    vector[i].b = pixel.b;
}

Jadi defaultnya Pixel tetap tidak diinisialisasi, sementara sisanya diinisialisasi dengan default Pixel's tidak diinisiasi nilai-nilai.

Dibandingkan dengan situasi alternatif dengan New[]/Delete[]:

int main() {
    Tester* myvec = new Tester[300];

    printf("Default Constructed: %i\nCopy Constructed:%i\n", Tester::count, Tester::count2);

    delete[] myvec;

    return 0;
}

Default Constructed: 300
Copy Constructed: 0

Mereka semua ditinggalkan untuk nilai-nilai yang tidak diinisialisasi, dan tanpa iterasi ganda di urutan.

Berbekal informasi ini, bagaimana kita bisa mengujinya? Mari mencoba menulis ulang konstruktor salinan implisit.

Pixel(const Pixel&) {}

Dan hasilnya?

UseArray completed in 2.617 seconds
UseVector completed in 2.682 seconds
The whole thing completed in 5.301 seconds

Jadi secara ringkas, jika Anda membuat ratusan vektor sangat sering: pikirkan kembali algoritme Anda.

Dalam hal apapun, itu STL implementasi tidak lebih lambat untuk beberapa alasan yang tidak diketahui, itu hanya melakukan apa yang Anda minta; berharap kamu tahu lebih baik.


21
2017-09-08 02:45



Coba nonaktifkan memeriksa iterator dan membangun dalam mode rilis. Anda tidak harus melihat banyak perbedaan kinerja.


7
2017-09-08 02:43



GNU's STL (dan lain-lain), diberikan vector<T>(n), default membangun objek prototypal T() - kompiler akan mengoptimalkan konstruktor kosong - tetapi kemudian salinan dari sampah apa pun yang terjadi di alamat memori sekarang disediakan untuk objek yang diambil oleh STL __uninitialized_fill_n_aux, yang mengalirkan salinan objek itu sebagai nilai default dalam vektor. Jadi, "saya" STL tidak mengulang membangun, tetapi membangun kemudian loop / menyalin. Ini kontra intuitif, tapi aku harus ingat ketika saya mengomentari pertanyaan stackoverflow baru-baru ini tentang hal ini: konstruk / copy dapat lebih efisien untuk referensi benda-benda yang dihitung dll.

Begitu:

vector<T> x(n);

atau

vector<T> x;
x.resize(n);

- pada banyak penerapan STL - sesuatu seperti:

T temp;
for (int i = 0; i < n; ++i)
    x[i] = temp;

Masalahnya adalah bahwa generasi saat ini pengoptimal compiler tampaknya tidak bekerja dari wawasan bahwa temp adalah sampah yang tidak diinisialisasi, dan gagal mengoptimalkan penyalinan loop dan penyalinan salinan default. Anda dapat secara kredibel berpendapat bahwa kompiler benar-benar tidak boleh mengoptimalkan ini, sebagai programmer yang menulis di atas memiliki harapan yang wajar bahwa semua objek akan identik setelah loop, bahkan jika sampah (peringatan biasa tentang 'identik' / operator == vs memcmp / operator = dll berlaku). Compiler tidak dapat diharapkan untuk memiliki wawasan tambahan ke dalam konteks yang lebih besar dari std :: vector <> atau penggunaan data yang nantinya akan menyarankan bahwa pengoptimalan ini aman.

Ini dapat dibandingkan dengan implementasi langsung yang lebih jelas:

for (int i = 0; i < n; ++i)
    x[i] = T();

Yang dapat kita harapkan kompilator untuk mengoptimalkan.

Untuk menjadi sedikit lebih eksplisit tentang pembenaran untuk aspek perilaku vektor ini, pertimbangkan:

std::vector<big_reference_counted_object> x(10000);

Jelas itu perbedaan utama jika kita membuat 10.000 objek independen versus 10.000 referensi data yang sama. Ada argumen yang masuk akal bahwa keuntungan dari melindungi pengguna C ++ biasa dari tidak sengaja melakukan sesuatu yang sangat mahal melebihi biaya dunia nyata yang sangat kecil dari konstruksi salinan yang sulit dioptimalkan.

ASLI JAWABAN (untuk referensi / memahami komentar): Tidak ada kesempatan. vektor secepat array, setidaknya jika Anda memesan ruang dengan bijaksana. ...


4
2017-09-08 04:43



Jawaban Martin York mengganggu saya karena sepertinya upaya untuk menyikat masalah inisialisasi di bawah karpet. Tapi dia benar untuk mengidentifikasi konstruksi standar yang berlebihan sebagai sumber masalah kinerja.

[EDIT: Jawaban Martin tidak lagi menyarankan mengganti konstruktor default.]

Untuk masalah segera di tangan, Anda pasti bisa memanggil versi 2-parameter dari vector<Pixel> sebagai gantinya:

std::vector<Pixel> pixels(dimension * dimension, Pixel(255, 0, 0));

Itu berfungsi jika Anda ingin menginisialisasi dengan nilai konstan, yang merupakan kasus umum. Tetapi masalah yang lebih umum adalah: Bagaimana Anda dapat secara efisien memulai dengan sesuatu yang lebih rumit daripada nilai konstan?

Untuk ini, Anda dapat menggunakan back_insert_iterator, yang merupakan adaptor iterator. Berikut ini contoh dengan vektor ints, meskipun ide umum bekerja dengan baik untuk Pixels:

#include <iterator>
// Simple functor return a list of squares: 1, 4, 9, 16...
struct squares {
    squares() { i = 0; }
    int operator()() const { ++i; return i * i; }

private:
    int i;
};

...

std::vector<int> v;
v.reserve(someSize);     // To make insertions efficient
std::generate_n(std::back_inserter(v), someSize, squares());

Atau Anda bisa menggunakan copy() atau transform() dari pada generate_n().

Kelemahannya adalah bahwa logika untuk membangun nilai awal perlu dipindahkan ke kelas yang terpisah, yang kurang nyaman daripada memilikinya di tempat (meskipun lambdas di C ++ 1x membuat ini jauh lebih baik). Saya juga berharap ini masih tidak akan secepat malloc()versi non-STL, tetapi saya berharap itu akan dekat, karena hanya satu konstruksi untuk setiap elemen.


3
2017-09-08 02:58



Yang vektor juga disebut konstruktor Pixel.

Masing-masing menyebabkan hampir satu juta ctor berlari bahwa Anda menentukan waktu.

edit: lalu ada 1 ... 1000 loop luar, jadi buatlah satu miliar panggilan ctor!

sunting 2: menarik melihat pembongkaran untuk kasus UseArray. Pengoptimal dapat mengoptimalkan semuanya, karena tidak memiliki efek selain membakar CPU.


2
2017-09-08 02:53