[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/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/core.hpp>

template<class T>
void generate_elements(T elements[], std::size_t element_count, std::size_t key_reps[], std::size_t key_len)
{
   std::srand(0);
   for(std::size_t i = 0; i < (key_len ? key_len : element_count); ++i){
      key_reps[i]=0;
   }
   for(std::size_t  i=0; i < element_count; ++i){
      std::size_t  key = key_len ? (i % key_len) : i;
      elements[i].key=key;
   }
   ::random_shuffle(elements, elements + element_count);
   ::random_shuffle(elements, elements + element_count);
   ::random_shuffle(elements, elements + element_count);
   for(std::size_t i = 0; i < element_count; ++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 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,
   AdaptiveSort,
   SqrtHAdaptiveSort,
   SqrtAdaptiveSort,
   Sqrt2AdaptiveSort,
   QuartAdaptiveSort,
   InplaceStableSort,
   SlowStableSort,
   HeapSort,
   MaxSort
};

const char *AlgoNames [] = { "MergeSort      "
                           , "StableSort     "
                           , "AdaptSort      "
                           , "SqrtHAdaptSort "
                           , "SqrtAdaptSort  "
                           , "Sqrt2AdaptSort "
                           , "QuartAdaptSort "
                           , "InplStableSort "
                           , "SlowSort       "
                           , "HeapSort       "
                           };

BOOST_STATIC_ASSERT((sizeof(AlgoNames)/sizeof(*AlgoNames)) == MaxSort);

template<class T>
bool measure_algo(T *elements, std::size_t key_reps[], std::size_t element_count, std::size_t key_len, unsigned alg, nanosecond_type &prev_clock)
{
   generate_elements(elements, element_count, key_reps, key_len);

   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 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 SlowStableSort:
         boost::movelib::detail_adaptive::slow_stable_sort(elements, elements+element_count, order_type_less());
      break;
      case HeapSort:
         std::make_heap(elements, elements+element_count, order_type_less());
         std::sort_heap(elements, elements+element_count, 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);
   return res;
}

template<class T>
bool measure_all(std::size_t L, std::size_t NK)
{
   boost::movelib::unique_ptr<T[]> pdata(new T[L]);
   boost::movelib::unique_ptr<std::size_t[]> pkeys(new std::size_t[NK ? NK : L]);
   T *A              = pdata.get();
   std::size_t *Keys = pkeys.get();
   std::printf("\n - - N: %u, NK: %u - -\n", (unsigned)L, (unsigned)NK);

   nanosecond_type prev_clock = 0;
   nanosecond_type back_clock;
   bool res = true;
   res = res && measure_algo(A,Keys,L,NK,MergeSort, prev_clock);
   back_clock = prev_clock;
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,StableSort, prev_clock);
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,HeapSort, prev_clock);
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,QuartAdaptiveSort, prev_clock);
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,Sqrt2AdaptiveSort, prev_clock);
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,SqrtAdaptiveSort, prev_clock);
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,SqrtHAdaptiveSort, prev_clock);
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,AdaptiveSort, prev_clock);
   //
   prev_clock = back_clock;
   res = res && measure_algo(A,Keys,L,NK,InplaceStableSort, prev_clock);
   //
   //prev_clock = back_clock;
   //res = res && measure_algo(A,Keys,L,NK,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_SHORT
   #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);

   //
   #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);

   //
   #ifdef NDEBUG
   #ifndef BENCH_SORT_UNIQUE_VALUES
   measure_all<order_perf_type>(1000001,1);
   measure_all<order_perf_type>(1000001,1024);
   measure_all<order_perf_type>(1000001,32768);
   measure_all<order_perf_type>(1000001,524287);
   #endif
   measure_all<order_perf_type>(1000001,0);
   measure_all<order_perf_type>(1500001,0);
   #endif   //NDEBUG

   #endif   //#ifndef BENCH_SORT_SHORT

   //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
	16
	17	#include <boost/config.hpp>
	18
	19	#include <boost/move/unique_ptr.hpp>
	20	#include <boost/timer/timer.hpp>
	21
	22	using boost::timer::cpu_timer;
	23	using boost::timer::cpu_times;
	24	using boost::timer::nanosecond_type;
	25
	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>
