[C++] sort 함수에 함수 객체가 좋을까 함수가 좋을까?

서론 

 Effective STL을 읽는 도중 "함수 객체가 함수 인자로 넘기는데 더 좋다!"라는 이야기가 있었습니다. 이 내용을 요약하면 sort 같은 알고리즘에는 함수 포인터를 넣기보다는 함수 객체를 넣으면 인라인화 되고 빠른데 함수로 정의하는 건 더 느리다라고 하는 이야기입니다.

 

 그런데 이 책이 옛날이어도 워낙 옛날이어야지 bind2nd 같은 이전 함수들이 나오는 책이라서 현재와 비교해야 하는 부분들이 상당히 많은 책입니다. 그래서 이번 항목도 알아보던 중 "정말 이게 빠를까?" 싶어서 한번 비교를 해보고 정리하기로 마음먹었습니다.

 

일단 코드를 보자, 왜 유의미한 차이가 없지?

#include <algorithm>
#include <iostream>
#include <vector>
#include <chrono>

using namespace std;

inline bool DoubleGreater(const double& a, const double& b)
{
	return a > b;
}

int main(){
    const int MAX = 10000001;
    vector<double> v;
    v.reserve(MAX);

    for(int i = 0; i < MAX; i++){
        v[i] = MAX - 1;
    }

    using namespace chrono;

    // 1. sort with object
    auto start = chrono::steady_clock::now();
    sort(v.begin(), v.end(), greater<double>());
    auto end = chrono::steady_clock::now();

    cout << "Sort with object time is " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << '\n';

    for(int i = 0; i < MAX; i++){
        v[i] = MAX - 1;
    }

    // 2. sort with function
    start = chrono::steady_clock::now();
    sort(v.begin(), v.end(), DoubleGreater);
    end = chrono::steady_clock::now();

    cout << "Sort with function time is " << chrono::duration_cast<chrono::nanoseconds>(end - start).count() << '\n';
}

 chrono 헤더를 사용해서 만든 풀 코드입니다. 다른 블로그들은 긁어내는 거 막던데 제껀 안 막혀 있겠죠? 혹시나 막혀있다면 댓글로 알려주심 감사하겠습니다.

 

 근데 일단 이거 결과를 보면 상당히 괴랄하게 등장하게 됩니다.

 가끔은 함수 객체가 더 빠르고 주로 함수로 되어 있는게 빨랐습니다. 책의 내용에서는 전부 함수로 전달할 시 100% 함수 객체보다 느리다고 했는데 이게 어떻게 된 일일까요?

 

 

실험이 잘못된거 아닐까?

일단 위 코드에서는 한 코드에 함수 오브젝트와 함수를 넘기는 거 둘 다 들어가 있었습니다. 그래서 일단 이걸 한번 빼보고 돌려보기로 결심했습니다.

 

1. 함수를 넘겨준 경우

회차	1	2	3	4	5	6	7	8	9	10
시간(ns)	762	717	653	730	847	899	628	542	483	879

2. 함수 객체를 준 경우

회차	1	2	3	4	5	6	7	8	9	10
시간(ns)	563	527	623	468	747	666	476	780	744	744

 

 뭔가 함수 객체가 대체적으로 뛰어난 것 같지만 뭔가 캥깁니다. 확실한 무언가가 없어요. 실험 자체는 뭐 큰 문제는 없었다고 해도 확실하게 알 수 있는 부분이 없습니다.

 

 

목적을 바꿔서 C++ 에서는 인자로 전달된 함수를 인라인화 할 수 있을까?

 

Template functors vs functions

 일단 위 글을 봤을 때 sort 같은 함수에서 함수 포인터보다 펑터가 일반적으로 더 빠르다고 합니다. 여기서 펑터(functor)는 우리가 애타게 찾던 함수 객체의 다른 이름입니다.

Global function is slower than functor or lambda when passed to std::sort

 이곳에서는 제가 본 스콧 마이어스의 Effective STL과 관련한 이야기가 나옵니다. 여기서도 일단 함수 객체가 인라인화 되기 쉽고 더 나은 쪽이라는데 기울어져 있지만 확답을 딱! 주는 느낌은 아닙니다. 여기 토론장에서 qsort가 sort보다 훨씬 느리다 라는 한번 더 확정하게 되었네요.

 

 그러던 중 다른 질문에서 "엄청나게 큰 자료에 해보면 차이가 두드러진다" 라는 글을 본 뒤 이를 직접 해보기로 결심했습니다.

 

확실히 큰 곳에서 정렬은 함수 객체가 더 성능이 좋았다. 아주 조금

const int MAX = 125000000 * 2;
vector<double> v;
v.resize(MAX);

for(int i = 0; i < MAX; i++)
{
    v[i] = MAX - 1;
}

 위 코드에서 double을 250,000,000개, 8바이트가 2억 5천만개이니 2GB라는 큰 데이터가 나오게 됩니다. 이만한 크기의 정렬을 한 10번 정도 반복하면 의미 있는 차이가 계속 보이게 됩니다. 

 + 눈치채셨을 수 있지만 1GB에서는 가끔 함수 포인터가 이기는 경우가 있었습니다.

차이를 확 보기 위해서 마이크로 초 단위로 측정

 처음에는 함수 객체가 3초대가 나오다가 후반에 가면 과부하가 걸렸는지 4초 이상으로 계속 나왔습니다. 일단 여기서 10번 시도를 해본 결과 함수 객체가 함수 포인터보다 .3초 빨리 정렬을 했으며 백분율 차이로 6%라는 좀 의미 있는 결과가 등장했습니다. 이제 확실히 함수 객체가 더 빠르다! 라고 할 수 있을 것 같습니다. 물론 아주 조금.

 

 

 

이쯤 다시 보는 sort 함수

여기서 sort 함수가 어떻게 되어있는지 한번 보겠습니다.

template< class ExecutionPolicy, class RandomIt, class Compare >
void sort( ExecutionPolicy&& policy,
           RandomIt first, RandomIt last, Compare comp );

 이건 cppreference에서 가져온 sort의 원형입니다. comp 부분이 템플릿으로 되어 있어 실제 코드에서 어떻게 인스턴스화 될지 한번 보겠습니다.

sort(v.begin(), v.end(), DoubleGreater);
// comp = bool(*_Pred)(const double &a, const double &b)

sort(v.begin(), v.end(), greater<double>());
// comp = std::greater<double> _Pred

 함수를 넘긴 경우 포인터로 이를 받게 되었고 greater<int>()의 경우 함수 객체로 넘겨지게 되었습니다. 이런 부분에서 확실히 함수 객체는 컴파일 타임에 정확히 객체를 알 수 있어서 인라인 될 가능성이 높다는 걸 추론할 수 있습니다. 반면 함수 포인터의 경우 컴파일 타임에는 이에 대한 시그니처만 알 수 있기에 인라인을 하기 힘들어질 것입니다. 이로 인해서 함수 객체가 속도적 이득을 가져올 수 있는 것이죠.

 

 

결론

함수 객체 전달이 인라인화 될 가능성이 있어 함수 포인터에 비해 성능적 이득이 있습니다.

 

 가 결론이 되겠습니다. 싸잘데기 없는 저의 탐구 과정까지 함께 봐주셔서 감사하고 뭔가 오류가 있거나 틀린 점이 있었다면 항상 말씀해주시면 감사하겠습니다!