분기 인식 프로그래밍

분기 인식 프로그래밍

분기 예측 오류가 애플리케이션 성능의 핫 병목 현상이 될 수 있다는 것을 알고 있습니다.제가 볼 수 있듯이, 사람들은 종종 문제를 드러내는 어셈블리 코드를 보여주고 프로그래머들은 보통 분기가 가장 자주 어디로 갈지 예측할 수 있고 분기의 잘못된 예측을 피할 수 있습니다.

제 질문은 다음과 같습니다.

1. 일부 고급 프로그래밍 기법(즉, 어셈블리 없음)을 사용하여 분기 오예측을 방지할 수 있습니까?

2. 고급 프로그래밍 언어로 지점 친화적인 코드를 생성하려면 무엇을 염두에 두어야 합니까(저는 주로 C와 C++에 관심이 있습니다)?

코드 예제 및 벤치마크를 환영합니다.

사람들은 종종... 그리고 프로그래머들은 보통 지점이 어디로 갈 수 있는지 예측할 수 있다고 말합니다.

(*) 숙련된 프로그래머들은 종종 인간 프로그래머들이 그것을 예측하는 것에 매우 서툴다는 것을 상기시킵니다.

1 - 일부 고급 프로그래밍 기법(즉, 어셈블리 없음)을 사용하여 분기 오예측을 방지할 수 있습니까?

표준 c++ 또는 c에는 없습니다.적어도 지점 하나는 아닙니다.종속성 체인의 깊이를 최소화하여 분기 예측 오류가 영향을 미치지 않도록 할 수 있습니다.최신 CPU는 분기의 두 코드 경로를 모두 실행하고 선택되지 않은 경로를 삭제합니다.하지만 여기에는 한계가 있습니다. 그렇기 때문에 지점 예측은 깊은 의존성 체인에서만 중요합니다.

일부 컴파일러는 __builtin_expecting gcc와 같이 수동으로 예측을 제안하기 위한 확장을 제공합니다.다음은 이에 대한 스택 오버플로 질문이 있습니다.더 좋은 것은 일부 컴파일러(예: gcc)가 코드 프로파일링을 지원하고 최적의 예측을 자동으로 감지한다는 점입니다.(*) 때문에 수작업보다는 프로파일링을 사용하는 것이 현명합니다.

2- 고급 프로그래밍 언어로 지점 친화적인 코드를 생성하려면 무엇을 염두에 두어야 합니까(C와 C++에 주로 관심이 있습니다)?

첫째, 분기 예측 오류는 프로그램에서 가장 성능이 중요한 부분에만 영향을 미치고 문제를 측정하고 발견할 때까지 걱정하지 않는다는 점에 유의해야 합니다.

그러나 일부 프로파일러(valgrind, VTune, ...)가 foo.cpp 온라인에서 분기 예측 패널티를 받았다고 말하면 어떻게 해야 합니까?

룬딘은 매우 현명한 조언을 했습니다.

1. 그것이 중요한지 알아보기 위한 조치.
2. 그게 중요하다면, 그럼.
   • 계산의 종속성 체인 깊이를 최소화합니다.그것을 하는 방법은 꽤 복잡하고 제 전문 지식을 넘어서는 것일 수 있으며 조립에 뛰어들지 않고 할 수 있는 것은 많지 않습니다.고급 언어로 수행할 수 있는 작업은 조건부 검사(**) 수를 최소화하는 것입니다.그렇지 않으면 컴파일러 최적화에 좌우됩니다.또한 깊은 의존성 체인을 방지하면 고장난 슈퍼 스칼라 프로세서를 보다 효율적으로 사용할 수 있습니다.
   • 분기를 일관성 있게 예측할 수 있도록 합니다.그 효과는 이 스택 오버플로 질문에서 확인할 수 있습니다.질문에서 배열 위에 루프가 있습니다.루프에 분기가 포함되어 있습니다.분기는 현재 요소의 크기에 따라 달라집니다.데이터가 정렬되었을 때, 루프는 특정 컴파일러로 컴파일되고 특정 CPU에서 실행될 때 훨씬 더 빠르다는 것을 증명할 수 있었습니다.물론 모든 데이터를 정렬 상태로 유지하면 CPU 시간도 소요되며, 분기의 잘못된 예측보다 더 많은 시간이 소요될 수 있습니다.