7c673cae FG	39	#include <boost/move/core.hpp>
	40
	41	template<class T>
	42	void generate_elements(T elements[], std::size_t element_count, std::size_t key_reps[], std::size_t key_len)
	43	{
	44	std::srand(0);
	45	for(std::size_t i = 0; i < (key_len ? key_len : element_count); ++i){
	46	key_reps[i]=0;
	47	}
	48	for(std::size_t i=0; i < element_count; ++i){
	49	std::size_t key = key_len ? (i % key_len) : i;
	50	elements[i].key=key;
	51	}
b32b8144 FG	52	::random_shuffle(elements, elements + element_count);
	53	::random_shuffle(elements, elements + element_count);
	54	::random_shuffle(elements, elements + element_count);
7c673cae FG	55	for(std::size_t i = 0; i < element_count; ++i){
	56	elements[i].val = key_reps[elements[i].key]++;
	57	}
	58	}
	59
	60	template<class T, class Compare>
	61	void adaptive_sort_buffered(T *elements, std::size_t element_count, Compare comp, std::size_t BufLen)
	62	{
	63	boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*BufLen]);
	64	boost::movelib::adaptive_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()), BufLen);
	65	}
	66
	67	template<class T, class Compare>
	68	void merge_sort_buffered(T *elements, std::size_t element_count, Compare comp)
	69	{
	70	boost::movelib::unique_ptr<char[]> mem(new char[sizeof(T)*((element_count+1)/2)]);
	71	boost::movelib::merge_sort(elements, elements + element_count, comp, reinterpret_cast<T*>(mem.get()));
	72	}
	73
	74	enum AlgoType
	75	{
	76	MergeSort,
	77	StableSort,
	78	AdaptiveSort,
	79	SqrtHAdaptiveSort,
	80	SqrtAdaptiveSort,
	81	Sqrt2AdaptiveSort,
	82	QuartAdaptiveSort,
7c673cae FG	83	InplaceStableSort,
	84	SlowStableSort,
	85	HeapSort,
	86	MaxSort
	87	};
	88
	89	const char *AlgoNames [] = { "MergeSort "
	90	, "StableSort "
	91	, "AdaptSort "
	92	, "SqrtHAdaptSort "
	93	, "SqrtAdaptSort "
	94	, "Sqrt2AdaptSort "
	95	, "QuartAdaptSort "
7c673cae FG	96	, "InplStableSort "
	97	, "SlowSort "
	98	, "HeapSort "
	99	};
	100
	101	BOOST_STATIC_ASSERT((sizeof(AlgoNames)/sizeof(*AlgoNames)) == MaxSort);
	102
	103	template<class T>
	104	bool measure_algo(T *elements, std::size_t key_reps[], std::size_t element_count, std::size_t key_len, unsigned alg, nanosecond_type &prev_clock)
	105	{
	106	generate_elements(elements, element_count, key_reps, key_len);
	107
	108	std::printf("%s ", AlgoNames[alg]);
b32b8144 FG	109	order_perf_type::num_compare=0;
	110	order_perf_type::num_copy=0;
	111	order_perf_type::num_elements = element_count;
7c673cae FG	112	cpu_timer timer;
	113	timer.resume();
	114	switch(alg)
	115	{
	116	case MergeSort:
b32b8144	117	merge_sort_buffered(elements, element_count, order_type_less());
7c673cae FG	118	break;
7c673cae FG	119	case StableSort:
b32b8144	120	std::stable_sort(elements,elements+element_count,order_type_less());
7c673cae FG	121	break;
7c673cae FG	122	case AdaptiveSort:
b32b8144	123	boost::movelib::adaptive_sort(elements, elements+element_count, order_type_less());
7c673cae FG	124	break;
7c673cae FG	125	case SqrtHAdaptiveSort:
b32b8144	126	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	127	, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count)/2+1);
	128	break;
	129	case SqrtAdaptiveSort:
b32b8144	130	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	131	, boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
	132	break;
	133	case Sqrt2AdaptiveSort:
b32b8144	134	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	135	, 2*boost::movelib::detail_adaptive::ceil_sqrt_multiple(element_count));
	136	break;
	137	case QuartAdaptiveSort:
b32b8144	138	adaptive_sort_buffered( elements, element_count, order_type_less()
7c673cae FG	139	, (element_count-1)/4+1);
7c673cae FG	140	break;
7c673cae	141	case InplaceStableSort:
b32b8144	142	boost::movelib::inplace_stable_sort(elements, elements+element_count, order_type_less());
7c673cae FG	143	break;
7c673cae FG	144	case SlowStableSort:
b32b8144	145	boost::movelib::detail_adaptive::slow_stable_sort(elements, elements+element_count, order_type_less());
7c673cae FG	146	break;
7c673cae FG	147	case HeapSort:
b32b8144 FG	148	std::make_heap(elements, elements+element_count, order_type_less());
b32b8144 FG	149	std::sort_heap(elements, elements+element_count, order_type_less());
7c673cae FG	150	break;
	151	}
	152	timer.stop();
	153
b32b8144	154	if(order_perf_type::num_elements == element_count){
7c673cae FG	155	std::printf(" Tmp Ok ");
	156	} else{
	157	std::printf(" Tmp KO ");
	158	}
	159	nanosecond_type new_clock = timer.elapsed().wall;
	160
b32b8144 FG	161	//std::cout << "Cmp:" << order_perf_type::num_compare << " Cpy:" << order_perf_type::num_copy; //for old compilers without ll size argument
b32b8144 FG	162	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	163
	164	double time = double(new_clock);
	165
	166	const char *units = "ns";
	167	if(time >= 1000000000.0){
	168	time /= 1000000000.0;
	169	units = " s";
	170	}
	171	else if(time >= 1000000.0){
	172	time /= 1000000.0;
	173	units = "ms";
	174	}
	175	else if(time >= 1000.0){
	176	time /= 1000.0;
	177	units = "us";
	178	}
	179
	180	std::printf(" %6.02f%s (%6.02f)\n"
	181	, time
	182	, units
	183	, prev_clock ? double(new_clock)/double(prev_clock): 1.0);
	184	prev_clock = new_clock;
