当前位置: 首页 > 知识库问答 >
问题:

为什么将函数参数中的'const ull'更改为'const ull&'会导致性能提高?

蒙光华
2023-03-14

因此,使用下面的代码,将参数x的类型从const ull更改为const ull&(其中typedef unsigned long long ull)在使用gcc 4.7.2和标志-o3-std=C++11-g编译时,会导致大约25%的加速,我不明白为什么这会产生如此大的差异。

static void inline single_mult(const std::vector<ull>::iterator& data,
                  const std::vector<ull>::const_iterator& rbegin,
                  const std::vector<ull>::const_iterator& rend,
                  const ull x) {
        ull tmp=0, carry=0, i=0;
        for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
                tmp = x*(*rhs_it) + data[i] + carry;
                if (tmp >= imax) {
                        carry = tmp >> numbits;
                        tmp &= imax - 1;
                } else { 
                        carry = 0;
                }
                data[i++] = tmp;
        }
        data[i] += carry;
}

在下面的函数中调用它(用于做教科书上的长乘法)

static void naive(std::vector<ull>::iterator data, 
              std::vector<ull>::const_iterator cbegin,
              std::vector<ull>::const_iterator cend  ,
              std::vector<ull>::const_iterator rbegin,
              std::vector<ull>::const_iterator rend) {

    for (auto data_it  = cbegin;
          data_it != cend; ++data_it) {
        if (*data_it != 0) {
            single_mult(data, rbegin, rend, *data_it);
        }
        ++data;
    }
}

计时是通过在循环中调用clock()来完成的,以测量它需要多长时间。不是最精确的方法,但我认为25%的一致性差异意味着这种差异在统计学上是显著的。

完整工作代码块:

#include <vector>
#include <limits>
#include <ctime>
#include <iostream>

typedef unsigned long long ull;
typedef unsigned int uint;
const ull numbits = (ull) std::numeric_limits<uint>::digits;        
const ull imax = 1LL << numbits;     

static void inline single_mult(const std::vector<ull>::iterator& data,
              const std::vector<ull>::const_iterator& rbegin,
              const std::vector<ull>::const_iterator& rend,
              const ull x) {
    ull tmp=0, carry=0, i=0;
    for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
            tmp = x*(*rhs_it) + data[i] + carry;
            if (tmp >= imax) {
                    carry = tmp >> numbits;
                    tmp &= imax - 1;
            } else {
                    carry = 0;
            }
            data[i++] = tmp;
    }
    data[i] += carry;
}

static void naive(std::vector<ull>::iterator data,
              std::vector<ull>::const_iterator cbegin,
              std::vector<ull>::const_iterator cend  ,
              std::vector<ull>::const_iterator rbegin,
              std::vector<ull>::const_iterator rend) {

    for (auto data_it  = cbegin; data_it != cend; ++data_it) {
            if (*data_it != 0) {
                    single_mult(data, rbegin, rend, *data_it);
            }
    ++data;
    }
}


int main() {
    int N = 10000;
    std::vector<ull> vec(N);
    for (int i=0; i<N; ++i) {
        vec[i] = i;
    }

    auto s1 = clock();
    int num = 10;
    std::vector<ull> result(2*N);
    for (int i=0; i<num; ++i) {
    //Need to zero out the vector or the result will be different.
        std::fill(result.begin(), result.end(), 0);
        naive(result.begin(), vec.cbegin(), vec.cend(), vec.cbegin(), vec.cend());
    }
    s1 = (clock() - s1);
    std::cout << "Took " << float(s1)/CLOCKS_PER_SEC << "seconds total." << std::endl;
}
$ g++ -O3 -std=c++11 -g -o reference reference.cpp
$ g++ -O3 -std=c++11 -g -o value value.cpp
$ ./reference                                                                                                                                           
Took 1.05seconds total.                                                                        
$ ./value                                                                 
Took 1.83seconds total.            

共有1个答案

许博达
2023-03-14

我能够再现你对加速的观察,这对我来说更加明显(快了1.75倍)。问题似乎是当您按值传递x时,它使编译器能够执行它不执行的优化,而这些优化适得其反,它们显然在处理器中引入了一个意想不到的停顿。编译器生成两个背靠背的条件移动,而不是比较和分支。比较和分支比背靠背条件移动运行得快得多。