3. 그래도 문제가 있는 경우 프로파일 기반 최적화(사용 가능한 경우)를 사용합니다.

2번과 3번의 순서를 바꿀 수 있습니다.수작업으로 코드를 최적화하는 것은 많은 일입니다.반면에 프로파일링 데이터를 수집하는 것은 일부 프로그램에서도 어려울 수 있습니다.

(**) 이를 위한 한 가지 방법은 예를 들어 루프를 언롤링하여 변환하는 것입니다.최적화 도구가 자동으로 이 작업을 수행하도록 할 수도 있습니다.그러나 롤을 풀면 캐시와 상호 작용하는 방식에 영향을 미치고 비관적으로 끝날 수 있으므로 측정해야 합니다.

주의할 점으로, 저는 미세 최적화 마법사가 아닙니다.하드웨어 분기 예측 변수가 어떻게 작동하는지 정확히 모르겠습니다.저에게 그것은 가위바위보를 하는 마법의 짐승이고 항상 제 마음을 읽고 저를 이길 수 있는 것처럼 보입니다.저는 디자인과 건축 타입입니다.

그럼에도 불구하고, 이 질문은 높은 수준의 사고방식에 관한 것이었기 때문에, 저는 몇 가지 조언을 할 수 있을 것입니다.

프로파일링

앞서 말했듯이, 저는 컴퓨터 아키텍처 마법사는 아니지만 VTune로 코드를 프로파일링하고 분기 오예측 및 캐시 누락과 같은 것을 측정하여 성능이 중요한 분야에서 항상 이 작업을 수행하는 방법을 알고 있습니다.이 작업(프로파일링)을 수행하는 방법을 모르는 경우 가장 먼저 조사해야 할 사항이 바로 그것입니다.이러한 마이크로 레벨 핫스팟의 대부분은 프로파일러를 손에 쥐고 나중에 발견하는 것이 가장 좋습니다.

분기 제거

