분기 예측 자에게 분기를 따를 가능성이 얼마나됩니까?

분기 예측 자에게 분기를 따를 가능성이 얼마나됩니까?

---

명확히하기 위해 여기서는 어떤 종류의 이식성도 고려하지 않기 때문에 나를 특정 상자에 묶어주는 솔루션은 괜찮습니다.

기본적으로 99 %의 시간이 참으로 평가되는 if 문이 있고 마지막 성능 클럭을 모두 출력하려고합니다. 어떤 종류의 컴파일러 명령을 실행할 수 있습니까? 중요) 분기 예측 자에게 해당 분기에 대해 캐시해야한다고 알려주는 것이 중요합니까?

---

예. http://kerneltrap.org/node/4705

이는 __builtin_expectgcc (버전> = 2.96)가 프로그래머에게 분기 예측 정보를 컴파일러에 표시하기 위해 제공하는 방법입니다. 의 반환 값 __builtin_expect은 전달 된 첫 번째 인수 (정수일 수 있음)입니다.

if (__builtin_expect (x, 0))
                foo ();

     [This] would indicate that we do not expect to call `foo', since we
     expect `x' to be zero. 

---

예,하지만 효과 가 없습니다 . 예외는 Netburst 이전의 오래된 (구식) 아키텍처이며, 그 후에도 측정 가능한 작업을 수행하지 않습니다.

인텔이 Netburst 아키텍처와 함께 도입 한 "브랜치 힌트"opcode와 일부 오래된 아키텍처의 콜드 점프 (역방향 예측, 전방 예측 비 점점)에 대한 기본 정적 분기 예측이 있습니다. GCC는를 사용하여이를 구현합니다 __builtin_expect (x, prediction). 여기서 예측은 일반적으로 0 또는 1입니다. 컴파일러가 내 보낸 opcode는 모든 최신 프로세서 아키텍처 (> = Core 2)에서 무시 됩니다. 이것이 실제로 어떤 일을하는 작은 모퉁이의 경우는 예전 Netburst 아키텍처의 콜드 점프의 경우입니다. 인텔은 이제 정적 분기 힌트를 사용하지 않는 것이 좋습니다. 아마도 코드 크기의 증가가 가능한 한계 속도 증가보다 더 해롭다 고 생각하기 때문일 것입니다.

예측 자에 대한 쓸모없는 분기 힌트 외에도 __builtin_expect컴파일러는 캐시 사용을 개선하거나 메모리를 절약하기 위해 코드를 재정렬 할 수 있습니다.

예상대로 작동하지 않는 데는 여러 가지 이유가 있습니다.

• 프로세서는 작은 루프 (n <64)를 완벽하게 예측할 수 있습니다.
• 프로세서는 작은 반복 패턴 (n ~ 7)을 완벽하게 예측할 수 있습니다.
• 프로세서 자체는 컴파일 시간 동안 컴파일러 / 프로그래머보다 런타임 동안 분기 확률을 더 잘 예측할 수 있습니다.
• 분기 의 예측 가능성 (= 분기가 올바르게 예측 될 확률)은 분기를 취할 확률보다 훨씬 더 중요합니다. 안타깝게도 이는 아키텍처에 크게 의존하며 분기의 예측 가능성을 예측하는 것은 매우 어렵습니다.

Agner Fogs 매뉴얼 에서 분기 예측의 내부 작업에 대해 자세히 알아보십시오 . gcc 메일 링리스트를 참조하십시오 .

---

Pentium 4 (일명 Netburst 마이크로 아키텍처)에는 jcc 명령어에 대한 접두사로 분기 예측 자 힌트가 있었지만 P4만이 이러한 작업을 수행했습니다. http://ref.x86asm.net/geek32.html을 참조하십시오 . 그리고 http://www.agner.org/optimize/ 에서 Agner Fog의 훌륭한 asm opt 가이드의 섹션 3.5 . 그는 C ++ 최적화에 대한 가이드도 가지고 있습니다.

