Czy std :: vector jest o wiele wolniejszy niż zwykłe tablice?

Zawsze myślałem, że to ogólna mądrość std::vector„zaimplementowana jako tablica”, bla bla bla. Dzisiaj zszedłem na dół i przetestowałem go, i wydaje się, że tak nie jest:

Oto kilka wyników testu:

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

To około 3 - 4 razy wolniej! Naprawdę nie usprawiedliwia to vectorkomentarzy „ może być wolniejsze dla kilku nanosektów”.

I użyłem kodu:

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

Czy robię to źle czy coś? A może po prostu rozwaliłem ten mit o wydajności?

Używam trybu Release w Visual Studio 2005 .

W Visual C ++ , #define _SECURE_SCL 0zmniejsza UseVectorsię o połowę (doprowadzenia do 4 sekund). To naprawdę ogromne, IMO.

Wykorzystując następujące:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseArray ukończony w 2.196 sekund
UseVector zakończony w
4.412 sekund UseVectorPushBack ukończony w 8.017 sekund
Cała rzecz ukończona w 14.626 sekund

Tak więc tablica jest dwa razy szybsza niż wektor.

Ale po szczegółowym spojrzeniu na kod jest to oczekiwane; gdy dwa razy biegniesz przez wektor, a tablicę tylko raz. Uwaga: gdy jesteś resize()wektorem, nie tylko alokujesz pamięć, ale również biegniesz przez wektor i wywołujesz konstruktor na każdym elemencie.

Lekkie ponowne uporządkowanie kodu, aby wektor inicjował każdy obiekt tylko raz:

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

Teraz znów wykonuj ten sam czas:

g ++ -O3 Time.cpp -I <MyBoost>
./a.out
UseVector ukończony w 2.216 sekund

Wydajność wektora jest teraz tylko nieco gorsza niż macierz. IMO ta różnica jest nieznaczna i może być spowodowana całą masą rzeczy niezwiązanych z testem.

Chciałbym również wziąć pod uwagę, że nie inicjujesz poprawnie / niszczymy obiektu Pixel w UseArrray()metodzie, ponieważ żaden konstruktor / destruktor nie jest wywoływany (może to nie być problem dla tej prostej klasy, ale coś nieco bardziej złożonego (tj. Ze wskaźnikami lub elementami) ze wskaźnikami) spowoduje problemy.

Świetne pytanie. Przyszedłem tutaj, oczekując prostej poprawki, która przyspieszyłaby testy wektorowe. To nie zadziałało tak, jak się spodziewałem!

Optymalizacja pomaga, ale to nie wystarczy. Przy włączonej optymalizacji wciąż widzę 2-krotną różnicę wydajności między UseArray i UseVector. Co ciekawe, UseVector był znacznie wolniejszy niż UseVectorPushBack bez optymalizacji.

# 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

Pomysł nr 1 - Użyj nowego [] zamiast malloc

Próbowałem zmienić malloc()na new[]UseArray, aby obiekty mogły zostać skonstruowane. I przejście z indywidualnego przypisania pola do przypisania instancji Pixel. Aha, i zmiana nazwy zmiennej pętli wewnętrznej na 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;
    }
}

Zaskakujące (dla mnie), żadna z tych zmian nie zrobiła żadnej różnicy. Nawet zmiana, new[]która domyślnie skonstruuje wszystkie piksele. Wygląda na to, że gcc może zoptymalizować domyślne wywołania konstruktora podczas używania new[], ale nie podczas używania vector.

Pomysł nr 2 - Usuwanie powtarzających się połączeń operatora []

Próbowałem także pozbyć się potrójnego operator[]wyszukiwania i buforować odniesienie do pixels[j]. To faktycznie spowolniło 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

Pomysł # 3 - Usuń konstruktory

A co z całkowitym usunięciem konstruktorów? Być może wtedy gcc może zoptymalizować konstrukcję wszystkich obiektów podczas tworzenia wektorów. Co się stanie, jeśli zmienimy Pixel na:

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

Wynik: około 10% szybciej. Wciąż wolniejszy niż tablica. Hm

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

Pomysł 4 - Użyj iteratora zamiast indeksu pętli

A może vector<Pixel>::iteratorzamiast indeksu pętli?

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

Wynik:

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

Nie, nie inaczej. Przynajmniej nie jest wolniejszy. Myślałem, że będzie to miało wydajność podobną do # 2, w której użyłem Pixel&odniesienia.

