Czy std:: vector jest o wiele wolniejszy od zwykłych tablic?

Świetne pytanie. Przyszedłem tu, oczekując, że znajdę jakąś prostą poprawkę, która przyspieszy testy wektorowe. Nie wyszło tak, jak się spodziewałem!

Optymalizacja pomaga, ale to nie wystarczy. Z optimization on nadal widzę 2X 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

Idea # 1-Użyj nowego [] zamiast malloc

Próbowałem zmienić malloc() do new[] W UseArray, aby obiekty były konstruowane. I zmiana z indywidualnego przypisania pola na przypisanie instancji pikselowej. 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ąco (dla mnie), żadna z tych zmian nie zrobiła żadnej różnicy. Nawet zmiana na new[], która domyślnie konstruuje 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ł # 2 - Usuwanie powtarzających się wywołań operatora []

Próbowałem też pozbyć się potrójnego operator[] wyszukiwania i buforowania odniesienia do pixels[j]. To faktycznie spowolniło Usevectora! 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

Idea # 3-Usuń konstruktory

A co z całkowitym usunięciem konstruktorów? Wtedy być może gcc może zoptymalizować budowę wszystkich obiektów, gdy wektory są tworzone. Co się stanie jeśli zmienimy piksel na:

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

Wynik: o 10% szybszy. Jeszcze wolniej niż / align = "left" / Hm.

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

Może użyjesz vector<Pixel>::iterator zamiast 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

Podsumowanie

Nawet jeśli jakiś inteligentny cookie wymyśla, jak zrobić pętlę wektorową tak szybko, jak tablica, to nie mówi dobrze o domyślnym zachowaniu std::vector. To tyle, jeśli chodzi o to, że kompilator jest wystarczająco inteligentny, aby zoptymalizować wszystkie ness C++i uczynić kontenery STL tak szybko, jak surowe tablice.

Najważniejsze jest to, że kompilator nie jest w stanie zoptymalizować wywołań domyślnego konstruktora no-op podczas używania std::vector. Jeśli używasz zwykłego new[], optymalizuje je dobrze. Ale nie z std::vector. Nawet jeśli możesz przepisać swój kod, aby wyeliminować wywołania konstruktora, które latają w obliczu mantry tutaj: "kompilator jest mądrzejszy od Ciebie. STL jest tak samo szybki jak zwykłe C. Nie martw się tym."

Aby być uczciwym, nie można porównywać implementacji C++ do implementacji C, jak nazwałbym twoją wersję malloc. malloc nie tworzy obiektów - przydziela tylko surową pamięć. To, że wtedy traktujesz tę pamięć jako obiekty bez wywoływania konstruktora to słabe C++ (ewentualnie nieprawidłowe - to zostawię prawnikom języka).

To powiedziawszy, po prostu zmiana malloc na new Pixel[dimensions*dimensions] i free na {[10] } nie robi wielkiej różnicy z prostą implementacją piksela, którą masz. Oto wyniki na moim pudełku (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 drobną zmianą, stoły się obracają:

Piksel.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]

Skompilowane 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 nieinlinowanym konstruktorem dla piksela, std::vector bije teraz surową tablicę.

Wydaje się, że złożoność alokacji poprzez std:: vector i STD:allocator jest zbyt duża, aby zoptymalizowany tak skutecznie jak prosty new Pixel[n]. Jednak możemy zauważyć, że problem polega po prostu na alokacji, a nie na dostępie wektorowym, zmieniając kilka funkcji testowych, aby utworzyć wektor/tablicę raz, przesuwając ją 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 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

Z tego możemy się dowiedzieć, że std::vector jest porównywalny do surowej tablicy dostępu, ale jeśli musisz utworzyć i usunąć wektor/tablicę wiele razy, tworząc złożony obiekt będzie bardziej czasochłonny niż tworzenie prostej tablicy, gdy konstruktor elementu nie jest inlined. Nie wydaje mi się to zbyt zaskakujące.

To stare, ale popularne pytanie.

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

UseVector completed in 3.74482 seconds
UseArray completed in 3.70414 seconds

Podstawowy problem polegał na tym, że podczas gdy twoja Pixel struktura była niezinicjalizowana, std::vector<T>::resize( size_t, T const&=T() ) przyjmuje domyślną konstrukcję 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>::resize ma dwa przeciążenia. Pierwszy to std::vector<T>::resize(size_t), drugi to std::vector<T>::resize(size_t, T const&). Oznacza to, że gdy wywołujesz resize bez drugiego argumentu, to po prostu domyślne konstrukcje, a kompilator jest wystarczająco inteligentny, aby zdać sobie sprawę, że domyślna konstrukcja nic nie robi, więc pomija przejście nad buforem.

