123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377 |
- //////////////////////////////////////////////////////////////////////////////
- //
- // (C) Copyright Ion Gaztanaga 2015-2016.
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- //
- // See http://www.boost.org/libs/move for documentation.
- //
- //////////////////////////////////////////////////////////////////////////////
- #include <cstdlib> //std::srand
- #include <algorithm> //std::stable_sort, std::make|sort_heap, std::random_shuffle
- #include <cstdio> //std::printf
- #include <iostream> //std::cout
- #include <boost/container/vector.hpp> //boost::container::vector
- #include <boost/config.hpp>
- #include <boost/move/unique_ptr.hpp>
- #include <boost/timer/timer.hpp>
- using boost::timer::cpu_timer;
- using boost::timer::cpu_times;
- using boost::timer::nanosecond_type;
- #include "order_type.hpp"
- #include "random_shuffle.hpp"
- //#define BOOST_MOVE_ADAPTIVE_SORT_STATS
- //#define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
- void print_stats(const char *str, boost::ulong_long_type element_count)
- {
- std::printf("%sCmp:%7.03f Cpy:%8.03f\n", str, double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
- }
- #include <boost/move/algo/adaptive_sort.hpp>
- #include <boost/move/algo/detail/merge_sort.hpp>
- #include <boost/move/algo/detail/pdqsort.hpp>
- #include <boost/move/algo/detail/heap_sort.hpp>
- #include <boost/move/core.hpp>
- template<class T>
- void generate_elements(boost::container::vector<T> &elements, std::size_t L, std::size_t NK)
- {
- elements.resize(L);
- boost::movelib::unique_ptr<std::size_t[]> key_reps(new std::size_t[NK ? NK : L]);
- std::srand(0);
- for (std::size_t i = 0; i < (NK ? NK : L); ++i) {
- key_reps[i] = 0;
- }
- for (std::size_t i = 0; i < L; ++i) {
- std::size_t key = NK ? (i % NK) : i;
- elements[i].key = key;
- }
- ::random_shuffle(elements.data(), elements.data() + L);
- ::random_shuffle(elements.data(), elements.data() + L);
- for (std::size_t i = 0; i < L; ++i) {
- elements[i].val = key_reps[elements[i].key]++;
- }
- }
- template<class T, class Compare>
- void adaptive_sort_buffered(T *elements, std::size_t element_count, Compare comp, std::size_t BufLen)
- {
- boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*BufLen]);
- boost::movelib::adaptive_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()), BufLen);
- }
- template<class T, class Compare>
- void std_like_adaptive_stable_sort_buffered(T *elements, std::size_t element_count, Compare comp, std::size_t BufLen)
- {
- boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*BufLen]);
- boost::movelib::stable_sort_adaptive_ONlogN2(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()), BufLen);
- }
- template<class T, class Compare>
- void merge_sort_buffered(T *elements, std::size_t element_count, Compare comp)
- {
- boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*((element_count+1)/2)]);
- boost::movelib::merge_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()));
- }
- enum AlgoType
- {
- MergeSort,
- StableSort,
- PdQsort,
- StdSort,
- AdaptiveSort,
- SqrtHAdaptiveSort,
- SqrtAdaptiveSort,
- Sqrt2AdaptiveSort,
- QuartAdaptiveSort,
- InplaceStableSort,
- StdSqrtHAdpSort,
- StdSqrtAdpSort,
- StdSqrt2AdpSort,
- StdQuartAdpSort,
- SlowStableSort,
- HeapSort,
- MaxSort
- };
- const char *AlgoNames [] = { "MergeSort "
- , "StableSort "
- , "PdQsort "
- , "StdSort "
- , "AdaptSort "
- , "SqrtHAdaptSort "
- , "SqrtAdaptSort "
- , "Sqrt2AdaptSort "
- , "QuartAdaptSort "
- , "InplStableSort "
- , "StdSqrtHAdpSort"
- , "StdSqrtAdpSort "
- , "StdSqrt2AdpSort"
- , "StdQuartAdpSort"
- , "SlowSort "
- , "HeapSort "
- };
- BOOST_STATIC_ASSERT((sizeof(AlgoNames)/sizeof(*AlgoNames)) == MaxSort);
- template<class T>
- bool measure_algo(T *elements, std::size_t element_count, std::size_t alg, nanosecond_type &prev_clock)
- {
- std::printf("%s ", AlgoNames[alg]);
- order_perf_type::num_compare=0;
- order_perf_type::num_copy=0;
- order_perf_type::num_elements = element_count;
- cpu_timer timer;
- timer.resume();
- switch(alg)
- {
- case MergeSort:
- merge_sort_buffered(elements, element_count, order_type_less());
- break;
- case StableSort:
- std::stable_sort(elements,elements+element_count,order_type_less());
- break;
- case PdQsort:
- boost::movelib::pdqsort(elements,elements+element_count,order_type_less());
- break;
- case StdSort:
- std::sort(elements,elements+element_count,order_type_less());
- break;
- case AdaptiveSort:
- boost::movelib::adaptive_sort(elements, elements+element_count, order_type_less());
- break;
- case SqrtHAdaptiveSort:
- adaptive_sort_buffered( elements, element_count, order_type_less()
- , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
- break;
- case SqrtAdaptiveSort:
- adaptive_sort_buffered( elements, element_count, order_type_less()
- , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
- break;
- case Sqrt2AdaptiveSort:
- adaptive_sort_buffered( elements, element_count, order_type_less()
- , 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
- break;
- case QuartAdaptiveSort:
- adaptive_sort_buffered( elements, element_count, order_type_less()
- , (element_count-1)/4+1);
- break;
- case InplaceStableSort:
- boost::movelib::inplace_stable_sort(elements, elements+element_count, order_type_less());
- break;
- case StdSqrtHAdpSort:
- std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
- , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
- break;
- case StdSqrtAdpSort:
- std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
- , boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
- break;
- case StdSqrt2AdpSort:
- std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
- , 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
- break;
- case StdQuartAdpSort:
- std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
- , (element_count-1)/4+1);
- break;
- case SlowStableSort:
- boost::movelib::detail_adaptive::slow_stable_sort(elements, elements+element_count, order_type_less());
- break;
- case HeapSort:
- boost::movelib::heap_sort(elements, elements+element_count, order_type_less());
- boost::movelib::heap_sort((order_move_type*)0, (order_move_type*)0, order_type_less());
- break;
- }
- timer.stop();
- if(order_perf_type::num_elements == element_count){
- std::printf(" Tmp Ok ");
- } else{
- std::printf(" Tmp KO ");
- }
- nanosecond_type new_clock = timer.elapsed().wall;
- //std::cout << "Cmp:" << order_perf_type::num_compare << " Cpy:" << order_perf_type::num_copy; //for old compilers without ll size argument
- std::printf("Cmp:%7.03f Cpy:%8.03f", double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
- double time = double(new_clock);
- const char *units = "ns";
- if(time >= 1000000000.0){
- time /= 1000000000.0;
- units = " s";
- }
- else if(time >= 1000000.0){
- time /= 1000000.0;
- units = "ms";
- }
- else if(time >= 1000.0){
- time /= 1000.0;
- units = "us";
- }
- std::printf(" %6.02f%s (%6.02f)\n"
- , time
- , units
- , prev_clock ? double(new_clock)/double(prev_clock): 1.0);
- prev_clock = new_clock;
- bool res = is_order_type_ordered(elements, element_count, alg != HeapSort && alg != PdQsort && alg != StdSort);
- return res;
- }
- template<class T>
- bool measure_all(std::size_t L, std::size_t NK)
- {
- boost::container::vector<T> original_elements, elements;
- generate_elements(original_elements, L, NK);
- std::printf("\n - - N: %u, NK: %u - -\n", (unsigned)L, (unsigned)NK);
- nanosecond_type prev_clock = 0;
- nanosecond_type back_clock;
- bool res = true;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,MergeSort, prev_clock);
- back_clock = prev_clock;
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,StableSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,PdQsort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,StdSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,HeapSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,QuartAdaptiveSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L, StdQuartAdpSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,Sqrt2AdaptiveSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L, StdSqrt2AdpSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,SqrtAdaptiveSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L, StdSqrtAdpSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,SqrtHAdaptiveSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L, StdSqrtHAdpSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,AdaptiveSort, prev_clock);
- //
- prev_clock = back_clock;
- elements = original_elements;
- res = res && measure_algo(elements.data(), L,InplaceStableSort, prev_clock);
- //
- //prev_clock = back_clock;
- //elements = original_elements;
- //res = res && measure_algo(elements.data(), L,SlowStableSort, prev_clock);
- //
- if(!res)
- throw int(0);
- return res;
- }
- //Undef it to run the long test
- #define BENCH_SORT_SHORT
- #define BENCH_SORT_UNIQUE_VALUES
- int main()
- {
- #ifndef BENCH_SORT_UNIQUE_VALUES
- measure_all<order_perf_type>(101,1);
- measure_all<order_perf_type>(101,7);
- measure_all<order_perf_type>(101,31);
- #endif
- measure_all<order_perf_type>(101,0);
- //
- #ifndef BENCH_SORT_UNIQUE_VALUES
- measure_all<order_perf_type>(1101,1);
- measure_all<order_perf_type>(1001,7);
- measure_all<order_perf_type>(1001,31);
- measure_all<order_perf_type>(1001,127);
- measure_all<order_perf_type>(1001,511);
- #endif
- measure_all<order_perf_type>(1001,0);
- //
- #ifndef BENCH_SORT_UNIQUE_VALUES
- measure_all<order_perf_type>(10001,65);
- measure_all<order_perf_type>(10001,255);
- measure_all<order_perf_type>(10001,1023);
- measure_all<order_perf_type>(10001,4095);
- #endif
- measure_all<order_perf_type>(10001,0);
- //
- #ifdef NDEBUG
- #ifndef BENCH_SORT_UNIQUE_VALUES
- measure_all<order_perf_type>(100001,511);
- measure_all<order_perf_type>(100001,2047);
- measure_all<order_perf_type>(100001,8191);
- measure_all<order_perf_type>(100001,32767);
- #endif
- measure_all<order_perf_type>(100001,0);
- //
- #ifndef BENCH_SORT_SHORT
- #ifndef BENCH_SORT_UNIQUE_VALUES
- measure_all<order_perf_type>(1000001, 8192);
- measure_all<order_perf_type>(1000001, 32768);
- measure_all<order_perf_type>(1000001, 131072);
- measure_all<order_perf_type>(1000001, 524288);
- #endif
- measure_all<order_perf_type>(1000001,0);
- #ifndef BENCH_SORT_UNIQUE_VALUES
- measure_all<order_perf_type>(10000001, 65536);
- measure_all<order_perf_type>(10000001, 262144);
- measure_all<order_perf_type>(10000001, 1048576);
- measure_all<order_perf_type>(10000001, 4194304);
- #endif
- measure_all<order_perf_type>(1000001,0);
- #endif //#ifndef BENCH_SORT_SHORT
- #endif //NDEBUG
- //measure_all<order_perf_type>(100000001,0);
- return 0;
- }
|