[ceph.git] / ceph / src / boost / libs / move / test / bench_sort.cpp

//////////////////////////////////////////////////////////////////////////////
//
// (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/move/detail/nsec_clock.hpp>
#include <cstdlib>

using boost::move_detail::cpu_timer;
using boost::move_detail::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)
      std::abort();
   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;
}
Commit	Line	Data
7c673cae FG	1	//////////////////////////////////////////////////////////////////////////////
	2	//
	3	// (C) Copyright Ion Gaztanaga 2015-2016.
	4	// Distributed under the Boost Software License, Version 1.0.
	5	// (See accompanying file LICENSE_1_0.txt or copy at
	6	// http://www.boost.org/LICENSE_1_0.txt)
	7	//
	8	// See http://www.boost.org/libs/move for documentation.
	9	//
	10	//////////////////////////////////////////////////////////////////////////////
	11
	12	#include <cstdlib> //std::srand
	13	#include <algorithm> //std::stable_sort, std::make\|sort_heap, std::random_shuffle
	14	#include <cstdio> //std::printf
	15	#include <iostream> //std::cout
92f5a8d4	16	#include <boost/container/vector.hpp> //boost::container::vector
7c673cae FG	17
7c673cae FG	18	#include <boost/config.hpp>
7c673cae	19	#include <boost/move/unique_ptr.hpp>
20effc67 TL	20	#include <boost/move/detail/nsec_clock.hpp>
20effc67 TL	21	#include <cstdlib>
7c673cae	22
20effc67 TL	23	using boost::move_detail::cpu_timer;
20effc67 TL	24	using boost::move_detail::nanosecond_type;
7c673cae FG	25
7c673cae FG	26	#include "order_type.hpp"
b32b8144	27	#include "random_shuffle.hpp"
7c673cae FG	28
7c673cae FG	29	//#define BOOST_MOVE_ADAPTIVE_SORT_STATS
b32b8144	30	//#define BOOST_MOVE_ADAPTIVE_SORT_INVARIANTS
7c673cae FG	31	void print_stats(const char *str, boost::ulong_long_type element_count)
7c673cae FG	32	{
b32b8144	33	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 );
7c673cae FG	34	}
	35
	36
	37	#include <boost/move/algo/adaptive_sort.hpp>
	38	#include <boost/move/algo/detail/merge_sort.hpp>
11fdf7f2 TL	39	#include <boost/move/algo/detail/pdqsort.hpp>
11fdf7f2 TL	40	#include <boost/move/algo/detail/heap_sort.hpp>
7c673cae FG	41	#include <boost/move/core.hpp>
	42
	43	template<class T>
92f5a8d4	44	void generate_elements(boost::container::vector<T> &elements, std::size_t L, std::size_t NK)
7c673cae	45	{
92f5a8d4 TL	46	elements.resize(L);
	47	boost::movelib::unique_ptr<std::size_t[]> key_reps(new std::size_t[NK ? NK : L]);
	48
7c673cae	49	std::srand(0);
92f5a8d4 TL	50	for (std::size_t i = 0; i < (NK ? NK : L); ++i) {
92f5a8d4 TL	51	key_reps[i] = 0;
7c673cae	52	}
92f5a8d4 TL	53	for (std::size_t i = 0; i < L; ++i) {
	54	std::size_t key = NK ? (i % NK) : i;
	55	elements[i].key = key;
7c673cae	56	}
92f5a8d4 TL	57	::random_shuffle(elements.data(), elements.data() + L);
	58	::random_shuffle(elements.data(), elements.data() + L);
	59
	60	for (std::size_t i = 0; i < L; ++i) {
7c673cae FG	61	elements[i].val = key_reps[elements[i].key]++;
	62	}
	63	}
	64
	65	template<class T, class Compare>
	66	void adaptive_sort_buffered(T *elements, std::size_t element_count, Compare comp, std::size_t BufLen)
	67	{
	68	boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*BufLen]);
	69	boost::movelib::adaptive_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()), BufLen);
	70	}
	71
92f5a8d4 TL	72	template<class T, class Compare>
	73	void std_like_adaptive_stable_sort_buffered(T *elements, std::size_t element_count, Compare comp, std::size_t BufLen)
	74	{
	75	boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*BufLen]);
	76	boost::movelib::stable_sort_adaptive_ONlogN2(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()), BufLen);
	77	}
	78