많은 사람들이 지점의 예측 가능성을 개선하는 방법에 대해 우수한 수준의 조언을 하고 있습니다. 변수를 .if일반적인 사례를 먼저 확인하기 위한 진술.인텔(https://software.intel.com/en-us/articles/branch-and-loop-reorganization-to-prevent-mispredicts )에서 제공하는 중요한 세부 정보에 대한 포괄적인 기사가 있습니다.

그러나 기본적인 일반적인 사례/희귀 사례 예상치를 초과하여 이 작업을 수행하는 것은 매우 어려우며 측정 후에는 거의 항상 나중에 사용할 수 있도록 저장하는 것이 가장 좋습니다.인간이 분기 예측자의 본질을 정확하게 예측할 수 있는 것은 너무 어렵습니다.페이지 결함이나 캐시 누락과 같은 것들보다 예측하는 것이 훨씬 더 어렵고, 그것들조차도 복잡한 코드베이스에서 인간이 완벽하게 예측하는 것은 거의 불가능합니다.

그러나 분기의 잘못된 예측을 완화하는 보다 쉽고 높은 수준의 방법이 있습니다. 즉, 분기를 완전히 방지하는 것입니다.

소규모/희귀 작업 건너뛰기

제가 경력 초기에 흔히 범했던 실수 중 하나는 많은 동료들이 프로파일링하는 것을 배우기도 전에 시작할 때, 그리고 아직도 열심히 공부하기도 전에, 작고 희귀한 일을 건너뛰려고 하는 것입니다.

, 를 저장하여 계산을 . 예를 들어, 예 한 로 반 는 피 위 트 것 검 큰 메 않 테 수 반 계 로 을 으 적 행 복 하산지 도 색록에모 하블이는니 다입 에한렴저비적 교같이이사테것블검을이는에르색는용하과복이하가바출해을적인 호기메▁to▁an이▁megabytes▁to-▁that▁memoationscos그리고.sin인간의 뇌에는 한 번 계산하고 저장하는 것이 작업을 절약하는 것처럼 보입니다. 단, 이 거대한 LUT에서 메모리 계층을 통해 아래로 메모리를 로드하고 레지스터에 저장하는 것은 저장하려는 계산보다 훨씬 더 많은 비용이 듭니다.

또 다른 경우는 코드 전반에 걸쳐 불필요하게 수행하는(정확성에 영향을 미치지 않는) 작은 계산을 피하기 위해 여러 개의 작은 분기를 추가하는 것입니다. 이는 단순한 최적화 시도로, 불필요한 계산을 수행하는 것보다 분기 비용이 더 많이 들 뿐입니다.

최적화로 분기하려는 이러한 순진한 시도는 약간 비싸지만 드문 작업에도 적용될 수 있습니다.다음 C++ 예를 들어 보겠습니다.

struct Foo
{
    ...
    Foo& operator=(const Foo& other)
    {
        // Avoid unnecessary self-assignment.
        if (this != &other)
        {
            ...
        }
        return *this;
    }
    ...
};

_{대부분의 사용자가 값에 의해 전달된 매개 변수에 대해 복사 및 스왑을 사용하여 복사 할당을 구현하고 어떠한 경우에도 분기를 방지하기 때문에 이는 단순한/설명적인 예입니다.}

이 경우, 우리는 자가 할당을 피하기 위해 분기하고 있습니다.그러나 자가 할당이 중복 작업만 수행하고 결과의 정확성을 저해하지 않는다면, 단순히 자가 복사를 허용하는 실제 성능을 향상시킬 수 있습니다.

struct Foo
{
    ...
    Foo& operator=(const Foo& other)
    {
        // Don't check for self-assignment.
        ...
        return *this;
    }
    ...
};

이것은 자기 평가가 매우 드문 경향이 있기 때문에 도움이 될 수 있습니다.중복 자기배정을 통해 희귀사건의 발생 속도를 늦추고 있지만, 다른 모든 사건에 대해서는 확인할 필요가 없도록 함으로써 공통사건의 발생 속도를 높이고 있습니다.물론 분기 측면에서 일반적인/희귀한 경우 차이가 있기 때문에 분기 오예측을 크게 줄일 수는 없지만, 실제로 존재하지 않는 분기를 잘못 예측할 수는 없습니다.

작은 벡터에 대한 순진한 시도

개인적인 이야기로, 저는 이전에 다음과 같은 많은 코드가 있는 대규모 C 코드베이스에서 일했습니다.

char str[256];
// do stuff with 'str'

물론 사용자 기반이 상당히 넓기 때문에 소프트웨어에서 255자가 넘는 재료의 이름을 입력하고 버퍼를 오버플로하여 세그먼트 결함이 발생할 수 있습니다.우리 팀은 C++에 접속하여 많은 소스 파일을 C++로 이식하고 코드를 다음과 같이 교체했습니다.

std::string str = ...;
// do stuff with 'str'

많은 노력 없이 버퍼 오버런을 제거했습니다.그 당시에는, 만하그, 도당는에시, 너들은이와 같은 이 있습니다.std::string그리고.std::vector힙(자유 저장소)이 할당된 구조물이었고, 효율성을 위해 정확성/안전성을 거래했습니다.이러한 교체된 영역 중 일부는 성능에 매우 중요했으며(엄격한 루프라고 함), 이러한 대량 교체를 통해 많은 버그 보고서를 제거하는 동안 사용자는 속도 저하를 알아차리기 시작했습니다.

그래서 우리는 이 두 기술 사이의 하이브리드 같은 것을 원했습니다.우리는 C 스타일 고정 버퍼 변형(일반적인 경우 시나리오에 완벽하게 적합하고 매우 효율적임)에 대한 안전을 달성하기 위해 무언가를 적용할 수 있기를 원했지만, 버퍼가 사용자 입력에 충분히 크지 않은 드문 경우 시나리오에서 여전히 작동합니다.저는 팀에서 성능 괴짜 중 한 명이었고 프로파일러를 사용하는 몇 안 되는 사람들 중 한 명이었습니다(불행히도 저는 프로파일러를 사용하기에는 너무 똑똑하다고 생각하는 많은 사람들과 함께 일했습니다). 그래서 저는 그 일에 소집되었습니다.

저의 첫 번째 순진한 시도는 이와 같은 것이었습니다(매우 단순화되었습니다: 실제 것은 새로운 배치 등을 사용했고 완전히 표준을 준수하는 시퀀스였습니다).일반적인 경우 고정 크기 버퍼(컴파일 시 지정된 크기)를 사용하고 크기가 해당 용량을 초과하는 경우 동적으로 할당된 버퍼를 사용합니다.

template <class T, int N>
class SmallVector
{
public:
    ...
    T& operator[](int n)
    {
        return num < N ? buf[n]: ptr[n];
    }
    ...
private:
    T buf[N];
    T* ptr;
};

이 시도는 완전히 실패했습니다.구축할 힙/프리 스토어의 가격을 지불하지 않았지만, 지사는operator[]그것을 더 나쁘게 만들었습니다.std::string그리고.std::vector<char>대신 프로파일링 핫스팟으로 나타났습니다malloc한 ()std::allocator그리고.operator new사용했다malloc후드 아래에)그래서 저는 간단히 할당할 아이디어를 빠르게 얻었습니다.ptrbuf생성자에서.지금이다ptr을 가리키는 말.buf 지금은 일적인경도에우, 지고금그.operator[]다음과 같이 구현할 수 있습니다.

