>

다음 코드로 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;
}

및 런타임 ( value.cpp 값을 전달하는 파일의 이름을 지정했습니다.  그리고 참고 reference.cpp )

$ 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

    스피드 업에 대한 관찰을 재현 할 수 있었는데, 훨씬 더 눈에 띄었습니다 (1.75 배 더 빠름). 문제는 x 값을 전달할 때 컴파일러가 그렇지 않은 최적화를 수행 할 수있게하는 것 같습니다. 이러한 최적화는 역효과를 일으켜 프로세서에 의도하지 않은 중단을 초래합니다. 컴파일러는 비교 및 ​​분기가 아닌 연속적인 몇 가지 조건부 이동을 생성합니다. 비교 및 분기는 연속적인 조건부 이동보다 훨씬 빠릅니다.

    컴파일러가 문제를 일으킨 코드를 단순화하여 이것을 피할 수있었습니다.

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

    로 줄일 수 있습니다

    carry = tmp >> numbits;
    tmp &= imax - 1;
    
    

    사용중인 gcc 버전은 다음과 같습니다

    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 보고서 프레스 enter   main 에서   Annotate main 를 선택하십시오 , 소스 코드와 함께 프로그램의 해체와 프로파일 러가 함수의 각 명령에서 프로그램이 실행되는 것을 발견 한 시간의 백분율을 볼 수 있습니다 ... 실제로이 숫자는 힌트로만 사용해야합니다. 실제로 캐시에서 멈췄거나 누락 된 이전 명령이거나 잘못 예측 된 분기 등이있을 때 많은 수의 명령어가 표시됩니다. 따라서 큰 카운트가 표시되면이 명령어의 원인을 확인하십시오. 그 이유는 프로파일이 통계적이며 프로그램이 일정한 속도로 중단되고 명령 포인터가 어디에 있는지 확인하고 종종 캐시 누락 또는 잘못 예측 한 분기 또는 일부 내부로 인해 프로세서가 정지되는 동안 인터럽트가 발생하기 때문입니다 데이터 의존성.

    프로파일 러에 더 많은 시간을 허용하기 위해 반복 횟수를 늘 렸습니다

    int N = 20000;
    
    

    x가 값으로 전달되면 Took 11.58seconds total  이것이 내가 보는 것입니다. 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가 참조로 전달되면 Took 6.59seconds total , 이것이 내가 보는 것입니다

          :            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                                                                                                                        
    
    

  • 답변 # 2

    어셈블러 코드를 보지 않으면 확실하지 않지만 일반적으로 unsigned long long 전달  값별로 스택에 값을 복사하기 위해 컴파일러에서 추가 코드를 생성해야 할 수도 있습니다.

    참조로 전달하면 컴파일러가 포인터를 쉽게 전달할 수 있습니다. 포인터는 이미 편리한 레지스터에있을 수 있습니다.

관련 자료

  • 이전 objective c - UITableView의 둥근 모서리 (iOS7)
  • 다음 winforms - 여러 파일 열기 (OpenFileDialog, C #)