c++ - 表达式模板实现未优化

Question

我试图理解 C++ 中表达式模板的概念，因此我拼凑了一些示例代码等，以生成一个简单的向量和相关的表达式模板基础结构，以仅支持二进制运算符 (+、-、)。

一切都可以编译，但是我注意到标准手写循环与表达式模板变体之间的性能差异非常大。ET 的速度几乎是手写速度的两倍。我预计会有所不同，但并没有那么大。

完整的代码清单可以在这里找到：

https://gist.github.com/BernieWt/769a4a3ceb90bb0cae9e

（为混乱的代码道歉。）

.

简而言之，我本质上是在比较以下两个循环：

东部时间：

for (std::size_t i = 0 ; i < rounds; ++i)
{
   v4 = ((v0 - v1) + (v2 * v3)) + v4;
   total += v4[0];
}

硬件：

for (std::size_t i = 0 ; i < rounds; ++i)
{
   for (std::size_t x = 0; x < N; ++x)
   {
      v4[x] = (v0[x] - v1[x]) + (v2[x] * v3[x]) + v4[x];
   }
   total += v4[0];
}

当我反汇编输出时，会产生以下内容，不同之处显然是在 ET 变体返回期间发生的额外 memcpy 和几个 64 位加载：

Standard Loop                           | Expression Template
----------------------------------------+--------------------------------
L26:                                    | L12:
xor   edx, edx                          | xor   edx, edx
jmp   .L27                              | jmp   .L13
L28:                                    | L14:
movsd xmm3, QWORD PTR [rsp+2064+rdx*8]  | movsd xmm3, QWORD PTR [rsp+2064+rdx*8]
L27:                                    | L13:
movsd xmm2, QWORD PTR [rsp+1040+rdx*8]  | movsd xmm1, QWORD PTR [rsp+1552+rdx*8]
movsd xmm1, QWORD PTR [rsp+16+rdx*8]    | movsd xmm2, QWORD PTR [rsp+16+rdx*8]
mulsd xmm2, QWORD PTR [rsp+1552+rdx*8]  | mulsd xmm1, QWORD PTR [rsp+1040+rdx*8]
subsd xmm1, QWORD PTR [rsp+528+rdx*8]   | subsd xmm2, QWORD PTR [rsp+528+rdx*8]
addsd xmm1, xmm2                        | addsd xmm1, xmm2
addsd xmm1, xmm3                        | addsd xmm1, xmm3
movsd QWORD PTR [rsp+2064+rdx*8], xmm1  | movsd QWORD PTR [rsp+2576+rdx*8], xmm1
add   rdx, 1                            | add   rdx, 1
cmp   rdx, 64                           | cmp   rdx, 64
jne   .L28                              | jne   .L14
                                        | mov   dx, 512
                                        | movsd QWORD PTR [rsp+8], xmm0
                                        | lea   rsi, [rsp+2576]
                                        | lea   rdi, [rsp+2064]
                                        | call  memcpy
movsd xmm3, QWORD PTR [rsp+2064]        | movsd xmm0, QWORD PTR [rsp+8]
sub   rcx, 1                            | sub   rbx, 1
                                        | movsd xmm3, QWORD PTR [rsp+2064]
addsd xmm0, xmm3                        | addsd xmm0, xmm3
jne   .L26                              | jne   .L12

我的问题是：此时我被困在如何删除副本上，我基本上想在没有副本的情况下更新 v4 。关于如何去做这件事的任何想法？

注意 1：我已经尝试过 GCC 4.7/9、Clang 3.3、VS2010/2013 - 我在提到的所有编译器上都得到了大致相同的性能配置文件。

注意2：我也尝试过为 vec 前向声明 bin_exp，然后添加以下赋值运算符并从 bin_exp 中删除转换运算符，~~但无济于事~~：

template<typename LHS, typename RHS, typename Op>
inline vec<N>& operator=(const bin_exp<LHS,RHS,Op,N>& o)
{
   for (std::size_t i = 0; i < N; ++i)  { d[i] = o[i]; }
   return *this;
}

更新注 2 中提出的解决方案实际上是正确的。并且确实导致编译器生成与手写循环几乎相同的代码。

.

另一方面，如果我将 ET 变体的用例重写如下：

auto expr = ((v0 - v1) + (v2 * v3)) + v4;

//auto& expr = ((v0 - v1) + (v2 * v3)) + v4;   same problem
//auto&& expr = ((v0 - v1) + (v2 * v3)) + v4;   same problem

for (std::size_t i = 0 ; i < rounds; ++i)
{
   v4 = expr
   total += v4[0];
}

发生崩溃是因为在 ET 实例化期间生成的临时变量（右值）在分配之前被销毁。我想知道是否有任何方法使用 C++11 导致编译器错误。

score 0 · Accepted Answer

表达式模板的要点是子表达式的评估可能会导致临时变量，这会产生成本并且不会带来任何好处。在您的代码中，您并没有真正将苹果与苹果进行比较。比较的两个替代方案是：

// Traditional
vector operator+(vector const& lhs, vector const& rhs);
vector operator-(vector const& lhs, vector const& rhs);
vector operator*(vector const& lhs, vector const& rhs);

