특히 일련의 if… else if문이 있고 각 문이 평가 할 상대 확률을 미리 알고 true있다면 확률 순서대로 정렬하는 데 실행 시간의 차이가 얼마나됩니까? 예를 들어, 이것을 선호해야합니까?

if (highly_likely)
  //do something
else if (somewhat_likely)
  //do something
else if (unlikely)
  //do something

이에?:

if (unlikely)
  //do something
else if (somewhat_likely)
  //do something
else if (highly_likely)
  //do something

정렬 된 버전이 더 빠를 것 같지만, 가독성이나 부작용의 존재를 위해 최적화되지 않은 순서로 주문할 수 있습니다. 실제로 코드를 실행할 때까지 CPU가 분기 예측을 얼마나 잘 수행하는지 말하기도 어렵습니다.

따라서 이것을 실험하는 과정에서 특정 사례에 대한 내 자신의 질문에 대답했지만 다른 의견 / 통찰력도 듣고 싶습니다.

중요 :이 질문은 if프로그램 동작에 다른 영향을주지 않으면 서 문을 임의로 재정렬 할 수 있다고 가정합니다 . 내 대답에 따르면, 세 가지 조건부 테스트는 상호 배타적이며 부작용이 없습니다. 분명히, 원하는 행동을 달성하기 위해 진술을 일정한 순서로 평가해야한다면 효율성 문제는 문제가된다.

답변

일반적으로 모든 인텔 CPU가 포워드 브랜치를 처음 볼 때 사용하지 않는 것으로 간주하는 것은 아닙니다. Godbolt의 작업을 참조하십시오 .

그 후, 브랜치는 브랜치 예측 캐시로 들어가고, 과거의 브랜치는 예측을 알리기 위해 사용됩니다.

따라서 긴밀한 루프에서 잘못된 순서의 영향은 상대적으로 작습니다. 브랜치 예측기는 어떤 브랜치 세트가 가장 가능성이 높은지 알게 될 것이며 루프에서 사소한 양의 작업을 수행하면 작은 차이가 크게 증가하지 않습니다.

일반적으로 대부분의 컴파일러는 기본적으로 (다른 이유가 없음) 생성 된 머신 코드를 코드에서 주문한 방식과 거의 동일하게 주문합니다. 따라서 문이 실패 할 때 정방향 분기 인 경우.

따라서 “첫 번째 만남”에서 최상의 분기 예측을 얻을 가능성을 줄이는 순서로 분기를 주문해야합니다.

일련의 조건에 걸쳐 여러 번 단단히 반복되고 사소한 작업을 수행하는 마이크로 벤치 마크는 명령 수 등의 작은 영향으로 인해 상대적 분기 예측 문제에는 거의 영향을 미치지 않습니다. 따라서이 경우 경험 법칙이 신뢰할 수 없으므로를 프로파일 링해야합니다 .

또한 벡터화 및 기타 여러 최적화가 작은 타이트 루프에 적용됩니다.

따라서 일반적인 코드에서 가장 가능성이 높은 코드를 if블록 내에 넣으면 캐시되지 않은 분기 예측 누락이 최소화됩니다. 꽉 조이는 경우 일반 규칙에 따라 시작하십시오. 더 많은 정보가 필요하면 프로파일 링 이외의 선택은 거의 없습니다.

일부 테스트가 다른 테스트보다 훨씬 저렴하면 당연히이 모든 것이 창 밖으로 나옵니다.

답변