T& operator[](int n)
{
    return ptr[n];
}

간단한 분기 제거로 핫스팟이 사라졌습니다.우리는 이제 이전의 C 스타일 고정 버퍼 솔루션과 거의 같은 속도의 범용 표준 호환 컨테이너를 사용할 수 있게 되었습니다. (하나의 추가 포인터와 몇 개의 생성자 명령어만 다를 뿐) 그러나 크기가 다음보다 커야 하는 드문 경우의 시나리오를 처리할 수 있었습니다.N이제 우리는 이것을 더 많이 사용합니다.std::vector(그러나 우리의 사용 사례가 여러 개의 작은 임시 연속 랜덤 액세스 컨테이너를 선호하기 때문입니다.)그리고 그것을 빠르게 만드는 것은 단지 지점을 제거하는 것으로 귀결되었습니다.operator[].

일반적인 대/희귀 대/소문자 구분 기호

프로파일링과 최적화를 수년간 수행한 후 배운 것 중 하나는 "모든 곳에서 절대적으로 빠른" 코드가 없다는 것입니다.최적화의 대부분은 비효율성을 더 큰 효율성과 맞바꾸는 것입니다.사용자는 코드가 어디에서나 절대적으로 빠른 것으로 인식할 수 있지만, 이는 최적화가 일반적인 사례와 일치하는 스마트 트레이드오프(일반적인 사례는 현실적인 사용자-최종 시나리오와 일치하며 이러한 일반 시나리오를 측정하는 프로파일러에서 지적된 핫스팟에서 발생함)에서 비롯됩니다.

성능을 일반적인 경우에 치우치고 드문 경우에서 벗어나면 좋은 일이 발생하는 경향이 있습니다.일반적인 경우가 더 빨라지기 위해서는 종종 드문 경우가 더 느려져야 하지만, 그것은 좋은 일입니다.