Wniosek

Nawet jeśli niektóre inteligentne pliki cookie dowiedzą się, jak zrobić pętlę wektorową tak szybko jak tablica, nie mówi to dobrze o domyślnym zachowaniu std::vector . Tyle, że kompilator jest wystarczająco inteligentny, aby zoptymalizować całą C ++ i sprawić, że kontenery STL są tak szybkie, jak surowe tablice.

Najważniejsze jest to, że kompilator nie jest w stanie zoptymalizować domyślnych wywołań konstruktora, gdy nie można go użyć std::vector. Jeśli używasz zwykłego new[], optymalizuje je w porządku. Ale nie z std::vector. Nawet jeśli możesz przepisać kod, aby wyeliminować wywołania konstruktora, które lecą w pobliżu mantry: „Kompilator jest mądrzejszy od ciebie. STL jest tak samo szybki jak zwykły C. Nie martw się o to”.

To stare, ale popularne pytanie.

W tym momencie wielu programistów będzie pracować w C ++ 11. A w C ++ 11 zapisany kod OP działa równie szybko dla UseArraylub UseVector.

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

Podstawowym problemem było to, że podczas gdy Twoja Pixelstruktura nie była zainicjalizowana, std::vector<T>::resize( size_t, T const&=T() )pobiera domyślną konstrukt Pixeli kopiuje ją . Kompilator nie zauważył, że został poproszony o skopiowanie niezainicjowanych danych, więc faktycznie wykonał kopię.

W C ++ 11 std::vector<T>::resizema dwa przeciążenia. Pierwsza to std::vector<T>::resize(size_t)druga std::vector<T>::resize(size_t, T const&). Oznacza to, że gdy wywołujesz resizebez drugiego argumentu, to po prostu domyślna konstrukcja, a kompilator jest wystarczająco inteligentny, aby zdać sobie sprawę, że domyślna konstrukcja nic nie robi, więc pomija przejście przez bufor.

(Dwa przeciążenia zostały dodane w celu obsługi typów ruchomych, możliwych do zbudowania i niemożliwych do skopiowania - poprawa wydajności podczas pracy z niezainicjowanymi danymi jest zaletą).

push_backRozwiązanie ma również Fencepost kontrolnych, które spowalnia go, więc pozostaje wolniejszy od mallocwersji.

przykład na żywo (zastąpiłem również timer chrono::high_resolution_clock).

Pamiętaj, że jeśli masz strukturę, która zwykle wymaga inicjalizacji, ale chcesz obsłużyć ją po zwiększeniu bufora, możesz to zrobić za pomocą niestandardowego programu std::vectorprzydzielającego. Jeśli chcesz zmienić go na bardziej normalny std::vector, uważam, że ostrożne użycie allocator_traitsi zastąpienie ==może to spowodować, ale nie jestem pewien.

Szczerze mówiąc, nie można porównywać implementacji C ++ z implementacją C, jak nazwałbym twoją wersję malloc. malloc nie tworzy obiektów - przydziela tylko surową pamięć. To, że następnie traktujesz tę pamięć jako obiekty bez wywoływania konstruktora, to słabe C ++ (być może nieprawidłowe - zostawię to prawnikom językowym).

To powiedziawszy, po prostu zmiana malloc na new Pixel[dimensions*dimensions]i free delete [] pixelsto nie robi dużej różnicy z prostą implementacją Pixela, którą masz. Oto wyniki na moim urządzeniu (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

Ale z niewielką zmianą tabele zmieniają się:

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]

Opracowano w ten sposób:

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

otrzymujemy bardzo różne wyniki:

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

Z nie wbudowanym konstruktorem Pixela, std :: vector bije teraz surową tablicę.

Wydaje się, że złożoność alokacji poprzez std :: vector i std: alokator jest zbyt duża, aby ją zoptymalizować równie skutecznie jak prostą new Pixel[n]. Widzimy jednak, że problemem jest po prostu alokacja, a nie dostęp do wektora, poprzez dostosowanie kilku funkcji testowych w celu utworzenia wektora / tablicy raz poprzez przeniesienie go poza pętlę:

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

i

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

Otrzymujemy teraz te wyniki:

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