나는 두 가지 다른 if… else if블록 의 실행 시간을 정하기 위해 다음 테스트를 구성했습니다. 하나는 확률 순서로 정렬되고 다른 하나는 역순으로 정렬되었습니다.

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    long long sortedTime = 0;
    long long reverseTime = 0;

    for (int n = 0; n != 500; ++n)
    {
        //Generate a vector of 5000 random integers from 1 to 100
        random_device rnd_device;
        mt19937 rnd_engine(rnd_device());
        uniform_int_distribution<int> rnd_dist(1, 100);
        auto gen = std::bind(rnd_dist, rnd_engine);
        vector<int> rand_vec(5000);
        generate(begin(rand_vec), end(rand_vec), gen);

        volatile int nLow, nMid, nHigh;
        chrono::time_point<chrono::high_resolution_clock> start, end;

        //Sort the conditional statements in order of increasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 95) ++nHigh;               //Least likely branch
            else if (i < 20) ++nLow;
            else if (i >= 20 && i < 95) ++nMid; //Most likely branch
        }
        end = chrono::high_resolution_clock::now();
        reverseTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

        //Sort the conditional statements in order of decreasing likelyhood
        nLow = nMid = nHigh = 0;
        start = chrono::high_resolution_clock::now();
        for (int& i : rand_vec) {
            if (i >= 20 && i < 95) ++nMid;  //Most likely branch
            else if (i < 20) ++nLow;
            else if (i >= 95) ++nHigh;      //Least likely branch
        }
        end = chrono::high_resolution_clock::now();
        sortedTime += chrono::duration_cast<chrono::nanoseconds>(end-start).count();

    }

    cout << "Percentage difference: " << 100 * (double(reverseTime) - double(sortedTime)) / double(sortedTime) << endl << endl;
}

/ O2와 함께 MSVC2017을 사용하면 정렬 된 버전이 정렬되지 않은 버전보다 일관되게 약 28 % 빠릅니다. luk32의 의견에 따라, 나는 또한 두 테스트의 순서를 바꾸어 눈에 띄는 차이를 만듭니다 (22 % 대 28 %). 이 코드는 Intel Xeon E5-2697 v2의 Windows 7에서 실행되었습니다. 이것은 물론 문제에 따라 다르며 결정적인 답변으로 해석되어서는 안됩니다.

답변

대상 시스템이 실제로 영향을받는 것이 확실하지 않으면 안됩니다. 기본적으로 가독성이 좋습니다.

나는 당신의 결과를 의심합니다. 예제를 약간 수정 했으므로 실행을 취소하는 것이 더 쉽습니다. 오히려 Ideone 은 역순이 빠르지 만 일관성있게 보여줍니다. 특정 달리기에서도 때때로 뒤집어집니다. 결과가 결정적이지 않다고 말하고 싶습니다. 콜리 루 는 실제 차이도보고하지 않습니다. 나중에 내 odroid xu4에서 Exynos5422 CPU를 확인할 수 있습니다.

현대 CPU에는 분기 예측기가 있습니다. 데이터와 명령어를 모두 프리 페치 (pre-fetch)하기위한 많은 로직이 있으며, 최신 x86 CPU는 다소 똑똑합니다. ARM 또는 GPU와 같은 일부 슬림 아키텍처는이 취약점에 취약 할 수 있습니다. 그러나 실제로 컴파일러와 대상 시스템에 크게 의존합니다.

지점 순서 최적화는 매우 취약하고 임시적이라고 말할 수 있습니다. 정말 미세 조정 단계로만 수행하십시오.

암호:

#include <chrono>
#include <iostream>
#include <random>
#include <algorithm>
#include <iterator>
#include <functional>

using namespace std;

int main()
{
    //Generate a vector of random integers from 1 to 100
    random_device rnd_device;
    mt19937 rnd_engine(rnd_device());
    uniform_int_distribution<int> rnd_dist(1, 100);
    auto gen = std::bind(rnd_dist, rnd_engine);
    vector<int> rand_vec(5000);
    generate(begin(rand_vec), end(rand_vec), gen);
    volatile int nLow, nMid, nHigh;

    //Count the number of values in each of three different ranges
    //Run the test a few times
    for (int n = 0; n != 10; ++n) {

        //Run the test again, but now sort the conditional statements in reverse-order of likelyhood
        {
          nLow = nMid = nHigh = 0;
          auto start = chrono::high_resolution_clock::now();
          for (int& i : rand_vec) {
              if (i >= 95) ++nHigh;               //Least likely branch
              else if (i < 20) ++nLow;
              else if (i >= 20 && i < 95) ++nMid; //Most likely branch
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Reverse-sorted: \t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }

        {
          //Sort the conditional statements in order of likelyhood
          nLow = nMid = nHigh = 0;
          auto start = chrono::high_resolution_clock::now();
          for (int& i : rand_vec) {
              if (i >= 20 && i < 95) ++nMid;  //Most likely branch
              else if (i < 20) ++nLow;
              else if (i >= 95) ++nHigh;      //Least likely branch
          }
          auto end = chrono::high_resolution_clock::now();
          cout << "Sorted:\t\t\t" << chrono::duration_cast<chrono::nanoseconds>(end-start).count() << "ns" << endl;
        }
        cout << endl;
    }
}

답변

그냥 내 5 센트. 진술이 다음에 의존해야하는 경우 주문의 효과가있는 것 같습니다.

각 if 문의 가능성
분기 예측자가 시작할 수있는 반복 횟수입니다.
코드 힌트와 같은 컴파일러 힌트

이러한 요소를 탐색하기 위해 다음 기능을 벤치마킹했습니다.

ordered_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] < check_point) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] == check_point) // very unlikely
        s += 1;
}