비용이 들지 않는 예외 처리

일반적인 사례/희귀 사례 스큐의 예로는 많은 최신 컴파일러에서 사용되는 예외 처리 기술이 있습니다.그들은 제로 코스트 EH를 적용하는데, 이것은 전반적으로 실제로 "제로 코스트"가 아닙니다.예외가 발생할 경우, 그 어느 때보다 속도가 느려집니다.그러나 예외가 발생하지 않는 경우에는 이전보다 더 빠르며 성공적인 시나리오에서는 다음과 같은 코드보다 더 빠릅니다.

if (!try_something())
    return error;
if (!try_something_else())
    return error;
...

여기서 비용이 들지 않는 EH를 대신 사용하고 수동으로 오류를 확인하고 전파하는 것을 피하면 위의 이 코드 스타일보다 예외적이지 않은 경우에 상황이 훨씬 더 빨리 진행되는 경향이 있습니다.대략적으로 말하면, 그것은 지점이 감소했기 때문입니다.하지만 그 대가로 예외가 발생할 경우 훨씬 더 비싼 일이 발생해야 합니다.그럼에도 불구하고 일반적인 사례와 드문 사례 사이의 차이는 실제 시나리오에 도움이 되는 경향이 있습니다.파일을 성공적으로 로드하지 못하는 속도(희귀한 경우)는 일반적인 경우(일반적인 경우)만큼 중요하지 않으므로 많은 최신 C++ 컴파일러가 "비용이 들지 않는" EH를 구현합니다.일반적인 사례와 드문 사례를 왜곡하여 성능 면에서 각각의 사례에서 더 멀리 밀어내는 것이 다시 한 번 이익이 됩니다.

가상 디스패치 및 동질성

의존성이 추상화(예: 안정적 추상화 원리)로 흐르는 객체 지향 코드의 많은 분기는 동적 디스패치(가상 함수 호출 또는 함수 포인터 호출)의 형태로 분기의 많은 부분(물론 분기 예측자에게 잘 작동하는 루프 외에도)을 가질 수 있습니다.

이러한 경우, 일반적인 유혹은 모든 종류의 하위 유형을 기본 포인터를 저장하는 다형성 컨테이너에 통합하고, 이를 통해 루프하고, 해당 컨테이너의 각 요소에서 가상 메서드를 호출하는 것입니다.이로 인해 특히 이 컨테이너가 항상 업데이트되는 경우 많은 분기 예측 오류가 발생할 수 있습니다.유사 코드는 다음과 같이 표시될 수 있습니다.

for each entity in world:
    entity.do_something() // virtual call

이 시나리오를 피하기 위한 전략은 하위 유형을 기준으로 이 다형성 컨테이너를 정렬하기 시작하는 것입니다.이것은 게임 산업에서 인기 있는 꽤 오래된 스타일의 최적화입니다.오늘날 그것이 얼마나 도움이 되는지는 모르겠지만, 그것은 고도의 최적화입니다.

유사한 효과를 달성하는 최근의 경우에도 여전히 유용하다는 것을 알게 된 또 다른 방법은 다형성 컨테이너를 각 하위 유형에 대해 여러 개의 컨테이너로 분할하여 다음과 같은 코드로 이끄는 것입니다.

for each human in world.humans():
    human.do_something()
for each orc in world.orcs():
    orc.do_something()
for each creature in world.creatures():
    creature.do_something()