Możemy się z tego nauczyć, że std :: vector jest porównywalny z surową tablicą w celu uzyskania dostępu, ale jeśli trzeba wiele razy tworzyć i usuwać wektor / tablicę, tworzenie obiektu złożonego będzie bardziej czasochłonne niż tworzenie prostej tablicy gdy konstruktor elementu nie jest wstawiony. Nie sądzę, żeby to było bardzo zaskakujące.

Spróbuj tego:

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

Dostaję prawie dokładnie taką samą wydajność jak w przypadku macierzy.

Chodzi o vectorto, że jest to znacznie bardziej ogólne narzędzie niż tablica. A to oznacza, że ​​musisz rozważyć, w jaki sposób niego korzystać. Można go używać na wiele różnych sposobów, zapewniając funkcjonalność, której tablica nawet nie ma. A jeśli użyjesz go „niewłaściwie” do swoich celów, poniesiesz dużo narzutu, ale jeśli użyjesz go poprawnie, zwykle jest to w zasadzie struktura danych zerowych narzutów. W takim przypadku problem polega na tym, że oddzielnie zainicjowałeś wektor (powodując wywołanie domyślnego ctor wszystkich elementów), a następnie nadpisałeś każdy element osobno prawidłową wartością. Jest to o wiele trudniejsze dla kompilatora do optymalizacji, niż gdy robisz to samo z tablicą. Właśnie dlatego wektor zapewnia konstruktor, który pozwala zrobić dokładnie to: .NX

A kiedy go użyjesz, wektor jest tak samo szybki jak tablica.

Więc nie, nie zniszczyłeś mitu o wydajności. Ale pokazałeś, że jest to prawdą tylko wtedy, gdy używasz wektora optymalnie, co również jest całkiem dobrym punktem. :)

Z drugiej strony, to naprawdę najprostsze użycie, które okazuje się najszybsze. Jeśli porównasz mój fragment kodu (pojedynczą linię) z odpowiedzią Johna Kugelmana, zawierającą stosy ulepszeń i optymalizacji, które wciąż nie do końca eliminują różnicę wydajności, jest całkiem jasne, że vectorjest całkiem sprytnie zaprojektowany. Nie musisz skakać przez obręcze, aby uzyskać prędkość równą tablicy. Przeciwnie, musisz użyć najprostszego możliwego rozwiązania.

To nie było uczciwe porównanie, kiedy po raz pierwszy spojrzałem na twój kod; Zdecydowanie myślałem, że nie porównujesz jabłek z jabłkami. Pomyślałem więc: wywołajmy konstruktory i destruktory wywoływane we wszystkich testach; a następnie porównaj.

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

Myślałem, że przy takim ustawieniu powinny być dokładnie takie same. Okazuje się, że się myliłem.

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

Dlaczego więc w ogóle spadła ta 30% wydajność? STL ma wszystko w nagłówkach, więc kompilator powinien mieć możliwość zrozumienia wszystkiego, co było wymagane.

Myślałem, że to w ten sposób pętla inicjuje wszystkie wartości do domyślnego konstruktora. Więc wykonałem test:

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

Wyniki były takie, jak podejrzewałem:

Default Constructed: 1
Copy Constructed: 300

Jest to oczywiście źródło spowolnienia, fakt, że wektor używa konstruktora kopiowania do inicjowania elementów z domyślnie zbudowanego obiektu.

Oznacza to, że podczas budowy wektora zachodzi następująca kolejność pseudooperacji:

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

Który, ze względu na niejawny konstruktor kopii wykonany przez kompilator, jest rozszerzony do następujących elementów:

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

Tak więc domyślna Pixelpozostaje niezainicjalizowana, podczas gdy pozostałe są inicjalizowane z domyślnym Pixel„s un-zainicjowane wartościami.

W porównaniu do alternatywnej sytuacji z 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

Wszystkie są pozostawione niezainicjowanym wartościom i bez podwójnej iteracji w sekwencji.

Uzbrojeni w te informacje, w jaki sposób możemy to przetestować? Spróbujmy nadpisać niejawny konstruktor kopii.

Pixel(const Pixel&) {}

A wyniki?

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

Podsumowując, jeśli robisz setki wektorów bardzo często: przemyśl swój algorytm .

W każdym razie implementacja STL nie jest wolniejsza z nieznanego powodu, robi dokładnie to, o co prosisz; mając nadzieję, że wiesz lepiej.

Spróbuj wyłączyć sprawdzone iteratory i budować w trybie zwolnienia. Nie powinieneś widzieć dużej różnicy w wydajności.

