Apakah std :: vector jauh lebih lambat daripada array biasa?

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

Inilah 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 vectorkomentar " mungkin lebih lambat untuk beberapa nanosec".

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? Atau apakah saya baru saja merusak mitos kinerja ini?

Saya menggunakan mode Rilis di Visual Studio 2005 .

Dalam Visual C ++ , #define _SECURE_SCL 0kurangi UseVectorsetengahnya (turun menjadi 4 detik). Ini sangat besar, IMO.

Menggunakan yang berikut ini:

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.

Tetapi setelah melihat kode secara lebih rinci ini diharapkan; saat Anda menjalankan melintasi vektor dua kali dan array hanya sekali. Catatan: saat Anda resize()vektor, Anda tidak hanya mengalokasikan memori tetapi juga menjalankan vektor dan memanggil konstruktor pada setiap anggota.

Menyusun ulang kode sedikit sehingga vektor hanya menginisialisasi setiap objek sekali:

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

Sekarang lakukan pengaturan 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 menginisialisasi dengan benar / Menghancurkan objek Pixel dalam UseArrray()metode karena konstruktor / destruktor tidak dipanggil (ini mungkin bukan masalah untuk kelas sederhana ini tetapi sesuatu yang sedikit lebih kompleks (yaitu dengan pointer atau anggota dengan pointer) akan menyebabkan masalah.

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

Optimalisasi 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 alih-alih malloc

Saya mencoba mengubah malloc()ke new[]dalam UseArray sehingga objek akan dibangun. Dan berubah dari penugasan bidang individual ke menetapkan contoh Pixel. Oh, dan mengganti nama variabel loop dalam 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 perubahan new[]yang akan membangun semua Pixel secara default. Tampaknya gcc dapat mengoptimalkan panggilan konstruktor default saat menggunakan new[], tetapi tidak saat menggunakan vector.

Ide # 2 - Hapus panggilan operator yang berulang]

Saya juga berusaha untuk menyingkirkan operator[]pencarian tiga dan cache referensi 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 pembangunan semua objek ketika vektor dibuat. Apa yang terjadi jika kami mengubah Pixel ke:

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

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

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

Ide # 4 - Gunakan iterator sebagai ganti loop index

Bagaimana kalau menggunakan vector<Pixel>::iteratorindeks loop bukan?

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 mengetahui cara membuat loop vektor secepat array satu, ini tidak berbicara dengan baik tentang perilaku default std::vector. Begitu banyak untuk kompiler menjadi cukup pintar untuk mengoptimalkan semua C ++ ness dan membuat wadah STL secepat array mentah.

Intinya adalah bahwa kompiler tidak dapat mengoptimalkan panggilan konstruktor default no-op saat 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 hadapan mantra di sekitar sini: "Kompiler lebih pintar daripada Anda. STL sama cepatnya seperti biasa C. Jangan khawatir tentang hal itu."

Ini adalah pertanyaan lama tetapi populer.

Pada titik ini, banyak programmer akan bekerja di C ++ 11. Dan dalam C ++ 11 kode OP seperti yang ditulis berjalan sama cepat untuk UseArrayatau UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

Masalah mendasar adalah bahwa sementara Pixelstruktur Anda tidak diinisialisasi, std::vector<T>::resize( size_t, T const&=T() )mengambil standar dibangun Pixeldan menyalinnya . Kompiler tidak menyadari bahwa ia diminta untuk menyalin data yang tidak diinisialisasi, sehingga ia benar-benar melakukan penyalinan.

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

(Dua kelebihan beban di mana ditambahkan untuk menangani jenis bergerak, dapat dibangun dan tidak dapat disalin - peningkatan kinerja ketika bekerja pada data yang tidak diinisialisasi adalah bonus).

The push_backsolusi juga melakukan pengecekan fencepost, yang memperlambat ke bawah, sehingga tetap lebih lambat dari mallocversi.

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 menambah buffer, Anda dapat melakukan ini dengan std::vectorpengalokasi khusus . Jika Anda ingin kemudian memindahkannya ke yang lebih normal std::vector, saya percaya penggunaan allocator_traitsdan pengesampingan yang hati-hati ==mungkin berhasil, tetapi tidak yakin.

Agar adil, Anda tidak dapat membandingkan implementasi C ++ dengan implementasi C, seperti yang saya sebut 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 menyerahkannya kepada pengacara bahasa).

