Używając tablic lub wektorów std :: w C ++, jaka jest różnica w wydajności?

W naszym kursie C ++ sugerują, aby nie używać już tablic C ++ w nowych projektach. O ile wiem, sam Stroustroup sugeruje, aby nie używać tablic. Ale czy istnieją znaczące różnice w wydajności?

newNależy unikać używania tablic C ++ z (tj. Przy użyciu tablic dynamicznych). Problem polega na tym, że musisz śledzić rozmiar i musisz usunąć je ręcznie i wykonywać wszelkiego rodzaju czynności porządkowe.

Używanie tablic na stosie jest również odradzane, ponieważ nie masz sprawdzania zasięgu, a przekazywanie tablicy spowoduje utratę jakichkolwiek informacji o jej rozmiarze (konwersja tablicy na wskaźnik). W boost::arraytakim przypadku powinieneś użyć , który otacza tablicę C ++ małą klasą i zapewnia sizefunkcję i iteratory do iteracji po niej.

Teraz tablice std :: vector vs. natywne C ++ (pobrane z Internetu):

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Uwaga: Jeśli alokujesz tablice newi przydzielasz obiekty nieklasowe (takie jak zwykły int) lub klasy bez konstruktora zdefiniowanego przez użytkownika i nie chcesz początkowo inicjować elementów, użycie newalokowanych tablic może mieć przewagę wydajności, ponieważ std::vectorinicjuje wszystkie elementy do domyślne wartości (na przykład 0 dla int) na budowie (podziękowania dla @bernie za przypomnienie).

Preambuła dla osób mikrooptymalizujących

Zapamiętaj:

„Programiści tracą ogromną ilość czasu na myślenie lub martwienie się o szybkość niekrytycznych części swoich programów, a te próby wydajności mają silny negatywny wpływ, gdy rozważa się debugowanie i konserwację. Powinniśmy zapomnieć o małej wydajności, powiedzmy o 97% czasu: przedwczesna optymalizacja jest źródłem wszelkiego zła. Jednak nie powinniśmy tracić naszych możliwości w tak krytycznych 3% ”.

(Dzięki metamorfozie za pełny cytat)

Nie używaj tablicy C zamiast wektora (lub czegokolwiek) tylko dlatego, że uważasz, że jest szybszy, ponieważ powinien być niższego poziomu. Mylisz się

Użyj domyślnie wektora (lub bezpiecznego kontenera dostosowanego do twoich potrzeb), a następnie, jeśli Twój profiler stwierdzi, że jest to problem, sprawdź, czy możesz go zoptymalizować, używając lepszego algorytmu lub zmieniając kontener.

To powiedziawszy, możemy wrócić do pierwotnego pytania.

Tablica statyczna / dynamiczna?

Klasy tablic C ++ są lepiej zachowywane niż tablice C niskiego poziomu, ponieważ dużo wiedzą o sobie i potrafią odpowiedzieć na pytania, na które tablice C nie potrafią. Są w stanie oczyścić po sobie. I, co ważniejsze, zwykle są one pisane przy użyciu szablonów i / lub inliningu, co oznacza, że ​​to, co wydaje się dużo kodu w debugowaniu, rozwiązuje problem z niewielkim kodem produkowanym w kompilacji wersji lub nie ma go wcale, co nie ma znaczenia z jego wbudowaną mniej bezpieczną konkurencją.

Podsumowując, należy do dwóch kategorii:

Dynamiczne tablice

Użycie wskaźnika do tablicy malloc-ed / new-ed będzie co najwyżej tak szybkie jak wersja std :: vector i znacznie mniej bezpieczne (patrz post litba ).

Więc użyj std :: vector.

Tablice statyczne

Najlepiej będzie użyć tablicy statycznej:

• tak szybko, jak wersja std :: array
• i dużo mniej bezpieczne.

Więc użyj std :: array .

Niezainicjowana pamięć

Czasami użycie vectorzamiast surowego bufora wiąże się z widocznym kosztem, ponieważ vectorinicjuje on bufor podczas budowy, podczas gdy kod, który zastępuje, nie ma, jak zauważył Bernie w swojej odpowiedzi .

