有效使用 Lambda 表达式和 std::function

时间:2021-10-26 20:35:28
译文: http://www.ituring.com.cn/article/1184

原文: Efficient Use of Lambda Expressions and std::function

作者: Cassio Neri
译者: Breaker <breaker.zy_AT_gmail>

译文


有效使用 Lambda 表达式和 std::function

函数对象和 std::function 在各个库中实现各不同。C++11 的 lambda 表达式使它们更有效地被使用

函数对象类,即实现 operator() 的类,多年来被 C++ 程序员所熟知,它们被用做 STL 算法中的谓词 (predicate)。然而,实现简单的函数对象类是一件繁琐的事情,如:

假设 v 是 int 为元素的 STL 容器,我们要计算其中有多少元素是指定整数 n 的倍数。STL 的方式如下:

std::count_if(v.begin(), v.end(), is_multiple_of(n));

is_multiple_of 定义如下:

class is_multiple_of {
public:
typedef bool result_type; // 虽然无严格要求, 但建议定义这两个 typedef
typedef int argument_type; // 讨论 std::reference_wrapper 时会说明原因
is_multiple_of(int n) : n(n) {}
bool operator()(int i) const { return i%n == 0; }
private:
const int n;
};

这些冗长的代码让很多程序员宁愿写自己的循环,也不愿使用 std::count_if,如此一来,他们也丢掉了编译优化的机会

lambda 表达式 使创建这种简单的函数对象类更加方便。Boost 中的两个库 Boost.Lambda 和最近的 Boost.Phoenix,均提供了很好的 lambda 概念的实现,以提高 C++03 的语言表达能力,并且 C++ 标准委员会已决定在 C++11 中加入 lambda 表达式的语言支持。使用这些新特性后,之前的例子变为:

std::count_if(v.begin(), v.end(), [n](int i){return i%n == 0;});

上面的 lambda 表达式 [n](int i){return i%n == 0;} 会让编译器产生一个类似 is_multiple_of 的未命名函数对象类,并且具有以下优点:

  1. 它简约而不冗长
  2. 它不会为临时的使用而引入新的名字,所以不导致名字污染
  3. 通常(这个例子还看不出来),函数对象类名不如它的实际代码的表达能力强,把代码放到更靠近调用它的地方将提高代码清晰度

闭包类型

在前面的例子中,我们的函数对象类名为 is_multiple_of,而由编译器自动生成的函数对象类有不同的名字,并且只有编译器知道这个类型名字,可以认为它是一个未命名类型。为了阐述,它叫做 闭包类型 (closure type),而由 lambda 表达式产生的临时对象叫做 闭包对象。类型的匿名性并不影响 std::count_if 的调用,因为它是一个函数模板,它会进行参数类型推导

将函数改写为模板,可以让它接受 lambda 表达式作为参数。例如,一个科学计算库实现一个根查找器 (root-finder),比如一个接受函数对象 f,并返回满足 f(x) = 0 的 double 值 x 的 root-finder 函数,可以实现为函数模板:

template <class T>
double find_root(T const& f);

但是,一些少许而周知的 C++ 模板缺点让上面代码并不很合意:模板代码必须写在头文件中,这会增加编译时间,并且函数模板不能为 virtual

find_root 可以写为非模板函数吗?如果可以,它将具有怎样的原型 (signature)

double find_root(??? const& f);

参数类型推导并不是 C++11 引入的新事物,相比之下,新的标准将引入两个关键字,auto 和 decltype,以支持类型推导(注:auto 也是 C++03 的关键字,但意义不同)。如果要命名闭包对象,可以如下例:

auto f = [](double x){ return x * x - 0.5; };

另外,可以为闭包类型定义别名,如下:

typedef decltype(f) function_t;

但是不幸地是,function_t 只能在 lambda 表达式所在的同一作用域中定义,即其它地方是不可见的,故它也不能用来定义 find_root 的原型

下面来看另一个重要的东西 std::function

std::function 及其开销

另一个选择是 Boost 的 std::function,它实现了一套类型消除机制 (type erasure),可以统一处理不同的函数对象类型。它的前辈 boost::function 可以追溯到 2001 年,并在 2005 年引入为 TR1 的 std::tr1::function。现在,它是 C++11 的一部分,并且放入 std 名字空间中

下面看下 std::function 和相关类的三种不同实现:Boost, Microsoft C++ Standard library (MSLIB), GNU Standard C++ Library (libstdc++, 本文称 GCCLIB)。除非另行说明,这里提到的库类型和函数都属于 std 名字空间,虽然 Boost 不是。使用两个编译器:Microsoft Visual Studio 2010 (MSVC), GNU Compiler Collection 4.5.3 (GCC) 带 -std=c++0x 选项,对上述各自库和 Boost 进行编译。使用 std::function 后,find_root 声明变为:

double find_root(std::function<double(double)> const& f);

通常 std::function<R(T1, T2, ..., TN)> 是一个函数对象类,它包装其它任意的函数对象,被包装的函数对象具有类型为 T1, ..., TN 的 N 个参数,并且返回一个可转换到 R 类型的值。std::function 使用 模板转换构造函数 接收被包装的函数对象,特别是,闭包类型可以隐式地转换为 std::function。但是,在构造 std::function 时存在两个隐藏的,但也可预防的开销:

第一个开销,std::function 构造函数按值传递函数对象,这意味着进行拷贝。进一步,构造函数会将这个拷贝转发到一系列辅助函数上,而其中大多数也是按值传递,这意味着更多的拷贝。例如,MSLIB 和 GCCLIB 会做 4 次拷贝,而 Boost 则会做 7 次。不过,大量的拷贝还不是性能损害的元凶

