En C++, ¿debo molestarme con las variables de caché o dejar que el compilador haga la optimización?(Aliasing)

performance caching

Question

Considere el siguiente código ( p es de tipo unsigned char* y bitmap->width es de algún tipo entero, exactamente lo que se desconoce y depende de la versión de alguna biblioteca externa que estemos usando):

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

_{¿Vale la pena optimizarlo [..]}

¿Podría haber un caso en el que esto podría arrojar resultados más eficientes escribiendo:

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

... o es esto trivial para que el compilador optimice?

_{¿Cuál considerarías que es el código "mejor"?}

_{Nota del editor (Ike): para aquellos que se preguntan sobre el texto tachado, la pregunta original, como está redactada, estaba peligrosamente cerca del territorio fuera del tema y estaba muy cerca de ser cerrada a pesar de los comentarios positivos. Estos han sido eliminados. Sin embargo, no castiguen a los que respondieron que abordaron estas secciones afectadas de la pregunta.}

Answer 1

A menos que sepa exactamente cómo el compilador optimiza el código, es mejor hacer sus propias optimizaciones manteniendo la legibilidad y el diseño del código. Prácticamente es difícil verificar el código de ensamblaje para cada función que escribimos para las nuevas versiones del compilador.

Answer 2

El compilador no puede optimizar bitmap->width porque el valor de width se puede cambiar entre iteraciones. Hay algunas razones más comunes:

1. Multihilo. El compilador no puede predecir si otro hilo está a punto de cambiar el valor.
2. Modificación dentro del bucle, a veces no es simple saber si la variable se cambiará dentro del bucle.
3. Es llamada a la función, por ejemplo, iterator::end() o container::size() por lo que es difícil predecir si siempre se devuelve el mismo resultado.

Para resumir (mi opinión personal) para los lugares que requieren un alto nivel de optimización, debe hacerlo usted mismo, en otros lugares simplemente dejarlo, el compilador puede optimizarlo o no, si no hay una gran diferencia, la legibilidad del código es el objetivo principal.

Answer 3

A primera vista, pensé que el compilador podría generar un ensamblaje equivalente para ambas versiones con banderas de optimización activadas. Cuando lo revisé, me sorprendió ver el resultado:

Fuente unoptimized.cpp

nota: este código no está destinado a ser ejecutado.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    for (unsigned x = 0 ; x < static_cast<unsigned>(bitmap.width) ; ++x)
    {
        argv[x][0] = ''/0'';
    }
    return 0;
}

Fuente optimized.cpp

nota: este código no está destinado a ser ejecutado.

struct bitmap_t
{
    long long width;
} bitmap;

int main(int argc, char** argv)
{
    const unsigned width = static_cast<unsigned>(bitmap.width);
    for (unsigned x = 0 ; x < width ; ++x)
    {
        argv[x][0] = ''/0'';
    }
    return 0;
}

Compilacion

• $ g++ -s -O3 unoptimized.cpp
• $ g++ -s -O3 optimized.cpp

Ensamblaje (no optimizado)

    .file   "unoptimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    mov %eax, %edx
    addl    $1, %eax
    movq    (%rsi,%rdx,8), %rdx
    movb    $0, (%rdx)
    cmpl    bitmap(%rip), %eax
    jb  .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

Ensamblaje (optimizado.s)

    .file   "optimized.cpp"
    .text
    .p2align 4,,15
.globl main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    .cfi_personality 0x3,__gxx_personality_v0
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
    subl    $1, %eax
    leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L3:
    movq    (%rsi,%rax), %rdx
    addq    $8, %rax
    cmpq    %rcx, %rax
    movb    $0, (%rdx)
    jne .L3
.L2:
    xorl    %eax, %eax
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
.globl bitmap
    .bss
    .align 8
    .type   bitmap, @object
    .size   bitmap, 8
bitmap:
    .zero   8
    .ident  "GCC: (GNU) 4.4.7 20120313 (Red Hat 4.4.7-16)"
    .section    .note.GNU-stack,"",@progbits

diff

$ diff -uN unoptimized.s optimized.s
--- unoptimized.s   2015-11-24 16:11:55.837922223 +0000
+++ optimized.s 2015-11-24 16:12:02.628922941 +0000
@@ -1,4 +1,4 @@
-   .file   "unoptimized.cpp"
+   .file   "optimized.cpp"
    .text
    .p2align 4,,15
 .globl main
