C++ Array vs Vector test objaśnienia testu

Question

Aby policzyć różnicę w wydajności tablicy C-like i wektorów w C++, napisałem ten mały program. https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

Aby porównać je na wspólnych podstawach, postanowiłem przetestować zarówno dostęp losowy, jak i sekwencyjny. Dodałem iteratory, aby je również porównać (ale nie na tym się to koncentruje).

Wyniki, dla 64-bitowego Linux-7,7 GB pamięci RAM o wielkości na tablicy/wektor 1 milion są następujące: -

• Czas potrzebny do zapisu tablicy. : 12.0378 ms
• Czas do odczytu z tablicy po kolei. : 2.48413 ms
• Czas pobierania z tablicy losowo. : 37.3931 ms
• Czas zapisu do tablicy dynamicznej. : 11.7458 ms
• Czas do odczytu z dynamicznej tablicy sekwencyjnie. : 2.85107 ms
• Czas do losowego odczytu z tablicy dynamicznej. : 36.0579 ms
• Czas zapisu do wektora przy użyciu indeksów. : 11.3909 ms
• Czas do odczytu z wektora za pomocą indeksów, sekwencyjnie. : 4.09106 ms
• Czas do odczytu z wektora za pomocą indeksów, losowo. : 39 ms
• Czas zapisu do wektora przy użyciu iteratorów. : 24,9949 ms
• Czas potrzebny do odczytania z wektora za pomocą iteratorów. : 18,8049 ms

Wielkość wektora jest ustawiana na czas inicjalizacji i nie jest zmieniana, więc nie ma zmiany rozmiaru wektora (asercja w programie pomaga to sprawdzić). Czasy nie uwzględniają czasów inicjalizacji żadnej z tablic alokowanych statycznie, tablic alokowanych dynamicznie lub wektora.

Według statystyk, czas zapisu w wektorze jest mniejszy niż w tablicy, ale czas odczytu z wektora jest dwa razy większy niż w tablicy.

Różnica jest dość mała, ale czy istnieje wyjaśnienie, dlaczego występuje różnica w wydajności? Czy coś jest nie tak z testem? Spodziewałem się, że obydwaj wykonają tę samą prędkość. Powtórzenie tego testu pokazuje ten sam trend.

Kod:

#include <vector> 
#include <iostream> 
#include <cstdlib> 
#include <ctime> 
#include <sys/time.h> 
#include <cassert> 

#define ARR_SIZE 1000000 

using std::string; 

void printtime (struct timeval& start, struct timeval& end, string str); 

int main (void) 
{ 
    int arr[ARR_SIZE]; 
    int tmp; 
    struct timeval start, stop; 

    srand (time (NULL)); 

    /* Writing data to array */ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    arr[i] = rand(); 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to write to array.")); 

    /* Reading data from array */ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    tmp = arr[i]; 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to read from array sequentially.")); 

    /* Reading data from array randomly*/ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    tmp = arr[rand() % ARR_SIZE]; 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to read from array randomly.")); 


    int *darr = (int *) calloc (sizeof (int), ARR_SIZE); 

    /* Writing data to array */ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    darr[i] = rand(); 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to write to dynamic array.")); 

    /* Reading data from array */ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    tmp = darr[i]; 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to read from dynamic array sequentially.")); 

    /* Reading data from dynamic array randomly*/ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    tmp = darr[rand() % ARR_SIZE]; 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to read from dynamic array randomly.")); 

    std::vector<int> v(ARR_SIZE); 
    assert (v.capacity() == ARR_SIZE); 

    /* Writing to vector using indices*/ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    v[i] = rand(); 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to write to vector using indices.")); 
    assert (v.capacity() == ARR_SIZE); 

    /* Reading from vector using indices*/ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    tmp = v[i]; 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to read from vector using indices, sequentially.")); 

    /* Reading data from dynamic array randomly*/ 
    gettimeofday (&start, NULL); 
    for (int i = 0; i < ARR_SIZE; i++) 
    { 
    tmp = v[rand() % ARR_SIZE]; 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to read from vector using indices, randomly.")); 

    std::vector<int> v2(ARR_SIZE); 

    /* Writing to vector using iterators*/ 
    gettimeofday (&start, NULL); 
    std::vector<int>::iterator itr, itr_end; 
    for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++) 
    { 
    *itr = rand(); 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to write to vector using iterators.")); 


    /* Reading from vector using iterators*/ 
    gettimeofday (&start, NULL); 
    for (itr = v2.begin(), itr_end = v2.end(); itr != itr_end; itr++) 
    { 
    tmp = *itr; 
    } 
    gettimeofday (&stop, NULL); 
    printtime (start, stop, string ("Time taken to read from vector using iterators.")); 

    return 0; 
} 

void printtime (struct timeval& start, struct timeval& end, string str) 
{ 
    double start_time, end_time, diff; 

    start_time = ((start.tv_sec) * 1000 + start.tv_usec/1000.0); 
    end_time = ((end.tv_sec) * 1000 + end.tv_usec/1000.0); 
    diff = end_time - start_time; 

    std::cout << str << " : " << diff << " ms" << std::endl; 
} 

---

EDIT

Jak sugerowano w komentarzach, tutaj jest więcej informacji: -

• Compiler: - g ++ - 4.5.2
• Flagi: - brak (np. wartości błędów)
• Optymalizacje: - Brak (chciałem przetestować zachowanie w zwykłym ustawieniu. Optymalizacja może zmieniać zachowanie programu, na przykład, ponieważ zmienna tmp nigdy nie jest używana, krok odczytu wektora/tablicy może zostać całkowicie pominięty lub zredukowany do ostatniego przypisania.Przynajmniej to rozumiem).

Answer 1

Z pewnością nie jest to ostateczna odpowiedź, ale piszemy w pętli do zmiennej, co oznacza, że ​​kompilator może łatwo odgadnąć, jaki powinien być wynik końcowy dla odczytu sekwencyjnego, optymalizując w ten sposób pętlę. Ponieważ oczywiście tego nie robi, zakładam, że nie ma optymalizacji, która zdecydowanie nie faworyzuje podejścia iteracyjnego. Pozostałe liczby są zbyt bliskie, aby wyciągnąć wnioski.