Wektor inicjalizujący wolniej niż tablica ... dlaczego?

Question

Próbowałem 2 rzeczy: (pseudo kod poniżej)

int arr[10000]; 
for (int i = 0; i < 10000; i++) 
{ 
    for (int j = 0; j < 10000; j++) 
    { 
     arr[j] = j; 
    } 
} 

i

vector<int> arr(10000); 
for (int i = 0; i < 10000; i++) 
{ 
    for (int j = 0; j < 10000; j++) 
    { 
     arr[j] = j; 
    } 
} 

Pobiegłem oba programy i planowane go za pomocą polecenia powłoki "czas". Program 1 działa w ciągu 5 sekund, program 2 działa w ciągu 30 sekund. Uruchomiłem oba programy z włączoną optymalizacją kompilacji i oba programy działały mniej więcej w tym samym czasie (0,38s). Jestem zdezorientowany tymi wynikami. Czy ktoś może mi wyjaśnić, dlaczego tak się dzieje?

Dzięki!

Answer 1

Dla wzorca, indeksowanie odbywa się za pomocą operatora []. Po wyłączeniu optymalizacji zwykle generowane jest ono jako rzeczywiste wywołanie funkcji, co zwiększa nakład na coś tak prostego jak indeksowanie do tablicy. Po włączeniu optymalizacji jest on generowany inline, usuwając ten narzut.

Answer 2

W trybie debugowania implementacje std::vector zapewniają wiele sprawdzeń podczas wykonywania w celu ułatwienia użycia. To sprawdzanie nie jest dostępne dla tablic rodzimych. Na przykład w VC2008, jeśli skompilujesz swój przykład vector w trybie debugowania, pojawi się range-checkingnawet w przypadku operator[].

Answer 3

Jeśli niezoptymalizowana implementacja wektora wykonuje sprawdzanie granic, to uwzględniłaby rozbieżność.

Answer 4

ponieważ po wpisaniu wektora arr (10000); tworzysz obiekt, wywołujesz jego funkcje ... kiedy i będzie wolniejszy niż gdy utworzysz int arr [10000];

Answer 5

W przykładach tablica znajduje się na stosie. Dostęp do danych w tablicy wymaga dostępu do danych na stosie. To szybko. Z drugiej strony, podczas gdy vector znajduje się na stosie, dane dla std::vector są alokowane gdzie indziej (domyślnie przydzielane są na stercie za pośrednictwem std::allocator). Dostęp do danych w vector wymaga dostępu do danych na stercie. To znacznie wolniej niż dostęp do danych na stosie.

Dostajesz jednak coś za wykonanie kary. std::vector jest growable, podczas gdy regularna tablica nie jest. Ponadto, rozmiar std::vector nie musi być stałą czasową kompilacji, podczas gdy rozmiar tablicy na stosie ma miejsce. Tablica alokowana przez sterty (przez operator new[]) nie musi być stałą w czasie kompilacji. Jeśli porównać tablicę przydzieloną stertom z std::vector, okaże się, że wydajność jest znacznie bliższa.

int* arr = new int[10000]; 
for (int i = 0; i < 10000; i++) 
{ 
    for (int j = 0; j < 10000; j++) 
    { 
     arr[j] = j; 
    } 
} 

delete[] arr; // std::vector does this for you 

Answer 6

To są dobre odpowiedzi, ale istnieje szybki sposób, aby się przekonać.

Widzisz różnicę w wydajności 6 do 1, prawda? Po prostu uruchom wolną i naciśnij przycisk "pauza". Następnie spójrz na stos połączeń. Prawdopodobieństwo to 5 z 6 (83%), że dokładnie zobaczysz, jak wydaje się te 25 dodatkowych sekund. Zrób to kilka razy, aby uzyskać jak najwięcej wglądów, jak chcesz.

Dla zoptymalizowanego przypadku, wykonaj to samo z programem 1. Ponieważ jest 13 razy wolniejszy niż program zoptymalizowany, zobaczysz przyczynę, dla której na każdym "pauzie", z prawdopodobieństwem 12/13 = 92%.

To jest aplikacja o numerze this technique.