第二个问题和函数对象的大小有关。std::function 的三个库实现都采用了标准建议的小对象优化技术 (small object optimization),以避免动态内存分配。通常,它们使用一个数据成员存储被包装函数对象的拷贝。但是,因为被包装对象的大小是在 std::function 构造时确定,(被包装对象较大时)成员存储可能不足以容纳其拷贝。这时,将调用 new(除非自定义分配器)在堆上创建拷贝,只在数据成员中保存拷贝的指针。超出就分配堆存储的准确大小,依赖于具体平台和内存对齐,对于一般平台的 MSLIB, GCCLIB 和 Boost 的最好情况,分别是 12 bytes, 16 bytes 和 24 bytes

提高 std::function 的性能

为了解决上述性能问题,应该避免使用拷贝和大对象,直接的想法是用引用代替拷贝。但是,这通常很难,因为我们有时需要 std::function 比它的原始被包装函数对象有更长的生存期

这是个老问题,STL 算法按值传递函数对象参数时,就存在此问题。Boost 很早就提供了一种解决方法,现在被 C++11 采用。类模板 std::reference_wrapper 包装一个对象的引用,并提供到被包装类型的自动类型转换,这使得 std::reference_wrapper 可用在很多需要被包装类型的地方。std::reference_wrapper 和引用的大小相同,即它很小。另外,有两个函数模板 std::ref 和 std::cref,分别用来简化非 const 和 const 的 std::reference_wrappers 的创建(就像用 std::make_pair 简化 std::pairs 的创建)

再看下第一个例子:为了避免 is_multiple_of 的多次拷贝(虽然它很小,没有大的开销),可使用如下:

std::count_if(v.begin(), v.end(), std::cref(is_multiple_of(n)));

同样的思路,应用在 lambda 表达式时如下:

std::count_if(v.begin(), v.end(), std::cref([n](int i){return i%n == 0;}

不幸地是,这里的情况有些复杂,并且依赖编译器和库实现:

  • 两个编译器下的 Boost(将 std::cref 变为 boost::cref): 均无法工作,因为 boost::reference_wrapper<T> 不是一个函数对象

  • MSLIB: 无法工作,但未来会支持。实际上,MSLIB 为了操作函数对象的返回类型,使用了 TR1 中的 std::result_of,它依赖含 result_type 成员的函数对象类型,其中 result_type 是用作 operator() 返回类型的 typedef。注意,手工的 is_multiple_of 类已包含这个类型成员,但 C++11 的闭包类型却没有。C++11 中已经改变 std::result_of,它以 decltype 的方式定义。我们现在处于过渡期,MSLIB 仍然遵循 TR1,但 下一版 MSLIB 应该会遵循 C++11

  • GCCLIB: 可以工作

另外,按照 C++11,由 lambda 表达式产生的函数对象类不能适配 (adaptable)(译注:参考 STL 谓词适配),即它们没有 STL 适配器 (adaptor) 需要的特定类型成员,所以下面代码是非法的:

std::not1([n](int i){ return i%n == 0; });

这个例子中,std::not1 需要 argument_type 成员类型。注意,手工的 is_multiple_of 类中已定义了它

当使用 std::function 时,上面的 std::reference_wrapper 问题有些小变化。按照定义,std::function 只包装函数对象,因此,当它的构造函数接收std::reference_wrapper<T> 类型的对象时,它假定 T 是一个函数对象类并相应工作。例如,下面代码对于 Boost 和 GCCLIB 是合法的,而目前对 MSLIB 尚不合法(下一版应该可以):

std::function<bool(int)> f(std::cref([n](int i) {return i%n == 0));
std::count_if(v.begin(), v.end(), f);

值得一提的是,std::function 包装的一元和二元函数对象类可以适配,它们可以传递给 STL 适配器,如 std::not1

总结一下:如果你不想使用堆存储(和自定义分配器),可以选择 Boost 和 GCCLIB;如果考虑移植性,则应该使用 Boost;对于使用 MSVCLIB 的开发者,直到下一版之前,性能问题都会存在;对于那些不想等待的人,这里有一个可移植的变通方法(GCC 和 MSVC 都可工作)

思路很简单:保持小的闭包类型。闭包对象的大小依赖于 lambda 表达式捕获的变量(译注:参考闭包概念, upvalue),即 [] 中的东西。如之前的 lambda 表达式:

[n](int i){ return i%n == 0; };

这里捕获的变量是 n,所以闭包类型有一个 int 数据成员保存 n 的拷贝。放入 [] 中的标识符越多,闭包类型的尺寸就会越大。如果 [] 中所有标识符的合计尺寸很小,比如一个 int 或 double 的大小,那么便不会使用堆存储

一种保持小尺寸的方法是,创建一个只包含引用的 struct,其中的引用指向之前放入 [] 中的所有标识符,然后只将 struct 的引用放入 []。随后,可以在 lambda 表达式体内使用 struct 的成员。例如,下面 lambda 表达式:

double a;
double b;
// ...
[a, b](double x){ return a * x + b; };

将产生至少 2 * sizeof(double) = 16 bytes 的闭包类型,足以让 MSLIB 使用堆存储。将其改变如下:

double a;
double b;
// ...
struct {
const double& a;
const double& b;
} p = { a, b };
[&p](double x){ return p.a * x + p.b; };

这时,只有指向 p 的引用被捕获,这对于 MSLIB, GCC 和 Boost 都不会使用堆存储

最后的忠告是,标准中说,闭包类型实现可以使用不同的大小和字节对齐。这表示以上的变通方法也可能不奏效。准确地说,以上代码仍合法,但如果对象变大,也可能使用堆存储。还好,MSVC 和 GCC 都不如此

[END]



相关文章