@@ -10,16 +10,17 @@
    movl    bitmap(%rip), %eax
    testl   %eax, %eax
    je  .L2
+   subl    $1, %eax
+   leaq    8(,%rax,8), %rcx
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
 .L3:
-   mov %eax, %edx
-   addl    $1, %eax
-   movq    (%rsi,%rdx,8), %rdx
+   movq    (%rsi,%rax), %rdx
+   addq    $8, %rax
+   cmpq    %rcx, %rax
    movb    $0, (%rdx)
-   cmpl    bitmap(%rip), %eax
-   jb  .L3
+   jne .L3
 .L2:
    xorl    %eax, %eax
    ret

El ensamblaje generado para la versión optimizada realmente carga ( lea ) la constante de width diferencia de la versión no optimizada que calcula el desplazamiento de width en cada iteración ( movq ).

Cuando tenga tiempo, eventualmente publico algún punto de referencia sobre eso. Buena pregunta.

Answer 4

Como regla general, deje que el compilador haga la optimización por usted, hasta que determine que debe hacerse cargo. La lógica de esto no tiene nada que ver con el rendimiento, sino con la legibilidad humana. En la gran mayoría de los casos, la legibilidad de su programa es más importante que su rendimiento. Debería apuntar a escribir código que sea más fácil de leer para un humano, y luego solo preocuparse por la optimización cuando esté convencido de que el rendimiento es más importante que la capacidad de mantenimiento de su código.

Una vez que vea que el rendimiento es importante, debe ejecutar un generador de perfiles en el código para determinar qué bucles son ineficientes y optimizarlos individualmente. De hecho, puede haber casos en los que desee hacer esa optimización (especialmente si migra hacia C ++, donde los contenedores STL se involucran), pero el costo en términos de legibilidad es excelente.

Además, puedo pensar en situaciones patológicas en las que realmente podría ralentizar el código. Por ejemplo, considere el caso en el que el compilador no pudo probar que bitmap->width era constante durante el proceso. Al agregar la variable de width , obliga al compilador a mantener una variable local en ese ámbito. Si, por alguna razón específica de la plataforma, esa variable adicional impidió cierta optimización del espacio de pila, es posible que tenga que reorganizar cómo está emitiendo códigos de bytes y producir algo menos eficiente.

Como ejemplo, en Windows x64, uno está obligado a llamar a una llamada API especial, __chkstk en el preámbulo de la función si la función usará más de 1 página de variables locales. Esta función le da a Windows la oportunidad de administrar las páginas de protección que usan para expandir la pila cuando sea necesario. Si su variable adicional empuja el uso de la pila hacia arriba desde debajo de 1 página a 1 o más arriba, su función ahora está obligada a llamar a __chkstk cada vez que se ingresa. Si tuviera que optimizar este bucle en una ruta lenta, ¡en realidad podría ralentizar la ruta rápida más de lo que guardó en la ruta lenta!

Claro, es un poco patológico, pero el punto de ese ejemplo es que en realidad puedes ralentizar el compilador. Simplemente muestra que tiene que perfilar su trabajo para determinar a dónde van las optimizaciones. Mientras tanto, no sacrifique la legibilidad de ninguna manera por una optimización que pueda o no importar.

Answer 5

El compilador puede optimizar muchas cosas. Para su ejemplo, debe optar por la legibilidad, la mantenibilidad y lo que sigue su código estándar. Para obtener más información sobre lo que se puede optimizar (con GCC), consulte esta publicación de blog .

Answer 6

En realidad, no hay información suficiente de su fragmento de código para poder decirlo, y lo único que se me ocurre es el alias. Desde nuestro punto de vista, está bastante claro que no desea que p bitmap de bitmap apunten a la misma ubicación en la memoria, pero el compilador no lo sabe y (porque p es del tipo char* ) el compilador tiene que hacer este código funciona incluso si p y el bitmap superponen.

Esto significa en este caso que si el bucle cambia bitmap->width través del puntero p entonces eso debe verse al volver a leer bitmap->width más adelante, lo que a su vez significa que almacenarlo en una variable local sería ilegal.

Dicho esto, creo que algunos compiladores en realidad a veces generan dos versiones del mismo código (he visto evidencia circunstancial de esto, pero nunca busqué información directamente sobre lo que está haciendo el compilador en este caso), y comprueban rápidamente si los punteros alias y ejecuta el código más rápido si determina que está bien hacerlo.