7c673cae FG	79	template<class T, class Compare>
	80	void merge_sort_buffered(T *elements, std::size_t element_count, Compare comp)
	81	{
	82	boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*((element_count+1)/2)]);
	83	boost::movelib::merge_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()));
	84	}
	85
	86	enum AlgoType
	87	{
	88	MergeSort,
	89	StableSort,
11fdf7f2 TL	90	PdQsort,
11fdf7f2 TL	91	StdSort,
7c673cae FG	92	AdaptiveSort,
	93	SqrtHAdaptiveSort,
	94	SqrtAdaptiveSort,
	95	Sqrt2AdaptiveSort,
	96	QuartAdaptiveSort,
7c673cae	97	InplaceStableSort,
92f5a8d4 TL	98	StdSqrtHAdpSort,
	99	StdSqrtAdpSort,
	100	StdSqrt2AdpSort,
	101	StdQuartAdpSort,
7c673cae FG	102	SlowStableSort,
	103	HeapSort,
	104	MaxSort
	105	};
	106
	107	const char *AlgoNames [] = { "MergeSort "
	108	, "StableSort "
11fdf7f2 TL	109	, "PdQsort "
11fdf7f2 TL	110	, "StdSort "
7c673cae FG	111	, "AdaptSort "
	112	, "SqrtHAdaptSort "
	113	, "SqrtAdaptSort "
	114	, "Sqrt2AdaptSort "
	115	, "QuartAdaptSort "
7c673cae	116	, "InplStableSort "
92f5a8d4 TL	117	, "StdSqrtHAdpSort"
	118	, "StdSqrtAdpSort "
	119	, "StdSqrt2AdpSort"
	120	, "StdQuartAdpSort"
7c673cae FG	121	, "SlowSort "
	122	, "HeapSort "
	123	};
	124
	125	BOOST_STATIC_ASSERT((sizeof(AlgoNames)/sizeof(*AlgoNames)) == MaxSort);
	126
	127	template<class T>
92f5a8d4	128	bool measure_algo(T *elements, std::size_t element_count, std::size_t alg, nanosecond_type &prev_clock)
7c673cae	129	{
7c673cae	130	std::printf("%s ", AlgoNames[alg]);
b32b8144 FG	131	order_perf_type::num_compare=0;
	132	order_perf_type::num_copy=0;
	133	order_perf_type::num_elements = element_count;
7c673cae FG	134	cpu_timer timer;
	135	timer.resume();
	136	switch(alg)
	137	{
	138	case MergeSort:
b32b8144	139	merge_sort_buffered(elements, element_count, order_type_less());
7c673cae FG	140	break;
7c673cae FG	141	case StableSort:
b32b8144	142	std::stable_sort(elements,elements+element_count,order_type_less());
7c673cae	143	break;
11fdf7f2 TL	144	case PdQsort:
	145	boost::movelib::pdqsort(elements,elements+element_count,order_type_less());
	146	break;
	147	case StdSort:
	148	std::sort(elements,elements+element_count,order_type_less());
	149	break;
7c673cae	150	case AdaptiveSort:
b32b8144	151	boost::movelib::adaptive_sort(elements, elements+element_count, order_type_less());
7c673cae FG	152	break;
7c673cae FG	153	case SqrtHAdaptiveSort:
b32b8144	154	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	155	, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
	156	break;
	157	case SqrtAdaptiveSort:
b32b8144	158	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	159	, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
	160	break;
	161	case Sqrt2AdaptiveSort:
b32b8144	162	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	163	, 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
	164	break;
	165	case QuartAdaptiveSort:
b32b8144	166	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	167	, (element_count-1)/4+1);
7c673cae FG	168	break;
7c673cae	169	case InplaceStableSort:
b32b8144	170	boost::movelib::inplace_stable_sort(elements, elements+element_count, order_type_less());
7c673cae	171	break;
92f5a8d4 TL	172	case StdSqrtHAdpSort:
	173	std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
	174	, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
	175	break;
	176	case StdSqrtAdpSort:
	177	std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
	178	, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
	179	break;
	180	case StdSqrt2AdpSort:
	181	std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
	182	, 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
	183	break;
	184	case StdQuartAdpSort:
	185	std_like_adaptive_stable_sort_buffered( elements, element_count, order_type_less()
	186	, (element_count-1)/4+1);
	187	break;
7c673cae	188	case SlowStableSort:
b32b8144	189	boost::movelib::detail_adaptive::slow_stable_sort(elements, elements+element_count, order_type_less());
7c673cae FG	190	break;
7c673cae FG	191	case HeapSort:
11fdf7f2 TL	192	boost::movelib::heap_sort(elements, elements+element_count, order_type_less());
	193	boost::movelib::heap_sort((order_move_type)0, (order_move_type)0, order_type_less());
	194
7c673cae FG	195	break;
	196	}
	197	timer.stop();
	198
