C++ 코드의 런타임 효율성을 찾는 방법

Question

최근에 stackoverflow에 게시 한 프로그램의 효율성을 찾으려고합니다.

How to efficiently delete elements from a vector given an another vector

내가 chrono 객체를 사용하고 다른 답변과 함께 내 코드의 효율성을 비교합니다.

런타임 효율성을 확인하는 올바른 방법입니까?

그렇다면 예제를 사용하여 친절하게 제안 할 수 있습니다.

Code on Coliru

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <chrono> 
#include <ctime> 
using namespace std; 

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{ 
    if(!vDestination.empty() && !vSource.empty()) 
    { 
     for(auto i: vSource) { 
      vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end()); 
     } 
    } 
} 

int main() { 
    vector<int> v1={1,2,3}; 
    vector<int> v2={4,5,6}; 
    vector<int> v3={1,2,3,4,5,6,7,8,9}; 
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now(); 
    remove_elements(v3,v1); 
    remove_elements(v3,v2); 
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now(); 
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl; 
    for(auto i:v3) 
     cout << i << endl; 
    return 0; 
} 

출력

Time difference = 1472 
7 
8 
9 

Answer 1

는 런타임 효율을 확인하는 올바른 방법인가 ?

가장 좋은 방법은 아닌 것처럼 보입니다. 귀하의 방법에 다음과 같은 결함이 있습니다 :

1. 값이 정렬됩니다. Branch prediction 같은 알고리즘으로 정렬 된 값과 정렬되지 않은 값을 테스트 할 때 어리석은 효과가 발생할 수 있습니다. 가능한 수정 : 정렬 및 정렬되지 않은 상태에서 테스트하고 결과를 비교합니다.
2. 값은 하드 코딩됩니다. CPU 캐시는 tricky thing이며 하드 코딩 된 값과 실제 값의 테스트 사이에는 미묘한 차이가있을 수 있습니다. 실제 환경에서는 이러한 연산을 하드 코딩 된 값으로 수행하지 않으므로 파일에서 읽거나 임의의 값을 생성 할 수 있습니다.
3. 값이 너무 적습니다. 코드의 실행 시간은 타이머 정밀도보다 훨씬 작습니다.
4. 코드를 한 번만 실행합니다. 다른 모든 문제를 수정하고 코드를 두 번 실행하면 캐시 워밍업으로 인해 두 번째 실행이 첫 번째 실행보다 훨씬 빠를 수 있습니다. 후속 실행은 첫 번째 실행보다 덜 cache misses입니다.
5. 고정 크기 데이터에서 코드를 한 번 실행합니다. 정렬되지 않은 데이터에 대
   • 정렬
   • v3이 v3 크기는 CPU 캐시를 초과하는 CPU 캐시 대에 맞는에는 다음과 같은 매개 변수의 직교 제품을 충당하기 위해 적어도 네 번, 그렇지 않으면 정확한 테스트를 실행하는 것이 좋습니다 것입니다. 또한 (v1.length() + v3.length()) * sizeof(int)이 캐시에 맞는 지 여부를 고려해보십시오. (v1.length() + v2.length() + v3.length()) * sizeof(int)은 모든 조합에 대해 캐시에 맞는지 등을 결정합니다. 당신의 접근 방식과

Answer 2

가장 큰 문제는 다음과 같습니다 당신이 테스트하고

1) 코드가 너무 짧고 예측이다. 최소한 수백 밀리 초 단위가되도록 적어도 수천 번 실행해야합니다. 측정 사이에. 데이터를 더 크게 만들고 예측 가능성을 낮추어야합니다. 일반적으로 CPU 캐시는 합성 입력 데이터 인 PITA를 기반으로 정확한 측정을 수행합니다.

2) 컴파일러는 코드을 다시 주문할 수 있습니다. 일반적으로 시간을 확인하기 위해 호출간에 수행 할 코드를 보장하기 란 매우 어렵습니다. 한편으로 최적화를 전화 걸기가 가능하지만 다른 한편으로 최적화 된 코드를 측정하고 싶습니다.

하나의 해결책은 전체 프로그램 최적화를 끄고 타이밍 호출을 다른 컴파일 장치에 넣는 것입니다.

또 다른 가능한 해결책은 테스트와 관련하여 메모리 울타리를 사용하는 것입니다.

std::atomic_thread_fence(std::memory_order_seq_cst); 

(#include <atomic> 및 C++ 11 가능 컴파일러 필요).

또한 프로파일 러 데이터를 사용하여 L1/2/3 캐시가 얼마나 효율적인지, 메모리 병목 현상, 명령어 폐기율 등을 측정 할 수 있습니다. Intel x86에서 가장 좋은 도구는 상업용입니다 (vtune), AMD x86에서도 비슷한 도구가 무료입니다 (codeXL).

Answer 3

Celero과 같은 벤치마킹 라이브러리를 사용하여 측정을 수행하고 성능 측정의 까다로운 부분을 처리하는 것을 고려해 볼 수 있습니다. 최적화하려는 코드에 계속 집중할 수 있습니다. 더 복잡한 예는 내가 당신의 이전 질문 (How to efficiently delete elements from a vector given an another vector)에 대한 대답에 연결 한 코드에서 사용할 수 있지만 간단한 사용 사례는 다음과 같이 보일 것이다 :

BENCHMARK(VectorRemoval, OriginalQuestion, 100, 1000) 
{ 
    std::vector destination(10000); 
    std::generate(destination.begin(), destination.end(), std::rand); 
    std::sample(destination.begin(), destination.end(), std::back_inserter(source), 
     100, std::mt19937{std::random_device{}()})  

    for (auto i: source) 
     destination.erase(std::remove(destination.begin(), destination.end(), i), 
      destination.end());  
}