Biorąc pod uwagę vector<T>(n), że STL GNU (i inne) domyślnie konstruuje obiekt prototypowy T()- kompilator zoptymalizuje pustego konstruktora - ale następnie kopia wszelkiego śmieci, które zdarzyły się w adresach pamięci zarezerwowanych teraz dla obiektu, jest pobierana przez STL __uninitialized_fill_n_aux, które zapętla zapełniające się kopie tego obiektu jako wartości domyślne w wektorze. Tak więc „mój” STL nie tworzy pętli, lecz konstruuje następnie pętlę / kopiowanie. Jest to sprzeczne z intuicją, ale powinienem pamiętać, gdy skomentowałem ostatnie pytanie dotyczące przepełnienia stosu na ten temat: konstrukcja / kopia może być bardziej wydajna dla obiektów zliczanych według odniesienia itp.

Więc:

vector<T> x(n);

lub

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

jest - w wielu implementacjach STL - coś takiego:

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

Problem polega na tym, że obecna generacja optymalizatorów kompilatora nie wydaje się działać z wglądu, że temp jest niezainicjowanym śmieciem, i nie optymalizuje pętli i domyślnych wywołań konstruktora kopii. Można rzetelnie argumentować, że kompilatory absolutnie nie powinny tego optymalizować, ponieważ programista piszący powyższe ma uzasadnione oczekiwania, że ​​wszystkie obiekty będą identyczne po pętli, nawet jeśli zostaną wyrzucone (zwykłe zastrzeżenia dotyczące „identycznych” / operatora == vs obowiązują memcmp / operator = etc). Nie można oczekiwać, że kompilator będzie miał dodatkowy wgląd w szerszy kontekst std :: vector <> lub późniejsze użycie danych, które sugerują, że ta optymalizacja jest bezpieczna.

Można to skontrastować z bardziej oczywistą, bezpośrednią implementacją:

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

Którego możemy oczekiwać, że kompilator zoptymalizuje.

Aby być bardziej precyzyjnym na temat uzasadnienia tego aspektu zachowania wektora, rozważ:

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

Oczywiście jest to główna różnica, jeśli wykonujemy 10000 niezależnych obiektów w porównaniu do 10000 odwołujących się do tych samych danych. Istnieje uzasadniony argument, że korzyść z ochrony zwykłych użytkowników C ++ przed przypadkowym zrobieniem czegoś tak kosztownego przeważa nad bardzo małymi rzeczywistymi kosztami trudnej do optymalizacji konstrukcji kopii.

ORYGINALNA ODPOWIEDŹ (dla odniesienia / sensu komentarzy): Brak szansy. wektor jest tak szybki jak tablica, przynajmniej jeśli rozsądnie zarezerwujesz miejsce. ...

Martina mnie martwi odpowiedź Martina Yorka, ponieważ wydaje się to próbą wyszczotkowania problemu inicjalizacji pod dywan. Ma jednak rację, wskazując zbędną domyślną konstrukcję jako źródło problemów z wydajnością.

[EDYCJA: Odpowiedź Martina nie sugeruje już zmiany domyślnego konstruktora.]

W celu natychmiastowego rozwiązania problemu można vector<Pixel>zamiast tego wywołać 2-parametrową wersję ctor:

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

Działa to, jeśli chcesz zainicjować ze stałą wartością, co jest częstym przypadkiem. Ale bardziej ogólnym problemem jest: Jak skutecznie zainicjować coś bardziej skomplikowanego niż stała wartość?

W tym celu można użyć back_insert_iteratoradaptera iteratora. Oto przykład z wektorem ints, chociaż ogólny pomysł działa równie dobrze dla 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());

Alternatywnie możesz użyć copy()lub transform()zamiast generate_n().

Minusem jest to, że logika do konstruowania wartości początkowych musi zostać przeniesiona do osobnej klasy, co jest mniej wygodne niż posiadanie jej w miejscu (chociaż lambdas w C ++ 1x sprawiają, że jest to o wiele ładniejsze). Spodziewam się również, że to nie będzie tak szybkie, jak malloc()wersja nieoparta na STL, ale spodziewam się, że będzie blisko, ponieważ robi tylko jedną konstrukcję dla każdego elementu.

Te wektorowe wywołują dodatkowo konstruktory pikseli.

Każdy z nich powoduje prawie milion uruchomień ctor, które mierzysz.