당연히 이것은 코드의 유지보수성을 방해하고 확장성을 감소시킵니다.그러나 이 세상의 모든 하위 유형에 대해 이 작업을 수행할 필요는 없습니다.우리는 가장 일반적인 경우에만 그것을 하면 됩니다.예를 들어, 이 상상 속의 비디오 게임은 단연코 인간과 오크로 구성되어 있을 수 있습니다.그것은 또한 요정, 도깨비, 트롤, 요정, 요정, 요정 등을 가지고 있을지도 모르지만, 그들은 인간이나 오크만큼 흔하지는 않을지도 모릅니다.그래서 우리는 인간과 오크들을 다른 사람들로부터 떼어놓기만 하면 됩니다.경제적인 여유가 있다면 성능에 덜 중요한 루프에 사용할 수 있는 모든 하위 유형을 저장하는 다형성 컨테이너를 보유할 수도 있습니다.이는 기준 위치를 최적화하기 위한 핫/콜드 분할과 다소 유사합니다.

데이터 중심 최적화

분기 예측을 위한 최적화와 메모리 레이아웃 최적화는 함께 흐릿해지는 경향이 있습니다.분기 예측 변수에 대한 최적화를 시도한 적이 거의 없으며, 다른 모든 것을 다 사용한 후에야 가능했습니다.하지만 저는 기억과 참조의 지역성에 많이 초점을 맞추면 측정 결과 지점의 잘못된 예측이 줄어들었다는 것을 알게 되었습니다(대부분의 경우 정확한 이유는 알지 못합니다).

여기서 데이터 지향 설계를 연구하는 데 도움이 될 수 있습니다.최적화와 관련된 가장 유용한 지식 중 일부는 데이터 지향 설계의 맥락에서 메모리 최적화를 연구하는 데서 비롯된다는 것을 알게 되었습니다.데이터 지향 설계는 추상화(있는 경우)가 적고 대량의 데이터를 처리하는 대용량의 고급 인터페이스를 강조하는 경향이 있습니다.본질적으로 이러한 설계는 동종 데이터의 큰 청크를 처리하는 더 많은 루프 코드를 사용하여 코드에서 이질적인 분기 및 점프의 양을 줄이는 경향이 있습니다.

지사의 잘못된 예측을 줄이는 것이 목표라고 해도 데이터를 보다 신속하게 소비하는 데 더 집중할 수 있습니다.예를 들어, 이전에도 지점이 없는 SIMD에서 몇 가지 큰 이점을 발견했지만, 이러한 사고방식은 여전히 데이터를 더 빨리 소비하는 경향에 있었습니다(Harold와 같은 SO의 도움 덕분에 그렇게 되었습니다).

TL;DR

따라서 이러한 전략은 코드 전반에 걸쳐 높은 수준의 관점에서 분기의 잘못된 예측을 잠재적으로 줄일 수 있습니다.그들은 컴퓨터 아키텍처에 대한 최고 수준의 전문성이 부족하지만, 저는 질문의 수준을 고려할 때 이것이 적절한 종류의 도움이 되는 답변이기를 바랍니다.이러한 조언의 대부분은 일반적으로 최적화를 통해 모호하지만 분기 예측을 위한 최적화는 종종 그 이상의 최적화(메모리, 병렬화, 벡터화, 알고리즘)를 통해 모호해질 필요가 있다는 것을 알게 되었습니다.어쨌든, 가장 안전한 방법은 당신이 깊이 모험하기 전에 당신의 손에 프로파일러가 있는지 확인하는 것입니다.

은 리눅스를 정의합니다.likely그리고.unlikely에 __builtin_expectgcc 파일:

    #define likely(x)   __builtin_expect(!!(x), 1)
    #define unlikely(x) __builtin_expect(!!(x), 0)

의 매크로 정의는 여기를 참조하십시오.include/linux/compiler.h)

다음과 같이 사용할 수 있습니다.

if (likely(a > 42)) {
    /* ... */
} 

또는

if (unlikely(ret_value < 0)) {
    /* ... */
}

일반적으로 핫 내부 루프는 가장 일반적으로 발생하는 캐시 크기에 비례하여 유지하는 것이 좋습니다.즉, 프로그램이 한 번에 32KB 미만의 데이터를 처리하고 상당한 양의 작업을 수행하는 경우 L1 캐시를 잘 사용하는 것입니다.