b32b8144	185	bool res = is_order_type_ordered(elements, element_count, alg != HeapSort);
7c673cae FG	186	return res;
	187	}
	188
	189	template<class T>
	190	bool measure_all(std::size_t L, std::size_t NK)
	191	{
	192	boost::movelib::unique_ptr<T[]> pdata(new T[L]);
	193	boost::movelib::unique_ptr<std::size_t[]> pkeys(new std::size_t[NK ? NK : L]);
	194	T *A = pdata.get();
	195	std::size_t *Keys = pkeys.get();
	196	std::printf("\n - - N: %u, NK: %u - -\n", (unsigned)L, (unsigned)NK);
	197
	198	nanosecond_type prev_clock = 0;
	199	nanosecond_type back_clock;
	200	bool res = true;
	201	res = res && measure_algo(A,Keys,L,NK,MergeSort, prev_clock);
	202	back_clock = prev_clock;
	203	//
	204	prev_clock = back_clock;
	205	res = res && measure_algo(A,Keys,L,NK,StableSort, prev_clock);
	206	//
	207	prev_clock = back_clock;
	208	res = res && measure_algo(A,Keys,L,NK,HeapSort, prev_clock);
	209	//
	210	prev_clock = back_clock;
	211	res = res && measure_algo(A,Keys,L,NK,QuartAdaptiveSort, prev_clock);
	212	//
	213	prev_clock = back_clock;
	214	res = res && measure_algo(A,Keys,L,NK,Sqrt2AdaptiveSort, prev_clock);
	215	//
	216	prev_clock = back_clock;
	217	res = res && measure_algo(A,Keys,L,NK,SqrtAdaptiveSort, prev_clock);
	218	//
	219	prev_clock = back_clock;
	220	res = res && measure_algo(A,Keys,L,NK,SqrtHAdaptiveSort, prev_clock);
	221	//
	222	prev_clock = back_clock;
	223	res = res && measure_algo(A,Keys,L,NK,AdaptiveSort, prev_clock);
	224	//
	225	prev_clock = back_clock;
	226	res = res && measure_algo(A,Keys,L,NK,InplaceStableSort, prev_clock);
	227	//
7c673cae FG	228	//prev_clock = back_clock;
	229	//res = res && measure_algo(A,Keys,L,NK,SlowStableSort, prev_clock);
	230	//
	231	if(!res)
	232	throw int(0);
	233	return res;
	234	}
	235
	236	//Undef it to run the long test
	237	#define BENCH_SORT_SHORT
	238	#define BENCH_SORT_UNIQUE_VALUES
	239
	240	int main()
	241	{
	242	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	243	measure_all<order_perf_type>(101,1);
	244	measure_all<order_perf_type>(101,7);
	245	measure_all<order_perf_type>(101,31);
7c673cae	246	#endif
b32b8144	247	measure_all<order_perf_type>(101,0);
7c673cae FG	248
	249	//
	250	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	251	measure_all<order_perf_type>(1101,1);
	252	measure_all<order_perf_type>(1001,7);
	253	measure_all<order_perf_type>(1001,31);
	254	measure_all<order_perf_type>(1001,127);
	255	measure_all<order_perf_type>(1001,511);
7c673cae	256	#endif
b32b8144	257	measure_all<order_perf_type>(1001,0);
7c673cae FG	258	//
	259	#ifndef BENCH_SORT_SHORT
	260	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	261	measure_all<order_perf_type>(10001,65);
	262	measure_all<order_perf_type>(10001,255);
	263	measure_all<order_perf_type>(10001,1023);
	264	measure_all<order_perf_type>(10001,4095);
7c673cae	265	#endif
b32b8144	266	measure_all<order_perf_type>(10001,0);
7c673cae FG	267
	268	//
	269	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	270	measure_all<order_perf_type>(100001,511);
	271	measure_all<order_perf_type>(100001,2047);
	272	measure_all<order_perf_type>(100001,8191);
	273	measure_all<order_perf_type>(100001,32767);
7c673cae	274	#endif
b32b8144	275	measure_all<order_perf_type>(100001,0);
7c673cae FG	276
7c673cae FG	277	//
b32b8144	278	#ifdef NDEBUG
7c673cae	279	#ifndef BENCH_SORT_UNIQUE_VALUES
b32b8144 FG	280	measure_all<order_perf_type>(1000001,1);
	281	measure_all<order_perf_type>(1000001,1024);
	282	measure_all<order_perf_type>(1000001,32768);
	283	measure_all<order_perf_type>(1000001,524287);
7c673cae	284	#endif
b32b8144 FG	285	measure_all<order_perf_type>(1000001,0);
	286	measure_all<order_perf_type>(1500001,0);
	287	#endif //NDEBUG
7c673cae FG	288
	289	#endif //#ifndef BENCH_SORT_SHORT
	290
b32b8144	291	//measure_all<order_perf_type>(100000001,0);
7c673cae FG	292
	293	return 0;
	294	}