edycja: wtedy jest zewnętrzna pętla 1 ... 1000, więc spraw, aby miliard wywołań ctor!

edycja 2: byłoby interesujące zobaczyć demontaż skrzynki UseArray. Optymalizator może zoptymalizować całość, ponieważ nie ma innego efektu niż spalanie procesora.

Oto jak push_back metoda w wektorze:

1. Wektor przydziela X ilości miejsca podczas inicjalizacji.
2. Jak stwierdzono poniżej, sprawdza, czy w bieżącej podstawowej tablicy jest miejsce na przedmiot.
3. Tworzy kopię elementu w wywołaniu push_back.

Po wywołaniu push_backX przedmiotów:

3. Wektor przenosi ilość kX miejsca do drugiej tablicy.
4. Kopiuje wpisy z pierwszej tablicy do drugiej.
5. Odrzuca pierwszą tablicę.
6. Teraz używa drugiej tablicy jako pamięci, dopóki nie osiągnie pozycji kX.

Powtarzać. Jeśli nie jesteśreserving miejsca, to na pewno będzie wolniej. Co więcej, jeśli kopiowanie elementu jest drogie, wówczas „push_back” zje cię żywcem.

Co się tyczy vector kwestię porównania z tablicą, będę musiał się zgodzić z innymi ludźmi. Uruchom w wydaniu, włącz optymalizacje i dodaj jeszcze kilka flag, aby przyjaźni ludzie w Microsoft nie # @% $ ^ ci to zrobili.

Jeszcze jedno, jeśli nie musisz zmieniać rozmiaru, użyj Boost.Array.

Niektóre dane profilera (piksel jest wyrównany do 32 bitów):

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

Bla

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
 */

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

szyk

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

Większość kosztów ogólnych jest w konstruktorze kopiowania. Na przykład,

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

Ma taką samą wydajność jak tablica.

Mój laptop to Lenova G770 (4 GB pamięci RAM).

System operacyjny to Windows 7 64-bit (ten z laptopem)

Kompilatorem jest MinGW 4.6.1.

IDE to Code :: Blocks .

Testuję kody źródłowe pierwszego postu.

Wyniki

Optymalizacja O2

Użycie tablicy zakończono w 2,841 sekund

UseVector ukończono w 2,548 sekund

UseVectorPushBack ukończony w 11,95 sekundy

Całość zakończona w 17.342 sekund

pauza systemu

Optymalizacja O3

Użycie tablicy zakończone w 1.452 sekund

UseVector ukończony w 2,514 sekund

UseVectorPushBack ukończono w 12,967 sekund

Całość zakończona w 16,937 sekund

Wygląda na to, że wydajność wektora jest gorsza przy optymalizacji O3.

Jeśli zmienisz pętlę na

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

Szybkość macierzy i wektora pod O2 i O3 są prawie takie same.

Lepszy test porównawczy (myślę ...), kompilator ze względu na optymalizacje może zmieniać kod, ponieważ wyniki przydzielonych wektorów / tablic nigdzie nie są używane. Wyniki:

$ 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

Kompilator:

gcc version 6.2.0 20161019 (Debian 6.2.0-9)

PROCESOR:

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

I kod:

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

Zrobiłem teraz kilka obszernych testów, które chciałem zrobić. Równie dobrze mogę się tym podzielić.

To moja maszyna z podwójnym uruchomieniem i7-3770, 16 GB RAM, x86_64, na Windows 8.1 i Ubuntu 16.04. Więcej informacji i wnioski, uwagi poniżej. Testowano zarówno MSVS 2017, jak i g ++ (zarówno w systemie Windows, jak i Linux).

Program testowy

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

Wyniki

//////////////////////////////////////////////////////////////////////////////////////////
// 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
//
//////////////////////////////////////////////////////////////////////////////////////////

Notatki

• Złożony przez średnio 10 przebiegów.
• Początkowo przeprowadzałem też testy std::sort()(możesz to skomentować), ale później je usunąłem, ponieważ nie było istotnych różnic względnych.

Moje wnioski i uwagi