reversed_ifs ()

for (i = 0; i < data_sz * 1024; i++) {
    if (data[i] == check_point) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (data[i] < check_point) // highly likely
        s += 3;
}

ordered_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (likely(data[i] < check_point)) // highly likely
        s += 3;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
}

reversed_ifs_with_hints ()

for (i = 0; i < data_sz * 1024; i++) {
    if (unlikely(data[i] == check_point)) // very unlikely
        s += 1;
    else if (data[i] > check_point) // samewhat likely
        s += 2;
    else if (likely(data[i] < check_point)) // highly likely
        s += 3;
}

데이터

데이터 배열은 0에서 100 사이의 난수를 포함합니다.

const int RANGE_MAX = 100;
uint8_t data[DATA_MAX * 1024];

static void data_init(int data_sz)
{
    int i;
        srand(0);
    for (i = 0; i < data_sz * 1024; i++)
        data[i] = rand() % RANGE_MAX;
}

결과

다음 결과는 Intel i5 @ 3,2 GHz 및 G ++ 6.3.0에 대한 것입니다. 첫 번째 인수는 check_point (즉, 가능성이 높은 if 문의 경우 %% 확률)이고 두 번째 인수는 data_sz (예 : 반복 횟수)입니다.

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/75/4                    4326 ns       4325 ns     162613
ordered_ifs/75/8                   18242 ns      18242 ns      37931
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612
reversed_ifs/50/4                   5342 ns       5341 ns     126800
reversed_ifs/50/8                  26050 ns      26050 ns      26894
reversed_ifs/75/4                   3616 ns       3616 ns     193130
reversed_ifs/75/8                  15697 ns      15696 ns      44618
reversed_ifs/100/4                  3738 ns       3738 ns     188087
reversed_ifs/100/8                  7476 ns       7476 ns      93752
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/75/4         3165 ns       3165 ns     218492
ordered_ifs_with_hints/75/8        13785 ns      13785 ns      50574
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205
reversed_ifs_with_hints/50/4        6573 ns       6572 ns     105629
reversed_ifs_with_hints/50/8       27351 ns      27351 ns      25568
reversed_ifs_with_hints/75/4        3537 ns       3537 ns     197470
reversed_ifs_with_hints/75/8       16130 ns      16130 ns      43279
reversed_ifs_with_hints/100/4       3737 ns       3737 ns     187583
reversed_ifs_with_hints/100/8       7446 ns       7446 ns      93782

분석

1. 주문이 중요하다

4K 반복과 (거의) 100 % 확률로 선호도가 높은 진술의 경우 그 차이는 223 %에 달합니다.

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
reversed_ifs/100/4                  3738 ns       3738 ns     188087

4K 반복 및 선호도가 높은 50 % 확률의 경우 차이는 약 14 %입니다.

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
reversed_ifs/50/4                   5342 ns       5341 ns     126800

2. 반복 횟수가 중요

매우 좋아하는 진술의 (거의) 100 % 확률에 대한 4K와 8K 반복의 차이는 (예상대로) 약 2 배입니다.

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs/100/8                   3381 ns       3381 ns     207612

