Che cos'è l'aliasing e in che modo influisce sulle prestazioni?

Question

Alla manifestazione GoingNative, durante la Interactive Panel sul Day2 a segno nove minuti, Chandler Carruth dice:

Puntatori creano problemi di aliasing. Rallentano i tuoi binari e non li velocizzano.

Cosa significa? Questo può essere illustrato con un (semplice) esempio?

Answer 1

L'aliasing influisce sulle prestazioni impedendo al compilatore di eseguire determinate ottimizzazioni. Per esempio:

void foo(int *array,int *size,int *value) { 
    for(int i=0;i<*size;++i) { 
     array[i] = 2 * *value; 
    } 
} 

Osservando questo codice si potrebbe aspettare che il compilatore è riuscito a caricare *value una volta al di fuori del ciclo e quindi impostare ogni elemento della matrice per quel valore molto rapidamente. Ma questo non è il caso a causa dell'aliasing. Perché *value potrebbe essere un alias per un elemento dell'array che potrebbe cambiare in una determinata iterazione. Pertanto, il codice deve caricare il valore ogni singola iterazione, determinando un rallentamento potenzialmente grande.

Se le variabili non potevano alias allora il codice di cui sopra sarebbe equivalente al seguente:

void foo(int *array,int size,int value) { 
    for(int i=0;i<size;++i) { 
     array[i] = 2 * value; 
    } 
} 

Utilizzando LLVM di online demo per ottenere il codice generato, ecco i risultati diversi:

1) con aliasing

foo:         # @foo 
    .cfi_startproc 
# BB#0: 
    cmpl $0, (%rsi) 
    jle .LBB0_3 
# BB#1: 
    xorl %eax, %eax 
    .align 16, 0x90 
.LBB0_2:        # %.lr.ph 
             # =>This Inner Loop Header: Depth=1 
    movl (%rdx), %ecx 
    addl %ecx, %ecx 
    movl %ecx, (%rdi,%rax,4) 
    incq %rax 
    cmpl (%rsi), %eax 
    jl .LBB0_2 
.LBB0_3:        # %._crit_edge 
    ret 
    .size foo, .Ltmp1-foo 
    .cfi_endproc 
.Leh_func_end0: 

---

2) Senza aliasing

foo:         # @foo 
    .cfi_startproc 
# BB#0: 
    testl %esi, %esi 
    jle .LBB0_3 
# BB#1:         # %.lr.ph 
    addl %edx, %edx 
    .align 16, 0x90 
.LBB0_2:        # =>This Inner Loop Header: Depth=1 
    movl %edx, (%rdi) 
    addq $4, %rdi 
    decl %esi 
    jne .LBB0_2 
.LBB0_3:        # %._crit_edge 
    ret 
    .size foo, .Ltmp1-foo 
    .cfi_endproc 
.Leh_func_end0: 

Si può vedere che la versione con aliasing ha a che fare più lavoro nel corpo del ciclo (tra le etichette LBB0_2 e LBB0_3).

Answer 2

un puntatore è un valore che rappresenta un indirizzo di memoria a volte 2 puntatori può rappresentare gli stessi questo è indirizzo di memoria ciò aliasing è

int * p; 
*p = 5; 

int * alias; 
alias = p; 

variabile alias è un alias di p e *alias è uguale a 5 se cambiare *alias poi *p modifiche con esso

Answer 3

Il tipo di problema Chandler stava parlando può essere facilmente illustrato con una semplificata strcpy:

char *stpcpy (char * dest, const char * src); 

Durante la scrittura di un'implementazione di questo, è possibile presumere che la memoria indicata da dest sia completamente separata dalla memoria indicata da src. Il compilatore) potrebbe voler ottimizzarlo leggendo un blocco di caratteri dalla stringa puntata da src e scrivendoli tutti contemporaneamente in dest. Ma se dest puntava a un byte prima di src, il comportamento di questo sarebbe diverso da una semplice copia carattere per carattere.

Qui il problema aliasing è che src può alias dest, e il codice generato deve essere effettuato meno efficiente di quanto potrebbe essere se src non è stato permesso di alias dest.

Il vero strcpy utilizza una parola chiave in più, Restrict (che è technically only part of C, not C++, che dice al compilatore di supporre che src e dest non si sovrappongono, e questo permette al compilatore di generare codice molto più efficiente.

---

Ecco un esempio ancora più semplice in cui possiamo vedere una grande differenza nel montaggio:

void my_function_1(int* a, int* b, int* c) { 
    if (*a) *b = *a; 
    if (*a) *c = *a; 
} 

void my_function_2(int* __restrict a, int* __restrict b, int* __restrict c) { 
    if (*a) *b = *a; 
    if (*a) *c = *a; 
} 

supporre che questa è una semplificazione di una funzione in cui in realtà aveva senso usare due if-statement anziché solo if (*a) { *b=*a; *c=*a; }, ma l'intento è lo stesso.

Si può presumere quando si scrive questo a != b perché c'è qualche motivo per cui non avrebbe senso utilizzare my_function in questo modo.Ma il compilatore non può supporre che, e fa un negozio di b e una ri-carico di a dalla memoria prima di eseguire la seconda linea, per coprire il caso in cui b == a:

0000000000400550 <my_function_1>: 
    400550:  8b 07     mov (%rdi),%eax 
    400552:  85 c0     test %eax,%eax     <= if (*a) 
    400554:  74 0a     je  400560 <my_function_1+0x10> 
    400556:  89 06     mov %eax,(%rsi) 
    400558:  8b 07     mov (%rdi),%eax 
    40055a:  85 c0     test %eax,%eax     <= if (*a) 
    40055c:  74 02     je  400560 <my_function_1+0x10> 
    40055e:  89 02     mov %eax,(%rdx) 
    400560:  f3 c3     repz retq 

se togliamo potenziale di aliasing aggiungendo __restrict, il compilatore genera codice più corto e più veloce:

0000000000400570 <my_function_2>: 
    400570:  8b 07     mov (%rdi),%eax 
    400572:  85 c0     test %eax,%eax 
    400574:  74 04     je  40057a <_Z9my_function_2PiS_S_+0xa> 
    400576:  89 06     mov %eax,(%rsi) 
    400578:  89 02     mov %eax,(%rdx) 
    40057a:  f3 c3     repz retq 

Answer 4

Si consideri la seguente funzione:

void f(float* lhs, float* rhs, float* out, int size) { 
    for(int i = 0; i < size; i++) { 
     out[i] = *lhs + *rhs; 
    } 
} 

Qual è la versione più veloce di questa funzione? Probabilmente, hai sollevato *lhs + *rhs dal ciclo. Il problema è che cosa succede quando i puntatori sono alias. Immaginate cosa che l'ottimizzazione fa se io lo chiamo così:

float arr[6] = { ... }; 
f(arr, arr + 1, arr, 6); 

Come si può vedere, il problema è che *lhs + *rhs non può essere issata fuori dal giro, perché out[i] modifica i loro valori. In effetti, il compilatore non può sollevare nessuna logica fuori dal ciclo. Quindi il compilatore non può eseguire l'ottimizzazione "ovvia", perché se i parametri alias la logica è ora errata. Tuttavia, se i float sono presi in base al valore, il compilatore sa che non possono alias e possono eseguire il sollevamento.

Naturalmente, questa funzione è piuttosto stupida, ma dimostra il punto.