我可以通过简化编译器遇到麻烦的代码来避免这种情况,即

if (tmp >= imax) {
    carry = tmp >> numbits;
    tmp &= imax - 1;
} else {
    carry = 0;
}

可以简化为

carry = tmp >> numbits;
tmp &= imax - 1;
g++ --version
g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)

这些是我使用的命令,perf record将对您的代码进行配置文件,perf report将用配置文件的结果注释源代码和反汇编

 g++ -std=gnu++0x -O3 -g single_mult.cpp -o single_mult
 perf record ./single_mult
 perf report

在perf report中,在main上按Enter键并选择Annotate main,您将看到程序的反汇编以及源代码和探查器发现程序按函数中的每个指令运行的时间百分比...实际上,这些数字只能作为一种提示,通常您会看到具有大计数的指令,而实际上是前一条指令停滞了,或者在缓存中丢失了,或者有一个错误预测的分支等等。因此,当您看到大计数时,请回顾一下,看看是什么导致了它。原因是配置文件是统计的,它以恒定的速率中断程序,并查看指令指针在哪里,而且中断通常发生在处理器由于缓存未命中或错误预测分支或某些内部数据依赖关系而停顿时。

我增加了迭代次数,以便为探查器留出更多的时间

int N = 20000;

当x通过值传递时,总共花了11.58秒这就是我看到的,请注意cmovbe指令

       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
       :                    tmp = x*(*rhs_it) + data[i] + carry;                                                                                                                                 
 11.10 :          400b40:       4c 89 c9                mov    %r9,%rcx                                                                                                                          
  0.00 :          400b43:       48 89 fa                mov    %rdi,%rdx                                                                                                                         
  0.01 :          400b46:       48 03 14 c6             add    (%rsi,%rax,8),%rdx                                                                                                                
 11.65 :          400b4a:       48 0f af 0c c3          imul   (%rbx,%rax,8),%rcx                                                                                                                
  0.99 :          400b4f:       48 01 ca                add    %rcx,%rdx                                                                                                                         
       :                    if (tmp >= imax) {                                                                                                                                                   
       :                            carry = tmp >> numbits;                                                                                                                                      
  2.25 :          400b52:       48 89 d7                mov    %rdx,%rdi                                                                                                                         
       :                            tmp &= imax - 1;                                                                                                                                            
 10.99 :          400b55:       48 89 d1                mov    %rdx,%rcx                                                                                                                         
       :                      const ull x) {                                                                                                                                                     
       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
       :                    tmp = x*(*rhs_it) + data[i] + carry;                                                                                                                                 
       :                    if (tmp >= imax) {                                                                                                                                                    
       :                            carry = tmp >> numbits;                                                                                                                                      
  0.69 :          400b58:       48 c1 ef 20             shr    $0x20,%rdi                                                                                                                        
       :                            tmp &= imax - 1;                                                                                                                                              
  9.54 :          400b5c:       83 e1 ff                and    $0xffffffff,%ecx                                                                                                                   
  9.05 :          400b5f:       4c 39 c2                cmp    %r8,%rdx                                                                                                                          
 10.78 :          400b62:       49 0f 46 fb             cmovbe %r11,%rdi                                                                                                                          
       :                    } else {                                                                                                                                                              
       :                            carry = 0;                                                                                                                                                    
       :                    }                                                                                                                                                                     
       :                    data[i++] = tmp;                                                                                                                                                     
 20.73 :          400b66:       48 83 c0 01             add    $0x1,%rax                                                                                                                          
  0.02 :          400b6a:       4c 39 c2                cmp    %r8,%rdx                                                                                                                           
  0.17 :          400b6d:       48 0f 46 ca             cmovbe %rdx,%rcx                                                                                                                         
       :        static void inline single_mult(const std::vector<ull>::iterator& data,                                                                                                            
       :                      const std::vector<ull>::const_iterator& rbegin,                                                                                                                    
       :                      const std::vector<ull>::const_iterator& rend,                                                                                                                      
       :                      const ull x) {                                                                                                                                                     
       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
 11.47 :          400b71:       4c 39 d0                cmp    %r10,%rax                                                                                                                         
       :                            carry = tmp >> numbits;                                                                                                                                      
       :                            tmp &= imax - 1;                                                                                                                                             
       :                    } else {                                                                                                                                                             
       :                            carry = 0;                                                                                                                                                   
       :                    }                                                                                                                                                                    
       :                    data[i++] = tmp;                                                                                                                                                     
  0.01 :          400b74:       48 89 4c c6 f8          mov    %rcx,-0x8(%rsi,%rax,8)                                                                                                            
       :        static void inline single_mult(const std::vector<ull>::iterator& data,                                                                                                           
       :                      const std::vector<ull>::const_iterator& rbegin,                                                                                                                    
       :                      const std::vector<ull>::const_iterator& rend,                                                                                                                      
       :                      const ull x) {                                                                                                                                                     
       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
  0.53 :          400b79:       75 c5                   jne    400b40 <main+0x250>                                                                                                               
       :                    } else {                                                                                                                                                             
       :                            carry = 0;                                                                                                                                                   
       :                    }                                                                                                                                                                    
       :                    data[i++] = tmp;                                                                                                                                                     
       :            }                                                                                                                                                                             
       :            data[i] += carry;                                                                                                                                                            
  0.00 :          400b7b:       4a 01 3c d6             add    %rdi,(%rsi,%r10,8)                                                                                                                
  0.01 :          400b7f:       48 83 c5 08             add    $0x8,%rbp                                                                                                                         

