566 lines
18 KiB
C++
566 lines
18 KiB
C++
//----------------------------------------------------------------------------
|
|
/// @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 bsc = boost::sort::common;
|
|
namespace bsp = boost::sort;
|
|
|
|
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;
|
|
|
|
|
|
|
|
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 P A R A L L E L **\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<<"[ 1 ] block_indirect_sort [ 2 ] sample_sort\n";
|
|
cout<<"[ 3 ] parallel_stable_sort\n\n";
|
|
|
|
cout << " | [ 1 ] | [ 2 ] | [ 3 ] |\n";
|
|
cout << " | H L | H L | H L |\n";
|
|
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<< "--------------------+-----------+-----------+-----------+\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 ();
|
|
bsp::block_indirect_sort (A.begin (), A.end (), comp);
|
|
finish = now ();
|
|
duration = subtract_time (finish, start);
|
|
V.push_back (duration);
|
|
std::vector<IA> sorted(A);
|
|
|
|
A = B;
|
|
start = now ();
|
|
bsp::sample_sort (A.begin (), A.end (), comp);
|
|
finish = now ();
|
|
duration = subtract_time (finish, start);
|
|
V.push_back (duration);
|
|
|
|
A = B;
|
|
start = now ();
|
|
bsp::parallel_stable_sort (A.begin (), A.end (), comp);
|
|
finish = now ();
|
|
duration = subtract_time (finish, start);
|
|
V.push_back (duration);
|
|
//cout << duration << " secs\n";
|
|
/*
|
|
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 ();
|
|
timsort (A.begin (), A.end (), comp);
|
|
finish = now ();
|
|
duration = subtract_time (finish, start);
|
|
V.push_back (duration);
|
|
|
|
|
|
A = B;
|
|
//cout << "Boost spreadsort : ";
|
|
int sorted_count = 0;
|
|
for (unsigned i = 0; i + 1 < A.size(); ++i)
|
|
{
|
|
if (comp(A[i], A[i+1]))
|
|
{
|
|
sorted_count++;
|
|
};
|
|
};
|
|
start = now ();
|
|
boost::sort::spreadsort::integer_sort (A.begin (), A.end (), shift, comp);
|
|
finish = now ();
|
|
duration = subtract_time (finish, start);
|
|
int identical = 0;
|
|
for (unsigned i = 0; i + 1 < A.size(); ++i)
|
|
{
|
|
if (A[i].counter() != sorted[i].counter())
|
|
{
|
|
cout << "incorrect!" << std::endl;
|
|
}
|
|
if (!comp(A[i], A[i+1]) && !comp(A[i+1], A[i]))
|
|
{
|
|
identical++;
|
|
};
|
|
};
|
|
// cout << "identical: " << identical << " pre-sorted: " << sorted_count << std::endl;
|
|
V.push_back (duration);
|
|
//cout << duration << " secs\n";
|
|
*/
|
|
return 0;
|
|
};
|