반대로 핫 내부 루프가 100MB바이트의 데이터를 확인하고 각 데이터 항목에 대해 하나의 작업만 수행하는 경우 CPU는 DRAM에서 데이터를 가져오는 데 대부분의 시간을 소비합니다.

CPU에 분기 예측 기능이 있는 이유 중 일부는 다음 명령을 위해 피연산자를 사전에 가져올 수 있기 때문에 이 기능이 중요합니다.분기 오예측의 성능 결과는 어떤 분기를 취하든 L1 캐시에서 다음 데이터를 가져올 가능성이 높아지도록 코드를 배열함으로써 줄일 수 있습니다.완벽한 전략은 아니지만, L1 캐시 크기는 일반적으로 32K 또는 64K에 머물러 있는 것처럼 보입니다. 이는 업계 전반에 걸쳐 거의 일정한 현상입니다.이러한 방식으로 코딩하는 것은 종종 간단하지 않으며, 다른 사람들이 권장하는 프로파일 기반 최적화 등에 의존하는 것이 아마도 가장 간단한 방법일 것입니다.

분기 오예측 문제가 발생할지 여부는 CPU의 캐시 크기, 시스템에서 실행 중인 다른 항목, 기본 메모리 대역폭/지연 시간 등에 따라 달라집니다.

아마도 가장 일반적인 기법은 정규 및 오류 반환에 별도의 방법을 사용하는 것입니다.C에는 선택의 여지가 없지만 C++에는 예외가 있습니다.컴파일러는 예외 분기가 예외적이므로 예기치 않은 것임을 알고 있습니다.

이는 예외 분기가 예측되지 않은 것처럼 실제로 느리지만 오류가 없는 분기가 더 빨리 생성된다는 것을 의미합니다.평균적으로, 이것은 순승입니다.

1 - 일부 고급 프로그래밍 기법(즉, 어셈블리 없음)을 사용하여 분기 오예측을 방지할 수 있습니까?

피한다고요? 아마 아닐 겁니다.줄이라고요?물론...

2- 고급 프로그래밍 언어로 지점 친화적인 코드를 생성하려면 무엇을 염두에 두어야 합니까(C와 C++에 주로 관심이 있습니다)?

한 기계에 대한 최적화가 반드시 다른 기계에 대한 최적화는 아니라는 점에 유의할 필요가 있습니다.이러한 점을 염두에 두고, 프로파일 기반 최적화는 제공하는 테스트 입력에 따라 분기를 재정렬하는 데 상당히 유용합니다.즉, 이 최적화를 수행하기 위해 프로그래밍을 수행할 필요가 없으며 프로파일링 중인 컴퓨터에 상대적으로 맞게 조정되어야 합니다.테스트 입력과 프로파일링하는 기계가 일반적인 예상과 대략 일치할 때 최상의 결과가 얻어질 것입니다.그러나 이는 다른 최적화에 대한 고려사항이기도 합니다. 분기-표현과 관련이 있거나 다른 경우도 마찬가지입니다.

질문에 답하기 위해 분기 예측이 어떻게 작동하는지 설명하겠습니다.

먼저 프로세서가 촬영된 분기를 올바르게 예측할 때 분기 페널티가 있습니다.프로세서가 분기를 예측할 때 해당 주소에서 실행 흐름이 계속되므로 예측된 분기의 대상을 알아야 합니다.분기 대상 주소가 이미 BTB(Branch Target Buffer)에 저장되어 있다고 가정하면 BTB에서 발견된 주소에서 새 명령을 가져와야 합니다.따라서 분기가 정확하게 예측되더라도 여전히 몇 개의 클럭 주기를 낭비하고 있습니다.
BTB는 연관 캐시 구조를 가지고 있기 때문에 대상 주소가 없을 수 있으며, 따라서 더 많은 클럭 주기가 낭비될 수 있습니다.

