Efficienza tra puntatore e array (meno istruzioni di assemblaggio non richiedono meno tempo)

Question

Alcune persone hanno detto: "Qualsiasi operazione che può essere ottenuta con l'indice di array può essere eseguita anche con i puntatori.

dubito circa l'esito di quanto sopra, in modo da fare il seguente test:

Nel seguente articolo, noi non interessa ottimizzazione del compilatore. A proposito di ottimizzazione del compilatore come influenzano l'efficienza tra il puntatore e array, si prega di notare: Efficiency: arrays vs pointers

(Visual Studio 2010, la modalità di debug, nessuna ottimizzazione)

#include <windows.h> 
#include <stdio.h> 

int main() 
{ 
    int a[] = {10,20,30}; 
    int* ap = a; 

    long counter; 

    int start_time, end_time; 
    int index; 

    start_time = GetTickCount(); 
    for (counter = 1000000000L; counter>0; counter--) 
    { 
     *(ap+1) = 100; 
    } 
    end_time = GetTickCount(); 
    printf("10 billion times of *ap = %d\n", end_time-start_time); 

    start_time = GetTickCount(); 
    for (counter = 1000000000L; counter>0; counter--) 
    { 
     a[1] = 101; 
    } 
    end_time = GetTickCount(); 
    printf("10 billion times of a[0] = %d\n", end_time-start_time); 

    return 0; 
} 

il risultato è:

10 billion times of *ap = 3276 
10 billion times of a[0] = 3541 

Il puntatore sembra essere un po 'veloce. Ma dopo aver confrontato i dis-assemblare, caddi in una confusione profonda.

(Visual Studio 2010, modalità di debug, nessuna ottimizzazione)

; 17 :   *(ap+1) = 100; 
mov eax, DWORD PTR _ap$[ebp] 
mov DWORD PTR [eax+4], 100   ; 00000064H 

; 25 :   a[1] = 101; 
mov DWORD PTR _a$[ebp+4], 101  ; 00000065H 

Dall'output assemblare, accesso alla memoria attraverso un puntatore assume 2 istruzioni e array richiede solo 1 istruzione.

Perché la matrice esegue meno istruzioni ma non richiede meno tempo del puntatore?

È associato alla cache della CPU? Come posso modificare il mio codice di prova per dimostrarlo?

Answer 1

In primo luogo e, soprattutto, il linguaggio C non ha velocità. Questo è un attributo introdotto dalle implementazioni di C. Ad esempio, C non ha velocità, ma il compilatore GCC produce codice che potrebbe variare in velocità dal codice prodotto dal compilatore Clang, ed entrambi sono suscettibili di produrre codice che esegue il comportamento prodotto dagli interpreti Cint o Ch. Tutte queste sono implementazioni C. Alcuni di essi sono più lenti di altri, ma la velocità non può essere attribuita a C in ogni caso!

6.3.2.1 dello standard C dice:

Tranne quando è l'operando dell'operatore sizeof, l'operatore _Alignof , o l'unario & dell'operatore, o è una stringa letterale utilizzata per inizializza una matrice, un'espressione con tipo '' array di tipo '' è convertita in un'espressione con tipo '' puntatore a tipo '' che punta all'elemento iniziale dell'oggetto matrice e non è un lvalue.

Questo dovrebbe essere un'indicazione che sia *(ap+1) e a[1] nel codice sono operazioni puntatore. Questa traduzione avverrà durante la fase di compilazione in Visual Studio. Quindi, questo non dovrebbe avere alcun impatto sul runtime.

6.5.2.1 riferimento a "matrice indicizzazione di" dice:

Una delle espressioni avranno tipo '' puntatore completare oggetto tipo '', l'altra espressione ha tipo intero, e il risultato ha tipo ' 'genere''. Questo sembra indicare che l'array pedice operatore è in realtà un operatore di puntatore ...

Questa è la conferma che ap[1] è davvero un'operazione puntatore, come abbiamo ipotizzato in precedenza. Al momento dell'esecuzione, tuttavia, l'array è già stato convertito in un puntatore. Le prestazioni dovrebbero essere identiche.

... quindi, perché non sono identici?

Quali sono le caratteristiche del sistema operativo in uso? Non è un sistema operativo multitasking e multiutente? Supponiamo che il sistema operativo completasse il primo ciclo senza interruzioni, ma poi interrompe il secondo ciclo e cambia il controllo in un altro processo. Questa interruzione non invaliderebbe il tuo esperimento? Come si misurano la frequenza e i tempi delle interruzioni causate dalla commutazione delle attività? Si noti che questo sarà diverso per i diversi SO e il SO è parte dell'implementazione .

Quali sono le caratteristiche della CPU che si sta utilizzando? Ha la propria cache interna veloce per il codice macchina? Supponiamo che l'intero primo ciclo, e il suo meccanismo di tempificazione completo, si inserisca bene nella cache del codice, ma il secondo ciclo sia stato troncato. Questo non comporterebbe un errore di cache e una lunga attesa mentre la CPU recupera il resto del codice dalla RAM? Come si misurano i tempi delle interruzioni causate da errori di cache? Si noti che questo sarà diverso per le diverse CPU e la CPU fa parte dell'implementazione .

Queste domande dovrebbero sollevare alcune domande come "Questo benchmark di micro-ottimizzazione risolve un problema significativo o significativo?". Il successo di un'ottimizzazione varia a seconda delle dimensioni e della complessità del problema. Trova un problema importante, risolvilo, profila la soluzione, ottimizzala e profila di nuovo. In questo modo, è possibile fornire informazioni significative su quanto più veloce è la versione ottimizzata. Il tuo capo sarà molto più felice con te, a patto che tu non divulga che le ottimizzazioni sono probabilmente rilevanti solo per l'implementazione , come ho detto prima. Sono certo che scoprirai che l'ultima delle tue preoccupazioni sarà array dereference vs pointer dereference.