¿Qué es el aliasing y cómo afecta el rendimiento?

Question

En el evento GoingNative, durante el Interactive Panel el Día 2 en el minuto 9, Chandler Carruth dice:

Punteros crean problemas de solapamiento. Disminuyen la velocidad de tus binarios y no los aceleran.

¿Qué significa esto? ¿Esto se puede ilustrar con un ejemplo (simple)?

Answer 1

El alias afecta el rendimiento al impedir que el compilador realice ciertas optimizaciones. Por ejemplo:

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

En cuanto a este código se podría esperar que el compilador podría cargar *value una vez fuera del bucle y luego ajustar cada elemento de la matriz a ese valor muy rápidamente. Pero este no es el caso debido a aliasing. Debido a que *value podría ser un alias para un elemento de la matriz, podría cambiar en cualquier iteración dada. Por lo tanto, el código tiene que cargar el valor de cada iteración, lo que resulta en una desaceleración potencialmente grande.

Si las variables no podían alias continuación, el código anterior sería equivalente a lo siguiente:

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

Usando LLVM de online demo para obtener el código generado, aquí están los diferentes resultados:

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) Sin 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: 

Se puede ver que la versión con aliasing tiene que hacer más trabajo en el cuerpo del bucle (entre las etiquetas LBB0_2 y LBB0_3).

Answer 2

un puntero es un valor que representa una dirección de memoria a veces 2 punteros pueden representar los mismos eso de direcciones de memoria lo aliasing es

int * p; 
*p = 5; 

int * alias; 
alias = p; 

la variable alias es un alias de p y *alias es igual a 5 si cambiar *alias continuación *p cambios junto con él

Answer 3

El tipo de problema Chandler estaba hablando puede ser fácilmente ilustrado con un sistema simplificado strcpy:

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

Al escribir una implementación de esto, puede suponer que la memoria apuntada por dest está completamente separada de la memoria apuntada por src. El compilador) puede querer optimizarlo leyendo un bloque de caracteres de la cadena apuntada por src y escribiendo todos a la vez en dest. Pero si dest apunta a un byte delante de src, el comportamiento de esto diferiría de una simple copia de carácter por carácter.

Aquí el problema es que el aliasing src puede crear un alias dest, y el código generado debe ser menos eficiente de lo que podría ser si src no se le permitió alias dest.

El verdadero strcpy utiliza una palabra clave adicional, Restrict (que es technically only part of C, not C++, que le dice al compilador que asumir que src y dest no se solapan, y esto permite que el compilador generar código mucho más eficiente.

---

He aquí un ejemplo aún más simple en el que podemos ver una gran diferencia en la asamblea:

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

suponer que esto es una simplificación de una función donde en realidad tiene sentido usar dos declaraciones if en lugar de solo if (*a) { *b=*a; *c=*a; }, pero la intención es la misma.

Podemos suponer al escribir esto que a != b porque hay alguna razón por la que no tendría sentido que my_function se use así.Sin embargo, el compilador no puede asumir que, y lo hace de una tienda de b y una re-carga de a de la memoria antes de ejecutar la segunda línea, para cubrir el caso en que 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 

Si eliminamos potencial de aliasing añadiendo __restrict, el compilador genera código más corto y más rápido:

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

considera la siguiente función:

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

¿Cuál es la versión más rápida de esta función? Probablemente, levante *lhs + *rhs fuera del circuito. El problema es qué sucede cuando alias los punteros. Imagínese lo que hace que la optimización si llamo así:

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

Como se puede ver, el problema es que *lhs + *rhs no se puede elevar fuera del circuito, porque out[i] modifica sus valores. De hecho, el compilador no puede elevar ninguna lógica fuera del ciclo. Entonces el compilador no puede realizar la optimización "obvia", porque si los parámetros alias la lógica ahora es incorrecta. Sin embargo, si los flotadores se toman por valor, entonces el compilador sabe que no puede alias y puede realizar el alzamiento.

Por supuesto, esta función es bastante tonta, pero demuestra el punto.