Yang mengatakan, hanya mengubah malloc ke new Pixel[dimensions*dimensions]dan bebas untuk delete [] pixelstidak membuat banyak perbedaan dengan implementasi sederhana dari Pixel yang Anda miliki. Inilah hasil pada 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-inline untuk Pixel, std :: vector sekarang mengalahkan array mentah.

Akan terlihat bahwa kompleksitas alokasi melalui std :: vector dan std: dialokasikan terlalu banyak untuk dioptimalkan seefektif yang sederhana new Pixel[n]. Namun, kita dapat melihat bahwa masalahnya hanya dengan alokasi bukan akses vektor dengan mengubah beberapa fungsi tes untuk membuat vektor / array sekali dengan memindahkannya di luar loop:

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 dapat kita pelajari dari ini adalah std :: vector sebanding dengan array mentah untuk akses, tetapi jika Anda perlu membuat dan menghapus vektor / array berkali-kali, membuat objek yang kompleks akan lebih memakan waktu yang membuat array sederhana ketika konstruktor elemen tidak digarisbawahi. Saya tidak berpikir ini sangat mengejutkan.

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 yang hampir sama persis dengan array.

Masalahnya vectoradalah bahwa ini adalah alat yang jauh lebih umum daripada sebuah array. Dan itu berarti Anda harus mempertimbangkan bagaimana Anda menggunakannya. Ia dapat digunakan dalam banyak cara berbeda, menyediakan fungsionalitas yang bahkan tidak dimiliki array. Dan jika Anda menggunakannya "salah" untuk tujuan Anda, Anda mengalami banyak overhead, tetapi jika Anda menggunakannya dengan benar, biasanya pada dasarnya struktur data zero-overhead. Dalam kasus ini, masalahnya adalah Anda secara terpisah menginisialisasi vektor (menyebabkan semua elemen meminta ctor defaultnya), 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 sebabnya vektor menyediakan konstruktor yang memungkinkan Anda melakukan hal itu:NX.

Dan saat Anda menggunakannya, vektornya sama cepatnya dengan sebuah array.

Jadi tidak, Anda belum merusak 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, ini benar-benar penggunaan paling sederhana yang ternyata paling cepat. Jika Anda membandingkan potongan kode saya (satu baris) dengan jawaban John Kugelman, yang berisi tumpukan dan tumpukan penyesuaian dan optimisasi, yang masih belum cukup menghilangkan perbedaan kinerja, cukup jelas bahwa bagaimanapun vectorjuga dirancang dengan cerdik. Anda tidak harus melompat melewati lingkaran untuk mendapatkan kecepatan yang sama dengan array. Sebaliknya, Anda harus menggunakan solusi sesederhana mungkin.

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

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;
}

Pikiranku, bahwa dengan pengaturan ini, mereka harus 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 kerugian kinerja 30% ini bahkan terjadi? STL memiliki semua yang ada di header, sehingga seharusnya mungkin bagi kompiler untuk memahami semua yang diperlukan.

Pikiranku adalah bagaimana 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 copy constructor untuk menginisialisasi elemen dari objek yang dibangun secara default.

Ini berarti, bahwa urutan operasi pseudo berikut terjadi selama konstruksi vektor:

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

Yang, karena konstruktor salinan 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 default Pixeltetap un-dijalankan, sedangkan sisanya yang dijalankan dengan default Pixel's un-diinisialisasi 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 dibiarkan dengan nilai yang tidak diinisialisasi, dan tanpa iterasi ganda di atas urutan.

Berbekal informasi ini, bagaimana kita mengujinya? Mari kita coba menulis konstruktor salinan implisit secara berlebihan.

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 algoritma Anda .

Bagaimanapun, implementasi STL tidak lebih lambat untuk beberapa alasan yang tidak diketahui, ia hanya melakukan persis apa yang Anda minta; berharap kamu tahu lebih baik.

Coba nonaktifkan iterator yang dicentang dan bangun dalam mode rilis. Anda seharusnya tidak melihat banyak perbedaan kinerja.