Dicho esto, mantengo mi comentario sobre simplemente medir el rendimiento de las dos versiones, mi dinero está en no ver ninguna diferencia de rendimiento consistente entre las dos versiones del código.

En mi opinión, preguntas como estas están bien si su propósito es aprender sobre las teorías y técnicas de optimización del compilador, pero es una pérdida de tiempo (una microoptimización inútil) si su objetivo final aquí es hacer que el programa se ejecute más rápido.

Answer 7

Hay dos cosas a considerar.

A) ¿Con qué frecuencia se ejecutará la optimización?

Si la respuesta no es muy frecuente, como cuando un usuario hace clic en un botón, no se preocupe si hace que su código sea ilegible. Si la respuesta es 1000 veces por segundo, entonces probablemente querrá ir con la optimización. Si es incluso un poco complejo, asegúrese de poner un comentario para explicar lo que está sucediendo para ayudar al próximo tipo que aparece.

B) ¿Esto hará que el código sea más difícil de mantener / solucionar?

Si no está viendo una gran ganancia en el rendimiento, entonces hacer que su código sea críptico simplemente para ahorrar unos pocos tics de reloj no es una buena idea. Mucha gente le dirá que cualquier buen programador debería poder mirar el código y descubrir qué está sucediendo. Esto es verdad. El problema es que en el mundo de los negocios, el tiempo extra que se calcula cuesta dinero. Entonces, si puedes hacerlo más bonito para leer, entonces hazlo. Tus amigos te lo agradecerán.

Dicho esto, personalmente usaría el ejemplo B.

Answer 8

La comparación es incorrecta ya que los dos fragmentos de código

for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)

y

unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x<width ;  ++x)

no son equivalentes

En el primer caso, el width depende y no es constante, y uno no puede suponer que no puede cambiar entre iteraciones posteriores. Por lo tanto, no se puede optimizar, pero se debe verificar en cada bucle .

En su caso optimizado, a una variable local se le asigna el valor de bitmap->width en algún momento durante la ejecución del programa. El compilador puede verificar que esto realmente no cambie.

¿Pensó en subprocesos múltiples o tal vez el valor podría depender externamente de modo que su valor sea volátil? ¿Cómo cabría esperar que el compilador resuelva todas estas cosas si no se lo cuenta?

El compilador solo puede funcionar tan bien como lo permite su código.

Answer 9

La pregunta originalmente formulada:

¿Vale la pena optimizarlo?

Y mi respuesta a eso (obteniendo una buena combinación de votos positivos y negativos ...)

Deje que el compilador se preocupe por eso.

El compilador seguramente hará un mejor trabajo que usted. Y no hay garantía de que su ''optimización'' sea mejor que el código ''obvio'': ¿lo ha medido?

Más importante aún, ¿tiene alguna prueba de que el código que está optimizando tiene algún impacto en el rendimiento de su programa?

A pesar de los votos negativos (y ahora viendo el problema de alias), todavía estoy contento con eso como una respuesta válida. Si no sabe si vale la pena optimizar algo, probablemente no lo sea.

Una pregunta bastante diferente, por supuesto, sería esta:

¿Cómo puedo saber si vale la pena optimizar un fragmento de código?

Primero, ¿su aplicación o biblioteca necesita ejecutarse más rápido de lo que lo hace actualmente? ¿El usuario ha estado esperando demasiado? ¿Su software pronostica el clima de ayer en lugar del de mañana?

Solo usted realmente puede decir esto, en función de para qué es su software y qué esperan sus usuarios.

Suponiendo que su software necesita algo de optimización, lo siguiente que debe hacer es comenzar a medir. Los perfiladores le dirán dónde gasta su código su tiempo. Si su fragmento no se muestra como un cuello de botella, es mejor dejarlo solo. Los perfiladores y otras herramientas de medición también le dirán si sus cambios han marcado la diferencia. Es posible pasar horas intentando optimizar el código, solo para descubrir que no ha hecho una diferencia apreciable.

¿Qué quieres decir con ''optimizar'', de todos modos?

Si no está escribiendo código ''optimizado'', entonces su código debe ser tan claro, limpio y conciso como pueda hacerlo. El argumento "La optimización prematura es malvada" no es una excusa para un código descuidado o ineficiente.

