늘 그렇듯이 먼저 문제가 되는 코드 부분을 찾으십시오. 이 작업에는 perf가 훌륭한 도구입니다. perf stat을 사용하여 코드가 실제로 높은 분기 예측 오류율을 겪고 있는지 확인할 수도 있습니다(~10%는 매우 높은 수치입니다).

if 문이 선택하는 분기 자체는 예측할 수 없을지 모르지만, v와 비교되는 가능한 값의 범위에 대해 무언가 눈치채셨습니까? 그곳에 예측 가능한 것이 있습니까?

우리는 주어진 출력을 내야 하는 v의 범위를 알고 있습니다. 이러한 v 값을 기대 출력에 매핑하는 해시 테이블/배열을 사용하십시오. 범위를 벗어난 v 값을 처리하려면 std::min(v, largest - 1)을 사용할 수 있습니다. 올바른 최적화 옵션으로 컴파일하면 컴파일러가 std::min에 대해 분기 없는 코드를 생성한다는 점에 유의하십시오.

배경:

이 코드는 입력값 v를 받아, 이 값을 배열 내 버킷의 인덱스로 변환합니다.

아래 함수는 거의 아주 단순한 해시 함수라고 생각할 수 있습니다.

static std::size_t mapToBucket(std::size_t v) {
                              //   size of a bucket
  if      (v < 13)  return 0; //   13
  else if (v < 29)  return 1; //   16
  else if (v < 41)  return 2; //   12
  else if (v < 53)  return 3; //   12
  else if (v < 71)  return 4; //   18
  else if (v < 83)  return 5; //   12
  else if (v < 100) return 6; //   17
  return DEFAULT_BUCKET;
}

이 코드의 성능은 분기의 예측 불가능한 특성 때문에 저하됩니다. perf로 분석하면(빌드 결과물에 대해 perf stat ./lab을 실행한 후) 다음과 같은 결과가 나오며, 전체 분기의 11.93%가 분기 예측 실패였음을 보여 줍니다:

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
bench1           5475 us         5475 us          123

 Performance counter stats for './lab':

       755,117,145      task-clock                       #    0.998 CPUs utilized             
                 5      context-switches                 #    6.621 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
             2,321      page-faults                      #    3.074 K/sec                     
     3,082,840,080      instructions                     #    1.03  insn per cycle            
     2,984,387,486      cycles                           #    3.952 GHz                       
       804,485,800      branches                         #    1.065 G/sec                     
        95,962,434      branch-misses                    #   11.93% of all branches           

       0.756944478 seconds time elapsed

해결책

이를 해결하는 방법은 v 값을 사용해 룩업 테이블을 직접 인덱싱하여 원하는 결과를 반환하는 룩업 테이블을 사용하는 것입니다.

constexpr int TABLE_SIZE = 101;
uint8_t lookup_table[TABLE_SIZE] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
  DEFAULT_BUCKET
};
static std::size_t mapToBucket(std::size_t v) {
  return lookup_table[std::min(v, TABLE_SIZE - 1)];
}

이제 분기 수를 크게 줄였으므로 코드가 훨씬 빠르게 실행될 것입니다.

std::min은 컴파일러에 의해 분기 없는 코드로 최적화되는 경우가 많습니다(코드를 -O3 최적화로 컴파일한 이 시나리오에서 확인할 수 있습니다).

아래에서 볼 수 있듯이 분기 없는 버전은 더 뛰어난 성능을 달성하며(사이클당 2.67 명령어 대 사이클당 1.03 명령어), 전체 분기 중 예측 실패는 0.01%에 불과합니다(위의 11.93% 대비):

-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
bench1            995 us          995 us          689

 Performance counter stats for './lab':

       821,914,095      task-clock                       #    0.999 CPUs utilized             
                12      context-switches                 #   14.600 /sec                      
                 0      cpu-migrations                   #    0.000 /sec                      
             2,319      page-faults                      #    2.821 K/sec                     
     7,693,561,980      instructions                     #    2.67  insn per cycle            
     2,878,375,328      cycles                           #    3.502 GHz                       
       855,928,464      branches                         #    1.041 G/sec                     
            84,302      branch-misses                    #    0.01% of all branches           

       0.823010242 seconds time elapsed

풀이 링크