| /* | |
| Copyright 2007-2008 Adobe Systems Incorporated | |
| Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt | |
| or a copy at http://stlab.adobe.com/licenses.html ) | |
| This test file started life as | |
| ISO/IEC TR 18015:2006(E) Appendix D.4 | |
| Goals: | |
| Compare the performance of function pointers, functors, inline functors, | |
| standard functors, and native comparison operators | |
| Also compare the performance of qsort(), quicksort template, and std::sort | |
| Assumptions: | |
| 1) inline functors, standard functors and inlined native | |
| comparisons will perform similarly | |
| 2) using functors is faster than using function pointers | |
| 3) inline functors are as fast or faster than out of line functors | |
| 4) a template is at least as fast as a hard coded function of | |
| the same algorithm, sometimes faster | |
| 5) std::sort is faster than qsort() | |
| 6) std::sort is faster than a naive quicksort template using the same functor | |
| Since qsort's comparison function must return int (less than 0, 0, greater than 0) | |
| and std::sort's must return a bool, it is not possible to test them with each | |
| other's comparator. | |
| */ | |
| /******************************************************************************/ | |
| #include <functional> | |
| #include <algorithm> | |
| #include <cstdlib> | |
| #include "benchmark_results.h" | |
| #include "benchmark_timer.h" | |
| using namespace std; | |
| /******************************************************************************/ | |
| template <class Iterator> | |
| void verify_sorted(Iterator first, Iterator last) { | |
| Iterator prev = first; | |
| first++; | |
| while (first != last) { | |
| if (*first++ < *prev++) { | |
| printf("test %i failed\n", current_test); | |
| break; | |
| } | |
| } | |
| } | |
| /******************************************************************************/ | |
| // --------- helper functions -------------------------------------------- | |
| // qsort passes void * arguments to its comparison function, | |
| // which must return negative, 0, or positive value | |
| int | |
| less_than_function1( const void * lhs, const void * rhs ) | |
| { | |
| if( *(const double *) lhs < *(const double *) rhs ) return -1; | |
| if( *(const double *) lhs > *(const double *) rhs ) return 1; | |
| return 0; | |
| } | |
| // std::sort, on the other hand, needs a comparator that returns true or false | |
| bool | |
| less_than_function2( const double lhs, const double rhs ) | |
| { | |
| return( lhs < rhs? true : false ); | |
| } | |
| // the comparison operator in the following functor is defined out of line | |
| struct less_than_functor | |
| { | |
| bool operator()( const double& lhs, const double& rhs ) const; | |
| }; | |
| bool | |
| less_than_functor::operator()( const double& lhs, const double& rhs ) const | |
| { | |
| return( lhs < rhs? true : false ); | |
| } | |
| // the comparison operator in the following functor is defined inline | |
| struct inline_less_than_functor | |
| { | |
| inline bool operator()( const double& lhs, const double& rhs ) const | |
| { | |
| return( lhs < rhs? true : false ); | |
| } | |
| }; | |
| /******************************************************************************/ | |
| // hard coded comparison function | |
| template<class Iterator> | |
| void quicksort(Iterator begin, Iterator end) | |
| { | |
| // this only works for pointers and STL iterators | |
| typedef typename iterator_traits<Iterator>::value_type T; | |
| if ( (end - begin) > 1 ) { | |
| T middleValue = *begin; | |
| Iterator left = begin; | |
| Iterator right = end; | |
| for(;;) { | |
| while ( middleValue < *(--right) ); | |
| if ( !(left < right ) ) break; | |
| while ( *(left) < middleValue ) | |
| ++left; | |
| if ( !(left < right ) ) break; | |
| // swap | |
| T temp = *right; | |
| *right = *left; | |
| *left = temp; | |
| } | |
| quicksort( begin, right + 1 ); | |
| quicksort( right + 1, end ); | |
| } | |
| } | |
| /******************************************************************************/ | |
| // comparison function passed in as a functor | |
| template<class Iterator, typename Comparator> | |
| void quicksort(Iterator begin, Iterator end, Comparator compare) | |
| { | |
| // this only works for pointers and STL iterators | |
| typedef typename iterator_traits<Iterator>::value_type T; | |
| if ( (end - begin) > 1 ) { | |
| T middleValue = *begin; | |
| Iterator left = begin; | |
| Iterator right = end; | |
| for(;;) { | |
| while ( compare( middleValue, *(--right) ) ); | |
| if ( !(left < right ) ) break; | |
| while ( compare( *(left), middleValue ) ) | |
| ++left; | |
| if ( !(left < right ) ) break; | |
| // swap | |
| T temp = *right; | |
| *right = *left; | |
| *left = temp; | |
| } | |
| quicksort( begin, right + 1, compare ); | |
| quicksort( right + 1, end, compare ); | |
| } | |
| } | |
| /******************************************************************************/ | |
| typedef bool comparator_function( const double x, const double y ); | |
| // use a pointer to function as a template parameter | |
| // exact function is known at compile time, and can be inlined | |
| template<class Iterator, comparator_function compare> | |
| void quicksort(Iterator begin, Iterator end) | |
| { | |
| // this only works for pointers and STL iterators | |
| typedef typename iterator_traits<Iterator>::value_type T; | |
| if ( (end - begin) > 1 ) { | |
| T middleValue = *begin; | |
| Iterator left = begin; | |
| Iterator right = end; | |
| for(;;) { | |
| while ( compare( middleValue, *(--right) ) ); | |
| if ( !(left < right ) ) break; | |
| while ( compare( *(left), middleValue ) ) | |
| ++left; | |
| if ( !(left < right ) ) break; | |
| // swap | |
| T temp = *right; | |
| *right = *left; | |
| *left = temp; | |
| } | |
| quicksort( begin, right + 1, compare ); | |
| quicksort( right + 1, end, compare ); | |
| } | |
| } | |
| /******************************************************************************/ | |
| // use a function pointer | |
| // most compilers will not inline the function argument | |
| void quicksort_function(double* begin, double* end, comparator_function compare) | |
| { | |
| if ( (end - begin) > 1 ) { | |
| double middleValue = *begin; | |
| double* left = begin; | |
| double* right = end; | |
| for(;;) { | |
| while ( compare( middleValue, *(--right) ) ); | |
| if ( !(left < right ) ) break; | |
| while ( compare( *(left), middleValue ) ) | |
| ++left; | |
| if ( !(left < right ) ) break; | |
| // swap | |
| double temp = *right; | |
| *right = *left; | |
| *left = temp; | |
| } | |
| quicksort( begin, right + 1, compare ); | |
| quicksort( right + 1, end, compare ); | |
| } | |
| } | |
| /******************************************************************************/ | |
| int main(int argc, char* argv[]) | |
| { | |
| int i; | |
| #ifdef SMALL_PROBLEM_SIZE | |
| int iterations = (1 < argc) ? atoi(argv[1]) : 30; // number of iterations | |
| #else | |
| int iterations = (1 < argc) ? atoi(argv[1]) : 300; // number of iterations | |
| #endif | |
| int tablesize = (2 < argc) ? atoi(argv[2]) : 10000; // size of array | |
| // seed the random number generator, so we get repeatable results | |
| srand( tablesize + 123 ); | |
| // initialize the table to sort | |
| double * master_table = new double[tablesize]; | |
| for( int n = 0; n < tablesize; ++n ) | |
| { | |
| master_table[n] = static_cast<double>( rand() ); | |
| } | |
| double * table = new double[tablesize]; // working copy | |
| // here is where the timing starts | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| qsort( table, tablesize, sizeof(double), less_than_function1 ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| quicksort_function( table, table + tablesize, less_than_function2 ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| quicksort( table, table + tablesize, less_than_function2 ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| quicksort<double *, less_than_function2 >( table, table + tablesize ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| sort( table, table + tablesize, less_than_function2 ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| quicksort( table, table + tablesize, less_than_functor() ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| sort( table, table + tablesize, less_than_functor() ); | |
| verify_sorted( table, table + tablesize ); | |
| copy(master_table, master_table+tablesize, table); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| quicksort( table, table + tablesize, inline_less_than_functor() ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| sort( table, table + tablesize, inline_less_than_functor() ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| quicksort( table, table + tablesize, less<double>() ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| sort( table, table + tablesize, less<double>() ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy(master_table, master_table+tablesize, table); | |
| quicksort( table, table + tablesize ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| for (i = 0; i < iterations; ++i) | |
| { | |
| copy( master_table, master_table+tablesize, table ); | |
| sort( table, table + tablesize ); | |
| verify_sorted( table, table + tablesize ); | |
| } | |
| delete[] table; | |
| delete[] master_table; | |
| return 0; | |
| } |