使用这些操作定义，您想要解决的表达式：

v4 = ((v0 - v1) + (v2 * v3)) + v4;

变为（为所有临时人员提供名称）：

auto __tmp1 = v0 - v1;
auto __tmp2 = v2 * v3;
auto __tmp3 = __tmp1 + __tmp2;
auto __tmp4 = __tmp3 + v4;
// assignment is not really part of the expression
v4 = __tmp4;

如您所见，有 4 个临时对象，如果您使用表达式模板，它们会减少到最低限度：一个临时对象，因为这些操作中的任何一个都会生成一个不合适的值。

在您手卷的代码版本中，您没有执行相同的操作，而是展开整个循环并利用完整操作的知识，而不是真正相同的操作，因为知道您将在最后分配将表达式转换为元素之一，您将表达式转换为：

v4 += ((v0 - v1) + (v2 * v3));

现在考虑如果您创建一个新向量而不是分配给构成表达式的一部分的向量之一会发生什么v5。试试这个表达式：

auto v5 = ((v0 - v1) + (v2 * v3)) + v4;

表达式模板的神奇之处在于，您可以为在模板上工作的运算符提供与手动实现一样高效的实现，并且用户代码更简单且不易出错（无需遍历所有元素向量的潜在错误或维护成本，因为在执行算术运算的每个地方都需要知道向量的内部表示）

我基本上想在没有副本的情况下更新 v4

使用表达式模板和您当前的向量接口，您将支付临时和副本的费用。原因是在表达式的（概念）评估过程中创建了一个新向量，虽然对您来说这似乎很明显，v4 = ... + v4;但v4 += ...编译器或表达式模板无法完成转换。另一方面，您可以提供一个vector::operator+=（甚至可能是operator=）的重载，它采用表达式模板，并就地执行操作。

提供从表达式模板进行赋值的赋值运算符并使用 g++4.7 -O2 构建，这是为两个循环生成的程序集：

    call    __ZNSt6chrono12system_clock3nowEv   |    call    __ZNSt6chrono12system_clock3nowEv  
    movl    $5000000, %ecx                      |    movl    $5000000, %ecx                     
    xorpd   %xmm0, %xmm0                        |    xorpd   %xmm0, %xmm0                       
    movsd   2064(%rsp), %xmm3                   |    movsd   2064(%rsp), %xmm3                  
    movq    %rax, %rbx                          |    movq    %rax, %rbx                         
    .align 4                                    |    .align 4                                   
L9:                                             |L15:                                           
    xorl    %edx, %edx                          |    xorl    %edx, %edx                         
    jmp L8                                      |    jmp L18                                    
    .align 4                                    |    .align 4                                   
L32:                                            |L16:                                           
    movsd   2064(%rsp,%rdx,8), %xmm3            |    movsd   2064(%rsp,%rdx,8), %xmm3           
L8:                                             |L18:                                           
    movsd   1552(%rsp,%rdx,8), %xmm1            |    movsd   1040(%rsp,%rdx,8), %xmm2           
    movsd   16(%rsp,%rdx,8), %xmm2              |    movsd   16(%rsp,%rdx,8), %xmm1             
    mulsd   1040(%rsp,%rdx,8), %xmm1            |    mulsd   1552(%rsp,%rdx,8), %xmm2           
    subsd   528(%rsp,%rdx,8), %xmm2             |    subsd   528(%rsp,%rdx,8), %xmm1            
    addsd   %xmm2, %xmm1                        |    addsd   %xmm2, %xmm1                       
    addsd   %xmm3, %xmm1                        |    addsd   %xmm3, %xmm1                       
    movsd   %xmm1, 2064(%rsp,%rdx,8)            |    movsd   %xmm1, 2064(%rsp,%rdx,8)           
    addq    $1, %rdx                            |    addq    $1, %rdx                           
    cmpq    $64, %rdx                           |    cmpq    $64, %rdx                          
    jne L32                                     |    jne L16                                    
    movsd   2064(%rsp), %xmm3                   |    movsd   2064(%rsp), %xmm3                  
    subq    $1, %rcx                            |    subq    $1, %rcx                           
    addsd   %xmm3, %xmm0                        |    addsd   %xmm3, %xmm0                       
    jne L9                                      |    jne L15                                    
    movsd   %xmm0, (%rsp)                       |    movsd   %xmm0, (%rsp)                      
    call    __ZNSt6chrono12system_clock3nowEv   |    call    __ZNSt6chrono12system_clock3nowEv

score 0 · Accepted Answer

C++11 引入了移动语义以减少不必要的副本数量。

您的代码相当模糊，但我认为这应该可以解决问题

在你的struct vec替换

value_type d[N];

和

std::vector<value_type> d;

并添加d(N)到构造函数初始化列表中。std::array是显而易见的选择，但这意味着移动每个元素（即您试图避免的副本）。

然后添加一个移动构造函数：

vec(vec&& from): d(std::move(from.d))
{
}

移动构造函数让新对象“窃取”旧对象的内容。换句话说，不是复制整个向量（数组），而是复制指向数组的指针。

c++ - 表达式模板实现未优化

2 回答 2

Related

Reference