그러나 선호도가 높은 문장의 50 % 확률에 대한 4K와 8K 반복의 차이는 5,5 배입니다.

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/50/8                   25636 ns      25635 ns      27852

왜 그렇습니까? 분기 예측 변수가 누락되었습니다. 위에서 언급 한 각 사례에 대한 분기 누락이 있습니다.

ordered_ifs/100/4    0.01% of branch-misses
ordered_ifs/100/8    0.01% of branch-misses
ordered_ifs/50/4     3.18% of branch-misses
ordered_ifs/50/8     15.22% of branch-misses

따라서 i5에서 브랜치 예측기는 그렇게 크지 않은 브랜치 및 대규모 데이터 세트에 대해 놀랍도록 실패합니다.

힌트 힌트

4K 반복의 경우 결과는 50 % 확률에서는 다소 나쁘고 100 % 확률에 대해서는 다소 나아집니다.

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/4                    4660 ns       4658 ns     150948
ordered_ifs/100/4                   1673 ns       1673 ns     417073
ordered_ifs_with_hints/50/4         5551 ns       5551 ns     125160
ordered_ifs_with_hints/100/4        1575 ns       1575 ns     437687

그러나 8K 반복의 경우 결과가 항상 조금 더 좋습니다.

---------------------------------------------------------------------
Benchmark                              Time           CPU Iterations
---------------------------------------------------------------------
ordered_ifs/50/8                   25636 ns      25635 ns      27852
ordered_ifs/100/8                   3381 ns       3381 ns     207612
ordered_ifs_with_hints/50/8        23191 ns      23190 ns      30028
ordered_ifs_with_hints/100/8        3130 ns       3130 ns     221205

따라서 힌트도 도움이되지만 조금만 도움이됩니다.

결론은 항상 코드를 벤치마킹한다는 것입니다. 결과는 놀라 울 수 있습니다.

희망이 도움이됩니다.

답변

유일한 진짜 답이 같이 여기에 다른 몇 가지 답변을 바탕으로, 그것은 본다 : 그것은 의존한다 . 그것은 적어도 다음에 달려 있습니다 (그러나이 순서대로 중요하지는 않지만).

각 지점의 상대 확률. 이것은 원래 질문입니다. 기존의 답변을 바탕으로 확률 순으로 정렬하는 데 도움이되는 몇 가지 조건이있는 것처럼 보이지만 항상 그렇지는 않습니다. 상대 확률이 크게 다르지 않은 경우 순서가 어떤 순서로든 차이가 나지 않을 수 있습니다. 그러나 첫 번째 조건이 99.999 %의 시간에 발생하고 다음 조건이 남은 것의 일부인 경우에는 가장 가능성이 높은 것을 먼저 배치하는 것이 타이밍 측면에서 유리하다고 가정합니다.
각 브랜치에 대한 참 / 거짓 조건 계산 비용. 조건을 테스트하는 데 드는 시간 비용이 한 지점에서 다른 지점에 비해 실제로 높은 경우 이는 타이밍과 효율성에 큰 영향을 줄 수 있습니다. 예를 들어, 계산하는 데 1 시간 단위 (예 : 부울 변수의 상태 확인)가 걸리는 조건과 계산하는 데 수십, 수백, 수천 또는 심지어 수백만 시간 단위가 필요한 다른 조건 (예 : 디스크상의 파일 또는 대규모 데이터베이스에 대한 복잡한 SQL 쿼리 수행). 코드가 매번 순서대로 조건을 확인한다고 가정하면 더 빠른 조건이 먼저되어야합니다 (먼저 실패한 다른 조건에 종속되지 않는 한).
컴파일러 / 인터프리터 일부 컴파일러 (또는 인터프리터)에는 성능에 영향을 줄 수있는 다른 종류의 최적화가 포함될 수 있습니다 (일부 옵션은 컴파일 및 / 또는 실행 중에 특정 옵션을 선택한 경우에만 나타남). 따라서 동일한 분기를 정확히 동일한 컴파일러를 사용하여 동일한 시스템에서 두 개의 컴파일 및 달리 동일한 코드의 실행을 벤치마킹하지 않는 한 유일한 차이점은 컴파일러 변형에 대한 약간의 여유를 주어야합니다.
운영 체제 / 하드웨어 luk32 및 Yakk에서 언급했듯이 다양한 CPU에는 운영 체제와 마찬가지로 자체 최적화 기능이 있습니다. 따라서 벤치 마크는 여기서도 변형되기 쉽습니다.
코드 블록 실행 빈도 분기를 포함하는 블록에 거의 액세스하지 않는 경우 (예 : 시작 중 한 번만) 분기를 배치하는 순서는 거의 중요하지 않습니다. 다른 한편으로, 코드의 중요한 부분에서 코드가이 코드 블록을 망치는 경우 벤치 마크에 따라 순서가 중요 할 수 있습니다.