El código optimizado normalmente sacrifica algunos de los atributos anteriores por el rendimiento. Podría implicar la introducción de variables locales adicionales, tener objetos con un alcance más amplio de lo esperado o incluso invertir el orden normal del bucle. Todos estos pueden ser menos claros o concisos, así que documente el código (¡brevemente!) Sobre por qué está haciendo esto.

Pero a menudo, con el código ''lento'', estas microoptimizaciones son el último recurso. El primer lugar para mirar es en algoritmos y estructuras de datos. ¿Hay alguna forma de evitar hacer el trabajo? ¿Se pueden reemplazar las búsquedas lineales por las binarias? ¿Una lista vinculada sería más rápida aquí que un vector? O una tabla hash? ¿Puedo guardar en caché los resultados? ¡Tomar buenas decisiones ''eficientes'' aquí a menudo puede afectar el rendimiento en un orden de magnitud o más!

Answer 10

Lo único aquí que puede evitar la optimización es la estricta regla de alias . En resumen :

"El alias estricto es una suposición, hecha por el compilador de C (o C ++), de que la referencia de punteros a objetos de diferentes tipos nunca se referirá a la misma ubicación de memoria (es decir, alias entre sí)".

[...]

La excepción a la regla es un char* , que puede apuntar a cualquier tipo.

La excepción también se aplica a los punteros de caracteres unsigned y signed .

Este es el caso en su código: está modificando *p a p que es un unsigned char* , por lo que el compilador debe suponer que podría apuntar a bitmap->width . Por lo tanto, el almacenamiento en caché de bitmap->width es una optimización no válida. Este comportamiento de prevención de optimización se muestra en la respuesta de YSC .

Si y solo si p apunta a un tipo que no es de tipo char y sin tipo de decltype(bitmap->width) , el almacenamiento en caché sería una posible optimización.

Answer 11

Ok, muchachos, así que he medido con GCC -O3 (usando GCC 4.9 en Linux x64).

Resulta que la segunda versión funciona un 54% más rápido.

Entonces, supongo que el alias es la cosa, no lo había pensado.

[Editar]

Intenté nuevamente la primera versión con todos los punteros definidos con __restrict__ , y los resultados son los mismos. Extraño ... El alias no es el problema o, por alguna razón, el compilador no lo optimiza bien incluso con __restrict__ .

[Editar 2]

