¿Por qué GCC genera un programa más rápido que Clang en este código recursivo de Fibonacci?

 C Programming >> Programación C >  >> Tags >> Clang
¿Por qué GCC genera un programa más rápido que Clang en este código recursivo de Fibonacci?

GCC 4.9.2 en el explorador del compilador realmente desenrolla bucles e inserta muchas llamadas a funciones, mientras que Clang 3.5.1 llama a fib dos veces cada iteración sin siquiera la optimización de llamadas de cola como a continuación

fib(int):                                # @fib(int)
        push    rbp
        push    rbx
        push    rax
        mov     ebx, edi
        cmp     ebx, 2
        jge     .LBB0_1
        mov     eax, ebx
        jmp     .LBB0_3
.LBB0_1:
        lea     edi, dword ptr [rbx - 1]
        call    fib(int)       # fib(ebx - 1)
        mov     ebp, eax
        add     ebx, -2
        mov     edi, ebx
        call    fib(int)       # fib(ebx - 2)
        add     eax, ebp
.LBB0_3:
        add     rsp, 8
        pop     rbx
        pop     rbp
        ret

La versión GCC es más de 10 veces más larga, con solo un único fib llamada y más de 20 etiquetas para insertar la llamada , lo que también significa que la última llamada se ha optimizado para la cola en un jmp o GCC ha convertido parte de la recurrencia en iteración (ya que asigna una gran matriz para almacenar valores intermedios)

También he puesto a ICC en perspectiva, y sorprendentemente tiene 10 call instrucciones dentro de fib , y también en línea fib llama 9 veces dentro de main , pero no convierte el código recursivo en iterativo

Aquí están los resultados del compilador para comparar

Tenga en cuenta que puede modificar el código de esta manera para que la salida sea más fácil de leer

int fib(int n) {
    if (n<2) return n;
    int t = fib(n-1);
    return t + fib(n-2);
}

Ahora compilador explorador resaltará a qué línea de código fuente corresponde una instrucción en la salida del ensamblado con distintos colores, y verá fácilmente cómo se realizan las dos llamadas. La línea return t + fib(n-2) es compilado por GCC para

.L3:
        mov     eax, DWORD PTR [rsp+112]  # n, %sfp
        add     edx, DWORD PTR [rsp+64]   # D.35656, %sfp
        add     DWORD PTR [rsp+60], edx   # %sfp, D.35656
        sub     DWORD PTR [rsp+104], 2    # %sfp,

Yo no diría que gcc supera a clang por millas. En mi opinión, la diferencia de rendimiento (6,3 segundos frente a 9 segundos) es bastante pequeña. En mi sistema FreeBSD, clang requiere 26,12 segundos y gcc requiere 10,55 segundos.

Sin embargo, la forma de depurar esto es usar g++ -S y clang++ -S para obtener el resultado del ensamblado.

Probé esto en mi sistema FreeBSD. Los archivos de lenguaje ensamblador son demasiado largos para publicarlos aquí, pero parece que gcc realiza múltiples niveles de inserción en la función de cálculo de Fibonacci (había 20 fib() llamadas ahí!) mientras que clang simplemente llama a fib(n-1) y fib(n-2) sin niveles de inserción.

Por cierto, mi versión de gcc era 4.2.1 20070831 parcheada [FreeBSD] y la versión clang era 3.1 (branches/release_31 156863) 20120523. Estas eran las versiones que vienen con el sistema base FreeBSD 9.1-RELEAESE. La CPU es un procesador AMD Turion II Neo N40L de doble núcleo (1497,54 MHz).