for 루프 반복은 분기로 동일합니까?

Question

정상적인 날에 프로그래밍 할 때, 나는 모든 가지가 찍히지 않을 것입니다.

int retval = do_somting(); 
if(!retval) { /* Less-than-likely event*/ } 

이렇게하면 분기 예측이 최적화되어 CPU 예측기 비트가 "수행하지 않음"으로 설정됩니다. 그러나 for 루프 이후에 예측 변수 비트가 강제로 "take"로 돌아 가게됩니까?

// prediction = "likely take" 
if(false) { } 

// prediction = "probably take" 
if(false) { } 

// prediction = "probably not take" 
if(false) { } 

// prediction = "likely not take" 
if(false) { } 

/* ... thousands of other if(false) that are speedy-fast */ 

for(int i = 0; i < 5; i++) { } 
// prediction = "likely take"? 

나는 그것이 비현실적이고 소문자 최적화 알고 있지만, 헤이, 더 많은 것을 당신은 알고있다.

편집 : GCC가 위의 코드를 모두 지우지 않고 amd64 아키텍처에 대해서만 이야기 해 봅시다. 이 질문이 얼마나 저급인지는 몰랐습니다.

Answer 1

분기 예측은 CPU의 모델에 따라 달라집니다.

this paper에 따르면, 분기 예측은 루프를 정상 분기에 연관시킬 때 수많은 방식으로 처리됩니다. 일부 CPU에는 별도의 예측 루프가 있습니다. 따라서 if 문은 for 문에 대한 예측에 전혀 영향을 미치지 않습니다. 다른 이들은 동일한 예측을 공유합니다.

관계없이이 질문에 대한 진정한 대답은 하나도 없습니다. 분기 효율에 관해서는 루프를 측정하지 않아야합니다.

물론 단일 CPU 모델에서만 프로그램을 실행하려고 계획하지 않는 한.

Answer 2

분기 예측 (AMD64 포함)을 사용하는 대부분의 아키텍처는 짧은 하향/정방향 점프/분기 가능성이 낮고 상향/하향 분기/점프가 짧은 것으로 간주합니다. 즉, 대부분의 루프가 계속 반복 될 것으로 예상됩니다. 이렇게하면 do-while 루프는 초기 조건으로 인해 for 루프 또는 while 루프보다 훨씬 효율적입니다. 그러나 대부분의 최적화 컴파일러는 가능하면이 코드를 유사한 코드로 최적화합니다.

__builtin_expect()과 함께 조건을 사용하여 -O3 최적화 수준에서 gcc를 사용하여 어셈블리의 차이점을 확인할 수 있습니다. 가능성이 낮은 분기는 일반적으로 앞으로 건너 뛰기가 가능한 반면 조건은 전혀 분기하지 않거나 뒤로 건너 뜁니다. 논리를 뒤집을 수 있습니다. 참고 : -O3에서 gcc는 가능성이 낮은 분기로 코드를 복제하여 가능한 경우의 분기를 최소화 할 수 있습니다.

캐시 라인에 맞는 루프는 시작으로 분기하면 캐시 미스가 없으므로 의미가 있습니다. 비슷하게, 프로그램은 일반적으로 함수 내에서 선형 적으로 진행하기 때문에 최근 실행 된 코드가 이미 캐시에있을 가능성이 높습니다. 루프를 여러 개의 "최적화 된"조건문으로 대체하면 어떤 시점 (약 4 개의 조건부)에서 캐시 미스가 가독성과 유지 관리 비용을 감안할 때 얻을 수있는 미미한 이점보다 우선합니다.