表达式模板实现未优化



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

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

完整的代码列表可以在这里找到:

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

(为混乱的代码道歉。)

简而言之,我主要比较以下两个循环:

ET:

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

HW:

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

表达式模板的要点是,对子表达式的评估可能会导致临时性的,这会产生成本,但不会带来任何好处。在您的代码中,您并没有真正地将苹果与苹果进行比较。比较的两种选择是:

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

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

你的代码相当模糊,但我认为这应该能解决的问题

在您的struct vec中更换

value_type d[N];

带有

std::vector<value_type> d;

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

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

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

move构造函数允许新对象"窃取"旧对象的内容。换句话说,不是复制整个矢量(数组),而是只复制指向数组的指针。

最新更新