확실하게 알 수있는 유일한 방법은 코드를 최종적으로 실행할 의도 된 시스템과 동일하거나 매우 유사한 시스템에서 특정 사례를 벤치마킹하는 것입니다. 하드웨어, 운영 체제 등이 다른 다양한 시스템에서 실행하려는 경우 여러 변형을 벤치 마크하여 어느 것이 가장 적합한 지 확인하는 것이 좋습니다. 한 유형의 시스템에서는 하나의 순서로, 다른 유형의 시스템에서는 다른 순서로 코드를 컴파일하는 것이 좋습니다.

내 개인적인 경험 규칙 (대부분의 경우 벤치 마크가없는 경우)은 다음을 기준으로 주문해야합니다.

이전 조건의 결과에 의존하는 조건
조건 계산 비용
각 지점의 상대 확률.

답변

필자가 일반적으로 고성능 코드에 대해이 문제를 해결하는 방법은 가장 읽기 쉬운 순서를 유지하지만 컴파일러에 힌트를 제공하는 것입니다. 다음은 Linux 커널의 한 예입니다 .

if (likely(access_ok(VERIFY_READ, from, n))) {
    kasan_check_write(to, n);
    res = raw_copy_from_user(to, from, n);
}
if (unlikely(res))
    memset(to + (n - res), 0, res);

여기서는 액세스 확인이 통과되고에 오류가 반환되지 않는다고 가정 res합니다. 이러한 if 절 중 하나를 재정렬하려고하면 코드가 혼동 될 수 있지만, 매크로 likely()와 unlikely()매크로는 실제로 정상적인 경우와 예외는 무엇인지 지적함으로써 가독성을 향상시킵니다.

이러한 매크로의 Linux 구현은 GCC 특정 기능을 사용 합니다 . clang과 Intel C 컴파일러는 동일한 구문을 지원하는 것으로 보이지만 MSVC에는 그러한 기능이 없습니다 .

답변

또한 컴파일러와 컴파일하는 플랫폼에 따라 다릅니다.

이론적으로 가장 가능성이 높은 조건은 제어 점프를 가능한 한 적게해야합니다.

일반적으로 가장 가능성이 높은 조건은 다음과 같습니다.

if (most_likely) {
     // most likely instructions
} else …

가장 인기있는 asm은 condition이 true 일 때 점프하는 조건부 분기를 기반으로 합니다 . 그 C 코드는 다음과 같은 의사 asm으로 변환 될 것입니다.

jump to ELSE if not(most_likely)
// most likely instructions
jump to end
ELSE:
…

이것은 점프가 CPU가 실행 파이프 라인을 취소하고 프로그램 카운터가 변경 되었기 때문에 중단되기 때문입니다 (실제로는 파이프 라인을 지원하는 아키텍처의 경우). 그런 다음 컴파일러에 관한 것인데, 이는 컨트롤이 덜 점프하도록 통계적으로 가장 가능성이 높은 조건을 갖는 것에 대한 정교한 최적화를 적용하거나 적용하지 않을 수 있습니다.

Exit mobile version

How IT

언제든지 물어보세요.

카테고리 보관물: C++

if… else if 문을 확률 적으로 주문하면 어떤 효과가 있습니까? something else if (somewhat_likely) //do something else

답변

답변

답변

답변