이 실습은 정렬 속도를 높이기 위한 함수 인라이닝에 관한 것입니다.

함수 인라이닝은 함수 F에 대한 호출을 해당 호출의 실제 인자로 특수화한 F의 본문으로 대체하는 변환입니다. 인라이닝은 가장 중요한 컴파일러 최적화 중 하나입니다. 함수 호출의 오버헤드(프롤로그와 에필로그)를 제거할 뿐만 아니라 다른 최적화도 가능하게 하기 때문입니다.

성능 프로파일에서 프롤로그와 에필로그가 핫한 함수를 발견할 때마다, 그러한 함수를 인라이닝할 잠재적 후보 중 하나로 고려하십시오. 이 실습 과제에서는 이러한 성능 문제를 해결하는 연습을 합니다.

힌트

힌트 1:

여기서 문제는 qsort 함수입니다. 이 함수의 어떤 점이 컴파일러가 인라인 최적화를 수행하기 어렵게 만드는 것일까요?


힌트 2:

qsort는 컴파일된 C 라이브러리입니다. 컴파일러는 컴파일된 코드의 내부를 볼 수 없으므로 이를 인라이닝할 수 없으며, 따라서 함수 호출이 필요합니다. 더 현대적인 접근 방식이 있습니까?


힌트 3:

qsort 대신 std::sort와 사용자 정의 비교자를 사용하는 것을 고려해 보십시오. 성능 향상이 나타난다면, 어셈블리 출력에서 어떤 변화를 보게 될 것으로 예상합니까?


풀이:

배경:

함수 인라이닝은 성능을 위한 가장 중요한 컴파일러 최적화 중 하나입니다. 일반적인 함수 호출은 호출될 때 약간의 오버헤드를 발생시키며, 특히 프롤로그와 에필로그에서 그렇습니다. 함수 프롤로그는 해당 함수에 필요한 스택과 레지스터를 준비하는 코드이며, 에필로그는 그 반대로 스택과 레지스터를 함수 호출 이전의 상태로 복원합니다.

함수 인라이닝은 이러한 오버헤드를 최소화하는 데 도움이 됩니다. 함수가 인라이닝되면, 원래 함수 호출이 작성되어 있던 자리에 함수의 코드가 직접 들어간다고 생각할 수 있습니다. 함수를 인라이닝할 수 있다면 큰 성능 향상을 관찰하는 경우가 많습니다.

실습의 원래 코드를 살펴보면 다음과 같습니다.

void solution(std::array<S, N> &arr) {
  qsort(arr.data(), arr.size(), sizeof(S), compare);
}

C의 퀵소트 알고리즘인 qsort를 호출하고 있음을 알 수 있습니다. 여기서 문제는 이 함수가 컴파일된 C 라이브러리에 있다는 점이며, 이 때문에 컴파일러가 그 내부를 "들여다보고" 인라이닝에 필요한 최적화를 수행하는 것이 거의 불가능합니다.

해결 방법으로 넘어가기 전에 벤치마크 성능 점수를 기록해 둡시다.

-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
bench1/iterations:5000        760 us          760 us         5000

해결책

이 실습에서는 표준 라이브러리의 std::sort(C++20 이상에서는 std::ranges::sort)를 사용하는 것이 더 나은 방법입니다. 현대 C++ 컴파일러는 표준 라이브러리 코드를 매우 쉽게 인라인화합니다.

표준 라이브러리와 비교 함수용 람다 함수를 사용하여 다시 작성해 봅시다:

void solution(std::array<S, N> &arr) {
  std::sort(arr.begin(), arr.end(), [](const S& a, const S&b) {
    return a.key1 < b.key1 || (a.key1 == b.key1 && a.key2 < b.key2);
  });

  // This version can also be used in C++20 and above:
  // std::ranges::sort(arr.begin(), arr.end(), [](const S& a, const S&b) {
  //   return a.key1 < b.key1 || (a.key1 == b.key1 && a.key2 < b.key2);
  // });
}

이 코드를 실행하면 더 나은 성능 프로파일을 얻을 수 있습니다(518us 대 760us):

-----------------------------------------------------------------
Benchmark                       Time             CPU   Iterations
-----------------------------------------------------------------
bench1/iterations:5000        518 us          518 us         5000

해결책 코드(링크):

해답 링크