Início / user-13630037

TheJanzap's questions

Martin Hope
TheJanzap
Asked: 2025-04-20 16:00:26 +0800 CST
  • 10

Tenho a seguinte constexprfunção de Fibonacci:

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

Se eu comparar com o código abaixo, obtenho a seguinte saída:

benchmark name                       samples       iterations    est run time
                                     mean          low mean      high mean
                                     std dev       low std dev   high std dev
-------------------------------------------------------------------------------
Benchmark fibo(46)                             100             1        2.66 m 
                                         1.60356 s     1.60231 s     1.60477 s 
                                        6.30399 ms    5.51902 ms    7.32077 ms

Quando altero o numberparâmetro para unsigned int const &number, a velocidade melhora significativamente:

benchmark name                       samples       iterations    est run time
                                     mean          low mean      high mean
                                     std dev       low std dev   high std dev
-------------------------------------------------------------------------------
Benchmark fibo(46)                             100             1    17.7672 ms 
                                        177.013 us    176.272 us      177.9 us 
                                        4.13731 us    3.56318 us    4.80496 us

Por que há um aumento tão grande de velocidade ao passar o parâmetro por referência?

Código de benchmarking:

#include "Fibonacci.hpp"
#include "catch2/catch_message.hpp"

#include <catch2/benchmark/catch_benchmark.hpp>
#include <catch2/catch_test_macros.hpp>
#include <catch2/generators/catch_generators.hpp>
#include <catch2/generators/catch_generators_all.hpp>
#include <catch2/generators/catch_generators_range.hpp>
#include <sstream>
#include <utility>

TEST_CASE("Fibonacci calculation", "[Fibonacci Benchmark Suite]") {
  auto entry = GENERATE(table<unsigned long long, unsigned long long>({
    {0, 0}, 
    {1, 1}, 
    {2, 1}, 
    {3, 2}, 
    {4, 3}, 
    {5, 5}, 
    {46, 1836311903} // Runs long!
    }));
  auto input = std::get<0>(entry);
  auto expected = std::get<1>(entry);
  std::ostringstream oss;
  oss << "Benchmark fibo(" << input << ")";
  auto benchmarkName = oss.str();
  BENCHMARK(std::move(benchmarkName)) {
    return fibo(input);
  };
  CAPTURE(input, expected);
  REQUIRE(fibo(input) == expected);
}

(Nota: Este código também parece um pouco estranho, já que a compilação com o GCC 14.2.1 às vezes fazia com que ele consumisse toda a minha RAM antes de ser morto pelo kernel do Linux. Adicionei os sinalizadores -fconstexpr-ops-limit=100000000000000e -fconstexpr-cache-depth=50, mas eles não parecem ter ajudado)

c++