为什么这个本地递归C ++ lamda这么慢呢？

Question

为了理解，我使用带有递归调用（尾递归）的本地lamda。运行此命令（例如，在http://cpp.sh/或https://coliru.stacked-crooked.com/上），始终表明lamda调用的质量比其他解决方案要慢。

我的问题是为什么呢？

#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);