(dwa przeciążenia dodane do obsługi typów ruchomych, konstrukcyjnych i nie-kopiowalnych-poprawa wydajności podczas pracy na niezainicjalizowanych danych jest premią).

Rozwiązanie push_back również sprawdzanie fencepost, co spowalnia go, więc pozostaje wolniejszy niż Wersja malloc.

Przykład na żywo (zamieniłem również timer na chrono::high_resolution_clock).

Zauważ, że jeśli masz strukturę, która zwykle wymaga inicjalizacji, ale chcesz ją obsłużyć po powiększeniu bufora, możesz to zrobić za pomocą niestandardowego alokatora std::vector. Jeśli chcesz przenieść go do bardziej normalnego std::vector, uważam, że ostrożne użycie allocator_traits i nadpisanie == może to pociągnąć, ale jestem niepewny.

Spróbuj z tym:

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

Uzyskuję prawie dokładnie taką samą wydajność jak w przypadku array.

Rzecz w vector jest taka, że jest to znacznie bardziej ogólne narzędzie niż tablica. A to oznacza, że musisz rozważyć jak tego używasz. Może być używany na wiele różnych sposobów, zapewniając funkcjonalność, której tablica nawet nie ma. A jeśli używasz go "źle" do swojego celu, ponosisz dużo kosztów ogólnych, ale jeśli używasz go poprawnie, zazwyczaj są to dane zerowe struktura. W tym przypadku problem polega na tym, że oddzielnie zainicjalizowano wektor (powodując, że wszystkie elementy mają domyślny ctor wywołany), a następnie nadpisano każdy element indywidualnie z prawidłową wartością. Jest to o wiele trudniejsze dla kompilatora do optymalizacji niż gdy robisz to samo z tablicą. Dlatego wektor zapewnia konstruktor, który pozwala wykonać dokładnie to: zainicjalizować N elementy z wartością X.

I kiedy tego użyjesz, wektor jest tak samo szybki jako tablica.

Z jasnej strony, to naprawdę najprostsze użycie okazuje się być najszybsze. Jeśli zestawisz mój fragment kodu (pojedynczą linię) z odpowiedzią Johna Kugelmana, zawierającą sterty i sterty poprawek i optymalizacji, które nadal nie eliminują różnicy w wydajności, jest to całkiem jasne ten vector jest jednak całkiem sprytnie zaprojektowany. Nie musisz skakać przez obręcze, aby uzyskać prędkość równą tablicy. Wręcz 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. Więc pomyślałem, niech konstruktorzy i destruktorzy zostaną wezwani do wszystkich testów, a następnie porównamy.

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. Okazało 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 doszło do 30% utraty wydajności? STL ma wszystko w nagłówkach, więc powinno być możliwe, aby kompilator zrozumiał wszystko, co było wymagane.

Myślałem, że to w jaki 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 wyraźnie źródło spowolnienia, fakt, że wektor używa konstruktora kopiującego do inicjalizacji elementów z domyślnego zbudowanego obiektu.

Oznacza to, że następujący porządek pseudo-operacji dzieje się podczas budowy wektora:

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

Który, ze względu na niejawny Konstruktor kopiujący stworzony przez kompilator, jest rozszerzony do:

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ślne Pixelpozostaje niezinicjalizowane, podczas gdy pozostałe są zainicjalizowane z domyślnymi Pixelwartościami niezinicjalizowanymi.

W porównaniu do sytuacji alternatywnej 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 do swoich niezinicjowanych wartości i bez podwójnego iteracja nad sekwencją.

Uzbrojeni w te informacje, jak możemy je przetestować? Spróbujmy nadpisać Ukryty Konstruktor kopiujący.

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

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

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

GNU ' s STL (i inne), biorąc pod uwagę vector<T>(n), domyślne konstruuje prototypowy obiekt T() - kompilator zoptymalizuje pusty konstruktor - ale wtedy kopia tego, co stało się w adresach pamięci zarezerwowanych teraz dla obiektu, jest pobierana przez STL __uninitialized_fill_n_aux, które pętle wypełniają kopie tego obiektu jako domyślne wartości w wektorze. Tak więc," mój " STL nie jest pętlą konstruowania, ale konstruowaniem pętli / kopiowania. To jest intuicyjne, ale powinienem był pamiętać, jak ja skomentował ostatnie pytanie stackoverflow dotyczące tego właśnie punktu: construct/copy może być bardziej wydajny dla obiektów zliczonych odniesienia itp..

