C++ sort中Lambda比较器性能低下的原因探究

我发现在C++的sort函数中使用Lambda作为比较器时，存在明显的性能损耗。我尝试了以下实现：

// vector<int> F(N);
for (int i = 0; i < N; i++)
    idx[i] = i;
sort(idx.begin(), idx.end(), [F](int x, int y) {
    if (F[x] < F[y])
        return true;
    if (F[x] == F[y])
        return (x < y);
    return false;
});

我的需求是对F进行排序，同时保留元素的原始索引。但上述代码运行速度较慢。而以下实现则性能更优：

vector<pair<int,int>> tmp(N);
for (int i = 0; i < N; i++)
    tmp[i] = {F[i], i};
sort(tmp.begin(), tmp.end());

我想知道，在开启优化编译的情况下，为什么g++下的Lambda版本性能如此低下？

补充：评论区有人指出可以通过引用传递F，我曾考虑删除此帖，但下方已有不少有价值的回答。

性能差异的核心原因 #

1. Lambda捕获方式带来的拷贝开销 #

你写的Lambda用了[F]值捕获，这会把整个vector<int> F完整拷贝一份到Lambda对象中。排序过程中sort会频繁调用比较器，不仅初始化Lambda时的拷贝本身是一笔不小的开销，而且拷贝后的容器内存布局可能和原F不一致，导致缓存命中率下降，进一步拖慢访问速度。

如果改成引用捕获[&F]，就能避免拷贝，直接访问原容器的数据，性能会大幅提升，甚至接近pair版本的表现。

2. pair版本的编译器优化更彻底 #

std::pair的默认比较逻辑是编译器原生支持的优化路径：

• pair的比较是按成员顺序逐次比较，编译器可以把这个逻辑完全内联，生成更紧凑的机器码；
• 排序时访问的是连续存储的F[i]和i，数据局部性更好，缓存能更高效地加载数据，减少内存访问的等待时间。

而Lambda版本即使改成引用捕获，编译器对Lambda比较器的内联优化可能不如pair默认比较那么彻底——虽然单次操作差异细微，但排序的比较次数是O(N logN)级别的，累计起来就会形成明显的性能差距。

3. 索引访问的额外开销 #

Lambda版本是通过索引x、y去访问F的元素，这比pair版本直接访问连续存储的成员多了一层数组寻址计算。单看一次操作开销很小，但在海量比较次数的放大下，就会成为不可忽视的性能损耗点。

内容的提问来源于stack exchange，提问作者Matyas