qsort 대 std :: sort의 성능?

qsort 대 std :: sort의 성능?

---

Scott Meyers에 따르면, 그의 Effective STL 책-항목 46. 그는 인라인 사실 std::sort보다 약 670 % 더 빠르다고 주장했습니다 std::qsort. 나는 나 자신을 테스트했고 qsort가 더 빠르다는 것을 알았습니다 :(! 누구든지이 이상한 행동을 설명하도록 도와 줄 수 있습니까?

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

#include <cstdlib>
#include <ctime>
#include <cstdio>

const size_t LARGE_SIZE = 100000;

struct rnd {
    int operator()() {
        return rand() % LARGE_SIZE;
    }
};

int comp( const void* a, const void* b ) {
    return ( *( int* )a - *( int* )b );
}

int main() {
    int ary[LARGE_SIZE];
    int ary_copy[LARGE_SIZE];
    // generate random data
    std::generate( ary, ary + LARGE_SIZE, rnd() );
    std::copy( ary, ary + LARGE_SIZE, ary_copy );
    // get time
    std::time_t start = std::clock();
    // perform quick sort C using function pointer
    std::qsort( ary, LARGE_SIZE, sizeof( int ), comp );
    std::cout << "C quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
    // get time again
    start = std::clock();
    // perform quick sort C++ using function object
    std::sort( ary_copy, ary_copy + LARGE_SIZE );
    std::cout << "C++ quick-sort time elapsed: " << static_cast<double>( clock() - start ) / CLOCKS_PER_SEC << "\n";
}

이것은 내 결과입니다.

C quick-sort time elapsed: 0.061
C++ quick-sort time elapsed: 0.086
Press any key to continue . . .

최신 정보

효과적인 STL 3rd Edition (2001)
7 장 STL을 사용한 프로그래밍
항목 46 : 알고리즘 매개 변수로 함수 대신 함수 객체를 고려하십시오.

친애하는,

---

std :: clock ()은 실행 가능한 타이밍 시계가 아닙니다. Windows 고성능 타이머와 같은 플랫폼 별 고해상도 타이머를 사용해야합니다. 또한 clock ()을 호출하는 방법은 먼저 텍스트가 시간에 포함 된 콘솔로 출력된다는 것입니다. 이것은 확실히 테스트를 무효화합니다. 또한 모든 최적화를 사용하여 컴파일했는지 확인하십시오.

마지막으로 코드를 복사하여 붙여 넣었고 qsort에 대해 0.016, std :: sort에 대해 0.008을 얻었습니다.

---

아무도 캐시를 언급하지 않는다는 사실에 놀랐습니다.

코드에서 ary 및 * ary_copy * 를 터치하여 시작하여 qsort 시 캐시에 상주합니다 . qsort 동안 * ary_copy *가 제거 될 수 있습니다. std :: sort 시점에 요소는 메모리 또는 더 큰 ( 느린 읽기 ) 캐시 레벨 에서 가져와야 합니다. 이것은 물론 캐시 크기에 따라 다릅니다.

테스트를 반대로 시도하십시오. 즉, std :: sort 를 실행하여 시작하십시오 .

어떤 사람들이 지적했듯이; 어레이를 더 크게 만들면 테스트가 더 공정 해집니다. 그 이유는 대형 어레이가 캐시에 적합하지 않기 때문입니다.

---

최적화가 활성화되지 않은 두 정렬 알고리즘은 비슷한 성능을 가져야합니다. C ++ sort가 눈에 띄게이기는 경향이 있는 이유 qsort는 컴파일러가 비교를 수행하는 데 사용되는 함수에 대한 유형 정보를 가지고 있기 때문에 컴파일러가 수행되는 비교를 인라인 할 수 있기 때문입니다. 최적화가 활성화 된 상태에서 이러한 테스트를 실행 했습니까? 그렇지 않은 경우 전원을 켜고이 테스트를 다시 실행하십시오.

---

qsort가 예상보다 훨씬 더 잘 수행 될 수있는 또 다른 이유는 새로운 컴파일러가 함수 포인터를 통해 인라인하고 최적화 할 수 있기 때문입니다.

C 헤더가 라이브러리 내부에서 구현하는 대신 qsort의 인라인 구현을 정의하고 컴파일러가 간접 함수 인라인을 지원하는 경우 qsort는 std :: sort만큼 빠를 수 있습니다.

---

내 컴퓨터에서 고기를 추가하고 (배열을 천만 개의 요소로 만들고 데이터 섹션으로 이동) 컴파일합니다.

g++ -Wall -O2 -osortspeed sortspeed.cpp

나는 결과로 얻는다

C quick-sort time elapsed: 3.48
C++ quick-sort time elapsed: 1.26

또한 시스템 부하에 따라 가변 속도로 실행되도록 구성 될 수있는 최신 "친환경"CPU에 대해서도주의하십시오. 이런 종류의 행동을 벤치마킹 할 때 당신을 미치게 만들 수 있습니다 (내 컴퓨터에서 두 개의 작은 스크립트를 설정 normal했으며 fast속도 테스트를 할 때 사용할 수 있습니다).

---

정확한 벤치 마크를 작성하는 것은 어렵습니다. 그러니 Nonius 가 우리를 위해 그렇게하도록합시다 ! 하자 검사 qsort, std::sort어떤 인라인으로, 그리고 std::sort백만 무작위 정수의 벡터에 (기본값) 인라인으로.

// sort.cpp
#define NONIUS_RUNNER
#include <nonius.h++>
#include <random>
#include <algorithm>

// qsort
int comp(const void* a, const void* b) {
    const int arg1 = *static_cast<const int*>(a);
    const int arg2 = *static_cast<const int*>(b);

    // we can't simply return a - b, because that might under/overflow
    return (arg1 > arg2) - (arg1 < arg2);
}

// std::sort with no inlining
struct compare_noinline {
    __attribute__((noinline)) bool operator()(const int a, const int b) {
        return a < b;
    }
};

// std::sort with inlining
struct compare {
    // the compiler will automatically inline this
    bool operator()(const int a, const int b) {
        return a < b;
    }
};

std::vector<int> gen_random_vector(const size_t size) {

    std::random_device seed;
    std::default_random_engine engine{seed()};
    std::uniform_int_distribution<int> dist{std::numeric_limits<int>::min(), std::numeric_limits<int>::max()};

    std::vector<int> vec;
    for (size_t i = 0; i < size; i += 1) {
        const int rand_int = dist(engine);
        vec.push_back(rand_int);
    }

    return vec;
}

// generate a vector of a million random integers
constexpr size_t size = 1'000'000;
static const std::vector<int> rand_vec = gen_random_vector(size);

NONIUS_BENCHMARK("qsort", [](nonius::chronometer meter) {

    // Nonius does multiple runs of the benchmark, and each one needs a new
    // copy of the original vector, otherwise we'd just be sorting the same
    // one over and over
    const size_t runs = static_cast<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& current_vec = vectors[run];

        std::qsort(current_vec.data(), current_vec.size(), sizeof(int), comp);

        return current_vec;
    });
});

