c++ - 为什么将函数包装到 lambda 中可能会使程序更快？

Question

标题可能过于笼统。我正在对大型 vector<unsigned> v 上的以下 2 个语句进行基准测试:

sort(v.begin(), v.end(), l);

sort(v.begin(), v.end(), [](unsigned a, unsigned b) { return l(a, b); });

哪里l定义为

bool l(unsigned a, unsigned b) { return a < b; }

结果让我大吃一惊:第二个和sort(v.begin(), v.end());一样快或 sort(v.begin(), v.end(), std::less<>());而第一个明显较慢。

我的问题是为什么将函数包装在 lambda 中可以加快程序速度。

此外，sort(v.begin(), v.end(), [](unsigned a, unsigned b) { return l(b, a); });也一样快。

相关代码:

#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <functional>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

bool l(unsigned a, unsigned b) { return a < b; };

int main(int argc, char** argv)
{
    auto random = std::default_random_engine();
    vector<unsigned> d;
    for (unsigned i = 0; i < 100000000; ++i)
        d.push_back(random());
    auto t0 = std::chrono::high_resolution_clock::now();
    std::sort(d.begin(), d.end());
    auto t1 = std::chrono::high_resolution_clock::now();
    cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count() << endl;


    d.clear();
    for (unsigned i = 0; i < 100000000; ++i)
        d.push_back(random());
    t0 = std::chrono::high_resolution_clock::now();
    std::sort(d.begin(), d.end(), l);
    t1 = std::chrono::high_resolution_clock::now();
    cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count() << endl;

    d.clear();
    for (unsigned i = 0; i < 100000000; ++i)
        d.push_back(random());
    t0 = std::chrono::high_resolution_clock::now();
    std::sort(d.begin(), d.end(), [](unsigned a, unsigned b) {return l(a, b); });
    t1 = std::chrono::high_resolution_clock::now();
    cout << std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count() << endl;
    return 0;
}

在 g++ 和 MSVC 上测试。

更新:

我发现 lambda 版本生成的汇编代码与默认版本 ( sort(v.begin(), v.end()) ) 完全相同，而使用函数的版本则不同。但我不会汇编，因此无法做更多。

Answer 1

sort可能是一个很大的功能，所以它通常不是内联的。因此单独编译。考虑 sort :

template <typename RanIt, typename Pred>
void sort(RanIt, RanIt, Pred)
{
}

如果Pred是bool (*)(unsigned, unsigned) ，没有办法内联函数——函数指针类型不能唯一标识一个函数。只有一个 sort<It, It, bool (*)(unsigned, unsigned)> , 它被所有具有不同函数指针的调用所调用。用户通过 l到函数，但这只是作为一个普通参数处理。因此无法内联调用。

如果Pred是一个 lambda，内联函数调用是微不足道的——lambda 类型唯一标识一个函数。每次调用 sort 的实例化调用相同的 (lambda) 函数，所以我们没有函数指针的问题。 lambda 本身包含对 l 的直接调用，这也很容易内联。因此，编译器内联所有函数调用并生成与无谓词相同的代码 sort .

---

函数闭包类型 ( std::less<> ) 的情况类似:调用 std::less<> 的行为编译时完全知道sort , 所以内联是微不足道的。