Ok, creo que pude demostrar que el problema es el alias. Repetí mi prueba original, esta vez usando una matriz en lugar de un puntero:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
for (unsigned x = 0;  x < static_cast<unsigned>(bitmap->width);  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

Y medido (tenía que usar "-mcmodel = large" para vincularlo). Entonces intenté:

const std::size_t n = 0x80000000ull;
bitmap->width = n;
static unsigned char d[n*3];
std::size_t i=0;
unsigned width(static_cast<unsigned>(bitmap->width));
for (unsigned x = 0;  x < width;  ++x)
{
    d[i++] = 0xAA;
    d[i++] = 0xBB;
    d[i++] = 0xCC;
}

Los resultados de la medida fueron los mismos: parece que el compilador pudo optimizarlo por sí mismo.

Luego probé los códigos originales (con un puntero p ), esta vez cuando p es de tipo std::uint16_t* . Nuevamente, los resultados fueron los mismos, debido al alias estricto. Luego intenté construir con "-fno-estricto-aliasing", y nuevamente vi una diferencia en el tiempo.

Answer 12

Otras respuestas han señalado que levantar la operación del puntero fuera del bucle puede cambiar el comportamiento definido debido a las reglas de alias que permiten que char alias cualquier cosa y, por lo tanto, no es una optimización permitida para un compilador, aunque en la mayoría de los casos es obviamente correcto para un humano programador.

También han señalado que elevar la operación fuera del circuito suele ser, pero no siempre, una mejora desde el punto de vista del rendimiento y, a menudo, es negativo desde el punto de vista de la legibilidad.

Me gustaría señalar que a menudo hay una "tercera vía". En lugar de contar hasta la cantidad de iteraciones que desea, puede contar hasta cero. Esto significa que el número de iteraciones solo se necesita una vez al comienzo del ciclo, no tiene que almacenarse después de eso. Mejor aún en el nivel de ensamblador, a menudo elimina la necesidad de una comparación explícita ya que la operación de disminución generalmente establecerá indicadores que indican si el contador era cero tanto antes (indicador de acarreo) como después (indicador de cero) del decremento.

for (unsigned x = static_cast<unsigned>(bitmap->width);x > 0;  x--)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

Tenga en cuenta que esta versión del bucle da valores x en el rango 1..ancho en lugar del rango 0 .. (ancho-1). Eso no importa en su caso porque en realidad no está utilizando x para nada, pero es algo a tener en cuenta. Si desea un ciclo de cuenta regresiva con valores x en el rango 0 .. (ancho-1) puede hacerlo.

for (unsigned x = static_cast<unsigned>(bitmap->width); x-- > 0;)
{
    *p++ = 0xAA;
    *p++ = 0xBB;
    *p++ = 0xCC;
}

También puede deshacerse de los moldes en los ejemplos anteriores si lo desea sin preocuparse por su impacto en las reglas de comparación, ya que todo lo que está haciendo con bitmap-> width es asignarlo directamente a una variable.

Answer 13

Utilizo el siguiente patrón en una situación como esta. Es casi tan corto como el primer caso suyo, y es mejor que el segundo caso, ya que mantiene la variable temporal local en el bucle.

for (unsigned int x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
{
  *p++ = 0xAA;
  *p++ = 0xBB;
  *p++ = 0xCC;
}

Esto será más rápido con un compilador menos inteligente, compilación de depuración o ciertos indicadores de compilación.

Edit1 : colocar una operación constante fuera de un bucle es un buen patrón de programación. Muestra comprensión de los conceptos básicos del funcionamiento de la máquina, especialmente en C / C ++. Yo diría que el esfuerzo para demostrar su valía debe ser en personas que no siguen esta práctica. Si el compilador castiga por un buen patrón, es un error en el compilador.

Edit2:: he medido mi sugerencia contra el código original en vs2013, obtuve% 1 de mejora. ¿Podemos hacerlo mejor? Una simple optimización manual ofrece una mejora 3 veces superior al bucle original en la máquina x64 sin recurrir a instrucciones exóticas. El siguiente código supone un pequeño sistema endian y un mapa de bits correctamente alineado. TEST 0 es original (9 segundos), TEST 1 es más rápido (3 segundos). Apuesto a que alguien podría hacer esto aún más rápido, y el resultado de la prueba dependería del tamaño del mapa de bits. Definitivamente pronto en el futuro, el compilador podrá producir código consistentemente más rápido. Me temo que este será el futuro cuando el compilador también sea un programador AI, por lo que estaríamos sin trabajo. Pero por ahora, solo escriba código que muestre que sabe que no se necesita una operación adicional en el ciclo.

#include <memory>
#include <time.h>

struct Bitmap_line
{
  int blah;
  unsigned int width;
  Bitmap_line(unsigned int w)
  {
    blah = 0;
    width = w;
  }
};

#define TEST 0 //define 1 for faster test

int main(int argc, char* argv[])
{
  unsigned int size = (4 * 1024 * 1024) / 3 * 3; //makes it divisible by 3
  unsigned char* pointer = (unsigned char*)malloc(size);
  memset(pointer, 0, size);
  std::unique_ptr<Bitmap_line> bitmap(new Bitmap_line(size / 3));
  clock_t told = clock();
#if TEST == 0
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    for (unsigned x = 0; x < static_cast<unsigned>(bitmap->width); ++x)
    //for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#else
  for (int iter = 0; iter < 10000; iter++)
  {
    unsigned char* p = pointer;
    unsigned x = 0;
    for (const unsigned n = static_cast<unsigned>(bitmap->width) - 4; x < n; x += 4)
    {
      *(int64_t*)p = 0xBBAACCBBAACCBBAALL;
      p += 8;
      *(int32_t*)p = 0xCCBBAACC;
      p += 4;
    }

    for (const unsigned n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      *p++ = 0xAA;
      *p++ = 0xBB;
      *p++ = 0xCC;
    }
  }
#endif
  double ms = 1000.0 * double(clock() - told) / CLOCKS_PER_SEC;
  printf("time %0.3f/n", ms);

  {
    //verify
    unsigned char* p = pointer;
    for (unsigned x = 0, n = static_cast<unsigned>(bitmap->width); x < n; ++x)
    {
      if ((*p++ != 0xAA) || (*p++ != 0xBB) || (*p++ != 0xCC))
      {
        printf("EEEEEEEEEEEEERRRRORRRR!!!/n");
        abort();
      }
    }
  }

  return 0;
}