This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Testing replacement std::sort
- From: chris jefferson <caj at cs dot york dot ac dot uk>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Thu, 19 May 2005 13:20:32 +0100
- Subject: Testing replacement std::sort
I would be very thankful to anyone who could run the attached program
and return to me along with the flags used and it's output.
I've already got output for Pentium II, III, Athlon XP and the G4. A
64-bit processor would be particularily interesting, anything which
libstdc++ is run on is useful. Feel free to compile it with processor
specific flags.
Note that this is only designed to check algorithmic changes, and
doesn't actually contain any move symantics / rvalue reference, so a) it
should run on any version of libstdc++ and b) don't expect any great
speed improvements!
It should take about 20 minutes to run, you can change the amount of
time it does each test for by changing the "minimum_time_check" on the
4th line (it's in seconds) if your system has a poor resolution clock (I
just use clock()), or you want to run it for more/less time.
Chris
PS I take no responsibility for any physical or mental problems caused
by any attempt to read this code.
#include<algorithm>
#include<time.h>
const double minimum_time_check = 3.0;
const int threshold = 16;
namespace original {
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator
unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void
introsort_loop_old(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
while (__last - __first > threshold)
{
--__depth_limit;
_RandomAccessIterator __cut =
unguarded_partition(__first, __last,
_ValueType(std::__median(*__first,
*(__first
+ (__last
- __first)
/ 2),
*(__last - 1),
__comp)),
__comp);
introsort_loop_old(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
}
template<typename _RandomAccessIterator, typename _Compare>
void
sort_function(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
introsort_loop_old(__first, __last, 16, __comp);
std::__final_insertion_sort(__first, __last, __comp);
}
}
namespace cachefriendly {
template<bool left, typename _RandomAccessIterator, typename _Size,
typename _Compare>
void
introsort_loop_old(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
while (__last - __first > threshold)
{
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition(__first, __last,
_ValueType(std::__median(*__first,
*(__first
+ (__last
- __first)
/ 2),
*(__last - 1),
__comp)),
__comp);
introsort_loop_old<false>(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
if(left)
{ std::__insertion_sort(__first, __last, __comp); }
else
{ std::__unguarded_insertion_sort(__first, __last, __comp); }
}
template<typename _RandomAccessIterator, typename _Compare>
void
sort_function(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
introsort_loop_old<true>(__first, __last, 16, __comp);
}
}
namespace cachefriendly2 {
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator inline
unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
void inline
unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
_Compare __comp)
{
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, *__next))
{
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
/**
* @if maint
* This is a helper function for the sort routine.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
inline void
unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
}
template<bool left, typename _RandomAccessIterator, typename _Size,
typename _Compare>
void
introsort_loop_old(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
while (__last - __first > threshold)
{
--__depth_limit;
_RandomAccessIterator __cut =
unguarded_partition(__first, __last,
_ValueType(std::__median(*__first,
*(__first
+ (__last
- __first)
/ 2),
*(__last - 1),
__comp)),
__comp);
introsort_loop_old<false>(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
if(left)
{ std::__insertion_sort(__first, __last, __comp); }
else
{ unguarded_insertion_sort(__first, __last, __comp); }
}
template<typename _RandomAccessIterator, typename _Compare>
void
sort_function(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
introsort_loop_old<true>(__first, __last, 16, __comp);
}
}
namespace trisplitmincopy {
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
inline _RandomAccessIterator
unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
void inline
unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
_Compare __comp)
{
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, *__next))
{
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
/**
* @if maint
* This is a helper function for the sort routine.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
inline void
unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
}
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator
unguarded_mid_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first)/2;
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (__first == __mid)
{
if(__last == __mid)
return __first;
++__first;
while(__comp(*__first, __pivot))
++__first;
if(!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
break;
}
if (__last == __mid)
{
--__last;
while(__comp( __pivot,*__last))
--__last;
if(!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
break;
}
std::iter_swap(__first, __last);
++__first;
}
next:
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
template<bool left, typename _RandomAccessIterator, typename _Size, typename _Compare>
void
introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
while (__last - __first > threshold)
{
--__depth_limit;
_RandomAccessIterator __cut;
const _ValueType &__a = *__first;
const _ValueType &__b = *(__first + (__last - __first)/2);
const _ValueType &__c = *(__last - 1);
if (__comp(__a, __b))
if (__comp(__b, __c))
__cut = unguarded_partition(__first, __last, __b, __comp);
else if (__comp(__a, __c))
__cut = unguarded_partition(__first, __last-1, __c, __comp);
else
__cut = unguarded_partition(__first+1, __last, __a, __comp);
else if (__comp(__a, __c))
__cut = unguarded_partition(__first+1, __last, __a, __comp);
else if (__comp(__b, __c))
__cut = unguarded_partition(__first, __last-1, __c, __comp);
else
__cut = unguarded_partition(__first, __last, __b, __comp);
introsort_loop<false>(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
if(left)
{ std::__insertion_sort(__first, __last, __comp); }
else
{ unguarded_insertion_sort(__first, __last, __comp); }
}
template<typename _RandomAccessIterator, typename _Compare>
void
sort_function(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
introsort_loop<true>(__first, __last, 16, __comp);
}
}
namespace trisplitswap {
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
inline _RandomAccessIterator
unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
void inline
unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
_Compare __comp)
{
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, *__next))
{
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
/**
* @if maint
* This is a helper function for the sort routine.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
inline void
unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
}
template<bool left, typename _RandomAccessIterator, typename _Size, typename _Compare>
void
introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
while (__last - __first > threshold)
{
--__depth_limit;
_RandomAccessIterator __cut;
const _ValueType &__a = *__first;
const _ValueType &__b = *(__first + (__last - __first)/2);
const _ValueType &__c = *(__last - 1);
if (__comp(__a, __b))
if (__comp(__b, __c))
{
//__cut = unguarded_mid_partition(__first, __last, __b, __comp);
std::iter_swap(__first, __first+(__last-__first)/2);
__cut = unguarded_partition(__first+1, __last, __a, __comp);
}
else if (__comp(__a, __c))
__cut = unguarded_partition(__first, __last-1, __c, __comp);
else
__cut = unguarded_partition(__first+1, __last, __a, __comp);
else if (__comp(__a, __c))
__cut = unguarded_partition(__first+1, __last, __a, __comp);
else if (__comp(__b, __c))
__cut = unguarded_partition(__first, __last-1, __c, __comp);
else
{
//__cut = unguarded_mid_partition(__first, __last, __b, __comp);
std::iter_swap(__first, __first+(__last-__first)/2);
__cut = unguarded_partition(__first+1, __last, __a, __comp);
}
introsort_loop<false>(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
if(left)
{ std::__insertion_sort(__first, __last, __comp); }
else
{ unguarded_insertion_sort(__first, __last, __comp); }
}
template<typename _RandomAccessIterator, typename _Compare>
void
sort_function(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
introsort_loop<true>(__first, __last, 16, __comp);
}
}
namespace trisplitunmovingpivot
{
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator inline
unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
void inline
unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,
_Compare __comp)
{
_RandomAccessIterator __next = __last;
--__next;
while (__comp(__val, *__next))
{
*__last = *__next;
__last = __next;
--__next;
}
*__last = __val;
}
/**
* @if maint
* This is a helper function for the sort routine.
* @endif
*/
template<typename _RandomAccessIterator, typename _Compare>
inline void
unguarded_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);
}
template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
_RandomAccessIterator inline
unguarded_mid_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Tp __pivot, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first)/2;
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (__first == __mid)
{
if(__last == __mid)
return __first;
++__first;
while(__comp(*__first, __pivot))
++__first;
if(!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
break;
}
if (__last == __mid)
{
--__last;
while(__comp( __pivot,*__last))
--__last;
if(!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
break;
}
std::iter_swap(__first, __last);
++__first;
}
next:
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}
template<bool left, typename _RandomAccessIterator, typename _Size, typename _Compare>
void
introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit, _Compare __comp)
{
typedef typename std::iterator_traits<_RandomAccessIterator>::value_type
_ValueType;
while (__last - __first > threshold)
{
--__depth_limit;
_RandomAccessIterator __cut;
const _ValueType &__a = *__first;
const _ValueType &__b = *(__first + (__last - __first)/2);
const _ValueType &__c = *(__last - 1);
if (__comp(__a, __b))
if (__comp(__b, __c))
{
__cut = unguarded_mid_partition(__first, __last, __b, __comp);
//std::iter_swap(__first, __first+(__last-__first)/2);
//__cut = unguarded_partition(__first+1, __last, __a, __comp);
}
else if (__comp(__a, __c))
__cut = unguarded_partition(__first, __last-1, __c, __comp);
else
__cut = unguarded_partition(__first+1, __last, __a, __comp);
else if (__comp(__a, __c))
__cut = unguarded_partition(__first+1, __last, __a, __comp);
else if (__comp(__b, __c))
__cut = unguarded_partition(__first, __last-1, __c, __comp);
else
{
__cut = unguarded_mid_partition(__first, __last, __b, __comp);
//std::iter_swap(__first, __first+(__last-__first)/2);
//__cut = unguarded_partition(__first+1, __last, __a, __comp);
}
introsort_loop<false>(__cut, __last, __depth_limit, __comp);
__last = __cut;
}
if(left)
{ std::__insertion_sort(__first, __last, __comp); }
else
{ unguarded_insertion_sort(__first, __last, __comp); }
}
template<typename _RandomAccessIterator, typename _Compare>
void
sort_function(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
introsort_loop<true>(__first, __last, 16, __comp);
}
}
struct less
{
template<class T>
bool operator()(T i,T j) { return i<j; }
};
int primeval;
int seedval;
inline void
restart_generator()
{seedval=1009%primeval;}
inline int get_generator_value()
{
seedval = seedval * 1098301;
return seedval % primeval;
}
void check_int()
{
printf("check int\n");
int primearray[]={5,8000009};
for(int loop=0;loop<2;loop++)
{
primeval = primearray[loop];
printf("check sort drawn from 0..%d\n", primeval);
for(int length = 100; length < 1000001; length*=100)
{
printf("check sort length %d\n", length);
int* array;
array = new int[length];
int looplengthrandom = 1, looplengthfixed = 1;
// Calibrate random search
double timetaken = 0;
while(timetaken<minimum_time_check)
{
looplengthrandom*=2;
int start = clock();
for(int loop = 0; loop < looplengthrandom; loop++)
{
restart_generator();
for(int i = 0; i < length; i++)
array[i] = get_generator_value();
original::sort_function(array,array+length,less());
}
int end = clock();
timetaken = ((end-start)*1.0) / CLOCKS_PER_SEC;
}
// Calibrate fixed search
for(int i=0; i < length; i++)
array[i]=(i*primeval)/length;
timetaken = 0;
while(timetaken < minimum_time_check)
{
looplengthfixed *=2;
int start = clock();
for(int loop = 0; loop < looplengthfixed; loop++)
{
original::sort_function(array,array+length,less());
}
int end = clock();
timetaken = ((end-start)*1.0) / CLOCKS_PER_SEC;
}
printf("Random Iterations:%d, Sorted Iterations:%d\n",
looplengthrandom, looplengthfixed);
#define TEST_SORT(TEST_SPACE) {\
{\
int start = clock(); \
for(int i=0;i<looplengthrandom;i++) { \
restart_generator(); \
for(int i = 0; i < length; i++) \
array[i] = get_generator_value(); \
TEST_SPACE::sort_function(array, array+length, less());\
}\
int end=clock(); \
printf( "%22s:random:%f,", #TEST_SPACE, ((end-start)*1.0) / CLOCKS_PER_SEC);\
}\
{\
for(int i = 0; i < length; i++) \
array[i] = (i*primeval)/length;\
int start = clock(); \
for(int i=0;i<looplengthfixed;i++) { \
TEST_SPACE::sort_function(array, array+length, less());\
}\
int end=clock(); \
printf("sorted:%f\n", ((end-start)*1.0) / CLOCKS_PER_SEC);\
}\
}\
TEST_SORT(original);
TEST_SORT(cachefriendly);
TEST_SORT(cachefriendly2);
TEST_SORT(trisplitmincopy);
TEST_SORT(trisplitswap);
TEST_SORT(trisplitunmovingpivot);
delete[] array;
}
}
}
void check_char() {
printf("check char\n");
int primearray[]={5,251};
for(int loop=0;loop<2;loop++)
{
primeval = primearray[loop];
printf("check sort drawn from 0..%d\n", primeval);
for(int length = 100; length < 1000001; length*=100)
{
printf("check sort length %d\n", length);
char* array;
array = new char[length];
int looplengthrandom = 1, looplengthfixed = 1;
// Calibrate random search
double timetaken = 0;
while(timetaken<minimum_time_check)
{
looplengthrandom*=2;
int start = clock();
for(int loop = 0; loop < looplengthrandom; loop++)
{
restart_generator();
for(int i = 0; i < length; i++)
array[i] = get_generator_value();
original::sort_function(array,array+length,less());
}
int end = clock();
timetaken = ((end-start)*1.0) / CLOCKS_PER_SEC;
}
// Calibrate fixed search
for(int i=0; i < length; i++)
array[i]=(i*primeval)/length;
timetaken = 0;
while(timetaken < minimum_time_check)
{
looplengthfixed *=2;
int start = clock();
for(int loop = 0; loop < looplengthfixed; loop++)
{
original::sort_function(array,array+length,less());
}
int end = clock();
timetaken = ((end-start)*1.0) / CLOCKS_PER_SEC;
}
printf("Random Iterations:%d, Sorted Iterations:%d\n",
looplengthrandom, looplengthfixed);
#define TEST_SORT(TEST_SPACE) {\
{\
int start = clock(); \
for(int i=0;i<looplengthrandom;i++) { \
restart_generator(); \
for(int i = 0; i < length; i++) \
array[i] = get_generator_value(); \
TEST_SPACE::sort_function(array, array+length, less());\
}\
int end=clock(); \
printf( "%22s:random:%f,", #TEST_SPACE, ((end-start)*1.0) / CLOCKS_PER_SEC);\
}\
{\
for(int i = 0; i < length; i++) \
array[i] = (i*primeval)/length;\
int start = clock(); \
for(int i=0;i<looplengthfixed;i++) { \
TEST_SPACE::sort_function(array, array+length, less());\
}\
int end=clock(); \
printf("sorted:%f\n", ((end-start)*1.0) / CLOCKS_PER_SEC);\
}\
}\
TEST_SORT(original);
TEST_SORT(cachefriendly);
TEST_SORT(cachefriendly2);
TEST_SORT(trisplitmincopy);
TEST_SORT(trisplitswap);
TEST_SORT(trisplitunmovingpivot);
delete[] array;
}
}
}
struct big_struct
{
int array[20];
void operator=(int i)
{
array[0] = i;
for(int loop=0;loop<20;loop++)
array[loop]=0;
}
};
inline bool
operator<(const big_struct& a, const big_struct& b)
{
return a.array[0] < b.array[0];
}
void check_big_struct()
{
printf("check big_struct\n");
int primearray[]={5,8000009};
for(int loop=0;loop<2;loop++)
{
primeval = primearray[loop];
printf("check sort drawn from 0..%d\n", primeval);
for(int length = 100; length < 10001; length*=100)
{
printf("check sort length %d\n", length);
big_struct* array;
array = new big_struct[length];
int looplengthrandom = 1, looplengthfixed = 1;
// Calibrate random search
double timetaken = 0;
while(timetaken<minimum_time_check)
{
looplengthrandom*=2;
int start = clock();
for(int loop = 0; loop < looplengthrandom; loop++)
{
restart_generator();
for(int i = 0; i < length; i++)
array[i] = get_generator_value();
original::sort_function(array,array+length,less());
}
int end = clock();
timetaken = ((end-start)*1.0) / CLOCKS_PER_SEC;
}
// Calibrate fixed search
for(int i=0; i < length; i++)
array[i]=(i*primeval)/length;
timetaken = 0;
while(timetaken < minimum_time_check)
{
looplengthfixed *=2;
int start = clock();
for(int loop = 0; loop < looplengthfixed; loop++)
{
original::sort_function(array,array+length,less());
}
int end = clock();
timetaken = ((end-start)*1.0) / CLOCKS_PER_SEC;
}
printf("Random Iterations:%d, Sorted Iterations:%d\n",
looplengthrandom, looplengthfixed);
#define TEST_SORT(TEST_SPACE) {\
{\
int start = clock(); \
for(int i=0;i<looplengthrandom;i++) { \
restart_generator(); \
for(int i = 0; i < length; i++) \
array[i] = get_generator_value(); \
TEST_SPACE::sort_function(array, array+length, less());\
}\
int end=clock(); \
printf( "%22s:random:%f,", #TEST_SPACE, ((end-start)*1.0) / CLOCKS_PER_SEC);\
}\
{\
for(int i = 0; i < length; i++) \
array[i] = (i*primeval)/length;\
int start = clock(); \
for(int i=0;i<looplengthfixed;i++) { \
TEST_SPACE::sort_function(array, array+length, less());\
}\
int end=clock(); \
printf("sorted:%f\n", ((end-start)*1.0) / CLOCKS_PER_SEC);\
}\
}\
TEST_SORT(original);
TEST_SORT(cachefriendly);
TEST_SORT(cachefriendly2);
TEST_SORT(trisplitmincopy);
TEST_SORT(trisplitswap);
TEST_SORT(trisplitunmovingpivot);
delete[] array;
}
}
}
int main(void) {
check_big_struct();
check_int();
check_char();
}