Więc:

vector<T> x(n);

Lub

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

Jest - na wielu implementacjach STL-czymś w rodzaju:

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

Problem polega na tym, że obecna generacja optymalizatorów kompilatorów nie wydaje się działać z wglądu, że temp jest niezainicjowanym śmieciem i nie optymalizuje wywołań pętli i domyślnego konstruktora kopiującego. Mógłbyś wiarygodnie argumentuje, że Kompilatory absolutnie nie powinny tego optymalizować, ponieważ programista piszący powyżej ma uzasadnione oczekiwania, że wszystkie obiekty będą identyczne po pętli, nawet jeśli będą śmieci(zwykłe zastrzeżenia dotyczące 'identyczny' / operator = = vs memcmp / operator = etc zastosowanie). Kompilator nie może mieć dodatkowego wglądu w szerszy kontekst std:: vector lub późniejsze wykorzystanie danych, które sugerowałyby, że ta optymalizacja jest Bezpieczna.

Można to skontrastować z bardziej oczywiste, bezpośrednie wdrożenie:

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

Którego możemy się spodziewać, że kompilator zoptymalizuje się.

Aby być nieco bardziej jednoznacznym co do uzasadnienia tego aspektu zachowania wektora, rozważ:

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

Oczywiście jest to duża różnica, jeśli zrobimy 10000 niezależnych obiektów w porównaniu do 10000 odwołujących się do tych samych danych. Istnieje uzasadniony argument, że zaleta ochrony przypadkowych użytkowników C++ przed przypadkowym zrobieniem czegoś tak drogiego przewyższa bardzo małe rzeczywisty koszt trudnych do zoptymalizowania konstrukcji kopii.

Oryginalna odpowiedź (dla odniesienia / sens komentarzy): Nie ma mowy. wektor jest tak szybki jak tablica, przynajmniej jeśli rozsądnie rezerwujesz przestrzeń. ...

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

[EDIT: odpowiedź Martina nie sugeruje już zmiany domyślnego konstruktora.]

Dla natychmiastowego problemu, z pewnością można nazwać 2-parametrową wersję vector<Pixel> ctor zamiast:

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

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

Do tego można użyć back_insert_iterator, który jest adapterem iteracyjnym. Oto przykład z wektorem ints, chociaż ogólna idea działa równie dobrze dla Pixel s:

#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 być przeniesiona do osobnej klasy, co jest mniej wygodne niż posiadanie jej na miejscu (chociaż lambda w C++1x czynią to o wiele ładniejszym). Spodziewam się również, że nie będzie to tak szybkie jak wersja non-STL oparta na malloc(), ale spodziewam się, że będzie blisko, ponieważ robi tylko jedną konstrukcję dla każdego elementu.

Wektorowe dodatkowo wywołują konstruktory pikseli.

Każdy powoduje prawie milion cykli ctor, które masz czas.

Edit: wtedy jest zewnętrzne 1...1000 pętli, więc zrób miliard połączeń ctor!

Edit 2: byłoby ciekawie zobaczyć Demontaż dla sprawy UseArray. Optymalizator może zoptymalizować całość, ponieważ nie ma innego efektu niż spalanie procesora.

Oto jak działa metoda push_back w wektorze:

1. wektor przydziela X przestrzeni, gdy jest inicjowany.
2. jak podano poniżej sprawdza, czy w bieżącej tablicy znajduje się miejsce dla elementu.
3. tworzy kopię elementu w wywołaniu push_back.

Po wywołaniu push_back x elementów:

1. wektor przedziela kX przestrzeni na drugą tablicę.
2. kopiuje wpisy pierwszej tablicy na drugi.
3. odrzuca pierwszą tablicę.
4. używa teraz drugiej tablicy jako magazynu, dopóki nie osiągnie pozycji kX.

Powtórz. Jeśli nie jesteś reserving spacją to zdecydowanie będzie wolniej. Co więcej, jeśli kopiowanie elementu jest drogie, to "push_back" w ten sposób zje cię żywcem.

Jeszcze jedno, jeśli nie musisz zmieniać rozmiaru, użyj Boost./ Align = "left" /

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

Tablica

               :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ść narzutu znajduje się w konstruktorze kopiującym. 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 RAM).

SYSTEM OPERACYJNY to Windows 7 64-bit (ten z laptopem)

Kompilatorem jest MinGW 4.6.1.