이전 및 이후 x86 CPU는 이러한 접두사 바이트를 자동으로 무시합니다. 가능성 / 불가능 성 힌트 사용에 대한 성능 테스트 결과가 있습니까? PowerPC에는 인코딩의 일부로 분기 예측 힌트가있는 일부 점프 명령이 있다고 언급합니다. 매우 드문 건축 적 특징입니다. 컴파일 타임에 분기를 정적으로 예측하는 것은 정확하게 수행하기가 매우 어렵 기 때문에 일반적으로 하드웨어에 맡겨서 파악하는 것이 좋습니다.

최신 Intel 및 AMD CPU에서 분기 예측 자와 분기 대상 버퍼가 어떻게 작동하는지에 대해 공식적으로 게시 된 내용은 많지 않습니다. 최적화 매뉴얼 (AMD 및 Intel 웹 사이트에서 쉽게 찾을 수 있음)은 몇 가지 조언을 제공하지만 특정 동작을 문서화하지는 않습니다. 어떤 사람들은 구현을 구체화하기 위해 테스트를 실행했습니다. 예를 들어 Core2에 몇 개의 BTB 항목이 있는지 ... 어쨌든, 예측자를 명시 적으로 암시하는 아이디어는 (현재로서는) 포기되었습니다.

예를 들어 Core2에는 루프가 항상 짧은 반복 횟수 (<8 또는 16 IIRC)를 실행하는 경우 루프 종료를 잘못 예측하는 것을 방지 할 수있는 분기 히스토리 버퍼가 있습니다. 그러나, 너무 빨리 풀다을하지 말라 (펜린 (Penryn) 또는 19uops) 64bytes에 맞는, 그들은있는 거이 Agner 안개의 PDF 파일을 읽을 가서 ... 버퍼에서 다시 재생하기 때문에 명령이 병목 현상을 가져가되지 않습니다 루프 때문에 우수한 .

