Por que uma função constexpr recursiva é muito mais rápida com parâmetros de referência do que com valores?

Que caso de teste curto, mas incrivelmente estranho, para compiladores!

Nunca vi o problema de parada afetar diretamente a compilação antes, mas o GCC, ao tentar honrar a especificação recursiva deste código, sofre um aumento exponencial do tempo de compilação e do uso de memória com valores maiores de Numa constante conhecida fixa no tempo de compilação ao calcular fibo(N).

Os limites seguros para Nonde o GCC pode resolver completamente fibo(N)uma constante de tempo de compilação são N <= 35para chamada por valor e N <= 28para chamada por referência. Não tenho ideia de por que os limites superiores são diferentes, apenas que são. O código C é enganosamente semelhante, mas o assembler gerado é radicalmente diferente!

Também testei no MSVC C/C++ 17 e no Intel ICX 2024.1, mas obtive apenas um comportamento normal e desempenho bastante semelhante para ambos. O Intel ICX 2025 parece armazenar em cache os valores que já calculou se você acertar as opções do compilador gofaster. Não consigo reproduzir essa observação transitória no momento. "-O3 -Wall" não é suficiente.

Dei uma olhada neste código em detalhes porque a rotina recursiva não altera o valor de, numberentão eu não esperava ver muita diferença entre chamada por valor e chamada por referência.

Usando GCC para uma pequena N <= 28constante conhecida em tempo de compilação, isso é verdade - ele compila para carregar a constante mágica fibo(N)com exatamente o mesmo código gerado para ambos e um tempo de compilação muito longo (que cresce exponencialmente com N).

Criei uma versão canônica de brinquedo o mais simples possível em [Godbolt]( https://godbolt.org/z/h6G1z7WPh ). Por favor, sejam gentis com o site e não alimentem com N maiúsculo! Godbolt consegue sobreviver N=36em um dia bom se o vento estiver soprando na direção certa. Prepare-se para perder o processo se subir mais alto.

Você pode tentar várias combinações comentando as linhas dentro ou fora. N=28,29 (cbr) e 35,36 (cbv) são os casos de valor fixo mais interessantes, juntamente com o Ndesconhecido no momento da compilação.

A enorme diferença de velocidade não tem quase nada a ver com chamada por valor versus chamada por referência e tudo a ver com geração de código extremamente sofisticada quando o caminho cbr é tomado.

Ele praticamente coloca tudo em registradores e usa passos muito maiores, decrementando Nem 5 para cada nível de recursão e então terminando em uma tabela de consulta quando N<= 5.

O primeiro caso com chamada por valor não é nada fora do comum. Exceto para valores pequenos de N<35onde a compilação é muito lenta para carregar o valor constante fibo(N). A otimização geral consiste em desenrolar a recursão em um nível e escrever seu próprio código duas vezes (aproximadamente 300 bytes).

A geração de código do segundo caso é extraordinária, pelo menos no GCC-O3 (tentarei com mais afinco provocar o mesmo comportamento no Intel e no GCC). Ela utiliza truques que me sugerem que foi cuidadosamente otimizada para ter um desempenho incrivelmente bom neste tipo específico de benchmark.

Consegui obter três cenários, mas vou restringir esta discussão aos dois principais. Para N<29valores conhecidos em tempo de compilação, a compilação leva uma eternidade para carregar o valor constante fibo(N). Valores constantes maiores interromperão o compilador (ou farão com que o sistema operacional o faça) devido ao uso exponencial de memória ou timeouts (no Godbolt). Para ocultar o valor do compilador, coloquei-o em uma string que é boa o suficiente para gerar código genérico para qualquer valor N(aproximadamente 160 bytes).

Examinei o código do montador gerado pelo compilador GCC para as duas rotinas de exemplo e, em seguida, reconstruí o código C funcionalmente equivalente abaixo para ajudar a explicar mais facilmente como o código de chamada por referência obtém sua velocidade aparentemente mágica.

Ele utilizou um truque de recursão de cauda para minimizar a profundidade da recursão. Ele retira pedaços de 5 do valor de Npara cada chamada recursiva e, em seguida, cria uma tabela de consulta para N=1through 5! É uma transformação de código bastante notável em relação ao código-fonte original.

Aqui está o código. fibo_cbvé a geração de código embutido relativamente normal, típica de compiladores modernos, mas que faz uso intenso da pilha. fibo_cbré o código incomum gerado pelo GCC para esta função de benchmark específica. Este último é realmente bastante engenhoso! Meu código C não é exatamente equivalente ao assembler compilado, pois precisei ajustá-lo um pouco para que funcionasse corretamente.

A propósito, recursão é uma maneira terrível de calcular esses valores!

     #include <cmath>
     #include <string>
     #include <stdio.h>

    // N       : 1  2  3  4  5  6  7  8  9 10 11
    // fibo(N) : 1  1  2  3  5  8 13 21 34 55 89

    constexpr auto fibo(unsigned int number) -> unsigned long long {
    //constexpr auto fibo(unsigned int const& number) -> unsigned long long {
        if (number < 2) return number;
        return fibo(number - 1) + fibo(number - 2);
    }

    constexpr auto fibo_cbv(unsigned int number) -> unsigned long long {
        unsigned int result = 0;
        if (number < 2) return number;  
        if (--number < 2) return number; else result = fibo_cbv(number);
        if (--number < 2) return result + number; 
        return result + fibo_cbv(number);
    }

    constexpr auto fibo_cbr(unsigned int const& number) -> unsigned long long {
        switch (number) {
          case 1: return 1;
          case 2: return 1;
          case 3: return 2;
          case 4: return 3;
          case 5: return 5;
          case 6: return 8;
          case 7: return 13;
          default:
      //     return fibo_cbr(number - 1) + fibo_cbr(number - 2);// works much slower
          unsigned long long a = fibo_cbr(number - 6);
          unsigned long long b = fibo_cbr(number - 5);
          return 5 * a + 8 * b;
        }  
    }

    int main()
    {
        std::string input{ "28" };
        unsigned int n;
        for (n = 1; n < 36; n++)
        {
            printf("\nfibo_ref(%i) = %i\n", n,  fibo(n));
            printf("fibo_cbv(%i) = %i\n", n,  fibo_cbv(n));
            printf("fibo_cbr(%i) = %i\n", n, fibo_cbr(n));
        }
    //    return fibo(36);  // fixed value to test
        n = stol(input);
        return fibo(n);
    }

Também notei, durante os experimentos, que se eu lesse uma variável, No código de chamada por referência do GCC se tornava ainda mais complicado usando uma estratégia de potências de 2 em vez de subtrair pedaços de 8 ou 4 do valor inicial de N. Não tenho certeza de qual aspecto do código de teste levou a esse caminho. Não posso reproduzi-lo agora, mas tenho certeza de que não tive alucinações com essa versão do código gerado.

Vale ressaltar também que N=92para fibo(92)é o valor mais alto que você pode atingir sem transbordar para uint64_t.

Não consegui fazer com que nenhum outro compilador C/C++ que testei, além do GCC, fizesse os cálculos de tempo de compilação extensivos necessários para calcular fibo(N)uma constante estática de forma recursiva lenta.

A resposta curta para o motivo de ser mais rápido fazer chamadas por referência é que ele usa um algoritmo radicalmente diferente que não se parece em nada com o código fonte C original, mas é funcionalmente equivalente.

Nada a ver com o mecanismo de chamada por referência vs chamada por valor.