STL (dan lain-lain) GNU, yang diberikan vector<T>(n), default membangun objek prototypal T()- kompiler akan mengoptimalkan konstruktor kosong - tetapi kemudian salinan sampah apa pun yang ada di alamat memori sekarang dicadangkan untuk objek diambil oleh STL __uninitialized_fill_n_aux, yang loop mengisi salinan objek itu sebagai nilai default dalam vektor. Jadi, "my" STL tidak membangun perulangan, tetapi membangun kemudian perulangan / penyalinan. Ini kontra intuitif, tetapi saya harus ingat ketika saya mengomentari pertanyaan stackoverflow baru-baru ini tentang hal ini: konstruk / salin bisa lebih efisien untuk referensi benda terhitung dll.

Begitu:

vector<T> x(n);

atau

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

adalah - pada banyak implementasi STL - sesuatu seperti:

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

Masalahnya adalah bahwa generasi pengoptimal kompiler saat ini tampaknya tidak bekerja dari wawasan bahwa temp adalah sampah yang tidak diinisialisasi, dan gagal untuk mengoptimalkan keluar loop dan permintaan copy constructor default. Anda dapat berargumen dengan meyakinkan bahwa kompiler sama sekali tidak boleh mengoptimalkan ini, karena seorang programmer yang menulis di atas memiliki harapan yang masuk akal bahwa semua objek akan identik setelah loop, bahkan jika sampah (peringatan biasa tentang 'identik' / operator == vs memcmp / operator = dll berlaku). Kompiler tidak dapat diharapkan memiliki wawasan tambahan ke dalam konteks yang lebih besar dari std :: vector <> atau penggunaan data yang lebih baru yang akan menyarankan pengoptimalan ini aman.

Ini dapat dikontraskan dengan implementasi langsung yang lebih jelas:

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

Yang mana kita dapat mengharapkan kompiler untuk mengoptimalkan.

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

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

Jelas itu perbedaan besar jika kita membuat 10.000 objek independen versus 10.000 referensi data yang sama. Ada argumen yang masuk akal bahwa keuntungan melindungi pengguna kasual C ++ dari melakukan sesuatu yang begitu mahal secara tidak sengaja melebihi biaya konstruksi penyalin yang sulit dioptimalkan.

JAWABAN ASLI (untuk referensi / memahami komentar): Tidak ada peluang. vektor secepat array, setidaknya jika Anda memesan ruang secara masuk akal. ...

Jawaban Martin York menggangguku karena sepertinya upaya untuk menyapu masalah inisialisasi di bawah karpet. Tapi dia benar untuk mengidentifikasi konstruksi default yang berlebihan sebagai sumber masalah kinerja.

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

Untuk masalah langsung yang ada, Anda tentu bisa memanggil versi 2-parameter vector<Pixel>ctor 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 menginisialisasi secara efisien dengan sesuatu yang lebih rumit daripada nilai konstan?

Untuk ini, Anda dapat menggunakan a back_insert_iterator, yang merupakan adaptor iterator. Berikut ini adalah contoh dengan vektor ints, meskipun ide umum berfungsi 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()bukannya generate_n().

The downside 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 tidak akan secepat versi malloc()non-STL yang berbasis, tetapi saya berharap ini akan menjadi dekat, karena hanya melakukan satu konstruksi untuk setiap elemen.

Yang vektor juga memanggil konstruktor Pixel.

Masing-masing menyebabkan hampir satu juta ctor berjalan sesuai waktu Anda.

sunting: lalu ada bagian luar 1 ... 1000 loop, jadi buat satu miliar ctor memanggil!

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

Inilah cara kerja push_backmetode dalam vektor:

1. Vektor mengalokasikan jumlah ruang X ketika diinisialisasi.
2. Sebagaimana dinyatakan di bawah ini memeriksa apakah ada ruang dalam array yang mendasari saat ini untuk item.
3. Itu membuat salinan item dalam panggilan push_back.

Setelah memanggil push_backitem X:

3. Vektor merealokasi jumlah kX ruang menjadi array ke-2.
4. Ini Menyalin entri dari array pertama ke array kedua.
5. Buang array pertama.
6. Sekarang menggunakan array kedua sebagai penyimpanan sampai mencapai entri kX.

Ulang. Jika Anda tidak reservingruang pasti akan lebih lambat. Lebih dari itu, jika itu mahal untuk menyalin item maka 'push_back' seperti itu akan memakanmu hidup-hidup.

Mengenai hal vectorversus array, saya harus setuju dengan orang lain. Jalankan dalam rilis, nyalakan optimisasi, dan pasang beberapa flag lagi sehingga orang-orang yang ramah di Microsoft tidak # @% $ ^ untuk Anda.

