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

Question

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

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

可以在此处找到完整的代码 list :

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 导致编译器错误。

Answer 1

表达式模板的要点在于，子表达式的求值可能会产生临时值，这会产生成本并且不会提供任何好处。在您的代码中，您并没有真正将苹果与苹果进行比较。要比较的两个替代方案是:

// 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));

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

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

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

I essentially want to update v4 in place without the copy

使用表达式模板和您当前的 vector 界面，您将为临时和拷贝付费。原因是在表达式的(概念)评估期间创建了一个新 vector ，而对您来说 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