이전 포스팅에서의 모든 벤치마크는 동일한 입력에 대한 연산에 대한 것이었다. 즉, 이미 레지스터에 올라가 있는 값을 여러 연산에 동일한 입력으로 사용했다. 그 결과, 연산이 추가되더라도 런타임에서 연산 비용이 크게 증가하지 않는다는 것을 확인했다. 즉, 일단 레지스터에 값이 로드되어 있다면 이러한 값들에 대한 연산을 추가하더라도 프로그램이 하드웨어의 한계치까지 몰아붙이지 않는 이상 성능 저하가 크지 않을 것이다. 하지만, 이러한 연산들에서의 각 루프 반복이 서로 독립적이라면 문제가 되지 않겠지만, 일반적으로 루프의 각 반복은 독립적이지 않은 경우가 많다. 따라서 데이터 종속성(data dependencies)이 문제가 될 수 있는데, 이번 포스팅에서는 이에 대해서 살펴볼 예정이다.
포스팅에서 사용된 모든 코드는 link(02_pipelining.cpp, 03_branch.cpp)에서 확인해볼 수 있다.
아래에서 측정된 벤치마크 성능은 m1 mac (clang 17.0.2)에서 측정된 결과이다. 측정 결과는 컴파일러 및 하드웨어에 따라 다를 수 있다.
Data Dependencies and Pipelining
이전 포스팅에서의 벤치마크 결과를 통해 피연산자가 이미 레지스터에 있다면 프로세서는 여러 작업을 동시에 실행할 수 있는 것으로 확인했다. 하지만 이러한 예제 코드는 이상적인 경우이다. 보다 현실적인 예제 코드를 살펴보자.
for (size_t i = 0; i < N; ++i) {
a1 += (p1[i] + p2[i]) * (p1[i] - p2[i]);
}
이전 코드는
a1 += (p1[i] + p2[i]);
와 같이 간단한 표현식이었다. 이 코드보다 위의 코드가 더 복잡한데, 그 이유는 무엇일까?
이전 포스팅을 통해 프로세서는 한 사이클에 덧셈, 뺄셈, 곱셈 등의 연산을 수행할 수 있다는 것을 살펴봤고 아래 코드 또한,
a1 += (p1[i] + p2[i]) * (p1[i] - p2[i]);
p1[i], p2[i]라는 두 값에만 영향을 받는다. 그러나 이 표현식은 한 사이클로 평가될 수 없다. 이를 명확하게 표현하기 위해 중간 과정을 저장하는 두 임시 변수를 추가하면 처음 코드는 아래와 같이 표현할 수 있다.
for (size_t i = 0; i < N; ++i) {
s[i] = (p1[i] + p2[i]);
d[i] = (p1[i] - p2[i]);
a1 += s[i] * d[i];
}
덧셈과 뺄셈의 결과인 s[i]와 d[i]는 동시에 평가할 수 있다. 하지만, s[i]와 d[i]의 값을 얻을 때까지 마지막 코드는 실행할 수 없다. 즉, CPU가 얼마나 많은 덧셈과 뺄셈을 동시에 할 수 있는 것과는 관계없이 입력을 알 수 없는 연산의 결과는 계산할 수 없다. 따라서, CPU는 마지막 코드에서 곱셈에 대한 입력이 준비될 때까지 기다려야 한다. 위의 각 반복은 덧셈과 뺄셈(동시 실행)과 그 결과를 곱하는 방식으로 두 단계를 통해 실행된다. 두 번째 단계는 첫 번째 단계에서 생성된 값에 따라 달라지므로 각 반복은 이제 한 사이클이 아닌 두 사이클이 걸리게 된다.
CPU가 3가지 연산을 동시에 수행할 수 있는 리소스가 있더라도 연산에 내재된 데이터 종속성 때문에 이를 활용할 수 없으며, 이는 프로세서의 효율적 활용을 크게 제한한다.
데이터 종속성은 프로그램에서 굉장히 일반적이지만 다행히 해결 방법은 존재한다. 위의 그림을 살펴보면 s[i]와 d[i]를 계산하는 동안, 곱셈을 수행하는 하드웨어 장치는 가만히 대기하고 있는다. 입력이 준비될 때까지 곱셈을 계산할 수는 없지만, 이전 반복에서 얻은 s[i-1]과 d[i-1]은 동시에 수행할 수 있다. 즉, 두 반복을 인터리브(interleave)하여 수행하도록 하는 것이다.
이러한 식으로 코드를 변형하는 것을 파이프라이닝(pipelining)이라고 한다. 위의 코드에서 파이프라이닝은 표현식을 두 단계로 나누어서 이전 루프의 표현식의 두 번째 단계가 현재 루프의 첫 번째 단계와 동시에 실행되는 방식으로 실행되도록 한다. 더 복잡한 표현식은 이러한 단계가 더 많아지고 더 깊은 파이프라인이 필요하다. 이것이 정확하다면 CPU는 루프의 반복이 충분히 많은 경우에 단일 곱셈만큼 빠르게 두 단계의 덧셈-뺄셈-곱셈 표현식을 계산할 수 있을 것이다. 다만, 첫 번째 반복과 마지막 반복에서는 2사이클이 소모될 것이지만 이를 해결할 수 있는 방법은 없다. 그러나 그 사이의 모든 반복에서는 세 가지 연산을 동시에 실행한다. 동시에 실행되는 연산 중 곱셈이 현재 루프가 아닌 이전 루프에 속한다는 것은 파이프라인 관점에서 중요하지 않다.
단순히 루프 내에서 한 번의 곱셈을 수행하는 벤치마크와 2단계로 덧셈-뺄셈-곱셈을 수행하는 벤치마크 성능을 비교하면 우리의 예상이 맞다는 것을 확인할 수 있다.
void BM_multiply(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
a1 += p1[i] * p2[i];
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
void BM_add_multiply_dep(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
a1 += (p1[i] + p2[i]) * (p1[i] - p2[i]);
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
예상대로 두 벤치마크는 비슷한 성능을 보여주고 있다. 파이프라인을 통해 데이터 종속성으로 인한 성능 저하를 거의 무효화했다고 결론을 내릴 수 있다. 물론 실제 데이터 종속성을 제거하지는 않는다. 각 루프는 여전히 두 단계로 실행되며, 두 번째 단계는 첫 번째 단계의 결과에 따라 달라진다. 그러나 파이프라인은 여러 단계의 계산을 인터리브함으로써 이러한 종속성으로 인해 발생할 수 있는 비효율성을 제거한다. llvm-mca의 타임라인을 통해 이를 직접적으로 확인할 수 있다.
BM_multiply timelineBM_add_multiply timeline
두 벤치마크의 타임라인을 통해 파이프라이닝의 효과를 직접적으로 확인할 수 있다. 단일 곱셈에서는 10회 반복이 33 사이클이 걸렸고, 2단계 연산의 10회 반복은 39 사이클이 걸린 것을 확인할 수 있다. 2단계 연산의 타임라인을 자세히 살펴보면, 첫 번째 반복에서의 두 번째 연산 실행(e)이 두 번째 반복에서의 첫 번째 연산 실행(e)와 겹쳐있다는 것을 볼 수 있다.
Pipelining and Branches
프로세서는 아래의 같은 방식으로 효율적으로 동작한다는 것을 살펴봤다.
CPU는 동시에 덧셈과 곱셈 같은 여러 연산을 수행할 수 있다.
효율성을 제한하는 요소 중 하나는 연산에 사용되는 입력 데이터를 얼마나 빠르게 생성할 수 있는지 여부이다. 특히 이는 데이터 종속성에 의해 제한되는데, 파이프라인을 통해 데이터 종속성을 으로 인한 비효율성을 제거할 수 있다.
2번에서 설명하는 파이프라인에는 중요한 전제조건이 있다. 코드에서 미리 파이프라인을 계획하려면 루프 내 어떤 코드가 실행되는지 알아야 한다. if문이 존재할 때, 이 조건이 평가될 때까지 어느 분기의 코드가 실행될 지 알 수 없다. 데이터 종속성이 ILP를 제한하는 요소인 것처럼 조건부 실행(conditional execution) 또는 분기(branches)는 파이프라인을 제한하는 요소이다.
파이프라인이 중단되면 프로그램의 효율성이 크게 감소할 것으로 예상할 수 있다. 이러한 성능 저하를 확인하기 위해 아래 코드
a1 += p1[i] + p2[i];
를 아래와 같이 변경해보자.
a1 += (p1[i] > p2[i]) ? p1[i] : p2[i];
이제 데이터 종속성과 유사한 코드 종속성이 발생하고, 이는 아래 그림처럼 표현할 수 있다.
이제 코드는 선형적인 명령어들의 스트림으로 처리할 수 없으며, 조건부 점프도 피할 수 없다. 실제로는 조금 더 복잡한데, 벤치마크해보면 성능이 크게 저하될 수도 있고 그렇지 않을 수도 있다. 그 이유는 많은 프로세서에서는 일종의 conditional move 또는 conditional add 명령어가 존재하기 때문이며, 컴파일러가 이를 사용하도록 코드를 생성할 수 있다. 이를 사용하면 코드는 점프나 분기없이 완전히 순차적으로 파이프라인될 수 있다. 순차적으로 파이프라인이 되면 이제 이 코드는 아래 그림처럼 표현할 수 있다.
x86 CPU에는 cmove라는 conditional move 명령어가 있다. AVX 또는 AVX2 명령어 세트가 있는 프로세서는 강력한 masked addition 및 multiplication 명령어 세트가 있고, 이들은 조건부 코드를 실행하는데 사용될 수 있다. 따라서, 분기가 있는 코드를 벤치마크하고 최적화할 때, 생성된 목적 코드를 조사하고 코드가 실제로 분기를 포함하는지와 이들이 성능에 얼마나 영향을 주는지 확인하는 것이 중요하다.
대부분의 프로그램에서 분기나 조건문을 포함하지만, 벤치마크를 통해 일부 코드만 평가하면 이러한 분기나 조건문이 사라질 수 있다. 이는 컴파일러가 전체 프로그램을 컴파일할 때는 사용하지 않았지만 일부 코드만 컴파일할 때는 앞서 언급한 조건부 명령어 중 하나를 사용하도록 결정할 수도 있기 때문이다. 또 다른 이유는 컴파일러가 컴파일 타임에 해당 조건이 무엇으로 평가되는지 알아낼 수 있기 때문이다. 컴파일 타임에 평가되는 조건문들은 최적화되어 사라지며, 실행되지 않는 코드는 생성된 코드에서 제거된다. 따라서, 분기로 인한 영향을 제대로 관측하려면 컴파일러가 조건을 검사할 때 결과를 예측할 수 없도록 벤치마크를 구성해야 한다. 실제 벤치마크에서는 실제 프로그램에서 추출한 입력 데이터를 사용할 수 있는데, 예제로 사용할 벤치마크에서는 임의의 값으로 입력을 구성하여 사용하도록 한다.
분기없이 곱셈 및 덧셈 연산을 수행하는 벤치마크와 if문이 추가된 벤치마크의 성능을 비교해보자.
void BM_add_multiply(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
a1 += p1[i] * p2[i];
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
void BM_branch_not_predicated(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() >= 0;
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i]) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
분기가 추가된 벤치마크에는 두 개의 입력 벡터 v1, v2와 0과 1 사이의 값 중 하나의 값을 갖는 벡터 c1이 있다. vector<bool>은 바이트 배열이 아닌 압축된 비트 배열이므로 이를 액세스하는 비용이 더 크며, 비트 조작 명령에 대한 성능을 벤치마크하려는 목적이 아니므로 vector<bool>은 사용하지 않는다. 컴파일러는 생성된 난수가 짝수인지 홀수인지 예측할 수 없기 때문에 분기를 최적화할 수 없다. 베이스라인으로 비교하기 위해 매 루프마다 덧셈 및 곱셈을 수행하는 벤치마크와 함께 성능을 측정하면, 아래와 같은 결과를 얻을 수 있다.
결과로부터 알 수 있듯이 분기가 있는 코드는 그렇지 않은 코드보다 약 10배 느리다. 이는 다음에 실행될 명령어가 이전 명령어의 결과에 따라 달라지면 코드를 효과적으로 파이프라인화할 수 없다는 것을 확증한다.
Branch Prediction
사실 앞서 살펴본 파이프라인 그림은 완전하지 않고, 심지어 사실이 아닐 수 있다. 선형 코드로 나타낼 수 있는 아래 코드를 살펴보자.
for (size_t i = 0; i < N; ++i) {
a1 += v1[i] + v2[i]; // s[i] = v1[i] + v2[i] for saving intermediate result
}
이 코드는 프로세서 관점에서 아래와 같이 표현할 수 있다.
위 그림은 3번의 인터리브한 반복을 보여주는데, 실제로는 N의 크기에 따라 더 많을 수 있다. i 번째 반복에서 p1[i] + p2[i]를 계산하는 동시에 v[i+2]의 값에 액세스하는 것이 불가능할 수 있다는 점에 주목해보자. i 번째 반복을 실행할 때 i + 2번째 반복까지 더 실행된다는 보장이 없다. 만약 반복이 더 실행되지 않는다면 v[i+2] 요소는 존재하지 않으며 이를 액세스하는 것은 undefined behavior로 이어진다. 즉, 우리가 봤던 파이프라인에는 숨겨진 조건이 더 있다. 바로 매 반복마다 i가 N보다 작은지 검사하는 것이며, 이를 만족할 때 i 번째 반복을 수행할 수 있다. 따라서, 위의 파이프라인 그림은 사실 거짓이다. 우리는 매 반복이 실행할 수 있는지 체크하지 않았다.
코드에 분기가 있는 경우, 코드를 파이프라이닝하는 방법은 조건부 코드를 순차 코드로 변환하는 것이다. 이러한 변환은 분기가 어떤 경로로 실행되는지 미리 알면 수행될 수 있다. 그러면 간단히 분기를 제거하고 실행할 다음 명령어로 진행하도록 하면 된다. 물론, 조건이 무엇인지 미리 안다면 조건문을 작성할 필요가 없다. 하지만, 루프의 종료 조건(i < N)은 여전히 고려되어야 한다.
프로세서는 branch prediction(분기 예측)이라는 방식을 사용하여 실행될 코드를 가정한다. 코드의 모든 분기를 분석하고 앞으로도 동작이 변경되지 않을 것이라고 가정한다. 루프를 통해 프로세서는 대부분의 경우에서 다음 반복을 진행한다는 사실을 빠르게 학습한다. 그 결과, 다음 반복이 일어날 것이라고 확신하여 다음 반복을 파이프라인한다. 물론, 실제 결과를 메모리에 기록하는 작업은 조건이 실제로 평가되고 해당 반복이 실제로 일어나는지 확인할 때까지 지연해야 한다. 프로세서에는 확인되지 않은 결과를 메모리에 쓰기 전에 보관할 수 있는 버퍼들이 존재한다.
따라서, 바로 위의 루프 코드 예제는 아래 그림의 파이프라인과 정확히 동일하다.
유일한 문제점은 i 번째 반복이 완료되기 전에 i+2 번째 반복을 시작할 때, 프로세서가 조건부 분기가 수행될지 여부에 대한 예측을 기반으로 진행한다는 것이다. i+2 번째 반복 코드가 실제로 존재하는지 확인하기 전에 파이프라인을 통해 미리 실행하는 것을 추측 실행(speculative execution)이라고 한다. 추측이 맞다는 것을 알아낼 때면, 이미 결과를 계산해둔 상태이므로 어떠한 문제도 없다. 하지만, 추측이 잘못되었다면 계산해서는 안되는 것을 수행했고, 잘못된 결과가 발생하는 것을 방지하지 위해 미리 계산해둔 결과를 버려야 한다.
병렬로 실행할 더 많은 명령을 찾기 위해서 프로세서는 루프의 다음 반복에 대한 코드를 현재 반복과 동시에 실행하기 시작한다. 코드에 조건 분기가 포함되어 있어 어떤 명령이 실행될 지 확실히 알 수 없는 경우, 프로세서는 동일한 조건을 확인한 과거 결과를 바탕으로 학습하여 추측하며, 이 추측에 따라 코드를 실행한다. 이 추측이 올바르다고 확인되면 해당 파이프라인은 조건이 없는 코드와 동일한 성능을 보여줄 수 있을 것이다. 하지만 추측이 올바르지 않다고 확인되면, 프로세서는 평가해서는 안되는 모든 명령의 결과를 버리고, 추측을 통해 실행하지 않았던 명령을 평가한다. 이러한 이벤트를 pipeline flush라고 부르며, 이는 비용이 많이 소모되는 이벤트이다.
앞서 살펴본 두 벤치마크에는 모두 루프의 끝을 확인하는 조건이 있다. 프로세서의 추측은 거의 대부분 완벽하게 예측되며, pipeline flush는 끝에서 한 번만 발생한다. 두 번째 벤치마크인 BM_branch_not_predicted에는 무작위 숫자를 기반으로 결정되는 분기인 if (b1[i])도 있다. 이 조건은 무작위이며 약 50%가 true라고 볼 수 있을텐데, 프로세서는 결과를 예측할 수 없고 파이프라인은 절반의 시간 동안 중단될 것이라고 예상할 수 있다.
이를 실험으로 검증하려면, 무작위 조건을 항상 true로 바꾸는 것이다. 유일한 문제는 이를 컴파일러가 알아낼 수 없는 방식으로 바꿔야한다는 것이며, 일반적인 방법으로는 벡터 c1의 초기화를 아래와 같이 변경하는 것이다.
c1[i] = rand() >= 0;
컴파일러는 rand() 함수가 항상 음수가 아닌 임의의 수를 반환한다는 사실을 모르기 때문에 조건문의 결과를 예상할 수 없을 것이다. 따라서, 아래 벤치마크를 통해 CPU의 branch predictor circuit이 빠르게 if (b1[i])의 조건이 항상 true로 평가된다는 사실을 학습하고 해당 코드를 추측하여 실행하는지 확인해볼 수 있다. 즉, 잘 예측된 분기의 성능과 잘 예측되지 못하는 분기의 성능을 벤치마크를 통해 비교해볼 수 있다. 아래 벤치마크를 추가하여 측정한 성능 결과는 다음과 같다.
void BM_branch_predicated(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() >= 0;
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i]) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
실제 벤치마크 결과를 통해 CPU가 학습으로 조건 결과를 잘 예측하면 그렇지 않은 경우보다 훨씬 더 빠르게 실행된다는 것을 확인할 수 있다.
Profiling for Branch Mispredictions
잘못 예측되는 분기가 코드 성능에 얼마나 큰 영향을 미칠 수 있는지 방금 확인했다. 그렇다면 이제 이러한 코드가 어떻게 최적화할 수 있는지 살펴볼텐데, 이러한 코드를 포함하는 함수가 잘못 예측된 분기 때문인지 다른 비효율적인 코드 때문인지 알아낼 필요가 있다.
다행히 대부분의 프로파일러는 실행 시간뿐만 아니라 분기 예측 실패를 포함한 다양한 요소에 대해 프로파일링할 수 있다. 사용할 수 있는 유용한 프로파일러 중 하나가 바로 perf 이다.
BM_branch_not_predicated 벤치마크만 실행하는 프로그램에 대한 perf 결과는 다음과 같다.
전체 분기 중 약 12%가 잘못 예측된 것을 알 수 있다.
반면, BM_branch_predicated 벤치마크에 대한 perf 결과는 다음과 같다.
전체 분기 중 약 0.01% 정도만 잘못 예측되었다는 것을 알 수 있다.
위 결과를 기반으로 프로그램은 하나 이상의 잘못 예측된 분기로 인해 성능 하락이 발생했다고 결론을 내릴 수 있다. 어느 지점에서 분기 예측이 잘못되는지는 아래 커맨드를 통해 라인별 프로파일링 결과로 확인할 수 있다.
$ perf record -e branches,branch-misses ./branch_mbm $ perf report
잘못 예측된 모든 분기 중 99%가 BM_branch_not_predicated에서 발생하다는 것을 확인할 수 있다.
최신 프로세서의 분기 예측은 매우 정교하다. 예를 들어, 함수가 서로 다른 위치에서 호출되고 처음 호출될 때는 대부분 true로 평가되지만 두 번째 호출에서는 동일한 조건이 false로 평가되는 경우, 해당 패턴까지 학습하고 함수 호출 위치를 기반으로 분기를 올바르게 예측한다. 마찬가지로 상당히 복잡한 패턴도 감지할 수 있다. 예를 들어, 아래 벤치마크 코드에서는 첫 번째 조건은 무작위지만 다음 반복에서의 조건은 이전 조건의 반대가 되도록 조건을 초기화한다.
void BM_branch_predict12(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
if (i == 0) c1[i] = rand() >= 0; else c1[i] = !c1[i - 1];
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i]) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
이 코드를 perf로 프로파일링해보면, 아래와 같은 결과를 얻을 수 있다.
분기 예측이 상당히 잘 되었다는 것을 알 수 있다.
Speculative Execution
지금까지 살펴본 내용을 바탕으로 CPU는 조건 분기가 있는 경우, 결과를 예측하여 예상되는 코드를 추측적으로 실행함으로써 실제로 실행되어야 하는지 여부를 확실히 알기 전에 조건부 코드가 파이프라인이 되도록 한다는 것을 이해했다. 즉, 현재 반복 이후에 루프 조건이 다음 반복이 계속될 것이라고 가정함으로써 다음 반복의 명령어를 현재 반복의 명령어와 인터리브되도록 한다.
하지만 대부분의 루프에서는 끝이 존재하므로, 이 예측은 마지막에 틀리게 된다. 이때, 우리가 해야할 것은 애초에 계산되면 안되는 일부 결과를 버리고, 실제로 전혀 계산되지 않은 것처럼 보이도록 만드는 것뿐이다. 이로 인하여 시간이 조금 걸리지만, 분기 예측이 정확할 때 파이프라인의 속도를 향상시켜 이를 보상한다. 하지만 이것이 전부가 아니다.
위 파이프라인을 다시 살펴보자. i 번째 반복이 루프의 마지막이라면 다음 반복은 발생하지 않아야 한다. 물론 a[i+1] 값을 버리고 메모리에 쓰지 않을 수 있다. 하지만 파이프라인을 계속 수행하려면 v1[i+1]의 값을 로드해야 한다. 이 값을 읽었다는 사실은 버릴 수가 없다. 즉, i 번째 반복이 마지막이라는 것을 확인하기 전에 v1[i+1]에 액세스를 했으며, 이 사실을 부인할 수 없다. 하지만 v1[i+1]은 벡터에 할당된 유효한 메모리 영역 외부에 존재한다. 실제로 읽더라도 정의되지 않은 동작이 발생하게 된다는 것이다.
조금 더 일반적인 예제 코드를 살펴보자.
int f(int* p) {
if (p) {
return *p;
}
else {
return 0;
}
}
포인터 p가 NULL이 되는 경우는 거의 없으므로 branch predictor는 if (p) 조건문의 실제 분기가 일반적으로 true라고 학습한다고 가정해보자. 그렇다면 함수가 최종적으로 p == NULL로 호출되면 어떻게 될까 ? 프로세서는 평소와 같이 true로 추측하여 실행될 것이다. 이때, 가장 먼저하는 것은 NULL 포인터를 역참조하는 것이다. 그러면 프로그램은 conflict가 발생하게 될텐데, 이를 어떻게 되돌릴 수 있을까?
우리는 위와 같은 예제 함수가 실제로 상당히 일반적이며 예상치 못한 충돌이 발생하지 않는다는 경험으로부터 speculative execution은 실제로 존재하지 않거나 이러한 충돌을 되돌릴 수 있는 방법이 있다고 결론을 내릴 수 있다. 하지만 예측 실행이 실제로 발생하며, 이는 성능 향상에 상당히 효과적이라는 사실을 확인했다. 그렇다면 NULL 포인터 역참조와 같이 불가능한 연산을 추측하여 실행하는 상황은 어떻게 처리하게 될까?
정답은 이러한 잠재적인 에러에 대한 대응은 보류되어야 하고, 분기 조건이 실제로 평가될 때까지 폐기되거나 실제가 되도록 허용되서는 안되고, 프로세서는 이러한 실행이 실제 실행으로 간주되어야 하는지 여부를 알아야 한다는 것이다. 이와 관련하여 에러 및 유효하지 않은 기타 조건은 일반적으로 memory writes와 다르지 않다. 실행 취소할 수 없는 모든 작업은 해당 작업을 실행하는 명령이 추측으로 남아 있는 한 잠재적인 작업으로 처리된다. CPU는 이러한 이벤트를 임시로 저장하기 위해 버퍼와 같은 특수한 하드웨어 회로가 있다.
Optimization of Complex Conditions
조건문이 많은 프로그램의 경우, 분기 예측의 효율성이 전체 성능을 결정하는 경우가 많으며, 분기를 정확히 예측하면 비용이 거의 들지 않는다.
하드웨어 분기 예측이 프로세서에서 실행되는 조건부 명령을 기반으로 한다는 점을 이해하는 것이 중요하다. 조건에 대해서 우리가 이해하는 것과 프로세서가 이해하는 것이 다를 수 있다. 아래 벤치마크는 이를 이해하는데 큰 도움이 된다.
void BM_false_branch(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N), c2(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
c2[i] = !c1[i];
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
int* b2 = c2.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i] || b2[i]) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
위 코드는 for 루프 내 조건문(b1[i] || b2[i])이 항상 true로 평가되므로 프로세서의 완벽한 예측을 기대할 수 있다. 하지만, 그렇게 간단하지 않다. 우리에게는 논리적으로 단일 조건문처럼 보이지만 CPU에게는 두 개의 별도의 조건문 분기이다. 전체 루프에서 절반은 첫 번째 조건에 의해 true가 되고, 나머지 절반은 두 번째 조건에 의해서 true가 된다. 전체 루프에서 조건은 모두 true이지만, 어느 조건에 의해서 그렇게 되는지는 예측할 수 없다. perf를 통해 위 벤치마크를 프로파일링한 결과는 다음과 같다.
실제로 낮은 분기 예측을 보여준다. 이전에 살펴본 벤치마크와 함께 성능을 비교해도 성능이 좋지 않다는 것을 확인할 수 있다.
이러한 fake branch(실제로는 항상 true)의 성능은 예측하지 못하는 경우의 성능만큼 나쁘다. 실제 프로그램에서 이런 불필요한 조건문을 만나면 안된다. 하지만, 일반적으로 거의 항상 동일한 값으로 평가되지만 각자 다른 이유로 평가되는 조건식이 있다. 예를 들어, 아래 코드에서 false가 거의 발생하지 않는 상황을 가정해보자.
c3가 false라면, c1과 c2는 둘 다 true이다. false가 거의 발생하지 않는 상황이라고 가정했으므로, 우리가 봤을 때 전반적으로 true branch가 선택된다고 예상할 수 있다. 그러나 프로세서 관점에서 보면 이는 단일 조건이 아닌 3가지 별도의 조건부 점프이다. c1이 true라면 c2를 확인해야 하고, c2도 true라면 첫 번째 명령으로 점프하게 된다. c1 또는 c2 중 하나가 false라면 c3를 확인하고, c3가 true라면 true branch로 점프한다. 이러한 평가가 단계별로 특정 순서로 수행되는 이유는 C++ 표준 때문이며, 이는 조건에 side effect가 있을 때 특히 중요하다.
위 코드에서 f2()는 f1()이 false를 반환하는 경우에만 호출된다. 컴파일러는 side effect가 없으며, 표현식을 다 평가해도 관측 가능한 동작이 변경되지 않는다는 것을 감지할 수 있다. 일부 컴파일러는 이러한 최적화를 수행한다. 앞서 살펴본 벤치마크도 이러한 컴파일러로 컴파일되었다면 예측이 잘 되는 브랜치와 같은 성능을 보여줄테지만, 대부분의 컴파일러는 이를 잠재적인 문제로 인식하지 않는다. 따라서, 이는 프로그래머가 수동으로 해야 하는 최적화이다.
프로그래머가 조건문의 두 조건 중 하나가 훨씬 더 자주 사용된다는 것을 알고 있다고 가정해보자. 예를 들어, else 분기는 에러 상황이나 적절하게 처리할 필요가 있는 정상 동작 시에는 발생하지 않는 예외 조건에 해당한다고 할 수 있다. 또한 프로파일러를 통해 복잡한 조건문에서 분기 예측이 잘 되지 않는다고 확인했다고 가정하자. 그렇다면 코드를 어떻게 최적화할 수 있을까?
첫 번째 방법은 이러한 조건의 평가를 조건문 밖으로 옮기는 것이다.
const bool c = (c1 && c2) || c3;
if (c) { ... } else { ... }
하지만, 이는 두 가지 이유로 잘 동작하지 않는다. 첫 번째는 조건 표현식이 여전히 &&과 || 연산을 사용하므로 여러 조건들에 의한 조건부 점프가 있다. 둘째는 컴파일러가 불필요한 임시 변수, 즉, c를 제거하여 이 코드를 최적화할 가능성이 높다.
두 번째 방법은 조건부 변수 배열을 사용하여 사전에 모든 조건식을 평가하여 저장한 뒤, 이를 사용하는 것이다. 대부분의 컴파일러는 이러한 임시 배열을 제거하지 않는다.
for (size_t i = 0; i < N; ++i) {
c[i] = (c1[i] && c2[i]) || c3[i];
}
...
for (size_t i = 0; i < N; ++i) {
if (c[i]) { ... } else { ... }
}
물론, c[i]를 초기화할 때 사용한 표현식에서 branch misprediction으로 인한 문제가 발생하므로, 이 변환은 두 번째 루프의 비중이 첫 번째 루프보다 더 많이 실행되고 비중이 큰 경우에만 유용하다.
일반적으로 효과적인 또 다른 최적화는 && 및 || 연산을 덧셈 및 곱셈 또는 bitwise & 및 | 연산으로 대체하는 것이다. 단, && 및 || 연산에 대한 인수가 무엇인지 확실히 확인하고 변환해야 한다. 예를 들어, 2라는 값이 true로 해석되더라도 2 & 1 표현식의 결과는 bool(2) & bool(1)과 동일하지 않다. 전자는 0으로 평가되는 반면, 후자는 1(true)로 평가된다.
위의 최적화 방법들을 적용한 벤치마크는 다음과 같다.
BM_false_branch_temp : 임시 변수 c 적용
BM_false_branch_vtemp : 사전에 평가되는 임시 벡터 변수 c3 사용
BM_false_branch_sum : 덧셈 조건문 사용
BM_false_branch_bitwise : bitwise | 연산 사용
void BM_false_branch_temp(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N), c2(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
c2[i] = !c1[i];
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
int* b2 = c2.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
const bool c = b1[i] || b2[i];
if (c) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
void BM_false_branch_vtemp(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N), c2(N), c3(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
c2[i] = !c1[i];
c3[i] = c1[i] || c2[i];
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b3 = c3.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
if (b3[i]) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
void BM_false_branch_sum(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N), c2(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
c2[i] = !c1[i];
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
int* b2 = c2.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i] + b2[i]) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
void BM_false_branch_bitwise(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N), c2(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
c2[i] = !c1[i];
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
int* b2 = c2.data();
for (auto _ : state) {
unsigned long a1 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i] | b2[i]) {
a1 += p1[i];
} else {
a1 *= p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
벤치마크 결과는 다음과 같다.
결과를 보다시피 임시 변수를 도입하여 fake branch를 최적화하려는 BM_false_branch_temp는 전혀 효과가 없다는 것을 볼 수 있다. 사전에 평가하여 그 결과를 미리 임시 벡터 변수에 저장하는 벤치마크는 벡터의 모든 요소가 true이므로 분기 예측을 잘한다. 그 결과, 잘 예측된 분기의 벤치마크와 유사한 성능을 보여준다. || 연산자를 덧셈과 bitwise | 연산으로 교체한 벤치마크들 또한 잘 예측된 경우와 유사한 성능을 보여준다.
다만, 이러한 최적화가 프로그램의 정확성에 영향을 미치지 않도록 하는 것은 프로그래머에게 달려있다. 또한, 이러한 최적화로 성능이 항상 향상되는 것은 아니다. 예를 들어, f1()과 f2()를 평가하는데 시간이 많이 걸리는 경우, f1() + f2()로 변경하더라도 각 함수가 수행되는 시간 때문에 성능이 더 떨어질 수도 있다.
false branch에서 분기 예측을 최적화하는 표준 방식이 없기 때문에 컴파일러가 효율적인 최적화를 수행하는 것도 어렵다. 따라서, 특정 조건이 발생할 가능성이 있는 여부와 같은 문제에 대해 지식을 기반으로 프로파일링 결과와 결합하여 최적의 솔루션을 마련해야 한다.
Branchless Computing
지금까지 살펴본 내용을 정리하면 다음과 같다.
프로세서를 효율적으로 사용하려면 많은 명령을 병렬적으로 실행할 수 있어야 한다.
CPU가 계속 연산을 하도록 유지하기에 충분한 명령이 없는 이유 중 하나는 데이터 종속성이다. 이는 파이프라인을 통해 해결할 수 있지만, 어떠한 명령어가 실행될 지 미리 알고 있어야 한다. 어떤 경로로 실행될 지 미리 알 수 없으면 파이프라인이 불가능하다.
CPU는 조건문을 평가하고 이 기록을 바탕으로 다음에 어떤 분기가 선택될 지에 대해 학습하고, 다음 실행을 추론한다. 추론의 신뢰성이 높을수록 성능이 향상된다.
확실하게 추론할 수 없는 환경에서는 성능이 저하되는 경우가 있다.
파이프라인에서 성능이 저하되는 근본적인 원인은 실행될 다음 명령이 런타임에 알려지지 않는 조건부 분기이다. 근본적으로는 분기를 사용하지 않거나 최소한으로 사용하여 코드를 작성하여 해결해야 한다. 이러한 방법을 branchless computing이라고 한다.
Loop Unrolling
분기가 성능에 미치는 영향이 크다. loop unrolling은 분기의 수를 줄이는 방법 중 하나이다.
for (size_t i = 0; i < N; ++i) {
a1 += p1[i] + p2[i];
}
위 코드를 컴파일하면 루프가 완벽히 파이프라이닝되지만, 매 반복이 루프의 끝인지 확인하는 숨겨진 분기가 있다. 이는 매 반복마다 한 번씩 수행된다. 만약 우리가 N이 항상 짝수라는 것을 알고 있다면, 홀수 반복에서는 이를 확인할 필요가 없다. 따라서, 아래 코드처럼 수정할 수 있다.
for (size_t i = 0; i < N; i += 2) {
a1 += p1[i] + p2[i] + p1[i+1] + p2[i+1];
}
처음 코드에서 두 번의 반복을 하나의 더 큰 반복으로 변환했다. 하지만, 이러한 manual unrolling은 여러 가지 이유로 성능이 향상되지 않을 가능성이 높다. 먼저, N이 크다면 루프 분기의 끝은 거의 완벽하게 예측된다. 둘째, 컴파일러가 이미 unrolling 최적화를 적용할 수 있다. SSE 또는 AVX 명령어를 사용하는 컴파일러의 경우에는 여러 배열 요소를 한 번에 처리하도록 명령어를 사용하므로 사실상 loop unrolling을 적용하는 것과 동일하다.
Branchless Selection
Loop unrolling을 일반화하면 상당한 성능 향상을 얻을 수 있다. 간단한 예시를 통해 살펴보자.
unsigned long* p1 = ...; // data
bool* b1 = ...; // unpredictable condition
unsigned long a1 = 0, a2 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i]) {
a1 += p1[i];
} else {
a2 += p1[i];
}
}
조건문에 사용되는 변수 b[i]가 프로세서에 의해서 예측될 수 없다고 가정해보자. 이 코드는 예측이 잘 되는 분기가 있는 루프보다 몇 배 더 느리게 실행될 것이다. 하지만 분기를 완전히 제거하고 두 개의 destination 변수에 대한 포인터 배열을 인덱싱하여 더 나은 결과를 얻을 수 있다.
unsigned long* p1 = ...; // data
bool* b1 = ...; // unpredictable condition
unsigned long a1 = 0, a2 = 0;
unsigned long* a[2] = { &a2, &a1 };
for (size_t i = 0; i < N; ++i) {
a[b1[i]] += p1[i];
}
이 변환은 bool 변수가 0(false) 또는 1(true)의 두 값만 가질 수 있으며, 암시적으로 정수로 변환할 수 있다는 사실을 활용한다. 이렇게 코드를 바꾸면, 조건부 점프가 두 개의 가능한 메모리 위치 중 하나에 대해 조건부로 액세스하는 명령어로 대체된다. 이러한 조건부 메모리 액세스는 파이프라인화될 수 있으므로 상당한 성능 향상을 이끌어낸다.
두 벤치마크를 통해 성능을 비교해보자.
void BM_branched(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
}
unsigned long* p1 = v1.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0, a2 = 0;
for (size_t i = 0; i < N; ++i) {
#if 0
(b1[i] ? a1 : a2) += p1[i];
#else
if (b1[i]) {
a1 += p1[i];
} else {
a2 += p1[i];
}
#endif
}
benchmark::DoNotOptimize(a1);
benchmark::DoNotOptimize(a2);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
void BM_branchless(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
}
unsigned long* p1 = v1.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0, a2 = 0;
unsigned long* a[2] = { &a2, &a1 };
for (size_t i = 0; i < N; ++i) {
a[b1[i]] += p1[i];
}
benchmark::DoNotOptimize(a1);
benchmark::DoNotOptimize(a2);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
//state.SetBytesProcessed(N*sizeof(unsigned long)*state.iterations());
}
결과는 다음과 같다.
분기가 없는 버전이 약 1.5배 빠르다는 것을 확인할 수 있다. 일부 컴파일러는 가능할 때 조건부 분기 대신 lookup array를 사용하여 ?: 연산자를 구현하는데, 이러한 컴파일러에서는 아래와 같이 코드를 작성하여 동일한 성능 향상을 얻을 수 있다.
for (size_t i = 0; i < N; ++i) {
(b1[i] ? a1 : a2) += p1[i];
}
이 코드를 BM_branched에 적용하고 측정한 결과는 다음과 같다.
Branchless Computing Examples
대부분의 경우는 위에서 본 코드보다 훨씬 더 복잡하다. 예를 들어, 일부 중간 값에 따라 계산을 다르게 수행하는 경우가 있다.
void BM_branched2(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0, a2 = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i]) {
a1 += p1[i] - p2[i];
} else {
a2 += p1[i] * p2[i];
}
}
benchmark::DoNotOptimize(a1);
benchmark::DoNotOptimize(a2);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
}
위 코드에서 조건문 if (b1[i])는 계산하는 표현식과 결과가 저장되는 위치에 영향을 미친다. 동일한 것은 연산에 사용되는 입력뿐이다.
위 벤치마크 코드를 분기없이 동일한 결과를 얻도록 바꾸려면, 조건 변수에 의해 인덱싱된 메모리 위치에서 올바른 표현식의 결과를 가져와야 한다. 조건에 따라 실행하는 코드를 변경하지 않아야 하므로 두 표현식이 모두 평가되는 방식을 사용하여 분기가 없는 형태로 변경하면 다음과 같다.
void BM_branchless2(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0, a2 = 0;
unsigned long* a[2] = { &a2, &a1 };
for (size_t i = 0; i < N; ++i) {
unsigned long s[2] = { p1[i] * p2[i], p1[i] - p2[i] };
a[b1[i]] += s[b1[i]];
}
benchmark::DoNotOptimize(a1);
benchmark::DoNotOptimize(a2);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
}
위 벤치마크의 결과는 다음과 같다. 분기가 모두 잘 예측되었을 때의 결과를 비교하기 위해 BM_branched2_predicated 벤치마크를 추가했다.
추가할 수 있는 연산의 수에는 제한이 있겠지만, 조건부 코드보다 분기가 없는 버전이 성능이 더 좋다. 하지만, 예측을 매우 효과적으로 잘한다면, 조건부 코드가 있더라도 성능이 훨씬 더 좋다.
위의 결과로부터 주목할만한 점은 pipeline flush가 얼마나 비용이 크고, CPU가 ILP를 통해 한 번에 얼마나 연산을 수행할 수 있는지에 대한 것이다. 후자의 경우는 BM_branched2_predicated와 BM_branchless2 벤치마크의 상대적인 성능 차이로부터 추론할 수 있다.
다른 버전의 분기가 없는 코드로 변환도 가능하다.
void BM_branchless1(benchmark::State& state) {
srand(1);
const unsigned int N = state.range(0);
std::vector<unsigned long> v1(N), v2(N);
std::vector<int> c1(N);
for (size_t i = 0; i < N; ++i) {
v1[i] = rand();
v2[i] = rand();
c1[i] = rand() & 0x1;
}
unsigned long* p1 = v1.data();
unsigned long* p2 = v2.data();
int* b1 = c1.data();
for (auto _ : state) {
unsigned long a1 = 0, a2 = 0;
for (size_t i = 0; i < N; ++i) {
unsigned long s1[2] = { 0, p1[i] };
unsigned long s2[2] = { p2[i], 0 };
a1 += s1[b1[i]];
a2 += s2[b1[i]];
}
benchmark::DoNotOptimize(a1);
benchmark::DoNotOptimize(a2);
benchmark::ClobberMemory();
}
state.SetItemsProcessed(N*state.iterations());
}
위 벤치마크를 이전의 BM_branched와 BM_branchless 벤치마크와 함께 성능을 측정한 결과는 다음과 같다.
사용 중인 m1 mac에서는 마지막 버전의 분기 없는 코드가 압도적으로 성능이 좋았다.
ubuntu 20.04 (gcc 10)에서는 BM_branchless와 BM_branchless1 벤치마크가 비슷한 성능을 보여준다. 위에서 살펴본 모든 벤치마크를 ubuntu 20.04 (gcc 10) 환경에서 측정한 결과는 다음과 같다.
분기가 없는 코드로 변환했지만 성능이 향상되지 않는 이유는 컴파일러와 관련이 있다. 경우에 따라서 컴파일러는 동등하거나 더 나은 최적화를 수행할 수 있다. 예를 들어, clamp loop 코드를 고려해보자.
unsigned char* c = ...; // random values from 0 to 255
for (size_t i = 0; i < N; ++i) {
c[i] = (c[i] < 128) ? c[i] : 128;
}
위 코드는 unsigned char 배열 c의 값을 최대 128로 제한한다. 초기값이 무작위라고 가정한다면, 루프 본문의 조건은 확실하게 예측할 수 없고 매우 높은 branch mispredication이 발생할 것으로 기대한다. 이 코드의 대안으로 가능한 값을 보관하고 있는 256개의 요소의 LUT를 사용하여 분기가 없도록 구현할 수 있다. 0부터 127까지 인덱스 i에 대한 테이블 값은 인덱스 값과 동일하도록 하고, 나머지는 모두 128이 되도록 테이블 값을 설정한다.
unsigned char* c = ...; // random values from 0 to 255
unsigned char LUT[256] = {0, 1, ..., 127, 128, 128, ..., 128};
for (size_t i = 0; i < N; ++i) {
c[i] = LUT[c[i]];
}
대부분의 최신 컴파일러에서 이는 전혀 최적화되지 않는다. 컴파일러는 원본 코드로 더 나은 성능을 발휘할 가능성이 높다. 이는 SSE 또는 AVX와 같은 벡터 명령어를 사용하여 분기없이 한 번에 여러 char 값을 복사하고 clamping할 가능성이 높다.
분기가 없도록 변환하더라도 성능이 향상되지 않는 또 다른 시나리오도 있다. 이 경우는 루프의 본문이 분기보다 훨씬 비용이 큰 경우이다. 이 예시는 함수 호출을 수행하는 루프로 설명할 수 있다.
unsigned long f1(unsigned long x, unsigned long y);
unsigned long f2(unsigned long x, unsigned long y);
unsigned long *p1 = ...;, *p2 = ...; // data
bool* b1 = ...; // unpredicated condition
unsigned long a = 0;
for (size_t i = 0; i < N; ++i) {
if (b1[i]) {
a += f1(p1[i], p2[i]);
}
else {
a += f2(p1[i], p2[i]);
}
}
위 코드는 조건에 따라 f1()과 f2() 중 하나를 호출한다. 이 코드는 아래와 같이 if-else를 제거하고 함수 포인터 배열을 사용하여 분기가 없도록 만들 수 있다.
unsigned long f1(unsigned long x, unsigned long y);
unsigned long f2(unsigned long x, unsigned long y);
decltype(f1)* f[] = { f2, f1 };
unsigned long *p1 = ...;, *p2 = ...; // data
bool* b1 = ...; // unpredicated condition
unsigned long a = 0;
for (size_t i = 0; i < N; ++i) {
a += f[b1[i]](p1[i], p2[i]);
}
위의 변경은 일반적으로 최적은 아니다. 우선 함수 f1()과 f2()가 인라인될 수 있는 경우, 함수 포인터를 사용하면 인라인이 불가능해진다. 인라인은 주된 최적화 중 하나이므로, 브랜치를 제거하기 위해서 인라인을 포기하는 것은 합리적이지 않다. 함수가 인라인되지 않은 경우에는 함수 호출 자체가 파이프라인을 중단시킨다. 이것이 인라인이 효과적인 최적화 중 하나인 이유이다. 함수 호출 비용에 비하면 분기를 잘못 예측하는 비용은 아무것도 아니다.
그럼에도 때때로 이런 변경(함수의 룩업테이블)은 적절한 최적화가 되는데, 단일 조건을 기반으로 수 많은 함수 중에서 하나를 선택하는 경우라면 함수 룩업테이블이 if-else보다 더 효율적일 수 있다. 이는 virtual 함수 호출 구현과 유사한 경우이다.
분기가 없도록 코드를 변환하는 것이 코드 가독성에 미치는 영향도 고려해야 한다. 함수 포인터에 대한 룩업테이블은 읽기 쉽기 않을 수 있고, switch나 if-else보다 디버그하기 어려울 수 있다. 따라서 최종 결과에 기여하는 많은 요소를 고려할 때, 최적화는 벤치마크 및 프로파일링을 통해 측정 및 검증되어야 하고, 시간과 가독성, 복잡성 측면에서 프로그래머에게 부과되는 비용과 비교하여 평가되어야 한다.
댓글