为什么现代编译器没有消除对表达式模板的需求?
Why haven't modern compilers removed the need for expression templates?
C++ 中表达式模板的标准音调是它们通过删除不必要的临时对象来提高效率。为什么 C++ 编译器不能删除这些不必要的临时对象?
这是一个我认为我已经知道答案但我想确认的问题,因为我无法在网上找到低级别的答案。
表达式模板本质上是 allow/force 一种极端程度的内联。然而,即使使用内联,编译器也无法优化对 operator new
和 operator delete
的调用,因为它们将这些调用视为不透明的,因为这些调用可以在其他翻译单元中被覆盖。表达式模板完全删除了对中间对象的那些调用。
这些对 operator new
和 operator delete
的多余调用可以在我们仅复制的简单示例中看到:
#include <array>
#include <vector>
std::vector<int> foo(std::vector<int> x)
{
std::vector<int> y{x};
std::vector<int> z{y};
return z;
}
std::array<int, 3> bar(std::array<int, 3> x)
{
std::array<int, 3> y{x};
std::array<int, 3> z{y};
return z;
}
在 generated code 中,我们看到 foo()
编译为一个相对冗长的函数,两次调用 operator new
一次调用 operator delete
而 bar()
编译为仅传输寄存器并且不进行任何不必要的复制。
这个分析正确吗?
任何 C++ 编译器都可以合法地删除 foo()
中的副本吗?
However, even with inlining, compilers cannot optimize out calls to operator new and operator delete because they treat those calls as opaque since those calls can be overridden in other translation units.
从 c++14 开始,这不再正确,分配调用可以 optimized-out/reused 在某些条件下:
[expr.new#10] An implementation is allowed to omit a call to a replaceable global allocation function. When it does so, the storage is instead provided by the implementation or provided by extending the allocation of another new-expression.[conditions follows]
所以现在 foo() 可以合法地优化为等同于 bar() 的东西......
Expression templates essentially allow/force an extreme degree of inlining
IMO 表达式模板的要点与内联 本身 无关,而是利用 领域特定语言 [=] 类型系统的对称性27=] 表达式模型。
例如,当您将三个厄密矩阵相乘时,表达式模板可以使用 space 时间优化算法,利用乘积 关联性 并且厄密矩阵是伴随对称的,从而减少了总运算次数(甚至可能提高了精度)。而这一切,都发生在编译时。
相反,编译器无法知道厄密矩阵是什么,它只能以粗暴的方式评估表达式(根据您的实现浮点语义)。
有两种表达式模板。
一种是关于直接嵌入到 C++ 中的领域特定语言。 Boost.Spirit 将表达式转换为递归下降解析器。 Boost.Xpressive 把它们变成正则表达式。好的旧 Boost.Lambda 将它们变成带有参数占位符的函数对象。
显然,编译器无法消除这种需求。需要特殊用途的语言扩展来添加 eDSL 添加的功能,例如将 lambda 表达式添加到 C++11。但是对每一个编写的 eDSL 都这样做是没有效率的;这会使语言变得庞大且无法理解,还有其他问题。
第二种是保持高层语义相同但优化执行的表达式模板。他们应用特定领域的知识将表达式转换为更有效的执行路径,同时保持语义相同。正如 Massimiliano 在他的回答中解释的那样,线性代数库可能会这样做,或者像 Boost.Simd 这样的 SIMD 库可能会将多个操作转换为单个融合操作,如乘加。
这些库提供编译器理论上可以在不修改语言规范的情况下执行的服务。然而,为了这样做,编译器必须识别有问题的领域并拥有所有内置的领域知识来进行转换。这种方法太复杂了,会使编译器变得庞大甚至比它们慢。
为这些类型的库编写表达式模板的另一种方法是编译器插件,即不是编写一个具有所有表达式模板魔法的特殊矩阵 class,而是为编译器编写一个插件,它知道关于矩阵类型并转换编译器使用的 AST。这种方法的问题在于,要么编译器必须就插件达成一致 API(不会发生,它们在内部工作方式差异太大),要么库作者必须为他们想要的库的每个编译器编写一个单独的插件可用于(或至少性能)。
C++ 中表达式模板的标准音调是它们通过删除不必要的临时对象来提高效率。为什么 C++ 编译器不能删除这些不必要的临时对象?
这是一个我认为我已经知道答案但我想确认的问题,因为我无法在网上找到低级别的答案。
表达式模板本质上是 allow/force 一种极端程度的内联。然而,即使使用内联,编译器也无法优化对 operator new
和 operator delete
的调用,因为它们将这些调用视为不透明的,因为这些调用可以在其他翻译单元中被覆盖。表达式模板完全删除了对中间对象的那些调用。
这些对 operator new
和 operator delete
的多余调用可以在我们仅复制的简单示例中看到:
#include <array>
#include <vector>
std::vector<int> foo(std::vector<int> x)
{
std::vector<int> y{x};
std::vector<int> z{y};
return z;
}
std::array<int, 3> bar(std::array<int, 3> x)
{
std::array<int, 3> y{x};
std::array<int, 3> z{y};
return z;
}
在 generated code 中,我们看到 foo()
编译为一个相对冗长的函数,两次调用 operator new
一次调用 operator delete
而 bar()
编译为仅传输寄存器并且不进行任何不必要的复制。
这个分析正确吗?
任何 C++ 编译器都可以合法地删除 foo()
中的副本吗?
However, even with inlining, compilers cannot optimize out calls to operator new and operator delete because they treat those calls as opaque since those calls can be overridden in other translation units.
从 c++14 开始,这不再正确,分配调用可以 optimized-out/reused 在某些条件下:
[expr.new#10] An implementation is allowed to omit a call to a replaceable global allocation function. When it does so, the storage is instead provided by the implementation or provided by extending the allocation of another new-expression.[conditions follows]
所以现在 foo() 可以合法地优化为等同于 bar() 的东西......
Expression templates essentially allow/force an extreme degree of inlining
IMO 表达式模板的要点与内联 本身 无关,而是利用 领域特定语言 [=] 类型系统的对称性27=] 表达式模型。
例如,当您将三个厄密矩阵相乘时,表达式模板可以使用 space 时间优化算法,利用乘积 关联性 并且厄密矩阵是伴随对称的,从而减少了总运算次数(甚至可能提高了精度)。而这一切,都发生在编译时。
相反,编译器无法知道厄密矩阵是什么,它只能以粗暴的方式评估表达式(根据您的实现浮点语义)。
有两种表达式模板。
一种是关于直接嵌入到 C++ 中的领域特定语言。 Boost.Spirit 将表达式转换为递归下降解析器。 Boost.Xpressive 把它们变成正则表达式。好的旧 Boost.Lambda 将它们变成带有参数占位符的函数对象。
显然,编译器无法消除这种需求。需要特殊用途的语言扩展来添加 eDSL 添加的功能,例如将 lambda 表达式添加到 C++11。但是对每一个编写的 eDSL 都这样做是没有效率的;这会使语言变得庞大且无法理解,还有其他问题。
第二种是保持高层语义相同但优化执行的表达式模板。他们应用特定领域的知识将表达式转换为更有效的执行路径,同时保持语义相同。正如 Massimiliano 在他的回答中解释的那样,线性代数库可能会这样做,或者像 Boost.Simd 这样的 SIMD 库可能会将多个操作转换为单个融合操作,如乘加。
这些库提供编译器理论上可以在不修改语言规范的情况下执行的服务。然而,为了这样做,编译器必须识别有问题的领域并拥有所有内置的领域知识来进行转换。这种方法太复杂了,会使编译器变得庞大甚至比它们慢。
为这些类型的库编写表达式模板的另一种方法是编译器插件,即不是编写一个具有所有表达式模板魔法的特殊矩阵 class,而是为编译器编写一个插件,它知道关于矩阵类型并转换编译器使用的 AST。这种方法的问题在于,要么编译器必须就插件达成一致 API(不会发生,它们在内部工作方式差异太大),要么库作者必须为他们想要的库的每个编译器编写一个单独的插件可用于(或至少性能)。