• zauważ, jak globalna tablica w stylu c zajmuje prawie tyle samo czasu, co tablica w stylu c sterty
• Ze wszystkich testów zauważyłem niezwykłą stabilność std::array wahań czasowych między kolejnymi przebiegami, podczas gdy inne, szczególnie struktury std :: data, różniły się znacznie w porównaniu
• Optymalizacja O3 nie wykazała żadnych znaczących różnic czasowych
• Usunięcie optymalizacji w Windows cl (bez -O2) i na g ++ (Win / Linux nie -O2, nie -march = macierzysty) wydłuża czas ISTOTNIE. Szczególnie dla struktur std :: data. Ogólnie wyższe czasy na MSVS niż g ++, ale std::arraytablice w stylu c są szybsze w systemie Windows bez optymalizacji
• g ++ produkuje szybszy kod niż kompilator Microsoft (najwyraźniej działa szybciej nawet w systemie Windows).

Werdykt

Oczywiście jest to kod zoptymalizowanej kompilacji. A ponieważ pytanie dotyczyłostd::vector tak, to jest! wolniej niż zwykłe tablice (zoptymalizowane / niezoptymalizowane). Ale kiedy przeprowadzasz test porównawczy, naturalnie chcesz stworzyć zoptymalizowany kod.

Gwiazdą programu była jednak dla mnie std::array.

Przy odpowiednich opcjach wektory i tablice mogą generować identyczny asm . W takich przypadkach mają one oczywiście tę samą prędkość, ponieważ i tak uzyskujesz ten sam plik wykonywalny.

Nawiasem mówiąc, spowolnienie widzenia w klasach za pomocą wektora występuje również w przypadku standardowych typów, takich jak int. Oto kod wielowątkowy:

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

Zachowanie z kodu pokazuje, że tworzenie wektora jest najdłuższą częścią kodu. Po przejściu przez szyjkę butelki. Reszta kodu działa bardzo szybko. Jest to prawdą bez względu na to, ile wątków używasz.

Nawiasem mówiąc, zignoruj ​​absolutnie szaloną liczbę włączeń. Używam tego kodu do testowania różnych elementów projektu, więc liczba dołączeń ciągle rośnie.

Chcę tylko wspomnieć, że wektor (i smart_ptr) to po prostu cienka warstwa dodana na surowych tablicach (i surowych wskaźnikach). W rzeczywistości czas dostępu wektora w ciągłej pamięci jest szybszy niż macierz. Poniższy kod pokazuje wynik inicjalizacji i dostępu do wektora i tablicy.

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

Dane wyjściowe to:

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

Więc prędkość będzie prawie taka sama, jeśli użyjesz go prawidłowo. (jak inni wspominali przy użyciu zastrzeżone () lub resize ()).

Cóż, ponieważ vector :: resize () wykonuje znacznie więcej przetwarzania niż zwykły przydział pamięci (przez malloc).

Spróbuj umieścić punkt przerwania w swoim konstruktorze kopiowania (zdefiniuj go, aby można było zrobić punkt przerwania!), A wtedy pojawi się dodatkowy czas przetwarzania.

Muszę powiedzieć, że nie jestem ekspertem w C ++. Ale aby dodać wyniki niektórych eksperymentów:

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

maszyna:

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

OS:

2.6.32-642.13.1.el6.x86_64

Wynik:

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

Tutaj jedyne, co wydaje mi się dziwne, to wydajność „UseFillConstructor” w porównaniu z „UseConstructor”.

Kod:

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

Tak więc podana dodatkowa „wartość” znacznie spowalnia działanie, co moim zdaniem wynika z wielokrotnego wywołania konstruktora. Ale...

Skompilować:

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

Wynik:

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

Tak więc w tym przypadku optymalizacja gcc jest bardzo ważna, ale nie może ci pomóc, gdy wartość jest podana jako domyślna. To w rzeczywistości jest sprzeczne z moją nauką. Mam nadzieję, że pomoże nowemu programistowi w wyborze formatu inicjowania wektora.

Wygląda na to, że zależy od flag kompilatora. Oto kod testu porównawczego:

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

Różne flagi optymalizacji dają różne odpowiedzi:

$ 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

Twoje dokładne wyniki będą się różnić, ale jest to dość typowe na mojej maszynie.

Z mojego doświadczenia wynika, że ​​czasami, po prostu czasami, vector<int>może być wiele razy wolniejsza niż int[]. Należy pamiętać, że wektory wektorów są bardzo różne int[][]. Ponieważ elementy prawdopodobnie nie są ciągłe w pamięci. Oznacza to, że możesz zmieniać rozmiar różnych wektorów w głównym, ale procesor może nie być w stanie buforować elementów tak dobrze, jak w przypadku int[][].