b32b8144	199	if(order_perf_type::num_elements == element_count){
7c673cae FG	200	std::printf(" Tmp Ok ");
	201	} else{
	202	std::printf(" Tmp KO ");
	203	}
	204	nanosecond_type new_clock = timer.elapsed().wall;
	205
b32b8144 FG	206	//std::cout << "Cmp:" << order_perf_type::num_compare << " Cpy:" << order_perf_type::num_copy; //for old compilers without ll size argument
b32b8144 FG	207	std::printf("Cmp:%7.03f Cpy:%8.03f", double(order_perf_type::num_compare)/element_count, double(order_perf_type::num_copy)/element_count );
7c673cae FG	208
	209	double time = double(new_clock);
	210
	211	const char *units = "ns";
	212	if(time >= 1000000000.0){
	213	time /= 1000000000.0;
	214	units = " s";
	215	}
	216	else if(time >= 1000000.0){
	217	time /= 1000000.0;
	218	units = "ms";
	219	}
	220	else if(time >= 1000.0){
	221	time /= 1000.0;
	222	units = "us";
	223	}
	224
	225	std::printf(" %6.02f%s (%6.02f)\n"
	226	, time
	227	, units
	228	, prev_clock ? double(new_clock)/double(prev_clock): 1.0);
	229	prev_clock = new_clock;
