분기 예측 실패가 많이 일어날 수 있는 코드 부분을 찾았습니까? 무작위 입력에 따라 코드가 어느 쪽으로 흐를지 말하기 어려운 부분이 있습니까?

입력 데이터의 특성상 결과를 쉽게 예측할 수 없는 if나 switch 문을 찾아내는 것부터 시작하는 것이 좋습니다. 이런 곳은 하드웨어 분기 예측기에 문제를 일으킬 가능성이 높습니다. perf record 같은 도구로 프로파일링하고, 분기 예측 실패의 원인으로 강조 표시된 코드를 살펴보면 여러분의 생각을 확인할 수 있습니다.

집중해서 살펴볼 주요 코드 부분은 다음과 같습니다.

// Implementing the Rules of Life:
switch(aliveNeighbours) {
    // 1. Cell is lonely and dies
    case 0:
    case 1:
        future[i][j] = 0;
        break;                   
    // 2. Remains the same
    case 2:
        future[i][j] = current[i][j];
        break;
    // 3. A new cell is born
    case 3:
        future[i][j] = 1;
        break;
    // 4. Cell dies due to over population
    default:
        future[i][j] = 0;
}

aliveNeighbours가 2나 3인 경우를 제외하면 future[i][j]는 항상 0이 된다는 점을 깨달으면 많은 분기를 제거할 수 있다는 것에 주목하십시오. 그런 다음 (x86과 Clang 17 이상을 사용한다면) __builtin_unpredictable()을 사용해 이 분기들이 예측하기 까다롭다는 힌트를 컴파일러에 줄 수 있습니다. 이 내장 함수는 다시 컴파일러가 분기의 영향을 줄이는 더 적절한 어셈블리 코드를 생성하도록, 즉 cmov 명령어를 생성하도록 도울 수 있습니다.

배경:

이 실습의 목표는 예측할 수 없는 분기를 조건부 이동으로 대체하는 것입니다. 조건부 이동 cmov가 분기가 있는 코드보다 항상 빠른 것은 아니지만, 이 경우처럼 분기를 예측할 수 없을 때는 성능 향상을 기대할 수 있으며 실제로도 관찰됩니다.

해결책:

주요 분기 부분은 다음과 같습니다.

// Implementing the Rules of Life:
switch(aliveNeighbours) {
    // 1. Cell is lonely and dies
    case 0:
    case 1:
        future[i][j] = 0;
        break;                   
    // 2. Remains the same
    case 2:
        future[i][j] = current[i][j];
        break;
    // 3. A new cell is born
    case 3:
        future[i][j] = 1;
        break;
    // 4. Cell dies due to over population
    default:
        future[i][j] = 0;
}

위 코드의 어셈블리 코드 출력은 여기에서 볼 수 있습니다.

(참고: 위 코드는 설명을 위해 최적화 없이 컴파일한 코드 조각입니다. future와 current에 테스트 데이터를 제공하지 않았기 때문에, -O3은 aliveNeighbours == 3인 경우가 아니면 future[i][j]의 값이 0으로 유지된다는 것, 즉 변하지 않는다는 것을 알아차리고 어셈블리 명령어 대부분을 최적화로 제거합니다.)

이로부터 future[i][j]의 값에 대해 세 가지 서로 다른 최종 결과가 있음을 알 수 있습니다.

1. future[i][j] = 0 - aliveNeighbours가 2나 3이 아닌 다른 값인 경우입니다.
2. future[i][j] = current[i][j] - aliveNeighbours가 2와 같으면 그대로 유지됩니다.
3. future[i][j] = 1 - aliveNeighbours가 3과 같은 경우입니다.

이를 통해 future[i][j]가 0이 될 것이라고 가정하고 시작하여, aliveNeighbours == 2 또는 aliveNeighbours == 3인 경우에만 결과를 바꾸는 코드를 작성할 수 있음을 알 수 있습니다. 이렇게 하면 분기가 단순해집니다.

// Implementing the Rules of Life:
int cell_value = 0;
if (aliveNeighbours == 2) {
    cell_value = current[i][j];
} else if (aliveNeighbours == 3) {
    cell_value = 1;
}
future[i][j] = cell_value;

개선되기는 했지만, 아직 분기를 완전히 제거하지는 못했습니다.

이를 위해서는 컴파일러 내장 함수의 도움이 필요합니다. aliveNeighbours는 예측할 수 없으므로, 현재 상태의 코드는 성능 면에서 큰 분기 예측 실패 페널티를 겪게 됩니다. x86에서는 Clang(버전 17 이상)의 내장 함수 __builtin_unpredictable()을 사용하여 이 분기를 하드웨어 예측 방식으로 예측할 수 없음을 나타냅니다. 이는 컴파일러가 더 나은 어셈블리 코드를 생성하는 데 도움이 됩니다.

// Implementing the Rules of Life:
int cell_value = 0;
if (__builtin_unpredictable(aliveNeighbours == 2)) {
    cell_value = current[i][j];
} else if (__builtin_unpredictable(aliveNeighbours == 3)) {
    cell_value = 1;
}
future[i][j] = cell_value;

해결 방법 링크