C++ Array vs Vektör performans testi açıklaması

Question

C++ gibi bir dizinin ve Vektörlerin performansındaki farkı ölçmek için bu küçük programı yazdım. https://github.com/rajatkhanduja/Benchmarks/blob/master/C%2B%2B/vectorVsArray.cpp

Onları ortak zeminlerde karşılaştırmak için, hem rasgele hem ardışık erişim için test etmeye karar verdim. Yineleyiciler ekledim, sadece onları karşılaştırmak için (ama bu soruya odaklanmıyor). aşağıdaki gibi 1 milyon, bir dizi/vektör boyutuna 7.7 GB RAM ile bir 64-bit Linux makinesi için

sonuçlar aşağıdaki gibidir: - bir dizi yazmak için alınan

• saat. : 12.0378 ms
• Diziden ardışık olarak okunması için zaman alındı. : 2.48413 msn
• Diziden rasgele okunan zaman okunur. : 37.3931 ms
• Dinamik diziye yazma zamanı. : 11.7458 ms
• Sıralı olarak dinamik diziden okunan zaman. : 2.85107 msn Dinamik diziden rasgele okunan zaman alındı. : 36.0579 ms
• Zaman endeksleri kullanarak vektöre yazılır. : 11.3909 ms
• Vektörlerden, indisleri kullanarak art arda okumak için geçen süre. : 4.09106 ms
• Vektör, endeksleri kullanarak rasgele bir şekilde vektörden okundu. : 39 ms
• Yineleyicileri kullanarak vektöre yazılan zaman. : 24,9949 ms
• Yineleyicileri kullanarak vektörden okuma zamanı. : 18.8049 ms

Vektörün boyutu, başlatma sırasında ayarlanır ve değiştirilmez; dolayısıyla, vektörün yeniden boyutlandırılması yoktur (programdaki onaylama, bunu doğrulamaya yardımcı olur). Zamanlar, statik olarak ayrılmış dizinin, dinamik olarak ayrılmış dizinin veya vektörün herhangi birinin başlatma zamanlarını içermez.

İstatistiğe göre, Vector'e yazılacak zaman, dizininkinden daha azdır, ancak vektörden okunacak zaman, dizininkinden iki kat daha fazladır.

Bu fark oldukça küçüktür, ancak neden bir performans farkı olduğuna dair bir açıklama var mı? Testte yanlış bir şey mi var? Her ikisinin de aynı hızda performans göstermesini bekledim. Bu testin tekrarı aynı trendi gösterir.

kodu:

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

---

DÜZENLEME Yorum önerilen olarak

, burada daha fazla bilgi bulabilirsiniz: -

• Derleyici: - g ++ - 4.5.2
• Bayraklar: - yok (örn. De hata değerleri)
• Optimizasyonlar: - Yok (Bu davranışı normal bir ortamda test etmek istedim. Optimizasyon programın davranışını değiştirebilir, örneğin değişken tmp hiçbir zaman kullanılmadığından, vektör/dizi okuma aşaması tamamen atlanabilir veya sadece son atamaya indirgenebilir.En azından anladığım kadarıyla).

Answer 1

Kesin bir yanıt değil, ancak bir değişkendeki değişkene yazıyorsunuz, bu da bir derleyicinin sıralı okuma için son sonucun ne olması gerektiğini kolayca tahmin edebilmesi ve böylece döngüyü en iyi duruma getirmesi anlamına gelmektedir. Açıkçası bunu yapmadığından, kesinlikle yineleyici yaklaşımını tercih etmeyen bir optimizasyon olmadığını varsayalım. Diğer sayılar sonuç almak için çok yakın.