Satu hal lagi, jika Anda tidak perlu mengubah ukuran, gunakan Boost.Array.

Beberapa data profiler (piksel sejajar dengan 32 bit):

g++ -msse3 -O3 -ftree-vectorize -g test.cpp -DNDEBUG && ./a.out
UseVector completed in 3.123 seconds
UseArray completed in 1.847 seconds
UseVectorPushBack completed in 9.186 seconds
The whole thing completed in 14.159 seconds

Blah

andrey@nv:~$ opannotate --source libcchem/src/a.out  | grep "Total samples for file" -A3
Overflow stats not available
 * Total samples for file : "/usr/include/c++/4.4/ext/new_allocator.h"
 *
 * 141008 52.5367
 */
--
 * Total samples for file : "/home/andrey/libcchem/src/test.cpp"
 *
 *  61556 22.9345
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_vector.h"
 *
 *  41956 15.6320
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_uninitialized.h"
 *
 *  20956  7.8078
 */
--
 * Total samples for file : "/usr/include/c++/4.4/bits/stl_construct.h"
 *
 *   2923  1.0891
 */

Dalam allocator:

               :      // _GLIBCXX_RESOLVE_LIB_DEFECTS
               :      // 402. wrong new expression in [some_] allocator::construct
               :      void
               :      construct(pointer __p, const _Tp& __val)
141008 52.5367 :      { ::new((void *)__p) _Tp(__val); }

vector:

               :void UseVector()
               :{ /* UseVector() total:  60121 22.3999 */
...
               :
               :
 10790  4.0201 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
   495  0.1844 :            pixels[i].r = 255;
               :
 12618  4.7012 :            pixels[i].g = 0;
               :
  2253  0.8394 :            pixels[i].b = 0;
               :
               :        }

Himpunan

               :void UseArray()
               :{ /* UseArray() total:  35191 13.1114 */
               :
...
               :
   136  0.0507 :        for (int i = 0; i < dimension * dimension; ++i) {
               :
  9897  3.6874 :            pixels[i].r = 255;
               :
  3511  1.3081 :            pixels[i].g = 0;
               :
 21647  8.0652 :            pixels[i].b = 0;

Sebagian besar overhead ada di copy constructor. Sebagai contoh,

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

    pixels.reserve(dimension * dimension);

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

        pixels[i].r = 255;

        pixels[i].g = 0;

        pixels[i].b = 0;
    }

Ini memiliki kinerja yang sama dengan sebuah array.

Laptop saya adalah Lenova G770 (RAM 4 GB).

OS adalah Windows 7 64-bit (yang dengan laptop)

Kompiler adalah MinGW 4.6.1.

IDE-nya adalah Code :: Blocks .

Saya menguji kode sumber posting pertama.

Hasil

Pengoptimalan O2

UseArray selesai dalam 2,841 detik

UseVector selesai dalam 2,548 detik

UseVectorPushBack selesai dalam 11,95 detik

Semuanya selesai dalam 17,322 detik

jeda sistem

Pengoptimalan O3

UseArray selesai dalam 1,452 detik

UseVector selesai dalam 2,514 detik

UseVectorPushBack selesai dalam 12.967 detik

Semuanya selesai dalam 16.937 detik

Sepertinya kinerja vektor lebih buruk di bawah optimasi O3.

Jika Anda mengubah loop ke

    pixels[i].r = i;
    pixels[i].g = i;
    pixels[i].b = i;

Kecepatan array dan vektor di bawah O2 dan O3 hampir sama.

Tolok ukur yang lebih baik (saya pikir ...), kompiler karena optimasi dapat mengubah kode, karena hasil dari vektor / array yang dialokasikan tidak digunakan di mana pun. Hasil:

$ g++ test.cpp -o test -O3 -march=native
$ ./test 
UseArray inner completed in 0.652 seconds
UseArray completed in 0.773 seconds
UseVector inner completed in 0.638 seconds
UseVector completed in 0.757 seconds
UseVectorPushBack inner completed in 6.732 seconds
UseVectorPush completed in 6.856 seconds
The whole thing completed in 8.387 seconds

Penyusun:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

CPU:

model name  : Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz

Dan kodenya:

#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(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVector inner");

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

        std::vector<Pixel>& pixels = results.at(i);
        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(std::vector<std::vector<Pixel> >& results)
{
    TestTimer t("UseVectorPushBack inner");

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

        std::vector<Pixel>& pixels = results.at(i);
            pixels.reserve(dimension * dimension);

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

void UseArray(Pixel** results)
{
    TestTimer t("UseArray inner");

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

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

        results[i] = pixels;

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

        // free(pixels);
    }
}

void UseArray()
{
    TestTimer t("UseArray");
    Pixel** array = (Pixel**)malloc(sizeof(Pixel*)* 1000);
    UseArray(array);
    for(int i=0;i<1000;++i)
        free(array[i]);
    free(array);
}

void UseVector()
{
    TestTimer t("UseVector");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVector(vector);
    }
}

