c++ - 为什么这个本地递归 C++ lambda 如此慢？

Question

为了便于理解，我正在使用具有递归调用(尾递归)的本地 lambda。运行这个(例如在 http://cpp.sh/ 或 https://coliru.stacked-crooked.com/ 上)它总是表明 lambda 调用比其他解决方案慢得多。

我的问题是为什么会这样？

#include <iostream>
#include <chrono>
#include <functional>
 
//tail recursive lamda
long long int Factorial5(long long int n)
{ 
  std::function<long long int(long long int,long long int)> aux
     = [&aux](long long int n, long long int acc)
  { 
    return n < 1 ? acc : aux(n - 1, acc * n);
  };
  return aux(n,1);
}
 
//tail recursive inline class
long long int Factorial6(long long int n)
{ 
  class aux {
    public: inline static long long int tail(long long int n, long long int acc)
    { 
      return n < 1 ? acc : tail(n - 1, acc * n);
    }
  };
  return aux::tail(n,1);
}


int main()
{
    int v = 55;
    {
        auto t1 = std::chrono::high_resolution_clock::now();
        auto result = Factorial5(v);
        auto t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::fixed << "lamda(5)\tresult " << result
                  << " took " << ms.count() << " ms\n";
    }
    {
        auto t1 = std::chrono::high_resolution_clock::now();
        auto result = Factorial6(v);
        auto t2 = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::milli> ms = t2 - t1;
        std::cout << std::fixed << "inner class(6)\tresult " << result
                  << " took " << ms.count() << " ms\n";
    }
}

输出:

lamda(5)        result 6711489344688881664 took 0.076737 ms
inner class(6)  result 6711489344688881664 took 0.000140 ms

Answer 1

lambda 不是 std::function。每个 lambda 都有自己独特的类型。大致是这样的:

struct /* unnamed */ {
    auto operator()(long long int n, long long int acc) const
    { 
        return n < 1 ? acc : aux(n - 1, acc * n);
    }
} aux{};

所以原则上，lambda 非常快，与任何函数或非虚拟成员函数一样快。

缓慢来自 std::function，它是 lambda 的类型删除包装器。它将函数调用转换为虚拟调用，并可能动态分配 lambda。这是昂贵的，并且会阻止内联。

要创建递归 lambda，您必须使用 C++14 通用 lambda 并将 lambda 发送给它自己:

auto aux = [](auto aux, long long int n, long long int acc) -> long long int
{ 
  return n < 1 ? acc : aux(aux, n - 1, acc * n);
};

return aux(aux, n, 1);