optimización del acceso a los miembros en C++

Question

estoy corriendo en un comportamiento de optimización incompatibles con diferentes compiladores para el siguiente código:

class tester 
{ 
public: 
    tester(int* arr_, int sz_) 
     : arr(arr_), sz(sz_) 
    {} 

    int doadd() 
    { 
     sm = 0; 
     for (int n = 0; n < 1000; ++n) 
     { 
      for (int i = 0; i < sz; ++i) 
      { 
       sm += arr[i]; 
      } 
     } 
     return sm; 
    } 
protected: 
    int* arr; 
    int sz; 
    int sm; 
}; 

La función doadd simula algún acceso intensivo a los miembros (ignorar los desbordamientos, además de esta pregunta). En comparación con un código similar implementado como una función:

int arradd(int* arr, int sz) 
{ 
    int sm = 0; 
    for (int n = 0; n < 1000; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
     { 
      sm += arr[i]; 
     } 
    } 
    return sm; 
} 

El método doadd corre alrededor de 1,5 veces más lento que la función dearradd cuando se compila en modo de lanzamiento con Visual C++ 2008. Cuando modifico el método doadd a ser como sigue (Aliasing todos los miembros con los lugareños):

int doadd() 
{ 
    int mysm = 0; 
    int* myarr = arr; 
    int mysz = sz; 
    for (int n = 0; n < 1000; ++n) 
    { 
     for (int i = 0; i < mysz; ++i) 
     { 
      mysm += myarr[i]; 
     } 
    } 
    sm = mysm; 
    return sm; 
} 

Runtimes se convierten en más o menos lo mismo. ¿Estoy en lo cierto al concluir que esta es una optimización faltante por el compilador de Visual C++? g++ parece hacerlo mejor y ejecutar tanto la función de miembro como la función normal a la misma velocidad al compilar con -O2 o -O3.

---

La evaluación comparativa se realiza mediante la invocación de la función de doadd miembro y arradd en algunos suficientemente grande array (unos pocos millones de números enteros en tamaño).

---

EDIT: Algunas pruebas de grano fino muestra que el principal culpable es el miembro sm. Reemplazar todos los demás por las versiones locales todavía hace que el tiempo de ejecución sea largo, pero una vez que reemplazo sm por mysm, el tiempo de ejecución pasa a ser igual a la versión de la función.

---

Resolución

decepcionado con las respuestas (siento chicos), que Shaked de mi pereza y se sumergió en los listados de desmontaje de este código. Mi answer below resume los hallazgos. En resumen: no tiene nada que ver con el aliasing, tiene todo que ver con el desenrollado de bucles, y con algunas heurísticas extrañas se aplica MSVC al decidir qué bucle se debe desenrollar.

Answer 1

que desmontar el código con MSVC para entender mejor lo que está pasando. Resultó que el aliasing no era un problema en absoluto, y tampoco lo era algún tipo de seguridad paranoide hilo.

Aquí es la parte interesante de la función arradd disassambled:

for (int n = 0; n < 10; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
013C101C mov   ecx,ebp 
013C101E mov   ebx,29B9270h 
     { 
      sm += arr[i]; 
013C1023 add   eax,dword ptr [ecx-8] 
013C1026 add   edx,dword ptr [ecx-4] 
013C1029 add   esi,dword ptr [ecx] 
013C102B add   edi,dword ptr [ecx+4] 
013C102E add   ecx,10h 
013C1031 sub   ebx,1 
013C1034 jne   arradd+23h (13C1023h) 
013C1036 add   edi,esi 
013C1038 add   edi,edx 
013C103A add   eax,edi 
013C103C sub   dword ptr [esp+10h],1 
013C1041 jne   arradd+16h (13C1016h) 
013C1043 pop   edi 
013C1044 pop   esi 
013C1045 pop   ebp 
013C1046 pop   ebx 

ecx puntos de la matriz, y podemos ver que el bucle interno es x4 desenrollado aquí - tenga en cuenta los cuatro add instrucciones consecutivas de siguientes direcciones, y ecx siendo avanzado por 16 bytes (4 palabras) a la vez dentro del ciclo.

Para la versión no optimizada de la función miembro, doadd:

int tester::doadd() 
{ 
    sm = 0; 
    for (int n = 0; n < 10; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
     { 
      sm += arr[i]; 
     } 
    } 
    return sm; 
} 

El desmontaje es (que es más difícil de encontrar ya que el compilador inlined en main):

int tr_result = tr.doadd(); 
013C114A xor   edi,edi 
013C114C lea   ecx,[edi+0Ah] 
013C114F nop    
013C1150 xor   eax,eax 
013C1152 add   edi,dword ptr [esi+eax*4] 
013C1155 inc   eax 
013C1156 cmp   eax,0A6E49C0h 
013C115B jl   main+102h (13C1152h) 
013C115D sub   ecx,1 
013C1160 jne   main+100h (13C1150h) 

Nota 2 cosas:

• La suma se almacena en un registro - edi. Por lo tanto, no hay aliasing "cuidado" tomado aquí. El valor de sm no se vuelve a leer todo el tiempo.edi se inicializa solo una vez y luego se usa como temporal. No ve su retorno ya que el compilador lo optimizó y usó edi directamente como el valor de retorno del código en línea.
• El ciclo no está desenrollado. ¿Por qué? No hay una buena razón.

Por último, aquí es una versión "optimizado" de la función miembro, con mysm manteniendo la suma local de forma manual:

int tester::doadd_opt() 
{ 
    sm = 0; 
    int mysm = 0; 
    for (int n = 0; n < 10; ++n) 
    { 
     for (int i = 0; i < sz; ++i) 
     { 
      mysm += arr[i]; 
     } 
    } 
    sm = mysm; 
    return sm; 
} 

La (de nuevo, en línea) desmontaje es:

int tr_result_opt = tr_opt.doadd_opt(); 
013C11F6 xor   edi,edi 
013C11F8 lea   ebp,[edi+0Ah] 
013C11FB jmp   main+1B0h (13C1200h) 
013C11FD lea   ecx,[ecx] 
013C1200 xor   ecx,ecx 
013C1202 xor   edx,edx 
013C1204 xor   eax,eax 
013C1206 add   ecx,dword ptr [esi+eax*4] 
013C1209 add   edx,dword ptr [esi+eax*4+4] 
013C120D add   eax,2 
013C1210 cmp   eax,0A6E49BFh 
013C1215 jl   main+1B6h (13C1206h) 
013C1217 cmp   eax,0A6E49C0h 
013C121C jge   main+1D1h (13C1221h) 
013C121E add   edi,dword ptr [esi+eax*4] 
013C1221 add   ecx,edx 
013C1223 add   edi,ecx 
013C1225 sub   ebp,1 
013C1228 jne   main+1B0h (13C1200h) 

El bucle aquí se desenrolla, pero solo x2.

Esto explica mis observaciones de diferencia de velocidad bastante bien. Para una matriz 175e6, la función ejecuta ~ 1.2 segundos, el miembro no optimizado ~ 1.5 segundos, y el miembro optimizado ~ 1.3 segundos. (Tenga en cuenta que esto puede diferir para usted, en otra máquina obtuve tiempos de ejecución más cercanos para las 3 versiones).

¿Qué pasa con gcc? Cuando se compiló con él, las 3 versiones corrieron a ~ 1.5 segundos. Sospechando la falta de desenrollamiento, miré el desarme de gcc y de hecho: gcc no desenrolla ninguna de las versiones.

Answer 2

Puede ser un problema de aliasing - el compilador no puede saber que la variable de instancia sm nunca será señalado por arr, por lo que tiene para tratar sm como si se tratara efectivamente volátil, y guardarlo en cada iteración. Puede hacer sm un tipo diferente para probar esta hipótesis. O simplemente use una suma local temporal (que se almacenará en caché en un registro) y asígnela al sm al final.

Answer 3

Como Paul escribió probablemente sea porque sm member se actualiza realmente cada vez en la memoria "real", mientras tanto el resumen local en la función se puede acumular en la variable de registro (después de la optimización del compilador).

Answer 4

Puede obtener problemas similares al pasar argumentos de puntero. Si le gusta ensuciarse las manos, puede encontrar la palabra clave restrict útil en el futuro.

http://developers.sun.com/solaris/articles/cc_restrict.html

Answer 5

Esto no es realmente el mismo código en absoluto. Si coloca las variables sm, arr y sz dentro de la clase en lugar de hacer que el tema sea local, el compilador no puede (fácilmente) adivinar que alguna otra clase no heredará de la clase test y desea tener acceso a estos miembros, haciendo algo como ` arr = &sm; doadd() ;. De ahora en adelante, el acceso a estas variables no se puede optimizar como pueden cuando son locales para funcionar.

Al final, la razón es básicamente la que señaló Paul, sm se actualiza en la memoria real cuando se usa un miembro de la clase, se puede almacenar en un registro cuando se está en una función. Las lecturas de memoria de add no deberían cambiar mucho el tiempo resultante, ya que se debe leer memomry de todos modos para obtener el valor.

En este caso, si la prueba no se exporta a otro módulo y no se alias indirectamente a algo exportado, y si no hay alias como en el ejemplo anterior. El compilador podría optimizar las escrituras intermedias para sm ... algunos compiladores como gcc parecen optimizar lo suficientemente agresivo como para detectar casos anteriores (también lo sería si la clase de prueba se exporta). Pero estas son conjeturas realmente difíciles. Todavía hay optimizaciones mucho más simples que los compiladores aún no realizan (como en línea a través de diferentes unidades de compilación).

Answer 6

MSVC es correcto, ya que es el único que, dado el código que hemos visto, está garantizado que funciona correctamente. GCC emplea optimizaciones que probablemente sean seguras en esta instancia específica, pero eso solo puede verificarse al ver más del programa.

Dado que sm no es una variable local, MSVC aparentemente asume que podría alias arr. Esa es una suposición bastante razonable: como arr está protegido, una clase derivada podría configurarlo para apuntar a sm, por lo que arrpodría alias sm.

GCC ve que en realidad no es el alias arr, por lo que no escribe sm en la memoria hasta después del bucle, que es mucho más rápido.

Es ciertamente posible crear una instancia de la clase para que arr apunte a sm, que MSVC manejaría, pero no lo haría GCC.

Suponiendo que sz > 1, la optimización de GCC está permitida en general.

Debido a que la función de los bucles sobre arr, tratándolo como un conjunto de elementos sz, llamando a la función con sz > 1 produciría un comportamiento indefinido si o no arr alias sm, y así GCC podría suponer con seguridad que No alias . Pero si sz == 1, o si el compilador no puede estar seguro de lo que podría ser el valor sz 's, entonces se corre el riesgo de que szpodría ser 1, y así arr y sm podría alias de manera perfectamente legal, y el código de GCC se rompería.

Así que lo más probable es que GCC simplemente se salga con la suya al incluir toda la información, y al ver que en este caso, no alias.

Answer 7

La clave es probable que doadd se escribe así si se hace el miembro de accesos explícita con this:

int doadd() 
{ 
    this->sm = 0; 

    for (int n = 0; n < 1000; ++n) 
    { 
     for (int i = 0; i < this->sz; ++i) 
     { 
      this->sm += this->arr[i]; 
     } 
    } 

    return this->sm; 
} 

ahí radica el problema: todos los miembros de la clase se accede a través del puntero this, mientras que arradd tiene todo variables en la pila. Para acelerarlo, ha encontrado que al mover todos los miembros a la pila como variables locales, la velocidad coincide con arradd. Esto indica que la direccionalidad this es responsable de la pérdida de rendimiento.

Por qué podría ser? Según tengo entendido, this generalmente se almacena en un registro, así que no creo que en última instancia sea más lento que solo acceder a la pila (que también se compensa con el puntero de la pila). Como señalan otras respuestas, probablemente sea el problema del alias el que genera un código menos óptimo: el compilador no puede decir si alguna de las direcciones de memoria se superpone. Actualización de sm también podría, en teoría, cambiar el contenido de arr, por lo que decide escribir el valor de sm a la memoria principal cada vez más que el seguimiento en un registro. Cuando las variables están en la pila, el compilador puede asumir que están todas en diferentes direcciones de memoria. El compilador no ve el programa tan claramente como usted: puede decir qué hay en la pila (porque así lo declaró), pero todo lo demás son solo direcciones de memoria arbitrarias que podrían ser cualquier cosa, en cualquier lugar, superponiendo cualquier otro puntero.

No me sorprende que la optimización en su pregunta (utilizando variables locales) no se realice; el compilador no solo deberá probar que la memoria arr no se superpone a nada apuntado por this, sino que también no se está actualizando las variables miembro hasta el final de la función es equivalente a la actualización de la versión no optimizada en toda la función. Eso puede ser mucho más complicado de lo que imaginas, especialmente si tomas concurrencia en la cuenta.