11fdf7f2	230	bool res = is_order_type_ordered(elements, element_count, alg != HeapSort && alg != PdQsort && alg != StdSort);
7c673cae FG	231	return res;
	232	}
	233
	234	template<class T>
	235	bool measure_all(std::size_t L, std::size_t NK)
	236	{
92f5a8d4 TL	237	boost::container::vector<T> original_elements, elements;
92f5a8d4 TL	238	generate_elements(original_elements, L, NK);
7c673cae FG	239	std::printf("\n - - N: %u, NK: %u - -\n", (unsigned)L, (unsigned)NK);
	240
	241	nanosecond_type prev_clock = 0;
	242	nanosecond_type back_clock;
	243	bool res = true;
92f5a8d4 TL	244	elements = original_elements;
92f5a8d4 TL	245	res = res && measure_algo(elements.data(), L,MergeSort, prev_clock);
7c673cae FG	246	back_clock = prev_clock;
	247	//
	248	prev_clock = back_clock;
92f5a8d4 TL	249	elements = original_elements;
	250	res = res && measure_algo(elements.data(), L,StableSort, prev_clock);
	251	//
	252	prev_clock = back_clock;
	253	elements = original_elements;
	254	res = res && measure_algo(elements.data(), L,PdQsort, prev_clock);
7c673cae FG	255	//
7c673cae FG	256	prev_clock = back_clock;
92f5a8d4 TL	257	elements = original_elements;
92f5a8d4 TL	258	res = res && measure_algo(elements.data(), L,StdSort, prev_clock);
11fdf7f2 TL	259	//
11fdf7f2 TL	260	prev_clock = back_clock;
92f5a8d4 TL	261	elements = original_elements;
92f5a8d4 TL	262	res = res && measure_algo(elements.data(), L,HeapSort, prev_clock);
11fdf7f2 TL	263	//
11fdf7f2 TL	264	prev_clock = back_clock;
92f5a8d4 TL	265	elements = original_elements;
92f5a8d4 TL	266	res = res && measure_algo(elements.data(), L,QuartAdaptiveSort, prev_clock);
7c673cae FG	267	//
7c673cae FG	268	prev_clock = back_clock;
92f5a8d4 TL	269	elements = original_elements;
92f5a8d4 TL	270	res = res && measure_algo(elements.data(), L, StdQuartAdpSort, prev_clock);
7c673cae FG	271	//
7c673cae FG	272	prev_clock = back_clock;
92f5a8d4 TL	273	elements = original_elements;
92f5a8d4 TL	274	res = res && measure_algo(elements.data(), L,Sqrt2AdaptiveSort, prev_clock);
7c673cae FG	275	//
7c673cae FG	276	prev_clock = back_clock;
92f5a8d4 TL	277	elements = original_elements;
92f5a8d4 TL	278	res = res && measure_algo(elements.data(), L, StdSqrt2AdpSort, prev_clock);
7c673cae FG	279	//
7c673cae FG	280	prev_clock = back_clock;
92f5a8d4 TL	281	elements = original_elements;
92f5a8d4 TL	282	res = res && measure_algo(elements.data(), L,SqrtAdaptiveSort, prev_clock);
7c673cae FG	283	//
7c673cae FG	284	prev_clock = back_clock;
92f5a8d4 TL	285	elements = original_elements;
92f5a8d4 TL	286	res = res && measure_algo(elements.data(), L, StdSqrtAdpSort, prev_clock);
7c673cae FG	287	//
7c673cae FG	288	prev_clock = back_clock;
92f5a8d4 TL	289	elements = original_elements;
	290	res = res && measure_algo(elements.data(), L,SqrtHAdaptiveSort, prev_clock);
	291	//
	292	prev_clock = back_clock;
	293	elements = original_elements;
	294	res = res && measure_algo(elements.data(), L, StdSqrtHAdpSort, prev_clock);
	295	//
	296	prev_clock = back_clock;
	297	elements = original_elements;
	298	res = res && measure_algo(elements.data(), L,AdaptiveSort, prev_clock);
	299	//
	300	prev_clock = back_clock;
	301	elements = original_elements;
	302	res = res && measure_algo(elements.data(), L,InplaceStableSort, prev_clock);
7c673cae	303	//
7c673cae	304	//prev_clock = back_clock;
92f5a8d4 TL	305	//elements = original_elements;
92f5a8d4 TL	306	//res = res && measure_algo(elements.data(), L,SlowStableSort, prev_clock);
20effc67	307
7c673cae	308	if(!res)
20effc67	309	std::abort();
7c673cae FG	310	return res;
	311	}
	312
	313	//Undef it to run the long test
	314	#define BENCH_SORT_SHORT
	315	#define BENCH_SORT_UNIQUE_VALUES
	316
	317	int main()
	318	{
	319	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	320	measure_all<order_perf_type>(101,1);
	321	measure_all<order_perf_type>(101,7);
	322	measure_all<order_perf_type>(101,31);
7c673cae	323	#endif
b32b8144	324	measure_all<order_perf_type>(101,0);
7c673cae FG	325
	326	//
	327	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	328	measure_all<order_perf_type>(1101,1);
	329	measure_all<order_perf_type>(1001,7);
	330	measure_all<order_perf_type>(1001,31);
	331	measure_all<order_perf_type>(1001,127);
	332	measure_all<order_perf_type>(1001,511);
7c673cae	333	#endif
b32b8144	334	measure_all<order_perf_type>(1001,0);
7c673cae	335	//
7c673cae	336	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	337	measure_all<order_perf_type>(10001,65);
	338	measure_all<order_perf_type>(10001,255);
	339	measure_all<order_perf_type>(10001,1023);
	340	measure_all<order_perf_type>(10001,4095);
7c673cae	341	#endif
b32b8144	342	measure_all<order_perf_type>(10001,0);
7c673cae FG	343
7c673cae FG	344	//
92f5a8d4	345	#ifdef NDEBUG
7c673cae	346	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	347	measure_all<order_perf_type>(100001,511);
	348	measure_all<order_perf_type>(100001,2047);
	349	measure_all<order_perf_type>(100001,8191);
	350	measure_all<order_perf_type>(100001,32767);
7c673cae	351	#endif
b32b8144	352	measure_all<order_perf_type>(100001,0);
7c673cae FG	353
7c673cae FG	354	//
92f5a8d4	355	#ifndef BENCH_SORT_SHORT
7c673cae	356	#ifndef BENCH_SORT_UNIQUE_VALUES
92f5a8d4 TL	357	measure_all<order_perf_type>(1000001, 8192);
	358	measure_all<order_perf_type>(1000001, 32768);
	359	measure_all<order_perf_type>(1000001, 131072);
	360	measure_all<order_perf_type>(1000001, 524288);
7c673cae	361	#endif
b32b8144	362	measure_all<order_perf_type>(1000001,0);
7c673cae	363
92f5a8d4 TL	364	#ifndef BENCH_SORT_UNIQUE_VALUES
	365	measure_all<order_perf_type>(10000001, 65536);
	366	measure_all<order_perf_type>(10000001, 262144);
	367	measure_all<order_perf_type>(10000001, 1048576);
	368	measure_all<order_perf_type>(10000001, 4194304);
	369	#endif
	370	measure_all<order_perf_type>(1000001,0);
7c673cae	371	#endif //#ifndef BENCH_SORT_SHORT
92f5a8d4	372	#endif //NDEBUG
7c673cae	373
b32b8144	374	//measure_all<order_perf_type>(100000001,0);
7c673cae FG	375
	376	return 0;
	377	}