TODO: 소개 영상과 요약 영상을 추가합니다.
이 실습 과제는 분기 예측 실패 횟수를 줄여 성능을 개선하는 데 중점을 둡니다. 이 실습에는 키-값 쌍으로 이루어진 큰 컬렉션이 있고, 여기서 유용한 항목만 골라냅니다. 이런 알고리즘은 텍스처 압축 등 실제 애플리케이션에서 널리 쓰입니다. 입력 컬렉션에는 무작위 키 값이 들어 있어서, 현대 CPU가 각 항목을 선택해야 할지 말아야 할지 예측하기 어렵습니다. 여기서 여러분이 할 일은 분기 예측 실패 횟수를 줄이는 것입니다.
힌트
힌트 1:
먼저 루프 안의 코드를 예측하기 어려운 이유부터 파악하십시오. 입력 데이터의 어떤 성질이 그 이유를 설명해 줄 수 있습니까?
힌트 2:
입력이 무작위이므로 하드웨어는 item이
(lower <= item.first) && (item.first <= upper)를
만족할지 예측할 수 없습니다. 이 루프가 if 문에 의존하지
않도록 다시 작성할 방법이 있을까요?
힌트 3:
매 반복을 시작할 때 item이 조건에 맞는다고 가정하고
output[count]에 바로 써 보십시오. 그렇다면 이후 루프
반복에서 output에 들어가야 할 item만 남기려면
count를 어떻게 해야 할까요? count에 대한 이
갱신을 if 문 없이 해낼 수 있을까요?
풀이:
배경:
이 알고리즘의 목표는 input에서 지정된 범위에 속하는
요소를 골라 output에 채우는 것입니다.
원래 루프는 다음과 같습니다.
for (const auto item : input) {
if ((lower <= item.first) && (item.first <= upper)) {
output[count++] = item;
}
}다음은 10000회 반복하도록 설정하고
perf stat ./lab(lab은 빌드된 코드)을 실행해
얻은 출력 예시입니다.
------------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------------
bench1/iterations:10000 286 us 285 us 10000
Performance counter stats for './lab':
2,868,419,549 task-clock # 0.999 CPUs utilized
52 context-switches # 18.128 /sec
1 cpu-migrations # 0.349 /sec
528 page-faults # 184.073 /sec
6,275,596,090 instructions # 0.56 insn per cycle
11,294,443,984 cycles # 3.938 GHz
1,808,386,567 branches # 630.447 M/sec
425,721,046 branch-misses # 23.54% of all branches
2.870168980 seconds time elapsed분기 예측 실패 비율이 심각하게 높습니다. 23.54%는 극도로 높은 수치입니다. 이를 해결하려면 알고리즘을 다시 작성해야 합니다.
루프 안의 조건식을 살펴보면, 전달되는 데이터, 즉
item.first가 어떤 식으로도 정해져 있지 않기 때문에 예측할
수 없다는 것을 알 수 있습니다.
if ((lower <= item.first) && (item.first <= upper)) {
output[count++] = item;
}해야 할 일은 조건식
(lower <= item.first) && (item.first <= upper)의
정수 표현을 바탕으로 count를 증가시키도록 루프를 바꾸는
것입니다.
count += lower <= item.first && item.first <= upper;조건식이 참이면 count 인덱스를 전진시키고, 그다음 출력
배열의 다음 요소를 채울 수 있습니다. count가 증가하지
않았다면 해당 요소는 선택되지 않아야 한다는 뜻이고, 이후 반복에서
덮어써도 안전합니다.
이 알고리즘이 output에 쓴 요소의 총 개수를
K라고 합시다. 루프 전체가 실행되고 나면 출력 배열의
K번째 항목은 유효한 값이거나, 미리 추가되었지만 결국
item.first가 범위에 들지 않아 무시해야 하는 값입니다.
count를 사용하면 이 함수를 호출한 쪽에 출력 배열의
유효한 요소 총 개수를 알려 줄 수 있습니다. 마지막 루프 반복에서
count가 증가하지 않으면 count는
K-1과 같아지며, 이는 K번째 요소가 개수에
포함되지 않는다는 것을 나타냅니다.
최종 루프는 다음과 같아야 합니다:
for (const auto item : input) {
output[count] = item;
count += lower <= item.first && item.first <= upper;
}실습에서 perf stat을 다시 한 번 실행해 보면 알고리즘이
이전보다 4배 이상 빨라졌고(65.6마이크로초 대 286마이크로초), 분기 예측
실패 비율도 0.03%까지 떨어졌습니다. 이는 엄청난
개선입니다.
------------------------------------------------------------------
Benchmark Time CPU Iterations
------------------------------------------------------------------
bench1/iterations:10000 65.6 us 65.6 us 10000
Performance counter stats for './lab':
664,023,567 task-clock # 0.998 CPUs utilized
25 context-switches # 37.649 /sec
1 cpu-migrations # 1.506 /sec
528 page-faults # 795.153 /sec
8,548,524,227 instructions # 3.34 insn per cycle
2,557,919,718 cycles # 3.852 GHz
659,384,254 branches # 993.013 M/sec
167,557 branch-misses # 0.03% of all branches
0.665149897 seconds time elapsed