为什么将函数包装到 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 时是完全已知的，因此内联是微不足道的。

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

Why wrapping a function into a lambda potentially make the program faster?

c++

performance

lambda

stl

inlining