NONIUS_BENCHMARK("std::sort noinline", [](nonius::chronometer meter) {

    const size_t runs = static_cast<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& current_vec = vectors[run];

        std::sort(current_vec.begin(), current_vec.end(), compare_noinline{});

        return current_vec;

    });
});

NONIUS_BENCHMARK("std::sort inline", [](nonius::chronometer meter) {

    const size_t runs = static_cast<size_t>(meter.runs());
    std::vector<std::vector<int>> vectors{runs};
    std::fill(vectors.begin(), vectors.end(), rand_vec);

    meter.measure([&](const size_t run) {

        std::vector<int>& current_vec = vectors[run];

        std::sort(current_vec.begin(), current_vec.end(), compare{});

        return current_vec;

    });
});

Apple Clang 7.3.0으로 컴파일,

$ clang++ -std=c++14 -stdlib=libc++ -O3 -march=native sort.cpp -o sort
$ ./sort

1.7GHz i5 Macbook Air에서 실행하면

qsort                211 ms +/- 6 ms
std::sort noinline   127 ms +/- 5 ms
std::sort inline      87 ms +/- 4 ms

So std::sort with no inlining is about 1.7x faster than qsort (perhaps due to different sorting algorithms), and inlining bumps that up to about 2.4x faster. Certainly an impressive speedup, but much less than 670%.

---

Don´t know how std::sort was implemented years ago. But std::sort can be much faster, because std::sort is quicksort with a heap sort fallback. Heapsort is a linearhitmic alghoritm, meaning if you have twice the sorting data, the sorting time doubles. Actually it more than doubles because it is not exactly linear, but however, qsort can be quadratic, so needing exponential more time for sorting twice the input.

참고URL : https://stackoverflow.com/questions/4708105/performance-of-qsort-vs-stdsort