¿El compilador desenrollará este ciclo?

Question

Estoy creando un vector multidimensional (vector matemático) donde permití operaciones matemáticas básicas +, -, /, *, =. La plantilla toma dos parámetros, uno es el tipo (int, float, etc.) mientras que el otro es el tamaño del vector. Actualmente estoy aplicando las operaciones a través de un ciclo for. Ahora, considerando que el tamaño es conocido en tiempo de compilación, ¿el compilador desenrollará el ciclo? De lo contrario, ¿hay alguna manera de desenrollarlo sin una penalización de rendimiento (o mínima)?

template <typename T, u32 size> 
class Vector 
{ 
public: 
    // Various functions for mathematical operations. 
    // The functions take in a Vector<T, size>. 
    // Example: 
    void add(const Vector<T, size>& vec) 
    { 
     for (u32 i = 0; i < size; ++i) 
     { 
      values[i] += vec[i]; 
     } 
    } 

private: 
    T values[size]; 
}; 

Antes de que alguien comenta Profile then optimize tenga en cuenta que esta es la base de mi motor de gráficos en 3D y tiene que ser rápido. En segundo lugar, quiero saber por el bien de educarme a mí mismo.

Answer 1

Puede realizar el siguiente truco con desmontaje para ver cómo se compila el código en particular.

Vector<int, 16> a, b; 
    Vector<int, 65536> c, d; 

    asm("xxx"); // marker 
    a.Add(b); 
    asm("yyy"); // marker 
    c.Add(d); 
    asm("zzz"); // marker 

Ahora compila

gcc -O3 1.cc -S -o 1.s 

y ver la disasm

xxx 
# 0 "" 2 
#NO_APP 
    movdqa 524248(%rsp), %xmm0 
    leaq 524248(%rsp), %rsi 
    paddd 524184(%rsp), %xmm0 
    movdqa %xmm0, 524248(%rsp) 
    movdqa 524264(%rsp), %xmm0 
    paddd 524200(%rsp), %xmm0 
    movdqa %xmm0, 524264(%rsp) 
    movdqa 524280(%rsp), %xmm0 
    paddd 524216(%rsp), %xmm0 
    movdqa %xmm0, 524280(%rsp) 
    movdqa 524296(%rsp), %xmm0 
    paddd 524232(%rsp), %xmm0 
    movdqa %xmm0, 524296(%rsp) 
#APP 
# 36 "1.cc" 1 
    yyy 
# 0 "" 2 
#NO_APP 
    leaq 262040(%rsp), %rdx 
    leaq -104(%rsp), %rcx 
    xorl %eax, %eax 
    .p2align 4,,10 
    .p2align 3 
.L2: 
    movdqa (%rcx,%rax), %xmm0 
    paddd (%rdx,%rax), %xmm0 
    movdqa %xmm0, (%rdx,%rax) 
    addq $16, %rax 
    cmpq $262144, %rax 
    jne .L2 
#APP 
# 38 "1.cc" 1 
    zzz 

Como se ve, el primer bucle era lo suficientemente pequeño como para ser desenrollado. El segundo es el bucle.

Answer 2

Muchos compiladores desenrollarán este ciclo, no se sabe si "el compilador" al que te refieres lo hará. No hay solo un compilador en el mundo.

Si desea garantizar que se desenrolla, entonces TMP (con alineación) puede hacerlo. (Esta es en realidad una de las aplicaciones más triviales de TMP, a menudo utilizada como un ejemplo de metaprogramación).

Answer 3

Primero: las CPU modernas son bastante inteligentes para predecir las ramas, por lo que desenrollar el ciclo podría no ser de ayuda (e incluso podría dañar).

Segundo: Sí, los compiladores modernos saben cómo desenrollar un bucle como este, si es una buena idea para su CPU objetivo.

Tercero: los compiladores modernos incluso pueden auto-vectorizar el ciclo, que es incluso mejor que desenrollarlo.

Conclusión: No creo que sea más inteligente que su compilador a menos que conozca un lote sobre la arquitectura de la CPU. Escriba su código de una manera simple y directa, y no se preocupe por las micro-optimizaciones hasta que su perfilador se lo indique.

Answer 4

En primer lugar, no es del todo cierto que desenrollar el lazo sería beneficioso.

La única respuesta posible a su pregunta es "depende" (en los indicadores del compilador, en el valor de size, etc.).

Si realmente desea saber, pregunte a su compilador: compilar en el código de ensamblado con los valores típicos de size y con los indicadores de optimización que utilizaría para reales, y examinar el resultado.

Answer 5

La única manera de resolver esto es probarlo en su propio compilador con sus propios parámetros de optimización. Hacer un archivo de prueba con el código "no se desenrolla", test.cpp:

#include "myclass.hpp" 

void doSomething(Vector<double, 3>& a, Vector<double, 3>& b) { 
    a.add(b); 
} 

entonces un código de referencia fragmento reference.cpp:

#include "myclass.hpp" 

void doSomething(Vector<double, 3>& a, Vector<double, 3>& b) { 
    a[0] += b[0]; 
    a[1] += b[1]; 
    a[2] += b[2]; 
} 

y ahora usar GCC para compilar y escupir sólo el montaje:

for x in *.cpp; do g++ -c "$x" -Wall -Wextra -O2 -S -o "out/$x.s"; done 

en mi experiencia, GCC desenrollar bucles de 3 o menos de forma predeterminada cuando se utilizan bucles cuya duración se conocen en tiempo de compilación; usar el -funroll-loops hará que se desenrolle aún más.

Answer 6

El bucle se puede desenrollar utilizando la creación de instancias recursivas de plantillas. Esto puede o no ser más rápido en su implementación de C++.

Ajusté su ejemplo ligeramente para que compilara.

typedef unsigned u32; // or something similar 

template <typename T, u32 size> 
class Vector 
{ 
    // need to use an inner class, because member templates of an 
    // unspecialized template cannot be explicitly specialized. 
    template<typename Vec, u32 index> 
    struct Inner 
    { 
    static void add(const Vec& a, const Vec& b) 
    { 
     a.values[index] = b.values[index]; 
     // triggers recursive instantiation of Inner 
     Inner<Vec, index-1>::add(a,b); 
    } 
    }; 
    // this specialization terminates the recursion 
    template<typename Vec> 
    struct Inner<Vec, 0> 
    { 
    static void add(const Vec& a, const Vec& b) 
    { 
     a.values[0] = b.values[0]; 
    } 
    }; 

public: 

    // PS! this function should probably take a 
    // _const_ Vector, because the argument is not modified 
    // Various functions for mathematical operations. 
    // The functions take in a Vector<T, size>. 
    // Example: 
    void add(Vector<T, size>& vec) 
    { 
     Inner<Vector, size-1>::add(*this, vec); 
    } 

    T values[size]; 
};