Jeśli tak jest, możesz sobie z tym poradzić, używając unique_ptrzamiast a vectorlub, jeśli sprawa nie jest wyjątkowa w twojej linii kodu, faktycznie napisz klasę, buffer_ownerktóra będzie właścicielem tej pamięci, i zapewni ci łatwy i bezpieczny dostęp do niej, w tym bonusy takie jak zmiana rozmiaru (za pomocą realloc?) lub cokolwiek potrzebujesz.

Wektory to tablice pod maską. Wydajność jest taka sama.

Jednym z miejsc, w którym można napotkać problem z wydajnością, jest niewłaściwe dobranie wektora na początek.

Gdy wektor się zapełni, zmieni rozmiar, a to może oznaczać nowy przydział tablicy, następnie n konstruktorów kopiowania, następnie około n wywołań destruktora, a następnie usunięcie tablicy.

Jeśli twój konstrukt / destrukcja jest drogi, znacznie lepiej jest zacząć od wektora o prawidłowym rozmiarze.

Istnieje prosty sposób, aby to wykazać. Utwórz prostą klasę, która pokazuje, kiedy zostanie zbudowana / zniszczona / skopiowana / przypisana. Utwórz wektor tych rzeczy i zacznij je popychać na tylnym końcu wektora. Gdy wektor się zapełni, nastąpi kaskada aktywności w miarę zmiany rozmiaru wektora. Następnie spróbuj ponownie z wektorem o rozmiarze zgodnym z oczekiwaną liczbą elementów. Zobaczysz różnicę.

Aby odpowiedzieć na coś, co Mehrdad powiedział:

Mogą jednak wystąpić przypadki, w których nadal potrzebujesz tablic. Podczas łączenia z kodem niskiego poziomu (tj. Asemblerem) lub starymi bibliotekami, które wymagają tablic, używanie wektorów może być niemożliwe.

Zupełnie nieprawda. Wektory ładnie rozkładają się na tablice / wskaźniki, jeśli używasz:

vector<double> vector;
vector.push_back(42);

double *array = &(*vector.begin());

// pass the array to whatever low-level code you have

Działa to dla wszystkich głównych implementacji STL. W kolejnym standardzie będzie on musiał działać (nawet jeśli dzisiaj jest w porządku).

Masz jeszcze mniej powodów, aby używać zwykłych tablic w C ++ 11.

W naturze istnieją 3 rodzaje tablic, od najszybszego do najwolniejszego, w zależności od ich funkcji (oczywiście jakość implementacji może sprawić, że wszystko będzie naprawdę szybkie, nawet w przypadku 3 na liście):

1. Statyczny o rozmiarze znanym w czasie kompilacji. ---std::array<T, N>
2. Dynamiczny z rozmiarem znanym w czasie wykonywania i nigdy nie zmieniającym rozmiaru. Typowa optymalizacja polega na tym, że jeśli tablica może być przydzielona bezpośrednio na stosie. - Niedostępne . Możedynarray w C ++ TS po C ++ 14. W C są VLA
3. Dynamiczny i skalowalny w czasie wykonywania. ---std::vector<T>

Dla 1. zwykłych tablic statycznych ze stałą liczbą elementów użyjstd::array<T, N> w C ++ 11.

Dla 2. tablic o stałym rozmiarze określonych w czasie wykonywania, ale to nie zmieni ich rozmiaru, w C ++ 14 jest dyskusja, ale została ona przeniesiona do specyfikacji technicznej i ostatecznie wykonana z C ++ 14.

Dla 3. std::vector<T> zwykle poprosi o pamięć w stercie . Może to mieć wpływ na wydajność, ale można go użyć std::vector<T, MyAlloc<T>>do poprawy sytuacji za pomocą niestandardowego alokatora. Zaletą w porównaniu z T mytype[] = new MyType[n];tym jest to, że można zmienić jego rozmiar i że nie rozpadnie się na wskaźnik, jak to robią zwykłe tablice.

Użyj wspomnianych standardowych typów bibliotek, aby uniknąć rozkładania się tablic na wskaźniki . Zaoszczędzisz czas debugowania, a wydajność jest dokładnie taka sama jak w przypadku zwykłych tablic, jeśli używasz tego samego zestawu funkcji.

Idź z STL. Nie ma ograniczenia wydajności. Algorytmy są bardzo wydajne i dobrze sobie radzą z szczegółami, o których większość z nas nie pomyślałaby.