인텔이 지난 몇 년 동안 정적 분기 예측 메커니즘을 변경 한 이유는 무엇입니까? 도 참조하십시오 . : Sandybridge는 정적 예측을 전혀 사용하지 않기 때문에 CPU가 수행하는 작업을 리버스 엔지니어링하려는 성능 실험에서 알 수 있습니다. (많은 구형 CPU는 동적 예측이 실패 할 때 대체로 정적 예측을 사용합니다. 일반적인 정적 예측은 정방향 분기를 사용하지 않고 역방향 분기를 사용하는 것입니다 (역방향 분기는 종종 루프 분기이기 때문).

---

GNU C를 사용 하는 likely()/ unlikely()매크로 의 효과 __builtin_expect(Drakosha의 답변 언급처럼)는 BP 힌트를 asm에 직접 삽입 하지 않습니다 . (으로 그렇게 할 수 gcc -march=pentium4있지만 다른 것을 컴파일 할 때는 그렇지 않습니다.)

실제 효과는 빠른 경로가 취한 분기 수가 적고 총 명령어 수가 적도록 코드를 배치하는 것입니다. 이것은 정적 예측이 작동하는 경우에 분기 예측에 도움이 될 것입니다 (예 : 예측 자 캐시에서 분기를 서로 별칭을 지정하는 대신 정적 예측으로 대체하는 CPU에서 동적 예측자가 콜드).

if else 문에서 GCC의 __builtin_expect의 장점은 무엇입니까?를 참조하십시오 . 코드 생성의 특정 예를 보려면.

완벽하게 예측 된 경우에도 가져간 나뭇 가지는 가져 오지 않은 나뭇 가지보다 약간 더 비쌉니다. CPU가 16 바이트 단위로 코드를 가져와 병렬로 디코딩 할 때 취해진 분기는 해당 가져 오기 블록의 이후 명령어가 실행될 명령어 스트림의 일부가 아님을 의미합니다. 처리량이 많은 코드에서 병목이 될 수있는 프런트 엔드에 버블을 생성합니다 (캐시 누락시 백 엔드에서 중단되지 않고 높은 명령 수준 병렬 처리가 있음).

다른 블록 사이를 뛰어 다니면 잠재적으로 더 많은 코드 캐시 라인에 닿아 L1i 캐시 풋 프린트가 증가하고 추울 경우 더 많은 명령 캐시 미스가 발생할 수 있습니다. (그리고 잠재적으로 uop-cache 풋 프린트). 그래서 그것은 빠른 경로가 짧고 선형 적이라는 또 다른 장점입니다.

---

GCC의 프로필 기반 최적화는 일반적으로 가능성이 있거나 가능성이없는 매크로를 불필요하게 만듭니다. 컴파일러는 각 분기가 코드 레이아웃을 결정하는 방법에 대한 런타임 데이터를 수집하고 핫 블록과 콜드 블록 / 함수를 식별합니다. (예를 들어, 핫 기능에서는 루프가 풀리지 만 콜드 기능에서는 풀리지 않습니다.) -fprofile-generate및 -fprofile-use GCC 설명서를 참조하십시오 . g ++에서 프로필 기반 최적화를 사용하는 방법은 무엇입니까?

그렇지 않으면 GCC는 가능성이 있거나 가능성이없는 매크로를 사용하지 않고 PGO를 사용하지 않은 경우 다양한 휴리스틱을 사용하여 추측해야합니다. -fguess-branch-probability기본적으로 -O1이상 에서 활성화됩니다 .

https://www.phoronix.com/scan.php?page=article&item=gcc-82-pgo&num=1 은 제온 확장 가능 서버 CPU에서 gcc8.2를 사용하는 PGO 대 일반에 대한 벤치 마크 결과를 제공합니다. (Skylake-AVX512). 모든 벤치 마크는 최소한 약간의 속도 향상을 얻었으며 일부는 ~ 10 %의 이익을 얻었습니다. (대부분은 핫 루프에서 루프 풀기에서 발생하지만 일부는 아마도 더 나은 분기 레이아웃 및 기타 효과에서 가져온 것입니다.)

---

분기 예측에 대해 걱정하기보다는 코드를 프로파일 링하고 코드를 최적화하여 분기 수를 줄이는 것이 좋습니다. 한 가지 예는 if문을 사용하는 대신 부울 프로그래밍 기술을 사용하는 루프 언 롤링 입니다.

대부분의 프로세서는 명령문을 프리 페치하는 것을 좋아합니다. 일반적으로 분기 문은 프로세서 내에서 오류 를 생성 하여 프리 페치 큐를 플러시합니다. 이것이 가장 큰 페널티입니다. 이 패널티 시간을 줄이려면 더 적은 수의 분기를 사용할 수 있도록 코드를 다시 작성 (및 디자인)하십시오. 또한 일부 프로세서는 분기하지 않고도 조건부로 명령을 실행할 수 있습니다.

루프 풀기 및 대형 I / O 버퍼를 사용하여 1 시간의 실행 시간에서 2 분으로 프로그램을 최적화했습니다. 이 경우 분기 예측으로 많은 시간을 절약 할 수 없었을 것입니다.

---

SUN C Studio에는이 경우에 대해 정의 된 몇 가지 pragma가 있습니다.

#pragma rare_called ()

조건식의 한 부분이 함수 호출이거나 함수 호출로 시작하는 경우 작동합니다.

하지만 일반적인 if / while 문에 태그를 지정할 방법이 없습니다.

---

No, because there's no assembly command to let the branch predictor know. Don't worry about it, the branch predictor is pretty smart.

Also, obligatory comment about premature optimization and how it's evil.

EDIT: Drakosha mentioned some macros for GCC. However, I believe this is a code optimization and actually has nothing to do with branch prediction.

---

This sounds to me like overkill - this type of optimization will save tiny amounts of time. For example, using a more modern version of gcc will have a much greater influence on optimizations. Also, try enabling and disabling all the different optimization flags; they don't all improve performance.

Basically, it seems super unlikely this will make any significant difference compared to many other fruitful paths.

EDIT: thanks for the comments. I've made this community wiki, but left it in so others can see the comments.

참고URL : https://stackoverflow.com/questions/1851299/is-it-possible-to-tell-the-branch-predictor-how-likely-it-is-to-follow-the-branc