C++ 중첩 루프 성능

Question

기본적으로 요소 수가 많은 경우 두 개의 벡터가 있고 요소의 데이터를 샘플링하는 데 사용되는 소수의 프로브의 경우 두 번째 벡터가 있습니다. 나는 두 개의 고리를 구현하기위한 질문을 발견했다. 당연히 I는 큰 벡터 위에 외부 루프 일 것이다 갖는 생각 유익

구현 1

for(auto& elem: elements) { 
    for(auto& probe: probes) { 
     probe.insertParticleData(elem); 
    } 
} 

그러나 두 번째 구현은 시간

구현 (2)의 절반만을 취한다는 것 :

for(auto& probe: probes) { 
    for(auto& elem: elements) { 
     probe.insertParticleData(elem); 
    } 
} 

그 이유가 되겠습니까?

편집 : 프로브까지의 거리가 한계 미만인 경우

타이밍 내가 테스트, 기본적으로 두 가지를 다음 코드

clock_t t_begin_ps = std::clock(); 
... // timed code 
clock_t t_end_ps = std::clock(); 
double elapsed_secs_ps = double(t_end_ps - t_begin_ps)/CLOCKS_PER_SEC; 

에 의해 요소의 데이터를 삽입 생성되었고, 평균 계산

probe::insertParticleData (const elem& pP) { 
    if (!isInside(pP.position())) {return false;} 
    ... // compute alpha and beta 
    avg_vel = alpha*avg_vel + beta*pP.getVel(); 
    return true; 
} 

메모리 사용에 대한 아이디어를 얻으려면 대략 다음과 같습니다. 10 개의 요소는 30 개의 double 데이터 멤버가있는 객체입니다. 테스트를 위해 나는 15 개의 double을 포함하는 10 개의 probe를 사용했다.

Answer 1

내 생각 엔 : insertParticleData가 가상 인 경우 컴파일러는 함수의 주소를 내부 루프 내에서 상수로 처리하고 내부 루프 외부에서 vtable 인출을 이동합니다. 즉, 다음과 같은 코드를 효과적으로 생성합니다 :

for (auto& probe: probes) { 
     funcPtr p = probe.insertParticleData; 
     for (auto& elem: elements) { 
     (*p)(elem); 
     } 
    } 

반면에 첫 번째 버전에서 p는 모든 내부 반복에 대해 계산됩니다.

Answer 2

오늘의 CPU는 메모리에 대한 선형 액세스를 위해 많이 최적화되어 있습니다. 따라서 몇 개의 긴 루프가 많은 짧은 루프를 이길 것입니다. 내부 루프를 긴 벡터에 대해 반복 할 수 있습니다.