当x通过引用传递时,总共花费了6.59秒,这就是我看到的

       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
 20.90 :          400b30:       48 8b 17                mov    (%rdi),%rdx                                                                                                                       
       :                    tmp = x*(*rhs_it) + data[i] + carry;                                                                                                                                 
  1.38 :          400b33:       49 0f af 14 c1          imul   (%r9,%rax,8),%rdx                                                                                                                   
  4.82 :          400b38:       48 03 0c c6             add    (%rsi,%rax,8),%rcx                                                                                                                
 22.41 :          400b3c:       48 01 ca                add    %rcx,%rdx                                                                                                                         
       :                    if (tmp >= imax) {                                                                                                                                                   
       :                            carry = tmp >> numbits;                                                                                                                                      
       :                            tmp &= imax - 1;                                                                                                                                               
       :                    } else {                                                                                                                                                             
       :                            carry = 0;                                                                                                                                                   
  2.95 :          400b3f:       31 c9                   xor    %ecx,%ecx                                                                                                                         
       :                      const std::vector<ull>::const_iterator& rend,                                                                                                                      
       :                      const ull &x) {                                                                                                                                                    
       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
       :                    tmp = x*(*rhs_it) + data[i] + carry;                                                                                                                                 
       :                    if (tmp >= imax) {                                                                                                                                                   
  0.23 :          400b41:       4c 39 d2                cmp    %r10,%rdx                                                                                                                         
  0.00 :          400b44:       76 0a                   jbe    400b50 <main+0x260>                                                                                                               
       :                            carry = tmp >> numbits;                                                                                                                                      
  2.27 :          400b46:       48 89 d1                mov    %rdx,%rcx                                                                                                                         
       :                            tmp &= imax - 1;                                                                                                                                             
  1.29 :          400b49:       83 e2 ff                and    $0xffffffff,%edx                                                                                                                  
       :                      const ull &x) {                                                                                                                                                    
       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
       :                    tmp = x*(*rhs_it) + data[i] + carry;                                                                                                                                 
       :                    if (tmp >= imax) {                                                                                                                                                   
       :                            carry = tmp >> numbits;                                                                                                                                      
  0.26 :          400b4c:       48 c1 e9 20             shr    $0x20,%rcx                                                                                                                        
       :                            tmp &= imax - 1;                                                                                                                                             
       :                    } else {                                                                                                                                                             
       :                            carry = 0;                                                                                                                                                   
       :                    }                                                                                                                                                                    
       :                    data[i++] = tmp;                                                                                                                                                     
 19.67 :          400b50:       48 83 c0 01             add    $0x1,%rax                                                                                                                         
       :        static void inline single_mult(const std::vector<ull>::iterator& data,                                                                                                           
       :                      const std::vector<ull>::const_iterator& rbegin,                                                                                                                    
       :                      const std::vector<ull>::const_iterator& rend,                                                                                                                      
       :                      const ull &x) {                                                                                                                                                    
       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
  0.53 :          400b54:       4c 39 c0                cmp    %r8,%rax                                                                                                                          
       :                            carry = tmp >> numbits;                                                                                                                                      
       :                            tmp &= imax - 1;                                                                                                                                             
       :                    } else {                                                                                                                                                             
       :                            carry = 0;                                                                                                                                                   
       :                    }                                                                                                                                                                      
       :                    data[i++] = tmp;                                                                                                                                                     
  0.39 :          400b57:       48 89 54 c6 f8          mov    %rdx,-0x8(%rsi,%rax,8)                                                                                                            
       :        static void inline single_mult(const std::vector<ull>::iterator& data,                                                                                                           
       :                      const std::vector<ull>::const_iterator& rbegin,                                                                                                                    
       :                      const std::vector<ull>::const_iterator& rend,                                                                                                                      
       :                      const ull &x) {                                                                                                                                                    
       :            ull tmp=0, carry=0, i=0;                                                                                                                                                     
       :            for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {                                                                                                                       
 22.91 :          400b5c:       75 d2                   jne    400b30 <main+0x240>                                                                                                               
       :                    } else {                                                                                                                                                             
       :                            carry = 0;                                                                                                                                                   
       :                    }                                                                                                                                                                    
       :                    data[i++] = tmp;                                                                                                                                                     
       :            }                                                                                                                                                                            
       :            data[i] += carry;                                                                                                                                                            
  0.00 :          400b5e:       4a 01 0c c6             add    %rcx,(%rsi,%r8,8)                                                                                                                 
  0.00 :          400b62:       48 83 c7 08             add    $0x8,%rdi                                                                                                                         
 类似资料:
  • 考虑: 为什么改变的值会改变的值?

  • 问题内容: 目前,我正在研究Sams出版的《 24小时自学Android应用程序开发》一书。我是Java,Android或其他方面的新手。我在ActionScript 3中具有非常扎实的背景,该语言与Java具有足够的相似性,因此该语言本身并不难掌握,但对于本书中某些代码示例的基本原理,我仍然存在一些疑问。例如,以下是第9小时的示例代码随附的函数: 在此函数签名中,作者已将scoreTable参数

  • 谁能告诉我为什么函数参数不能是?这是函数参数在上声明并在函数返回时被取消分配的原因吗?没有办法保留参数值?只是糊涂了。请澄清。 多谢了。

  • 本文向大家介绍为什么虚拟dom会提高性能?相关面试题,主要包含被问及为什么虚拟dom会提高性能?时的应答技巧和注意事项,需要的朋友参考一下 虚拟dom相当于在js和真实dom中间加了一个缓存,利用dom diff算法避免了没有必要的dom操作,从而提髙性能。 具体实现步骤如下: 1. 用JavaScript对象结构表示DOM树的结构;然后用这个树构建一个真正的DOM树,插到文档当中 2.当状态变更

  • 问题内容: 我是ORMLite的主要作者,它使用类上的Java注释来构建数据库模式。我们的程序包最大的启动性能问题是在Android 1.6下调用注释方法。直到3.0我都看到了相同的行为。 我们看到以下简单的注释代码 难以置信地 占用大量GC,这是一个实际的性能问题。在快速的Android设备上,对注释方法的1000次调用几乎耗时一秒。Macbook Pro上运行的相同代码可以同时进行2800万次

  • 问题内容: 我有2张桌子-和。可以将产品存储为 Idn 或 Name (旧式设计),并且该列指定与之关联的实际 类型 。等等是一个子表,该子表被 合并到 该表中以获取真实数据。(在此示例中,是一个表,用于存储 Idn 来演示问题。) 通常,您不应将这些表连接在一起,因为它包含混合数据。但是,如果您选择LHS与RHS匹配的行,则可以正常工作 (1) 。例如,如果是一个存储 Idn 的表,则以下查询将