123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556 |
- //----------------------------------------------------------------------------
- /// @file benchmark_objects.cpp
- /// @brief Benchmark of several sort methods with different objects
- ///
- /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n
- /// Distributed under the Boost Software License, Version 1.0.\n
- /// ( See accompanying file LICENSE_1_0.txt or copy at
- /// http://www.boost.org/LICENSE_1_0.txt )
- ///
- /// This program use for comparison purposes, the Threading Building
- /// Blocks which license is the GNU General Public License, version 2
- /// as published by the Free Software Foundation.
- ///
- /// @version 0.1
- ///
- /// @remarks
- //-----------------------------------------------------------------------------
- #include <algorithm>
- #include <iostream>
- #include <iomanip>
- #include <random>
- #include <stdlib.h>
- #include <vector>
- #include <boost/sort/common/time_measure.hpp>
- #include <boost/sort/common/file_vector.hpp>
- #include "boost/sort/common/int_array.hpp"
- #include <boost/sort/sort.hpp>
- #define NELEM 100000000
- #define NMAXSTRING 10000000
- using namespace std;
- namespace bsort = boost::sort;
- namespace bsc = bsort::common;
- using bsc::time_point;
- using bsc::now;
- using bsc::subtract_time;
- using bsc::fill_vector_uint64;
- using bsc::write_file_uint64;
- using bsc::int_array;
- using bsc::H_comp;
- using bsc::L_comp;
- using bsort::flat_stable_sort;
- using bsort::spinsort;
- using bsort::spreadsort::spreadsort;
- using bsort::pdqsort;
- template <class IA>
- void Generator_random(uint64_t N);
- template <class IA>
- void Generator_sorted(uint64_t N);
- template <class IA>
- void Generator_sorted_end(uint64_t N, size_t n_last );
- template <class IA>
- void Generator_sorted_middle(uint64_t N, size_t n_last );
- template <class IA>
- void Generator_reverse_sorted(uint64_t N);
- template <class IA>
- void Generator_reverse_sorted_end(uint64_t N, size_t n_last );
- template <class IA>
- void Generator_reverse_sorted_middle(uint64_t N, size_t n_last );
- template < class IA >
- struct H_rightshift {
- inline uint64_t operator()(const IA& A1, unsigned offset) {
- return A1.counter() >> offset;
- }
- };
- template < class IA >
- struct L_rightshift {
- inline uint64_t operator()(const IA& A1, unsigned offset) {
- return A1.M[0] >> offset;
- }
- };
- template <class IA, class rightshift, class compare>
- int Test(std::vector<IA> &B, rightshift shift, compare comp, std::vector<double> & V );
- template <class IA>
- void Test_size ( uint64_t N);
- void Print_vectors ( std::vector<double> & V1, std::vector<double> & V2);
- int main(int argc, char *argv[])
- {
- cout << "\n\n";
- cout << "************************************************************\n";
- cout << "** **\n";
- cout << "** B O O S T S O R T **\n";
- cout << "** **\n";
- cout << "** O B J E C T S B E N C H M A R K **\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- cout << std::endl;
- cout << "=============================================================\n";
- cout << "= OBJECT COMPARISON =\n";
- cout << "= --------------------- =\n";
- cout << "= =\n";
- cout << "= The objects are arrays of 64 bits numbers =\n";
- cout << "= They are compared in two ways : =\n";
- cout << "= (H) Heavy : The comparison is the sum of all the numbers =\n";
- cout << "= of the array =\n";
- cout << "= (L) Light : The comparison is with the first element of =\n";
- cout << "= the array, as a key =\n";
- cout << "= =\n";
- cout << "============================================================\n";
- cout << "\n\n";
- //-----------------------------------------------------------------------
- // I N T _ A R R A Y < 1 >
- //-----------------------------------------------------------------------
- cout << "************************************************************\n";
- cout << "** **\n";
- cout << " "<<NELEM<<" OBJECTS UINT64_T [1]\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- Test_size<int_array<1> >(NELEM);
- //-----------------------------------------------------------------------
- // I N T _ A R R A Y < 4 >
- //-----------------------------------------------------------------------
- cout << "************************************************************\n";
- cout << "** **\n";
- cout << " "<<(NELEM >>2)<<" OBJECTS UINT64_T [4]\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- Test_size<int_array<4> >(NELEM >> 2);
- //-----------------------------------------------------------------------
- // I N T _ A R R A Y < 8 >
- //-----------------------------------------------------------------------
- cout << "************************************************************\n";
- cout << "** **\n";
- cout << " "<<(NELEM >>3)<<" OBJECTS UINT64_T [8]\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- Test_size<int_array<8> >(NELEM >> 3);
- //-----------------------------------------------------------------------
- // I N T _ A R R A Y < 1 6 >
- //-----------------------------------------------------------------------
- cout << "************************************************************\n";
- cout << "** **\n";
- cout << " "<<(NELEM >>4)<<" OBJECTS UINT64_T [16]\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- Test_size<int_array<16> >(NELEM >> 4);
- //-----------------------------------------------------------------------
- // I N T _ A R R A Y < 6 4 >
- //-----------------------------------------------------------------------
- cout << "************************************************************\n";
- cout << "** **\n";
- cout << " "<< (NELEM >>6)<<" OBJECTS UINT64_T [64]\n";
- cout << "** **\n";
- cout << "************************************************************\n";
- Test_size<int_array<64> >(NELEM >> 6);
- return 0;
- }
- template <class IA>
- void Test_size ( uint64_t N)
- {
- cout<<"\n";
- cout<<"[ 1 ] std::sort [ 2 ] pdqsort [ 3 ] std::stable_sort \n";
- cout<<"[ 4 ] spinsort [ 5 ] flat_stable_sort [ 6 ] spreadsort\n\n";
- cout << " | [ 1 ] | [ 2 ] | [ 3 ] |";
- cout << " [ 4 ] | [ 5 ] | [ 6 ] |\n";
- //cout << " | | | |";
- //cout << " | | |\n";
- cout << " | H L | H L | H L |";
- cout << " H L | H L | H L |\n";
- cout << "--------------------+-----------+-----------+-----------+";
- cout << "-----------+-----------+-----------+\n";
- std::string empty_line = " | | |"
- " | | | |\n";
- cout<<"random |";
- Generator_random<IA>(N);
- cout<<empty_line;
- cout<<"sorted |";
- Generator_sorted<IA>(N);
- cout<<"sorted + 0.1% end |";
- Generator_sorted_end<IA>(N, N / 1000);
- cout<<"sorted + 1% end |";
- Generator_sorted_end<IA>(N, N / 100);
- cout<<"sorted + 10% end |";
- Generator_sorted_end<IA>(N, N / 10);
- cout<<empty_line;
- cout<<"sorted + 0.1% mid |";
- Generator_sorted_middle<IA>(N, N / 1000);
- cout<<"sorted + 1% mid |";
- Generator_sorted_middle<IA>(N, N / 100);
- cout<<"sorted + 10% mid |";
- Generator_sorted_middle<IA>(N, N / 10);
- cout<<empty_line;
- cout<<"reverse sorted |";
- Generator_reverse_sorted<IA>(N);
- cout<<"rv sorted + 0.1% end|";
- Generator_reverse_sorted_end<IA>(N, N / 1000);
- cout<<"rv sorted + 1% end|";
- Generator_reverse_sorted_end<IA>(N, N / 100);
- cout<<"rv sorted + 10% end|";
- Generator_reverse_sorted_end<IA>(N, N / 10);
- cout<<empty_line;
- cout<<"rv sorted + 0.1% mid|";
- Generator_reverse_sorted_middle<IA>(N, N / 1000);
- cout<<"rv sorted + 1% mid|";
- Generator_reverse_sorted_middle<IA>(N, N / 100);
- cout<<"rv sorted + 10% mid|";
- Generator_reverse_sorted_middle<IA>(N, N / 10);
- cout<< "--------------------+-----------+-----------+-----------+";
- cout << "-----------+-----------+-----------+\n";
- cout<<endl<<endl<<endl;
- }
- void Print_vectors ( std::vector<double> & V1, std::vector<double> & V2)
- {
- assert ( V1.size() == V2.size());
- std::cout<<std::setprecision(2)<<std::fixed;
- for ( uint32_t i =0 ; i < V1.size() ; ++i)
- { std::cout<<std::right<<std::setw(5)<<V1[i]<<" ";
- std::cout<<std::right<<std::setw(5)<<V2[i]<<"|";
- };
- std::cout<<std::endl;
- }
- template <class IA>
- void Generator_random(uint64_t N)
- {
- bsc::uint64_file_generator gen("input.bin");
- vector<IA> A;
- A.reserve(N);
- std::vector<double> V1, V2 ;
- gen.reset();
- A.clear();
- for (uint32_t i = 0; i < N; i++) A.emplace_back(IA::generate(gen));
- Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
- Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
- Print_vectors ( V1, V2 ) ;
- };
- template <class IA>
- void Generator_sorted(uint64_t N)
- {
- bsc::uint64_file_generator gen("input.bin");
- vector<IA> A;
- A.reserve(N);
- std::vector<double> V1, V2 ;
- gen.reset();
- A.clear();
- for (uint32_t i = 0; i < N; i++) A.emplace_back(IA::generate(gen));
- std::sort( A.begin() , A.end(),H_comp<IA>() );
- Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
- std::sort( A.begin() , A.end(),L_comp<IA>() );
- Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
- Print_vectors ( V1, V2 ) ;
- };
- template <class IA>
- void Generator_sorted_end(uint64_t N, size_t n_last )
- {
- bsc::uint64_file_generator gen("input.bin");
- vector<IA> A;
- A.reserve(N);
- std::vector<double> V1, V2 ;
- gen.reset();
- A.clear();
- for (uint32_t i = 0; i < (N + n_last); i++)
- A.emplace_back(IA::generate(gen));
- std::sort ( A.begin() , A.begin() + N ,H_comp<IA>());
- Test(A, H_rightshift<IA>(), H_comp<IA>(),V1);
- std::sort ( A.begin() , A.begin() + N ,L_comp<IA>());
- Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
- Print_vectors ( V1, V2 ) ;
- };
- template <class IA>
- void Generator_sorted_middle(uint64_t N, size_t n_last )
- {
- bsc::uint64_file_generator gen("input.bin");
- std::vector<double> V1, V2 ;
- vector<IA> A;
- A.reserve(N + n_last);
- { A.clear() ;
- gen.reset();
- vector<IA> B, C;
- C.reserve(N + n_last);
- B.reserve ( n_last);
- for (uint32_t i = 0; i < (N + n_last); i++)
- C.emplace_back(IA::generate(gen));
- for ( size_t i = N ; i < C.size() ; ++i)
- B.push_back ( std::move ( C[i]));
- C.resize ( N);
- std::sort ( C.begin() , C.end() ,H_comp<IA>());
- size_t step = N /n_last ;
- size_t pos = 0 ;
- for ( size_t i =0 ; i < B.size() ; ++i)
- { A.push_back ( B[i]);
- for ( size_t k = 0 ; k < step ; ++k )
- A.push_back ( C[pos++] );
- };
- while ( pos < C.size() )
- A.push_back ( C[pos++]);
- };
- Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
- { A.clear() ;
- gen.reset();
- vector<IA> B,C;
- C.reserve(N + n_last);
- B.reserve ( n_last);
- for (uint32_t i = 0; i < (N + n_last); i++)
- C.emplace_back(IA::generate(gen));
- for ( size_t i = N ; i < C.size() ; ++i)
- B.push_back ( std::move ( C[i]));
- C.resize ( N);
- std::sort ( C.begin() , C.end() ,L_comp<IA>());
- size_t step = N /n_last ;
- size_t pos = 0 ;
- for ( size_t i =0 ; i < B.size() ; ++i)
- { A.push_back ( B[i]);
- for ( size_t k = 0 ; k < step ; ++k )
- A.push_back ( C[pos++] );
- };
- while ( pos < C.size() )
- A.push_back ( C[pos++]);
- };
- Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
- Print_vectors ( V1, V2 ) ;
- };
- template <class IA>
- void Generator_reverse_sorted(uint64_t N)
- {
- bsc::uint64_file_generator gen("input.bin");
- vector<IA> A;
- A.reserve(N);
- std::vector<double> V1, V2 ;
- gen.reset();
- A.clear();
- for (uint32_t i = 0; i < N; i++) A.emplace_back(IA::generate(gen));
- std::sort( A.begin() , A.end(),H_comp<IA>() );
- for ( size_t i = 0; i < (A.size() >>1) ; ++i)
- std::swap ( A[i], A[A.size() - i -1 ]);
- Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
- std::sort( A.begin() , A.end(),L_comp<IA>() );
- for ( size_t i = 0; i < (A.size() >>1) ; ++i)
- std::swap ( A[i], A[A.size() - i -1 ]);
- Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
- Print_vectors ( V1, V2 ) ;
- };
- template <class IA>
- void Generator_reverse_sorted_end(uint64_t N, size_t n_last )
- {
- bsc::uint64_file_generator gen("input.bin");
- vector<IA> A;
- A.reserve(N);
- std::vector<double> V1, V2 ;
- gen.reset();
- A.clear();
- for (uint32_t i = 0; i < (N + n_last); i++)
- A.emplace_back(IA::generate(gen));
- std::sort ( A.begin() , A.begin() + N ,H_comp<IA>());
- for ( size_t i =0 ; i < (N>>1); ++i)
- std::swap ( A[i], A[N-1-i]);
- Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
- std::sort ( A.begin() , A.begin() + N ,L_comp<IA>());
- for ( size_t i =0 ; i < (N>>1); ++i)
- std::swap ( A[i], A[N-1-i]);
- Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
- Print_vectors ( V1, V2 ) ;
- };
- template <class IA>
- void Generator_reverse_sorted_middle(uint64_t N, size_t n_last )
- {
- bsc::uint64_file_generator gen("input.bin");
- std::vector<double> V1, V2 ;
- vector<IA> A;
- A.reserve(N + n_last);
- { A.clear() ;
- gen.reset();
- vector<IA> B,C;
- C.reserve(N + n_last);
- B.reserve ( n_last);
- for (uint32_t i = 0; i < (N + n_last); i++)
- C.emplace_back(IA::generate(gen));
- for ( size_t i = N ; i < C.size() ; ++i)
- B.push_back ( std::move ( C[i]));
- C.resize ( N);
- std::sort ( C.begin() , C.end() ,H_comp<IA>());
- for ( size_t i =0 ; i < (N>>1); ++i)
- std::swap ( C[i], C[N-1-i]);
- size_t step = N /n_last ;
- size_t pos = 0 ;
- for ( size_t i =0 ; i < B.size() ; ++i)
- { A.push_back ( B[i]);
- for ( size_t k = 0 ; k < step ; ++k )
- A.push_back ( C[pos++ ] );
- };
- while ( pos < C.size() )
- A.push_back ( C[pos++]);
- };
- Test(A, H_rightshift<IA>(), H_comp<IA>(), V1);
- { A.clear() ;
- gen.reset();
- vector<IA> B,C;
- C.reserve(N + n_last);
- B.reserve ( n_last);
- for (uint32_t i = 0; i < (N + n_last); i++)
- C.emplace_back(IA::generate(gen));
- for ( size_t i = N ; i < C.size() ; ++i)
- B.push_back ( std::move ( C[i]));
- C.resize ( N);
- std::sort ( C.begin() , C.end() ,L_comp<IA>());
- for ( size_t i =0 ; i < (N>>1); ++i)
- std::swap ( C[i], C[N-1-i]);
- size_t step = N /n_last ;
- size_t pos = 0 ;
- for ( size_t i =0 ; i < B.size() ; ++i)
- { A.push_back ( B[i]);
- for ( size_t k = 0 ; k < step ; ++k )
- A.push_back ( C[pos++ ] );
- };
- while ( pos < C.size() )
- A.push_back ( C[pos++]);
- };
- Test(A, L_rightshift<IA>(), L_comp<IA>(), V2);
- Print_vectors ( V1, V2 ) ;
- };
- template<class IA, class rightshift, class compare>
- int Test (std::vector<IA> &B, rightshift shift, compare comp,std::vector<double> &V)
- { //---------------------------- begin --------------------------------
- double duration;
- time_point start, finish;
- std::vector<IA> A (B);
- V.clear() ;
- //--------------------------------------------------------------------
- A = B;
- start = now ();
- std::sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- pdqsort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- std::stable_sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- spinsort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- flat_stable_sort (A.begin (), A.end (), comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- A = B;
- start = now ();
- boost::sort::spreadsort::integer_sort (A.begin (), A.end (), shift, comp);
- finish = now ();
- duration = subtract_time (finish, start);
- V.push_back (duration);
- return 0;
- };
|