STL to mocno zoptymalizowana biblioteka. W rzeczywistości sugeruje się nawet stosowanie STL w grach, w których może być wymagana wysoka wydajność. Tablice są zbyt podatne na błędy, aby można je było stosować w codziennych zadaniach. Dzisiejsze kompilatory są również bardzo inteligentne i mogą naprawdę generować doskonały kod za pomocą STL. Jeśli wiesz, co robisz, STL może zwykle zapewnić niezbędną wydajność. Na przykład inicjując wektory do wymaganego rozmiaru (jeśli wiesz od początku), możesz w zasadzie osiągnąć wydajność macierzy. Mogą jednak wystąpić przypadki, w których nadal potrzebujesz tablic. Podczas łączenia z kodem niskiego poziomu (tj. Asemblerem) lub starymi bibliotekami, które wymagają tablic, używanie wektorów może być niemożliwe.

O wkładzie Duli .

Wniosek jest taki, że tablice liczb całkowitych są szybsze niż wektory liczb całkowitych (5 razy w moim przykładzie). Jednak tablice i wektory są rozmieszczone wokół tej samej prędkości w przypadku bardziej skomplikowanych / niepasowanych danych.

Jeśli skompilujesz oprogramowanie w trybie debugowania, wiele kompilatorów nie wstawi funkcji akcesora wektora. Spowoduje to, że implementacja wektora stl będzie znacznie wolniejsza w okolicznościach, w których wydajność stanowi problem. Ułatwi to także debugowanie kodu, ponieważ w debuggerze można zobaczyć, ile pamięci zostało przydzielone.

W trybie zoptymalizowanym oczekiwałbym, że wektor stl zbliży się do wydajności tablicy. Dzieje się tak, ponieważ wiele metod wektorowych jest teraz wbudowanych.

Zdecydowanie wpływ na wydajność ma użycie std::vectortablicy vs surowej, gdy chcesz niezainicjowany bufor (np. Do użycia jako miejsce docelowe memcpy()). Nastd::vectorZainicjuje wszystkie jego elementy przy użyciu domyślnego konstruktora. Surowa tablica nie będzie.

Specyfikacja c ++ dla std:vectorkonstruktora pobierającego countargument (jest to trzecia forma) mówi:

`Tworzy nowy kontener z różnych źródeł danych, opcjonalnie używając przydzielonego przez użytkownika przydziału alokatora.

3) Konstruuje kontener z domyślnie wstawionymi wystąpieniami T. Nie wykonuje się żadnych kopii.

Złożoność

2-3) Liniowe w policzeniu

Surowa tablica nie ponosi tego kosztu inicjalizacji.

Zobacz także Jak mogę uniknąć std :: vector <>, aby zainicjować wszystkie jego elementy?

Różnica w wydajności między nimi zależy w dużej mierze od implementacji - jeśli porównamy źle zaimplementowany std :: vector z optymalną implementacją tablicy, tablica wygra, ale odwróci ją i wektor wygra ...

Tak długo, jak porównasz jabłka z jabłkami (zarówno tablica, jak i wektor mają stałą liczbę elementów lub oba zmieniają się dynamicznie) pomyślałbym, że różnica w wydajności jest znikoma, o ile postępujesz zgodnie z praktyką kodowania STL. Nie zapominaj, że korzystanie ze standardowych kontenerów C ++ pozwala również na korzystanie ze wstępnie walcowanych algorytmów, które są częścią standardowej biblioteki C ++, a większość z nich prawdopodobnie będzie lepsza niż średnia implementacja tego samego algorytmu, który sam zbudowałeś .

To powiedziawszy, IMHO wektor wygrywa w scenariuszu debugowania z debugowaniem STL, ponieważ większość implementacji STL z odpowiednim trybem debugowania może przynajmniej wyróżnić / wyeliminować typowe błędy popełniane przez ludzi podczas pracy ze standardowymi kontenerami.

Aha, i nie zapominaj, że tablica i wektor mają ten sam układ pamięci, więc możesz używać wektorów do przekazywania danych do starszego kodu C lub C ++, który oczekuje podstawowych tablic. Pamiętaj jednak, że w tym scenariuszu większość zakładów jest wyłączona i znów masz do czynienia z czystą pamięcią.

Jeśli nie musisz dynamicznie dostosowywać rozmiaru, masz narzut pamięci związany z oszczędzaniem pojemności (jeden wskaźnik / size_t). Otóż ​​to.

Może istnieć przypadek krawędzi, w którym masz dostęp do wektora wewnątrz funkcji śródliniowej wewnątrz funkcji śródliniowej, gdzie wykroczyłeś poza to, co kompilator wstawi i wymusi wywołanie funkcji. Byłoby to tak rzadkie, że nie warto się o to martwić - generalnie zgodziłbym się z litb .

Dziwię się, że nikt jeszcze o tym nie wspominał - nie martw się o wydajność, dopóki nie zostanie udowodnione, że jest to problem, a następnie test.

Twierdziłbym, że głównym zmartwieniem nie jest wydajność, ale bezpieczeństwo. Możesz popełnić wiele błędów przy użyciu tablic (na przykład rozważ zmianę rozmiaru), gdzie wektor zaoszczędziłby ci dużo bólu.

Wektory wykorzystują nieco więcej pamięci niż tablice, ponieważ zawierają rozmiar tablicy. Zwiększają także rozmiar dysku twardego programów i prawdopodobnie zajmują mniej miejsca w pamięci programów. Te wzrosty są niewielkie, ale mogą mieć znaczenie, jeśli pracujesz z systemem wbudowanym. Chociaż większość miejsc, w których te różnice mają znaczenie, to miejsca, w których wolisz używać C niż C ++.

Następujący prosty test:

C ++ Array vs Vector wyjaśnienie testu wydajności

zaprzecza wnioskom z „Porównanie kodu asemblera wygenerowanego dla podstawowych operacji indeksowania, dereferencji i inkrementacji na wektorach i tablicach / wskaźnikach”.

Musi istnieć różnica między tablicami i wektorami. Test mówi, więc ... po prostu spróbuj, kod jest tam ...

Czasami tablice są rzeczywiście lepsze niż wektory. Jeśli zawsze manipulujesz zestawem obiektów o stałej długości, tablice są lepsze. Rozważ następujące fragmenty kodu:

int main() {
int v[3];
v[0]=1; v[1]=2;v[2]=3;
int sum;
int starttime=time(NULL);
cout << starttime << endl;
for (int i=0;i<50000;i++)
for (int j=0;j<10000;j++) {
X x(v);
sum+=x.first();
}
int endtime=time(NULL);
cout << endtime << endl;
cout << endtime - starttime << endl;

}

gdzie jest wektorowa wersja X

class X {
vector<int> vec;
public:
X(const vector<int>& v) {vec = v;}
int first() { return vec[0];}
};

a wersja tablicowa X to:

class X {
int f[3];

public:
X(int a[]) {f[0]=a[0]; f[1]=a[1];f[2]=a[2];}
int first() { return f[0];}
};

Wersja tablicy funkcji main () będzie szybsza, ponieważ unikamy narzutu „nowego” za każdym razem w wewnętrznej pętli.

(Ten kod został opublikowany przeze mnie na comp.lang.c ++).

Jeśli używasz wektorów do reprezentowania zachowania wielowymiarowego, oznacza to poprawę wydajności.

Czy wektory 2d + powodują spadek wydajności?

Istotą jest to, że każdy pod-wektor ma niewielki narzut na informacje o rozmiarze i niekoniecznie wystąpi szeregowanie danych (jak ma to miejsce w przypadku wielowymiarowych tablic c). Ten brak serializacji może zaoferować więcej niż możliwości mikrooptymalizacji. Jeśli wykonujesz tablice wielowymiarowe, najlepiej po prostu rozszerzyć std :: vector i rzucić własną funkcję bitów get / set / resize.

Zakładając, że tablica o stałej długości (np. int* v = new int[1000];Vs std::vector<int> v(1000);, z wielkością vutrzymywaną na poziomie 1000), jedyna kwestia wydajności, która naprawdę ma znaczenie (lub przynajmniej miała dla mnie znaczenie, gdy miałem podobny dylemat) to szybkość dostępu do element. Sprawdziłem kod wektorowy STL i oto, co znalazłem:

const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }

Ta funkcja z pewnością zostanie wprowadzona przez kompilator. Tak więc, o ile jedyną rzeczą, którą planujesz zrobić, vjest dostęp do jego elementów operator[], wydaje się, że tak naprawdę nie powinno być żadnej różnicy w wydajności.