IDE to Code:: Blocks .

Wyniki

Optymalizacja O2

UseArray zakończone w 2.841 sekund

UseVector ukończony w 2.548 sekund

UseVectorPushBack zakończony w 11.95 sekund

Całość zakończona w 17.342 sekund

Pauza systemowa

Optymalizacja O3

UseArray zakończone w 1.452 sekund

UseVector ukończony w 2.514 sekund

UseVectorPushBack zakończony w 12.967 sekund

Całość ukończona w 16.937 sekund

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

Jeśli zmienisz pętlę na

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

Lepszy benchmark (chyba...), kompilator ze względu na optymalizacje może zmieniać Kod, ponieważ wyniki przydzielonych wektorów/tablic nie są nigdzie 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)

CPU:

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

Z odpowiednimi opcjami, wektory i tablice mogą generować identyczne asm . W takich przypadkach są one oczywiście tej samej prędkości, ponieważ otrzymujesz ten sam plik wykonywalny.

Nawiasem mówiąc spowolnienie widzenia w klasach za pomocą wektora występuje również w typach standardowych, takich jak int. Heres 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 instancja wektora jest najdłuższą częścią kodu. Jak tylko przejdziesz przez szyjkę butelki. Reszta kodu działa bardzo szybko. Jest to prawdą bez względu na to, ile wątków jest uruchomionych.

Przy okazji zignoruj absolutnie szaloną liczbę includes. Używam tego kodu do testowania rzeczy do projektu, więc liczba obejmuje stale rośnie.

Chcę tylko wspomnieć, że vector (i smart_ptr) jest tylko cienką warstwą dodaną na surowych tablicach (i surowych wskaźnikach). A w rzeczywistości czas dostępu wektora w pamięci ciągłej jest szybszy niż tablica. Poniższy kod pokazuje wynik inicjalizacji i dostępu 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;
}

Wyjście 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 jej prawidłowo. (jak inni wspominali używając reserve () lub resize ()).

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

Spróbuj umieścić breakpoint w konstruktorze kopiującym(zdefiniuj go tak, aby można było breakpoint!) i idzie dodatkowy czas przetwarzania.

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

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

Wyjście:

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 mnie dziwi, 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));
    }
}

Więc dodatkowa "wartość" spowalnia wydajność dość dużo, co moim zdaniem jest spowodowane wielokrotnym wywołaniem do konstruktora kopiującego. Ale...

Kompilacja:

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

Wyjście:

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 pomóc, gdy wartość jest podana jako domyślna. To jest wbrew mojemu czesnemu. Mam nadzieję, że pomoże to nowemu programiście przy wyborze formatu inicjalizacji wektora.

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

To jest mój podwójny boot machine i7-3770, 16GB Ram, x86_64, w systemie Windows 8.1 i Ubuntu 16.04. Więcej informacji i wnioski, uwagi poniżej. Przetestowano 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
//
//////////////////////////////////////////////////////////////////////////////////////////

Uwagi

/ Align = "left" /
• ja też początkowo wykonywałem testy z std::sort() (widać to skomentowane), ale usunięte później, ponieważ nie było znaczących różnic względnych.

Moje wnioski i uwagi

• zauważ, że Globalna tablica w stylu c zajmuje prawie tyle czasu, co tablica w stylu C sterty
• ze wszystkich testów zauważyłem niezwykłą stabilność w wahaniach czasowych std::array pomiędzy kolejnymi uruchomieniami, podczas gdy inne, szczególnie std:: Data structs, różniły się szalenie w porównaniu
• optymalizacja O3 nie wykazała żadnych godne uwagi różnice czasowe
• usunięcie optymalizacji w Windows cl (no-O2) i w g++ (Win / Linux no-O2, no-march=native) znacznie wydłuża czas. Szczególnie dla std:: data structs. W przypadku systemów MSV jest to znacznie szybsze niż w przypadku g++, ale w przypadku Systemów Windows bez optymalizacji jest to znacznie szybsze.]}
• g++ wytwarza szybszy Kod niż kompilator Microsoftu (najwyraźniej działa szybciej nawet na Windows).

Werdykt

Oczywiście jest to kod dla zoptymalizowanego buduj. A skoro pytanie dotyczyło std::vector, to tak !much! wolniej niż zwykłe tablice (zoptymalizowane/nieoptymalizowane). Ale kiedy robisz benchmark, naturalnie chcesz stworzyć zoptymalizowany kod.

Gwiazdą serialu dla mnie był std::array.