void UseVectorPushBack()
{
    TestTimer t("UseVectorPush");
    {
        std::vector<std::vector<Pixel> > vector(1000, std::vector<Pixel>());
        UseVectorPushBack(vector);
    }
}


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

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

    return 0;
}

Saya melakukan beberapa tes ekstensif yang saya inginkan untuk sementara waktu sekarang. Mungkin juga bagikan ini.

Ini adalah mesin dual boot saya i7-3770, Ram 16GB, x86_64, pada Windows 8.1 dan Ubuntu 16.04. Informasi dan kesimpulan lebih lanjut, komentar di bawah. Diuji baik MSVS 2017 dan g ++ (baik pada Windows dan Linux).

Program Tes

#include <iostream>
#include <chrono>
//#include <algorithm>
#include <array>
#include <locale>
#include <vector>
#include <queue>
#include <deque>

// Note: total size of array must not exceed 0x7fffffff B = 2,147,483,647B
//  which means that largest int array size is 536,870,911
// Also image size cannot be larger than 80,000,000B
constexpr int long g_size = 100000;
int g_A[g_size];


int main()
{
    std::locale loc("");
    std::cout.imbue(loc);
    constexpr int long size = 100000;  // largest array stack size

    // stack allocated c array
    std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
    int A[size];
    for (int i = 0; i < size; i++)
        A[i] = i;

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style stack array size=" << sizeof(A) << "B\n\n";

    // global stack c array
    start = std::chrono::steady_clock::now();
    for (int i = 0; i < g_size; i++)
        g_A[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "global c-style stack array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "global c-style stack array size=" << sizeof(g_A) << "B\n\n";

    // raw c array heap array
    start = std::chrono::steady_clock::now();
    int* AA = new int[size];    // bad_alloc() if it goes higher than 1,000,000,000
    for (int i = 0; i < size; i++)
        AA[i] = i;

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "c-style heap array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "c-style heap array size=" << sizeof(AA) << "B\n\n";
    delete[] AA;

    // std::array<>
    start = std::chrono::steady_clock::now();
    std::array<int, size> AAA;
    for (int i = 0; i < size; i++)
        AAA[i] = i;
    //std::sort(AAA.begin(), AAA.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::array duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::array size=" << sizeof(AAA) << "B\n\n";

    // std::vector<>
    start = std::chrono::steady_clock::now();
    std::vector<int> v;
    for (int i = 0; i < size; i++)
        v.push_back(i);
    //std::sort(v.begin(), v.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::vector duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::vector size=" << v.size() * sizeof(v.back()) << "B\n\n";

    // std::deque<>
    start = std::chrono::steady_clock::now();
    std::deque<int> dq;
    for (int i = 0; i < size; i++)
        dq.push_back(i);
    //std::sort(dq.begin(), dq.end());

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::deque duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::deque size=" << dq.size() * sizeof(dq.back()) << "B\n\n";

    // std::queue<>
    start = std::chrono::steady_clock::now();
    std::queue<int> q;
    for (int i = 0; i < size; i++)
        q.push(i);

    duration = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count();
    std::cout << "std::queue duration=" << duration / 1000.0 << "ms\n";
    std::cout << "std::queue size=" << q.size() * sizeof(q.front()) << "B\n\n";
}

Hasil

//////////////////////////////////////////////////////////////////////////////////////////
// with MSVS 2017:
// >> cl /std:c++14 /Wall -O2 array_bench.cpp
//
// c-style stack array duration=0.15ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.130ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.90ms
// c-style heap array size=4B
//
// std::array duration=0.20ms
// std::array size=400,000B
//
// std::vector duration=0.544ms
// std::vector size=400,000B
//
// std::deque duration=1.375ms
// std::deque size=400,000B
//
// std::queue duration=1.491ms
// std::queue size=400,000B
//
//////////////////////////////////////////////////////////////////////////////////////////
//
// with g++ version:
//      - (tdm64-1) 5.1.0 on Windows
//      - (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609 on Ubuntu 16.04
// >> g++ -std=c++14 -Wall -march=native -O2 array_bench.cpp -o array_bench
//
// c-style stack array duration=0ms
// c-style stack array size=400,000B
//
// global c-style stack array duration=0.124ms
// global c-style stack array size=400,000B
//
// c-style heap array duration=0.648ms
// c-style heap array size=8B
//
// std::array duration=1ms
// std::array size=400,000B
//
// std::vector duration=0.402ms
// std::vector size=400,000B
//
// std::deque duration=0.234ms
// std::deque size=400,000B
//
// std::queue duration=0.304ms
// std::queue size=400,000
//
//////////////////////////////////////////////////////////////////////////////////////////

Catatan

• Dirakit dengan rata-rata 10 kali proses.
• Saya awalnya melakukan tes dengan std::sort()terlalu (Anda bisa melihatnya berkomentar) tetapi dihapus kemudian karena tidak ada perbedaan relatif yang signifikan.

Kesimpulan dan Ucapan Saya

• perhatikan bagaimana global c-style array memakan waktu hampir sama dengan heap c-style array
• Dari semua pengujian saya perhatikan stabilitas yang luar biasa dalam std::arrayvariasi waktu antara berjalan berturut-turut, sementara yang lain terutama std :: data structs sangat bervariasi dibandingkan
• Pengoptimalan O3 tidak menunjukkan perbedaan waktu yang penting
• Menghapus optimasi pada Windows cl (no -O2) dan pada g ++ (Win / Linux no -O2, no -march = asli) meningkatkan waktu secara SIGNIFIKAN. Khusus untuk std :: data structs. Keseluruhan waktu yang lebih tinggi pada MSVS daripada g ++, tetapi std::arraydan c-style array lebih cepat pada Windows tanpa optimasi
• g ++ menghasilkan kode lebih cepat dari kompiler microsoft (tampaknya itu berjalan lebih cepat bahkan pada Windows).

Putusan

Tentu saja ini adalah kode untuk bangunan yang dioptimalkan. Dan karena pertanyaannya adalah tentang std::vectorya itu banyak! lebih lambat dari array biasa (dioptimalkan / tidak dioptimalkan). Tetapi ketika Anda melakukan benchmark, Anda tentu ingin menghasilkan kode yang dioptimalkan.

Bintang pertunjukan bagi saya telah std::array.

Dengan opsi yang tepat, vektor dan array dapat menghasilkan asm identik . Dalam kasus ini, tentu saja mereka memiliki kecepatan yang sama, karena Anda juga mendapatkan file yang dapat dieksekusi yang sama.

By the way memperlambat Anda melihat di kelas menggunakan vektor juga terjadi dengan tipe standar seperti int. Inilah kode multithreaded:

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <typeinfo>
#include <vector>
#include <pthread.h>
#include <sstream>
#include <fstream>
using namespace std;

//pthread_mutex_t map_mutex=PTHREAD_MUTEX_INITIALIZER;

long long num=500000000;
int procs=1;

struct iterate
{
    int id;
    int num;
    void * member;
    iterate(int a, int b, void *c) : id(a), num(b), member(c) {}
};

//fill out viterate and piterate
void * viterate(void * input)
{
    printf("am in viterate\n");
    iterate * info=static_cast<iterate *> (input);
    // reproduce member type
    vector<int> test= *static_cast<vector<int>*> (info->member);
    for (int i=info->id; i<test.size(); i+=info->num)
    {
        //printf("am in viterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

void * piterate(void * input)
{
    printf("am in piterate\n");
    iterate * info=static_cast<iterate *> (input);;
    int * test=static_cast<int *> (info->member);
    for (int i=info->id; i<num; i+=info->num) {
        //printf("am in piterate loop\n");
        test[i];
    }
    pthread_exit(NULL);
}

int main()
{
    cout<<"producing vector of size "<<num<<endl;
    vector<int> vtest(num);
    cout<<"produced  a vector of size "<<vtest.size()<<endl;
    pthread_t thread[procs];

    iterate** it=new iterate*[procs];
    int ans;
    void *status;

    cout<<"begining to thread through the vector\n";
    for (int i=0; i<procs; i++) {
        it[i]=new iterate(i, procs, (void *) &vtest);
    //  ans=pthread_create(&thread[i],NULL,viterate, (void *) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the vector";
    //reuse the iterate structures

    cout<<"producing a pointer with size "<<num<<endl;
    int * pint=new int[num];
    cout<<"produced a pointer with size "<<num<<endl;

    cout<<"begining to thread through the pointer\n";
    for (int i=0; i<procs; i++) {
        it[i]->member=&pint;
        ans=pthread_create(&thread[i], NULL, piterate, (void*) it[i]);
    }
    for (int i=0; i<procs; i++) {
        pthread_join(thread[i], &status);
    }
    cout<<"end of threading through the pointer\n";

    //delete structure array for iterate
    for (int i=0; i<procs; i++) {
        delete it[i];
    }
    delete [] it;

    //delete pointer
    delete [] pint;

    cout<<"end of the program"<<endl;
    return 0;
}

Perilaku dari kode menunjukkan instantiation vektor adalah bagian terpanjang dari kode. Setelah Anda melewati leher botol itu. Sisa kode berjalan sangat cepat. Ini benar, tidak peduli berapa banyak utas yang Anda jalankan.

By the way mengabaikan jumlah benar-benar gila termasuk. Saya telah menggunakan kode ini untuk menguji berbagai hal untuk suatu proyek sehingga jumlah termasuk terus bertambah.

Saya hanya ingin menyebutkan bahwa vektor (dan smart_ptr) hanyalah lapisan tipis yang ditambahkan di atas array mentah (dan pointer mentah). Dan sebenarnya waktu akses vektor dalam memori terus menerus lebih cepat daripada array. Kode berikut menunjukkan hasil inisialisasi dan akses vektor dan array.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <iostream>
#include <vector>
#define SIZE 20000
int main() {
    srand (time(NULL));
    vector<vector<int>> vector2d;
    vector2d.reserve(SIZE);
    int index(0);
    boost::posix_time::ptime start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        vector2d.push_back(vector<int>(SIZE));
    }
    boost::posix_time::ptime start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            vector2d[index][index]++;
        }
    }
    boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time();
    boost::posix_time::time_duration msdiff = end - start_total;
    cout << "Vector total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Vector access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 


    int index(0);
    int** raw2d = nullptr;
    raw2d = new int*[SIZE];
    start_total = boost::posix_time::microsec_clock::local_time();
    //  timer start - build + access
    for (int i = 0; i < SIZE; i++) {
        raw2d[i] = new int[SIZE];
    }
    start_access = boost::posix_time::microsec_clock::local_time();
    //  timer start - access
    for (int i = 0; i < SIZE; i++) {
        index = rand()%SIZE;
        for (int j = 0; j < SIZE; j++) {

            raw2d[index][index]++;
        }
    }
    end = boost::posix_time::microsec_clock::local_time();
    msdiff = end - start_total;
    cout << "Array total time: " << msdiff.total_milliseconds() << "milliseconds.\n";
    msdiff = end - start_acess;
    cout << "Array access time: " << msdiff.total_milliseconds() << "milliseconds.\n"; 
    for (int i = 0; i < SIZE; i++) {
        delete [] raw2d[i];
    }
    return 0;
}

Outputnya adalah:

    Vector total time: 925milliseconds.
    Vector access time: 4milliseconds.
    Array total time: 30milliseconds.
    Array access time: 21milliseconds.

Jadi kecepatannya akan hampir sama jika Anda menggunakannya dengan benar. (seperti yang disebutkan orang lain menggunakan cadangan () atau mengubah ukuran ()).

Nah, karena vector :: resize () melakukan lebih banyak pemrosesan daripada alokasi memori biasa (oleh malloc).

Cobalah untuk meletakkan breakpoint di copy constructor Anda (tentukan sehingga Anda dapat breakpoint!) Dan sekarang ada tambahan waktu pemrosesan.

Saya harus mengatakan bahwa saya bukan ahli dalam C ++. Tetapi untuk menambahkan beberapa hasil percobaan:

kompilasi: gcc-6.2.0 / bin / g ++ -O3 -std = c ++ 14 vector.cpp

mesin:

Intel(R) Xeon(R) CPU E5-2690 v2 @ 3.00GHz 

OS:

2.6.32-642.13.1.el6.x86_64

Keluaran:

UseArray completed in 0.167821 seconds
UseVector completed in 0.134402 seconds
UseConstructor completed in 0.134806 seconds
UseFillConstructor completed in 1.00279 seconds
UseVectorPushBack completed in 6.6887 seconds
The whole thing completed in 8.12888 seconds

Di sini satu-satunya hal yang saya rasa aneh adalah kinerja "UseFillConstructor" dibandingkan dengan "UseConstructor".

Kode:

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

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

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


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

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

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

Jadi "nilai" tambahan yang disediakan memperlambat kinerja cukup banyak, yang saya pikir disebabkan oleh beberapa panggilan untuk menyalin konstruktor. Tapi...

Menyusun:

gcc-6.2.0/bin/g++ -std=c++14 -O vector.cpp

Keluaran:

UseArray completed in 1.02464 seconds
UseVector completed in 1.31056 seconds
UseConstructor completed in 1.47413 seconds
UseFillConstructor completed in 1.01555 seconds
UseVectorPushBack completed in 6.9597 seconds
The whole thing completed in 11.7851 seconds

Jadi dalam hal ini, optimasi gcc sangat penting tetapi tidak banyak membantu Anda ketika nilai diberikan sebagai default. Ini, sebenarnya bertentangan dengan biaya kuliah saya. Semoga ini membantu programmer baru ketika memilih format inisialisasi vektor mana.

Tampaknya bergantung pada flag-flag compiler. Berikut ini adalah kode benchmark:

#include <chrono>
#include <cmath>
#include <ctime>
#include <iostream>
#include <vector>


int main(){

    int size = 1000000; // reduce this number in case your program crashes
    int L = 10;

    std::cout << "size=" << size << " L=" << L << std::endl;
    {
        srand( time(0) );
        double * data = new double[size];
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C style heap array:    " << duration << "ms\n";
        delete data;
    }

    {
        srand( 1 + time(0) );
        double data[size]; // technically, non-compliant with C++ standard.
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of C99 style stack array: " << duration << "ms\n";
    }

    {
        srand( 2 + time(0) );
        std::vector<double> data( size );
        double result = 0.;
        std::chrono::steady_clock::time_point start = std::chrono::steady_clock::now();
        for( int l = 0; l < L; l++ ) {
            for( int i = 0; i < size; i++ ) data[i] = rand() % 100;
            for( int i = 0; i < size; i++ ) result += data[i] * data[i];
        }
        std::chrono::steady_clock::time_point end   = std::chrono::steady_clock::now();
        auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
        std::cout << "Calculation result is " << sqrt(result) << "\n";
        std::cout << "Duration of std::vector array:     " << duration << "ms\n";
    }

    return 0;
}

Bendera pengoptimalan yang berbeda memberikan jawaban berbeda:

$ g++ -O0 benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181182
Duration of C style heap array:    118441ms
Calculation result is 181240
Duration of C99 style stack array: 104920ms
Calculation result is 181210
Duration of std::vector array:     124477ms
$g++ -O3 benchmark.cpp
$ ./a.out 
size=1000000 L=10
Calculation result is 181213
Duration of C style heap array:    107803ms
Calculation result is 181198
Duration of C99 style stack array: 87247ms
Calculation result is 181204
Duration of std::vector array:     89083ms
$ g++ -Ofast benchmark.cpp 
$ ./a.out 
size=1000000 L=10
Calculation result is 181164
Duration of C style heap array:    93530ms
Calculation result is 181179
Duration of C99 style stack array: 80620ms
Calculation result is 181191
Duration of std::vector array:     78830ms

Hasil pasti Anda akan bervariasi tetapi ini cukup khas pada mesin saya.

Dalam pengalaman saya, kadang-kadang, hanya kadang-kadang, vector<int>bisa berkali-kali lebih lambat daripada int[]. Satu hal yang perlu diingat adalah bahwa vektor vektor sangat berbeda int[][]. Sebagai elemen mungkin tidak berdekatan dalam memori. Ini berarti Anda dapat mengubah ukuran vektor yang berbeda di dalam yang utama, tetapi CPU mungkin tidak dapat men-cache elemen serta dalam kasus int[][].