반면에 CPU가 분기를 실행되지 않은 것으로 예측하고 정확한 경우 CPU는 이미 연속된 명령이 어디에 있는지 알고 있기 때문에 아무런 불이익이 없습니다.

위에서 설명한 바와 같이, 예측되지 않은 분기는 예측된 분기보다 처리량이 높습니다.

일부 고급 프로그래밍 기법(즉, 어셈블리 없음)을 사용하여 분기 오예측을 방지할 수 있습니까?

합니다.", "가능합니다.코드를 구성하여 모든 분기가 항상 취해지거나 그렇지 않은 반복적인 분기 패턴을 갖도록 할 수 있습니다.
그러나 처리량을 높이려면 위에서 설명한 것처럼 가지를 사용하지 않을 가능성이 가장 높은 방식으로 지점을 구성해야 합니다.

고급 프로그래밍 언어로 지점 친화적인 코드를 생성하려면 무엇을 염두에 두어야 합니까(저는 주로 C와 C++에 관심이 있습니다)?

가능하면 가지를 제거합니다.문 문을 할 때 경우 합니다. if-else " switch " " switch " 렇 할 지 그 때 은 않 인 적 우 반 를 우 경 일 경 하 여 먼 저 인 다 니 합 기 인 가 확 되 지 높 은 용 장 지 을 가 사 이 확 분 성 능 가 않 장 문_를 사용해 보십시오._builtin_expect(condition, 1)컴파일러가 수행되지 않은 것으로 처리할 조건을 생성하도록 강제하는 함수입니다.

분기가 없는 것이 항상 더 나은 것은 아닙니다. 분기의 양쪽이 모두 사소한 것일지라도 말입니다.분기 예측이 작동할 경우 루프 전달 데이터 종속성보다 빠릅니다.

gcc 최적화 플래그 참조 - O3는 다음과 같은 경우에 코드를 -O2보다 느리게 만듭니다.gcc -O3형된을 합니다.if()분기가 없는 코드로 변환할 수 있습니다. 매우 예측 가능하여 속도가 느려집니다.

때로는 조건을 예측할 수 없다고 확신할 수 있습니다(예: 정렬 알고리즘 또는 이진 검색).또는 최악의 경우가 1.5배 빠른 경우보다 10배 느리지 않는 것이 더 중요합니다.

---

이 더 .cmovx86 조건부 이동 지침).

x = x>limit ? limit : x;   // likely to compile branchless

if (x>limit) x=limit;      // less likely to compile branchless, but still can

번째 첫번방항다씁음니다에상은법째에 씁니다.x는 방 법 않 동 안 지 되 정 수 이 안 동 ▁while 는 않 ▁doesn ▁the t ▁modify '두 ▁second 지x이 일부 대신 브런치를 내보내는 경향이 있는 이유인 것 같습니다.cmov를해위를 .if판본이는 다음과 같은 경우에도 적용됩니다.x 자치 단체입니다.int레지스터에 이미 존재하는 변수이므로 "쓰기"에는 메모리에 저장할 필요가 없으며 레지스터의 값만 변경됩니다.

컴파일러들은 여전히 그들이 원하는 것은 무엇이든 할 수 있지만, 저는 이 관용구의 차이가 차이를 만들 수 있다는 것을 발견했습니다.테스트하는 내용에 따라 컴파일러 마스크와 AND를 지원하는 것이 일반적인 오래된 작업을 수행하는 것보다 더 나을 수 있습니다. 저는 컴파일러가 단일 명령어로 마스크를 생성하는 데 필요한 작업을 수행할 수 있다는 것을 알고 있었기 때문입니다.

TODO: http://gcc.godbolt.org/ 의 예

언급URL : https://stackoverflow.com/questions/32581644/branch-aware-programming