diff options
Diffstat (limited to 'src/boost/libs/sort')
66 files changed, 8076 insertions, 0 deletions
diff --git a/src/boost/libs/sort/Jamfile.v2 b/src/boost/libs/sort/Jamfile.v2 new file mode 100644 index 000000000..da650b388 --- /dev/null +++ b/src/boost/libs/sort/Jamfile.v2 @@ -0,0 +1,42 @@ +# Copyright Steven Ross 2009. +# +# 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/sort for library home page. + +local properties = ; +if --tune in [ modules.peek : ARGV ] +{ + properties = <location>. <variant>release ; +} + +project spreadsort : source-location example : requirements <include>../.. <include>../../.. $(properties) ; + +exe spreadsort : sample.cpp ; +exe alreadysorted : alreadysorted.cpp ; +exe mostlysorted : mostlysorted.cpp ; +exe rightshift : rightshiftsample.cpp ; +exe reverseintsort : reverseintsample.cpp ; +exe int64 : int64.cpp ; +exe floatsort : floatsample.cpp ; +exe shiftfloatsort : shiftfloatsample.cpp ; +exe floatfunctorsort : floatfunctorsample.cpp ; +exe double : double.cpp ; +exe stringsort : stringsample.cpp ; +exe wstringsort : wstringsample.cpp ; +exe reversestringsort : reversestringsample.cpp ; +exe charstringsort : charstringsample.cpp ; +exe stringfunctorsort : stringfunctorsample.cpp ; +exe reversestringfunctorsort : reversestringfunctorsample.cpp ; +exe keyplusdata : keyplusdatasample.cpp ; +exe randomgen : randomgen.cpp ; +exe boostrandomgen : boostrandomgen.cpp ; +exe alrbreaker : alrbreaker.cpp ; +exe binaryalrbreaker : binaryalrbreaker.cpp ; +exe caseinsensitive : caseinsensitive.cpp ; +exe generalizedstruct : generalizedstruct.cpp ; + +# benchmarks need to be built with linkflags="-lboost_system -lboost_thread" +#exe parallelint : parallelint.cpp boost_system ; +#exe parallelstring : parallelstring.cpp ;
\ No newline at end of file diff --git a/src/boost/libs/sort/README.md b/src/boost/libs/sort/README.md new file mode 100644 index 000000000..c7588c29f --- /dev/null +++ b/src/boost/libs/sort/README.md @@ -0,0 +1,79 @@ +<h1>BOOST SORT</H1> + +<H2>Introduction</h2> + +The goal of the Boost Sort Library is provide to the users, the most modern and fast sorting algorithms. + +This library provides stable and not stable sorting algorithms, in single thread and parallel versions. + +These algorithms do not use any other library or utility. The parallel algorithms need a C++11 compliant compiler. + +<h2>Single Thread Algorithms</h2> + + + | | | | | + Algorithm |Stable | Additional memory |Best, average, and worst case | Comparison method | + ------------------|-------|----------------------------|-------------------------------|---------------------| + spreadsort | no | key_length | N, N sqrt(LogN), | Hybrid radix sort | + | | | min(N logN, N key_length) | | + pdqsort | no | Log N | N, N LogN, N LogN | Comparison operator | + spinsort | yes | N / 2 | N, N LogN, N LogN | Comparison operator | + flat_stable_sort | yes |size of the data / 256 + 8K | N, N LogN, N LogN | Comparison operator | + | | | | | + + +- **spreadsort** is a novel hybrid radix sort algorithm, extremely fast, designed and developed by Steven Ross. + +- **pdqsort** is a improvement of the quick sort algorithm, designed and developed by Orson Peters. + +- **spinsort** is a stable sort, fast with random and with near sorted data, designed and developed by Francisco Tapia. + +- **flat_stable_sort** stable sort with a small additional memory (around 1% of the size of the data), provide the 80% - 90% of the speed of spinsort, being fast with random and with near sorted data, designed and developed by Francisco Tapia. + + +<h2>Parallel Algorithms</h2> + + + | | | | + Algorithm |Stable | Additional memory |Best, average, and worst case | + ----------------------|-------|------------------------|------------------------------| + block_indirect_sort | no |block_size * num_threads| N, N LogN , N LogN | + sample_sort | yes | N | N, N LogN , N LogN | + parallel_stable_sort | yes | N / 2 | N, N LogN , N LogN | + | | | | + + +- **Sample_sort** is a implementation of the [Samplesort algorithm](https://en.wikipedia.org/wiki/Samplesort) done by Francisco Tapia. + +- **Parallel_stable_sort** is based on the samplesort algorithm, but using a half of the memory used by sample_sort, conceived and implemented by Francisco Tapia. + +- **Block_indirect_sort** is a novel parallel sort algorithm, very fast, with low additional memory consumption, conceived and implemented by Francisco Tapia. + +The **block_size** is an internal parameter of the algorithm, which in order to achieve the +highest speed, changes according to the size of the objects to sort according to the next table. The strings use a block_size of 128. + + + | | | | | | | | + object size (bytes) | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 - | + --------------------------------|--------|---------|---------|---------|---------|---------|----------| + block_size (number of elements) | 4096 | 2048 | 1024 | 768 | 512 | 256 | 128 | + | | | | | | | | + + +<h2>Installation </h2> +- This library is **include only**. +- Don't need to link with any static or dynamic library. Only need a C++11 compiler +- Only need to include the file boost/sort/sort.hpp + + +<h2>Author and Copyright</h2> +This library is integrated in the [Boost Library](https://boost.org) . + + +Copyright 2017 + +- [Steven Ross *(spreadsort@gmail.com)* ](mail:spreadsort@gmail.com) +- [Francisco Tapia *(fjtapia@gmail.com)* ](mail:fjtapia@gmail.com) +- [Orson Peters *(orsonpeters@gmail.com)* ](mail:orsonpeters@gmail.com) + +Distributed under the [Boost Software License, Version 1.0. ](http://www.boost.org/LICENSE_1_0.txt) (See http://www.boost.org/LICENSE_1_0.txt) diff --git a/src/boost/libs/sort/benchmark/parallel/README.txt b/src/boost/libs/sort/benchmark/parallel/README.txt new file mode 100644 index 000000000..69e3a3a84 --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/README.txt @@ -0,0 +1,15 @@ +README.TXT +============== +If you want to do manually or with different compiler. + +file_generator is a program which generte a file with random information + for to be used in the benchmark. + After compiled the invocation is + ./file_generator input.bin 1250000000 + +Now we have the data file and only need to compile and run the programs. + benchmark_objects.cpp + benchmark_strings.cpp + benchmark_numbers.cpp + +They show a detailed information on the screen in a compact mode diff --git a/src/boost/libs/sort/benchmark/parallel/benchmark_numbers.cpp b/src/boost/libs/sort/benchmark/parallel/benchmark_numbers.cpp new file mode 100644 index 000000000..edf139b7e --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/benchmark_numbers.cpp @@ -0,0 +1,301 @@ +//---------------------------------------------------------------------------- +/// @file benchmark_numbers.cpp +/// @brief Benchmark of several sort methods with integer objects +/// +/// @author Copyright (c) 2017 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 + +using namespace std; +namespace bsort = boost::sort; +namespace bsc = boost::sort::common; + +using bsc::time_point; +using bsc::now; +using bsc::subtract_time; +using bsc::fill_vector_uint64; +using bsc::write_file_uint64; + + +void Generator_random (void); +void Generator_sorted (void); +void Generator_sorted_end (size_t n_last); +void Generator_sorted_middle (size_t n_last); +void Generator_reverse_sorted (void); +void Generator_reverse_sorted_end (size_t n_last); +void Generator_reverse_sorted_middle (size_t n_last); + +template<class IA, class compare> +int Test (std::vector<IA> &B, compare comp = compare ()); + +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 << "** I N T E G E R B E N C H M A R K **\n"; + cout << "** **\n"; + cout << "** SORT OF 100 000 000 NUMBERS OF 64 BITS **\n"; + cout << "** **\n"; + cout << "************************************************************\n"; + cout << std::endl; + + cout<<"[ 1 ] block_indirect_sort [ 2 ] sample_sort\n"; + cout<<"[ 3 ] parallel_stable_sort\n\n"; + cout<<" | | | |\n"; + cout<<" | [ 1 ]| [ 2 ]| [ 3 ]|\n"; + cout<<"--------------------+------+------+------+\n"; + std::string empty_line = + " | | | |\n"; + cout<<"random |"; + Generator_random (); + cout<<empty_line; + cout<<"sorted |"; + Generator_sorted (); + + cout<<"sorted + 0.1% end |"; + Generator_sorted_end (NELEM / 1000); + + cout<<"sorted + 1% end |"; + Generator_sorted_end (NELEM / 100); + + cout<<"sorted + 10% end |"; + Generator_sorted_end (NELEM / 10); + + cout<<empty_line; + cout<<"sorted + 0.1% mid |"; + Generator_sorted_middle (NELEM / 1000); + + cout<<"sorted + 1% mid |"; + Generator_sorted_middle (NELEM / 100); + + cout<<"sorted + 10% mid |"; + Generator_sorted_middle (NELEM / 10); + + cout<<empty_line; + cout<<"reverse sorted |"; + Generator_reverse_sorted (); + + cout<<"rv sorted + 0.1% end|"; + Generator_reverse_sorted_end (NELEM / 1000); + + cout<<"rv sorted + 1% end|"; + Generator_reverse_sorted_end (NELEM / 100); + + cout<<"rv sorted + 10% end|"; + Generator_reverse_sorted_end (NELEM / 10); + + cout<<empty_line; + cout<<"rv sorted + 0.1% mid|"; + Generator_reverse_sorted_middle (NELEM / 1000); + + cout<<"rv sorted + 1% mid|"; + Generator_reverse_sorted_middle (NELEM / 100); + + cout<<"rv sorted + 10% mid|"; + Generator_reverse_sorted_middle (NELEM / 10); + cout<<"--------------------+------+------+------+\n"; + cout<<endl<<endl ; + return 0; +} +void +Generator_random (void) +{ + vector<uint64_t> A; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + Test<uint64_t, std::less<uint64_t>> (A); +} +; +void +Generator_sorted (void) +{ + vector<uint64_t> A; + + A.reserve (NELEM); + A.clear (); + for (size_t i = 0; i < NELEM; ++i) + A.push_back (i); + Test<uint64_t, std::less<uint64_t>> (A); + +} + +void Generator_sorted_end (size_t n_last) +{ + vector<uint64_t> A; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin (), A.begin () + NELEM); + + Test<uint64_t, std::less<uint64_t>> (A); + +} +; +void Generator_sorted_middle (size_t n_last) +{ + vector<uint64_t> A, B, C; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for (size_t i = NELEM; i < A.size (); ++i) + B.push_back (std::move (A[i])); + A.resize ( NELEM); + for (size_t i = 0; i < (NELEM >> 1); ++i) + std::swap (A[i], A[NELEM - 1 - i]); + + std::sort (A.begin (), A.end ()); + size_t step = NELEM / n_last + 1; + size_t pos = 0; + + for (size_t i = 0; i < B.size (); ++i, pos += step) + { + C.push_back (B[i]); + for (size_t k = 0; k < step; ++k) + C.push_back (A[pos + k]); + }; + while (pos < A.size ()) + C.push_back (A[pos++]); + A = C; + Test<uint64_t, std::less<uint64_t>> (A); +} +; +void Generator_reverse_sorted (void) +{ + vector<uint64_t> A; + + A.reserve (NELEM); + A.clear (); + for (size_t i = NELEM; i > 0; --i) + A.push_back (i); + Test<uint64_t, std::less<uint64_t>> (A); +} +void Generator_reverse_sorted_end (size_t n_last) +{ + vector<uint64_t> A; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin (), A.begin () + NELEM); + for (size_t i = 0; i < (NELEM >> 1); ++i) + std::swap (A[i], A[NELEM - 1 - i]); + + Test<uint64_t, std::less<uint64_t>> (A); +} +void Generator_reverse_sorted_middle (size_t n_last) +{ + vector<uint64_t> A, B, C; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for (size_t i = NELEM; i < A.size (); ++i) + B.push_back (std::move (A[i])); + A.resize ( NELEM); + for (size_t i = 0; i < (NELEM >> 1); ++i) + std::swap (A[i], A[NELEM - 1 - i]); + + std::sort (A.begin (), A.end ()); + size_t step = NELEM / n_last + 1; + size_t pos = 0; + + for (size_t i = 0; i < B.size (); ++i, pos += step) + { + C.push_back (B[i]); + for (size_t k = 0; k < step; ++k) + C.push_back (A[pos + k]); + }; + while (pos < A.size ()) + C.push_back (A[pos++]); + A = C; + Test<uint64_t, std::less<uint64_t>> (A); +}; + + +template<class IA, class compare> +int Test (std::vector<IA> &B, compare comp) +{ //---------------------------- begin -------------------------------- + double duration; + time_point start, finish; + std::vector<IA> A (B); + std::vector<double> V; + + //-------------------------------------------------------------------- + A = B; + start = now (); + bsort::block_indirect_sort (A.begin (), A.end (), comp); + finish = now (); + duration = subtract_time (finish, start); + V.push_back (duration); + + A = B; + start = now (); + bsort::sample_sort (A.begin (), A.end (), comp); + finish = now (); + duration = subtract_time (finish, start); + V.push_back (duration); + + A = B; + start = now (); + bsort::parallel_stable_sort (A.begin (), A.end (), comp); + finish = now (); + duration = subtract_time (finish, start); + V.push_back (duration); + + //----------------------------------------------------------------------- + // printing the vector + //----------------------------------------------------------------------- + std::cout<<std::setprecision(2)<<std::fixed; + for ( uint32_t i =0 ; i < V.size() ; ++i) + { std::cout<<std::right<<std::setw(5)<<V[i]<<" |"; + }; + std::cout<<std::endl; + return 0; +}; + diff --git a/src/boost/libs/sort/benchmark/parallel/benchmark_objects.cpp b/src/boost/libs/sort/benchmark/parallel/benchmark_objects.cpp new file mode 100644 index 000000000..f44f76b86 --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/benchmark_objects.cpp @@ -0,0 +1,565 @@ +//---------------------------------------------------------------------------- +/// @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; +}; diff --git a/src/boost/libs/sort/benchmark/parallel/benchmark_strings.cpp b/src/boost/libs/sort/benchmark/parallel/benchmark_strings.cpp new file mode 100644 index 000000000..1f2382159 --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/benchmark_strings.cpp @@ -0,0 +1,306 @@ +//---------------------------------------------------------------------------- +/// @file benchmark_strings.cpp +/// @brief Benchmark of several sort methods with strings +/// +/// @author Copyright (c) 2017 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 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; + + +void Generator_random (void); +void Generator_sorted(void); +void Generator_sorted_end(size_t n_last); +void Generator_sorted_middle (size_t n_last); +void Generator_reverse_sorted(void); +void Generator_reverse_sorted_end(size_t n_last); +void Generator_reverse_sorted_middle(size_t n_last); + +template <class IA, class compare> +int Test(std::vector<IA> &B, compare comp = compare()); + + +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 << "** S T R I N G S B E N C H M A R K **\n"; + cout << "** **\n"; + cout << "** S O R T O F 10 000 000 S T R I N G S **\n"; + cout << "** **\n"; + cout << "************************************************************\n"; + cout << std::endl; + + cout<<"[ 1 ] block_indirect_sort [ 2 ] sample_sort\n"; + cout<<"[ 3 ] parallel_stable_sort\n\n"; + cout<<" | | | |\n"; + cout<<" | [ 1 ]| [ 2 ]| [ 3 ]|\n"; + cout<<"--------------------+------+------+------+\n"; + std::string empty_line = + " | | | |\n"; + + cout<<"random |"; + Generator_random (); + + cout<<empty_line; + cout<<"sorted |"; + Generator_sorted(); + + cout<<"sorted + 0.1% end |"; + Generator_sorted_end(NMAXSTRING / 1000); + + cout<<"sorted + 1% end |"; + Generator_sorted_end(NMAXSTRING / 100); + + cout<<"sorted + 10% end |"; + Generator_sorted_end(NMAXSTRING / 10); + + cout<<empty_line; + cout<<"sorted + 0.1% mid |"; + Generator_sorted_middle (NMAXSTRING / 1000); + + cout<<"sorted + 1% mid |"; + Generator_sorted_middle (NMAXSTRING / 100); + + cout<<"sorted + 10% mid |"; + Generator_sorted_middle (NMAXSTRING / 10 ); + + cout<<empty_line; + cout<<"reverse sorted |"; + Generator_reverse_sorted(); + + cout<<"rv sorted + 0.1% end|"; + Generator_reverse_sorted_end(NMAXSTRING / 1000); + + cout<<"rv sorted + 1% end|"; + Generator_reverse_sorted_end(NMAXSTRING / 100); + + cout<<"rv sorted + 10% end|"; + Generator_reverse_sorted_end(NMAXSTRING / 10); + + cout<<empty_line; + cout<<"rv sorted + 0.1% mid|"; + Generator_reverse_sorted_middle(NMAXSTRING / 1000); + + cout<<"rv sorted + 1% mid|"; + Generator_reverse_sorted_middle(NMAXSTRING / 100); + + cout<<"rv sorted + 10% mid|"; + Generator_reverse_sorted_middle(NMAXSTRING / 10); + + cout<< "--------------------+------+------+------+\n"; + cout<<endl<<endl ; + return 0; +} + +void Generator_random(void) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + Test<std::string, std::less<std::string>>(A); + +}; +void Generator_sorted(void) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort( A.begin() , A.end() ); + Test<std::string, std::less<std::string>>(A); +}; + +void Generator_sorted_end(size_t n_last) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING+ n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin() , A.begin() + NMAXSTRING ); + Test<std::string, std::less<std::string>>(A); +}; +void Generator_sorted_middle(size_t n_last) +{ + std::vector<std::string> A,B,C; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for ( size_t i = NMAXSTRING ; i < A.size() ; ++i) + B.push_back ( std::move ( A[i])); + A.resize ( NMAXSTRING); + std::sort (A.begin() , A.end() ); + size_t step = NMAXSTRING /n_last +1 ; + size_t pos = 0 ; + + for ( size_t i =0 ; i < B.size() ; ++i, pos += step) + { C.push_back ( B[i]); + for ( size_t k = 0 ; k < step ; ++k ) + C.push_back ( A[pos + k] ); + }; + while ( pos < A.size() ) C.push_back ( A[pos++]); + A = C ; + + Test<std::string, std::less<std::string>>(A); +}; + +void Generator_reverse_sorted(void) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort( A.begin() , A.end()); + size_t nmid = (A.size() >>1), nlast = A.size() -1 ; + for (size_t i = 0 ; i < nmid ;++i) + std::swap ( A[i], A [nlast -i]); + + Test<std::string, std::less<std::string>>(A); + +}; +void Generator_reverse_sorted_end(size_t n_last) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING+ n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin() , A.begin() + NMAXSTRING ); + for ( size_t i =0 ; i< (NMAXSTRING >>1); ++i) + std::swap ( A[i], A[NMAXSTRING - 1 - i]); + + Test<std::string, std::less<std::string>>(A); + +}; +void Generator_reverse_sorted_middle(size_t n_last) +{ + std::vector<std::string> A,B,C; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for ( size_t i = NMAXSTRING ; i < A.size() ; ++i) + B.push_back ( std::move ( A[i])); + A.resize ( NMAXSTRING); + + std::sort (A.begin() , A.end() ); + for ( size_t i =0 ; i< (NMAXSTRING >>1); ++i) + std::swap ( A[i], A[NMAXSTRING - 1 - i]); + + size_t step = NMAXSTRING /n_last +1 ; + size_t pos = 0 ; + + for ( size_t i =0 ; i < B.size() ; ++i, pos += step) + { C.push_back ( B[i]); + for ( size_t k = 0 ; k < step ; ++k ) + C.push_back ( A[pos + k] ); + }; + while ( pos < A.size() ) + C.push_back ( A[pos++]); + A = C ; + + Test<std::string, std::less<std::string>>(A); +}; + + +template<class IA, class compare> +int Test (std::vector<IA> &B, compare comp) +{ //---------------------------- begin -------------------------------- + double duration; + time_point start, finish; + std::vector<IA> A (B); + std::vector<double> V; + + //-------------------------------------------------------------------- + A = B; + start = now (); + bsp::block_indirect_sort (A.begin (), A.end (), comp); + finish = now (); + duration = subtract_time (finish, start); + V.push_back (duration); + + 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); + + //----------------------------------------------------------------------- + // printing the vector + //----------------------------------------------------------------------- + std::cout<<std::setprecision(2)<<std::fixed; + for ( uint32_t i =0 ; i < V.size() ; ++i) + { std::cout<<std::right<<std::setw(5)<<V[i]<<" |"; + }; + std::cout<<std::endl; + return 0; +}; + diff --git a/src/boost/libs/sort/benchmark/parallel/file_generator.cpp b/src/boost/libs/sort/benchmark/parallel/file_generator.cpp new file mode 100644 index 000000000..7ceaff6d6 --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/file_generator.cpp @@ -0,0 +1,56 @@ +//---------------------------------------------------------------------------- +/// @file file_generator.cpp +/// @brief This program generte a file with random information, for to be used +/// in the benchmark programs +/// +/// @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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <boost/sort/common/file_vector.hpp> + +#include <iostream> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <vector> + +using std::cout; +using std::endl; +namespace bsc = boost::sort::common; + +void print_banner(); + +int main(int argc, char *argv[]) +{ //---------------------------- begin-------------------------------------- + std::string name; + size_t number; + + if (argc < 3) { + cout << "This program generate a file filled with random numbers\n"; + cout << "of 64 bits\n"; + cout << "The invocation format is :\n"; + cout << " file_generator file_name number_elements\n\n"; + return 0; + }; + name = argv[1]; + number = atoi(argv[2]); + if (number == 0) { + cout << "error, the number can't be zero\n"; + return 0; + }; + + if (bsc::generate_file(name, number) != 0) + std::cout << "Error in the file creation\n"; + return 0; +}; +void print_banner() +{ //---------------------------- begin ------------------------------------- + cout << " The format of this program is :\n"; + cout << " file_generator number_elements\n\n"; + cout << " The elements are 64 bits random numbers\n"; +}; diff --git a/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_numbers.sh b/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_numbers.sh new file mode 100755 index 000000000..dc45d74c4 --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_numbers.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K N U M B E R S ==" +echo "== ==" +echo "== C L A N G C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +clang++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +clang++ ./benchmark_numbers.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -pthread -s -lpthread -o benchmark_numbers + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_numbers +date +rm input.bin +rm file_generator +rm benchmark_numbers +echo "." + +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_objects.sh b/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_objects.sh new file mode 100755 index 000000000..98d613c1a --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_objects.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K O B J E C T S ==" +echo "== ==" +echo "== C L A N G C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." + +clang++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +clang++ ./benchmark_objects.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -pthread -s -lpthread -o benchmark_objects +echo "." +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 60 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_objects +date + +rm input.bin +rm file_generator +rm benchmark_objects +echo "." +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_strings.sh b/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_strings.sh new file mode 100755 index 000000000..108f4b4fc --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/runCLANG_benchmark_strings.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K S T R I N G S ==" +echo "== ==" +echo "== G C C C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +g++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +g++ ./benchmark_strings.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -pthread -s -lpthread -o benchmark_strings + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_strings +date + +rm input.bin +rm file_generator +rm benchmark_strings +echo "." +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_numbers.sh b/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_numbers.sh new file mode 100755 index 000000000..6ab2ea608 --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_numbers.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K N U M B E R S ==" +echo "== ==" +echo "== G C C C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +g++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +g++ ./benchmark_numbers.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -pthread -s -lpthread -o benchmark_numbers + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_numbers +date +rm input.bin +rm file_generator +rm benchmark_numbers +echo "." + +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_objects.sh b/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_objects.sh new file mode 100755 index 000000000..f74d3cd02 --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_objects.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K O B J E C T S ==" +echo "== ==" +echo "== G C C C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." + +g++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +g++ ./benchmark_objects.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -pthread -s -lpthread -o benchmark_objects +echo "." +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 60 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_objects +date + +rm input.bin +rm file_generator +rm benchmark_objects +echo "." +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_strings.sh b/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_strings.sh new file mode 100755 index 000000000..108f4b4fc --- /dev/null +++ b/src/boost/libs/sort/benchmark/parallel/runGCC_benchmark_strings.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K S T R I N G S ==" +echo "== ==" +echo "== G C C C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +g++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +g++ ./benchmark_strings.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -pthread -s -lpthread -o benchmark_strings + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_strings +date + +rm input.bin +rm file_generator +rm benchmark_strings +echo "." +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/single/README.txt b/src/boost/libs/sort/benchmark/single/README.txt new file mode 100644 index 000000000..69e3a3a84 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/README.txt @@ -0,0 +1,15 @@ +README.TXT +============== +If you want to do manually or with different compiler. + +file_generator is a program which generte a file with random information + for to be used in the benchmark. + After compiled the invocation is + ./file_generator input.bin 1250000000 + +Now we have the data file and only need to compile and run the programs. + benchmark_objects.cpp + benchmark_strings.cpp + benchmark_numbers.cpp + +They show a detailed information on the screen in a compact mode diff --git a/src/boost/libs/sort/benchmark/single/benchmark_numbers.cpp b/src/boost/libs/sort/benchmark/single/benchmark_numbers.cpp new file mode 100644 index 000000000..5da2a362b --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/benchmark_numbers.cpp @@ -0,0 +1,328 @@ +//---------------------------------------------------------------------------- +/// @file benchmark_numbers.cpp +/// @brief Benchmark of several sort methods with integer objects +/// +/// @author Copyright (c) 2017 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 + +using namespace std; +namespace bsort = boost::sort; +namespace bsc = boost::sort::common; + +using bsc::time_point; +using bsc::now; +using bsc::subtract_time; +using bsc::fill_vector_uint64; +using bsc::write_file_uint64; + +using bsort::spinsort; +using bsort::flat_stable_sort; +using bsort::spreadsort::spreadsort; +using bsort::pdqsort; + +void Generator_random (void); +void Generator_sorted (void); +void Generator_sorted_end (size_t n_last); +void Generator_sorted_middle (size_t n_last); +void Generator_reverse_sorted (void); +void Generator_reverse_sorted_end (size_t n_last); +void Generator_reverse_sorted_middle (size_t n_last); + +template<class IA, class compare> +int Test (std::vector<IA> &B, compare comp = compare ()); + +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 << "** S I N G L E T H R E A D **\n"; + cout << "** I N T E G E R B E N C H M A R K **\n"; + cout << "** **\n"; + cout << "** SORT OF 100 000 000 NUMBERS OF 64 BITS **\n"; + cout << "** **\n"; + cout << "************************************************************\n"; + cout << std::endl; + + cout<<"[ 1 ] std::sort [ 2 ] pdqsort [ 3 ] std::stable_sort \n"; + cout<<"[ 4 ] spinsort [ 5 ] flat_stable_sort [ 6 ] spreadsort\n\n"; + cout<<" | | | | | | |\n"; + cout<<" | [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]|\n"; + cout<<"--------------------+------+------+------+------+------+------+\n"; + std::string empty_line = + " | | | | | | |\n"; + cout<<"random |"; + Generator_random (); + cout<<empty_line; + cout<<"sorted |"; + Generator_sorted (); + + cout<<"sorted + 0.1% end |"; + Generator_sorted_end (NELEM / 1000); + + cout<<"sorted + 1% end |"; + Generator_sorted_end (NELEM / 100); + + cout<<"sorted + 10% end |"; + Generator_sorted_end (NELEM / 10); + + cout<<empty_line; + cout<<"sorted + 0.1% mid |"; + Generator_sorted_middle (NELEM / 1000); + + cout<<"sorted + 1% mid |"; + Generator_sorted_middle (NELEM / 100); + + cout<<"sorted + 10% mid |"; + Generator_sorted_middle (NELEM / 10); + + cout<<empty_line; + cout<<"reverse sorted |"; + Generator_reverse_sorted (); + + cout<<"rv sorted + 0.1% end|"; + Generator_reverse_sorted_end (NELEM / 1000); + + cout<<"rv sorted + 1% end|"; + Generator_reverse_sorted_end (NELEM / 100); + + cout<<"rv sorted + 10% end|"; + Generator_reverse_sorted_end (NELEM / 10); + + cout<<empty_line; + cout<<"rv sorted + 0.1% mid|"; + Generator_reverse_sorted_middle (NELEM / 1000); + + cout<<"rv sorted + 1% mid|"; + Generator_reverse_sorted_middle (NELEM / 100); + + cout<<"rv sorted + 10% mid|"; + Generator_reverse_sorted_middle (NELEM / 10); + cout<<"--------------------+------+------+------+------+------+------+\n"; + cout<<endl<<endl ; + return 0; +} +void +Generator_random (void) +{ + vector<uint64_t> A; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + Test<uint64_t, std::less<uint64_t>> (A); +} +; +void +Generator_sorted (void) +{ + vector<uint64_t> A; + + A.reserve (NELEM); + A.clear (); + for (size_t i = 0; i < NELEM; ++i) + A.push_back (i); + Test<uint64_t, std::less<uint64_t>> (A); + +} + +void Generator_sorted_end (size_t n_last) +{ + vector<uint64_t> A; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin (), A.begin () + NELEM); + + Test<uint64_t, std::less<uint64_t>> (A); + +} +; +void Generator_sorted_middle (size_t n_last) +{ + vector<uint64_t> A, B, C; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for (size_t i = NELEM; i < A.size (); ++i) + B.push_back (std::move (A[i])); + A.resize ( NELEM); + for (size_t i = 0; i < (NELEM >> 1); ++i) + std::swap (A[i], A[NELEM - 1 - i]); + + std::sort (A.begin (), A.end ()); + size_t step = NELEM / n_last + 1; + size_t pos = 0; + + for (size_t i = 0; i < B.size (); ++i, pos += step) + { + C.push_back (B[i]); + for (size_t k = 0; k < step; ++k) + C.push_back (A[pos + k]); + }; + while (pos < A.size ()) + C.push_back (A[pos++]); + A = C; + Test<uint64_t, std::less<uint64_t>> (A); +} +; +void Generator_reverse_sorted (void) +{ + vector<uint64_t> A; + + A.reserve (NELEM); + A.clear (); + for (size_t i = NELEM; i > 0; --i) + A.push_back (i); + Test<uint64_t, std::less<uint64_t>> (A); +} +void Generator_reverse_sorted_end (size_t n_last) +{ + vector<uint64_t> A; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin (), A.begin () + NELEM); + for (size_t i = 0; i < (NELEM >> 1); ++i) + std::swap (A[i], A[NELEM - 1 - i]); + + Test<uint64_t, std::less<uint64_t>> (A); +} +void Generator_reverse_sorted_middle (size_t n_last) +{ + vector<uint64_t> A, B, C; + A.reserve (NELEM); + A.clear (); + if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for (size_t i = NELEM; i < A.size (); ++i) + B.push_back (std::move (A[i])); + A.resize ( NELEM); + for (size_t i = 0; i < (NELEM >> 1); ++i) + std::swap (A[i], A[NELEM - 1 - i]); + + std::sort (A.begin (), A.end ()); + size_t step = NELEM / n_last + 1; + size_t pos = 0; + + for (size_t i = 0; i < B.size (); ++i, pos += step) + { + C.push_back (B[i]); + for (size_t k = 0; k < step; ++k) + C.push_back (A[pos + k]); + }; + while (pos < A.size ()) + C.push_back (A[pos++]); + A = C; + Test<uint64_t, std::less<uint64_t>> (A); +}; + + +template<class IA, class compare> +int Test (std::vector<IA> &B, compare comp) +{ //---------------------------- begin -------------------------------- + double duration; + time_point start, finish; + std::vector<IA> A (B); + std::vector<double> V; + + //-------------------------------------------------------------------- + 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 (); + spreadsort (A.begin (), A.end ()); + finish = now (); + duration = subtract_time (finish, start); + V.push_back (duration); + + //----------------------------------------------------------------------- + // printing the vector + //----------------------------------------------------------------------- + std::cout<<std::setprecision(2)<<std::fixed; + for ( uint32_t i =0 ; i < V.size() ; ++i) + { std::cout<<std::right<<std::setw(5)<<V[i]<<" |"; + }; + std::cout<<std::endl; + return 0; +}; + diff --git a/src/boost/libs/sort/benchmark/single/benchmark_objects.cpp b/src/boost/libs/sort/benchmark/single/benchmark_objects.cpp new file mode 100644 index 000000000..105cdc40b --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/benchmark_objects.cpp @@ -0,0 +1,556 @@ +//---------------------------------------------------------------------------- +/// @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; +}; diff --git a/src/boost/libs/sort/benchmark/single/benchmark_strings.cpp b/src/boost/libs/sort/benchmark/single/benchmark_strings.cpp new file mode 100644 index 000000000..df63f8f42 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/benchmark_strings.cpp @@ -0,0 +1,354 @@ +//---------------------------------------------------------------------------- +/// @file benchmark_strings.cpp +/// @brief Benchmark of several sort methods with strings +/// +/// @author Copyright (c) 2017 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 NMAXSTRING 10000000 + +using namespace std; +namespace bsort = boost::sort; +namespace bsc = boost::sort::common; + +using bsc::time_point; +using bsc::now; +using bsc::subtract_time; +using bsc::fill_vector_uint64; +using bsc::write_file_uint64; + +using bsort::spinsort; +using bsort::flat_stable_sort; +using bsort::spreadsort::spreadsort; +using bsort::pdqsort; + +void Generator_random (void); +void Generator_sorted(void); +void Generator_sorted_end(size_t n_last); +void Generator_sorted_middle (size_t n_last); +void Generator_reverse_sorted(void); +void Generator_reverse_sorted_end(size_t n_last); +void Generator_reverse_sorted_middle(size_t n_last); + +template <class IA, class compare> +int Test(std::vector<IA> &B, compare comp = compare()); + + +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 << "** S I N G L E T H R E A D **\n"; + cout << "** S T R I N G S B E N C H M A R K **\n"; + cout << "** **\n"; + cout << "** S O R T O F 10 000 000 S T R I N G S **\n"; + cout << "** **\n"; + cout << "************************************************************\n"; + cout << std::endl; + + cout<<"[ 1 ] std::sort [ 2 ] pdqsort [ 3 ] std::stable_sort \n"; + cout<<"[ 4 ] spinsort [ 5 ] flat_stable_sort [ 6 ] spreadsort\n\n"; + cout<<" | | | | | | |\n"; + cout<<" | [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]|\n"; + cout<<"--------------------+------+------+------+------+------+------+\n"; + std::string empty_line = + " | | | | | | |\n"; + + cout<<"random |"; + Generator_random (); + + cout<<empty_line; + cout<<"sorted |"; + Generator_sorted(); + + cout<<"sorted + 0.1% end |"; + Generator_sorted_end(NMAXSTRING / 1000); + + cout<<"sorted + 1% end |"; + Generator_sorted_end(NMAXSTRING / 100); + + cout<<"sorted + 10% end |"; + Generator_sorted_end(NMAXSTRING / 10); + + cout<<empty_line; + cout<<"sorted + 0.1% mid |"; + Generator_sorted_middle (NMAXSTRING / 1000); + + cout<<"sorted + 1% mid |"; + Generator_sorted_middle (NMAXSTRING / 100); + + cout<<"sorted + 10% mid |"; + Generator_sorted_middle (NMAXSTRING / 10 ); + + cout<<empty_line; + cout<<"reverse sorted |"; + Generator_reverse_sorted(); + + cout<<"rv sorted + 0.1% end|"; + Generator_reverse_sorted_end(NMAXSTRING / 1000); + + cout<<"rv sorted + 1% end|"; + Generator_reverse_sorted_end(NMAXSTRING / 100); + + cout<<"rv sorted + 10% end|"; + Generator_reverse_sorted_end(NMAXSTRING / 10); + + cout<<empty_line; + cout<<"rv sorted + 0.1% mid|"; + Generator_reverse_sorted_middle(NMAXSTRING / 1000); + + cout<<"rv sorted + 1% mid|"; + Generator_reverse_sorted_middle(NMAXSTRING / 100); + + cout<<"rv sorted + 10% mid|"; + Generator_reverse_sorted_middle(NMAXSTRING / 10); + + cout<<"--------------------+------+------+------+------+------+------+\n"; + cout<<endl<<endl ; + return 0; +} + +void Generator_random(void) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + Test<std::string, std::less<std::string>>(A); + +}; +void Generator_sorted(void) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort( A.begin() , A.end() ); + Test<std::string, std::less<std::string>>(A); +}; + +void Generator_sorted_end(size_t n_last) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING+ n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin() , A.begin() + NMAXSTRING ); + Test<std::string, std::less<std::string>>(A); +}; +void Generator_sorted_middle(size_t n_last) +{ + std::vector<std::string> A,B,C; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for ( size_t i = NMAXSTRING ; i < A.size() ; ++i) + B.push_back ( std::move ( A[i])); + A.resize ( NMAXSTRING); + std::sort (A.begin() , A.end() ); + size_t step = NMAXSTRING /n_last +1 ; + size_t pos = 0 ; + + for ( size_t i =0 ; i < B.size() ; ++i, pos += step) + { C.push_back ( B[i]); + for ( size_t k = 0 ; k < step ; ++k ) + C.push_back ( A[pos + k] ); + }; + while ( pos < A.size() ) C.push_back ( A[pos++]); + A = C ; + + Test<std::string, std::less<std::string>>(A); +}; + +void Generator_reverse_sorted(void) +{ + + std::vector<std::string> A; + A.reserve(NMAXSTRING); + { + std::vector<std::string> B; + B.reserve(NMAXSTRING); + if (bsc::fill_vector_string("input.bin", B, NMAXSTRING) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort(B.begin(), B.end()); + A.clear(); + for (size_t i = 0; i < NMAXSTRING; ++i) + A.push_back(B[NMAXSTRING - 1 - i]); + }; + Test<std::string, std::less<std::string>>(A); + +/* + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort( A.begin() , A.end()); + size_t nmid = (A.size() >>1), nlast = A.size() -1 ; + for (size_t i = 0 ; i < nmid ;++i) + std::swap ( A[i], A [nlast -i]); + + Test<std::string, std::less<std::string>>(A); +*/ +}; +void Generator_reverse_sorted_end(size_t n_last) +{ + std::vector<std::string> A; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING+ n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + std::sort (A.begin() , A.begin() + NMAXSTRING ); + for ( size_t i =0 ; i< (NMAXSTRING >>1); ++i) + std::swap ( A[i], A[NMAXSTRING - 1 - i]); + + Test<std::string, std::less<std::string>>(A); + +}; +void Generator_reverse_sorted_middle(size_t n_last) +{ + std::vector<std::string> A,B,C; + A.reserve(NMAXSTRING); + A.clear(); + if (bsc::fill_vector_string("input.bin", A, NMAXSTRING + n_last) != 0) + { + std::cout << "Error in the input file\n"; + return; + }; + for ( size_t i = NMAXSTRING ; i < A.size() ; ++i) + B.push_back ( std::move ( A[i])); + A.resize ( NMAXSTRING); + + std::sort (A.begin() , A.end() ); + for ( size_t i =0 ; i< (NMAXSTRING >>1); ++i) + std::swap ( A[i], A[NMAXSTRING - 1 - i]); + + size_t step = NMAXSTRING /n_last +1 ; + size_t pos = 0 ; + + for ( size_t i =0 ; i < B.size() ; ++i, pos += step) + { C.push_back ( B[i]); + for ( size_t k = 0 ; k < step ; ++k ) + C.push_back ( A[pos + k] ); + }; + while ( pos < A.size() ) + C.push_back ( A[pos++]); + A = C ; + + Test<std::string, std::less<std::string>>(A); +}; + + +template<class IA, class compare> +int Test (std::vector<IA> &B, compare comp) +{ //---------------------------- begin ----------------------------- + double duration; + time_point start, finish; + std::vector<IA> A (B); + std::vector<double> V; + + + 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 (); + spreadsort (A.begin (), A.end ()); + finish = now (); + duration = subtract_time (finish, start); + V.push_back (duration); + + //----------------------------------------------------------------------- + // printing the vector + //----------------------------------------------------------------------- + std::cout<<std::setprecision(2)<<std::fixed; + for ( uint32_t i =0 ; i < V.size() ; ++i) + { std::cout<<std::right<<std::setw(5)<<V[i]<<" |"; + }; + std::cout<<std::endl; + return 0; +}; + diff --git a/src/boost/libs/sort/benchmark/single/file_generator.cpp b/src/boost/libs/sort/benchmark/single/file_generator.cpp new file mode 100644 index 000000000..7ceaff6d6 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/file_generator.cpp @@ -0,0 +1,56 @@ +//---------------------------------------------------------------------------- +/// @file file_generator.cpp +/// @brief This program generte a file with random information, for to be used +/// in the benchmark programs +/// +/// @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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <boost/sort/common/file_vector.hpp> + +#include <iostream> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <vector> + +using std::cout; +using std::endl; +namespace bsc = boost::sort::common; + +void print_banner(); + +int main(int argc, char *argv[]) +{ //---------------------------- begin-------------------------------------- + std::string name; + size_t number; + + if (argc < 3) { + cout << "This program generate a file filled with random numbers\n"; + cout << "of 64 bits\n"; + cout << "The invocation format is :\n"; + cout << " file_generator file_name number_elements\n\n"; + return 0; + }; + name = argv[1]; + number = atoi(argv[2]); + if (number == 0) { + cout << "error, the number can't be zero\n"; + return 0; + }; + + if (bsc::generate_file(name, number) != 0) + std::cout << "Error in the file creation\n"; + return 0; +}; +void print_banner() +{ //---------------------------- begin ------------------------------------- + cout << " The format of this program is :\n"; + cout << " file_generator number_elements\n\n"; + cout << " The elements are 64 bits random numbers\n"; +}; diff --git a/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_numbers.sh b/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_numbers.sh new file mode 100755 index 000000000..1bab3baa3 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_numbers.sh @@ -0,0 +1,27 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K N U M B E R S ==" +echo "== ==" +echo "== C L A N G C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +clang++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +clang++ ./benchmark_numbers.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o benchmark_numbers + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_numbers +echo "." +date +rm input.bin +rm file_generator +rm benchmark_numbers +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_objects.sh b/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_objects.sh new file mode 100755 index 000000000..db0bda8f6 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_objects.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K O B J E C T S ==" +echo "== ==" +echo "== C L A N G C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." + +clang++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +clang++ ./benchmark_objects.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o benchmark_objects +echo "." +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 45 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_objects +date +echo "." +rm input.bin +rm file_generator +rm benchmark_objects + +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_strings.sh b/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_strings.sh new file mode 100755 index 000000000..2be5ccaf3 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/runCLANG_benchmark_strings.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K S T R I N G S ==" +echo "== ==" +echo "== C L A N G C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +clang++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +clang++ ./benchmark_strings.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o benchmark_strings + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_strings +date + +rm input.bin +rm file_generator +rm benchmark_strings +echo "." +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/single/runGCC_benchmark_numbers.sh b/src/boost/libs/sort/benchmark/single/runGCC_benchmark_numbers.sh new file mode 100755 index 000000000..741d7a143 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/runGCC_benchmark_numbers.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K N U M B E R S ==" +echo "== ==" +echo "== G C C C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +g++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +g++ ./benchmark_numbers.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o benchmark_numbers + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_numbers +date +rm input.bin +rm file_generator +rm benchmark_numbers +echo "." + +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/single/runGCC_benchmark_objects.sh b/src/boost/libs/sort/benchmark/single/runGCC_benchmark_objects.sh new file mode 100755 index 000000000..ef0ddb1a2 --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/runGCC_benchmark_objects.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K O B J E C T S ==" +echo "== ==" +echo "== G C C C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." + +g++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +g++ ./benchmark_objects.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o benchmark_objects +echo "." +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 45 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_objects +date + +rm input.bin +rm file_generator +rm benchmark_objects +echo "." +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/benchmark/single/runGCC_benchmark_strings.sh b/src/boost/libs/sort/benchmark/single/runGCC_benchmark_strings.sh new file mode 100755 index 000000000..9d029fedd --- /dev/null +++ b/src/boost/libs/sort/benchmark/single/runGCC_benchmark_strings.sh @@ -0,0 +1,28 @@ +clear +echo "==================================================================" +echo "== B E N C H M A R K S T R I N G S ==" +echo "== ==" +echo "== G C C C O M P I L E R ==" +echo "==================================================================" +echo "." +echo "C O M P I L I N G . . . . . . . . . . ." +echo "." +g++ ./file_generator.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o file_generator + +g++ ./benchmark_strings.cpp -std=c++11 -march=native -w -fexceptions -O3 -I../../include -s -o benchmark_strings + +echo "R U N N I N G . . . . . . . . . . ." +echo "( The time needed is around 10 minutes depending of your machine )" +./file_generator input.bin 125000000 +echo "." +date +./benchmark_strings +date + +rm input.bin +rm file_generator +rm benchmark_strings +echo "." +echo "." +echo "E N D" +echo "." diff --git a/src/boost/libs/sort/example/alrbreaker.cpp b/src/boost/libs/sort/example/alrbreaker.cpp new file mode 100644 index 000000000..b93fe89ac --- /dev/null +++ b/src/boost/libs/sort/example/alrbreaker.cpp @@ -0,0 +1,78 @@ +// a sorting example that uses the worst-case for conventional MSD radix sorts. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; +using namespace std; + +#define DATA_TYPE boost::uint64_t + +#define ALR_THRESHOLD 3 + +const unsigned max_count = ALR_THRESHOLD - 1; +const unsigned bit_shift = detail::rough_log_2_size(max_count) - + detail::int_log_mean_bin_size; +const unsigned radix_threshold = detail::rough_log_2_size(max_count) + 1; +//Increase this size if too fast to test accurately +const unsigned top_splits = 12; + +const DATA_TYPE typed_one = 1; + +void +fill_vector(vector<DATA_TYPE> & input, const DATA_TYPE base_value, + unsigned remaining_bits) +{ + if (remaining_bits >= radix_threshold) { + input.push_back((base_value << remaining_bits) + + ((typed_one << remaining_bits) - 1)); + fill_vector(input, base_value << bit_shift, remaining_bits - bit_shift); + } + else { + for (unsigned u = 0; u < max_count; ++u) + input.push_back((base_value << remaining_bits) + + (rand() % (1 << remaining_bits))); + } +} + +//Tests spreadsort on the worst-case distribution for standard MSD radix sorts. +int main(int, const char **) { + vector<DATA_TYPE> input; + for (int ii = (1 << top_splits) - 1; ii >= 0; --ii) + fill_vector(input, ii, (sizeof(DATA_TYPE) * 8) - top_splits); + + //Run both std::sort and spreadsort + for (unsigned u = 0; u < 2; ++u) { + vector<DATA_TYPE> array = input; + clock_t start, end; + double elapsed; + start = clock(); + if (u) + std::sort(array.begin(), array.end()); + else + boost::sort::spreadsort::spreadsort(array.begin(), array.end()); + end = clock(); + elapsed = static_cast<double>(end - start); + if (u) + printf("std::sort elapsed time %f\n", elapsed / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", elapsed / CLOCKS_PER_SEC); + array.clear(); + } + return 0; +} diff --git a/src/boost/libs/sort/example/alreadysorted.cpp b/src/boost/libs/sort/example/alreadysorted.cpp new file mode 100644 index 000000000..8f56d0825 --- /dev/null +++ b/src/boost/libs/sort/example/alreadysorted.cpp @@ -0,0 +1,91 @@ +// spreadsort fully sorted data example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE int + + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + //Sorts the data once, then times sorting of already-sorted data + loopCount += 1; + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) // EOF or failure stops the reading + input.read(reinterpret_cast<char *>(&(array[v++])), uSize ); + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else { + printf("call\n"); + //integer_sort(&(array[0]), &(array[0]) + uCount); + integer_sort(array.begin(), array.end()); + } + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + if (u) + total += elapsed; + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/binaryalrbreaker.cpp b/src/boost/libs/sort/example/binaryalrbreaker.cpp new file mode 100644 index 000000000..c5a163f79 --- /dev/null +++ b/src/boost/libs/sort/example/binaryalrbreaker.cpp @@ -0,0 +1,108 @@ +// a sorting example that uses the worst-case distribution for spreadsort. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; +using namespace std; + +#define DATA_TYPE boost::uint64_t + +#define ALR_THRESHOLD 3 + +const unsigned max_count = ALR_THRESHOLD - 1; +const unsigned bit_shift = detail::rough_log_2_size(max_count) - + detail::int_log_mean_bin_size; +const unsigned radix_threshold = detail::rough_log_2_size(max_count) + 1; + +const DATA_TYPE typed_one = 1; + +void +fill_vector(vector<DATA_TYPE> & input, const DATA_TYPE base_value, + unsigned remaining_bits, const vector<unsigned> & indices, + int index) +{ + if (index < 0) { + for (unsigned u = 0; u < max_count; ++u) + input.push_back((base_value << remaining_bits) + + (rand() % (1 << remaining_bits))); + } + else { + unsigned shift = indices[index]; + fill_vector(input, (base_value << shift) + ((1 << shift) - 1), + remaining_bits - shift, indices, index - 1); + fill_vector(input, base_value << shift, remaining_bits - shift, indices, + index - 1); + } +} + +//Generates a random index from 0 up to but not including count. +unsigned +get_index(unsigned count) +{ + unsigned result = unsigned((rand() % (1 << 16))*uint64_t(count)/(1 << 16)); + if (result >= count) + return count - 1; + return result; +} + +//Tests std::sort vs boost::sort::spreadsort on boost::sort's worst distribution. +int main(int, const char **) { + unsigned total_length = sizeof(DATA_TYPE) * 8; + double std_sort_time = 0; + double spreadsort_time = 0; + for (int repetition = 0; repetition < 10; ++repetition) { + vector<DATA_TYPE> input; + vector<unsigned> offsets; + unsigned bit_length = total_length - radix_threshold; + unsigned bit_offset = bit_shift; + for (; bit_length >= ++bit_offset; bit_length -= bit_offset) + offsets.push_back(bit_offset); + for (int ii = (1 << bit_length) - 1; ii >= 0; --ii) + fill_vector(input, ii, total_length - bit_length, + offsets, offsets.size() - 1); + + //Randomize the inputs slightly so they aren't in reverse-sorted order, for + //which std::sort is very fast. + for (unsigned u = 0; u < input.size() / 10; ++u) + std::swap(input[get_index(input.size())], input[get_index(input.size())]); + + //Run both std::sort and boost::sort::spreadsort. + for (unsigned u = 0; u < 2; ++u) { + vector<DATA_TYPE> array = input; + clock_t start, end; + double elapsed; + start = clock(); + if (u) + std::sort(array.begin(), array.end()); + else + boost::sort::spreadsort::spreadsort(array.begin(), array.end()); + end = clock(); + elapsed = static_cast<double>(end - start); + if (u) + std_sort_time += elapsed / CLOCKS_PER_SEC; + else + spreadsort_time += elapsed / CLOCKS_PER_SEC; + array.clear(); + } + } + + printf("std::sort elapsed time %f\n", std_sort_time); + printf("spreadsort elapsed time %f\n", spreadsort_time); + return 0; +} diff --git a/src/boost/libs/sort/example/boostrandomgen.cpp b/src/boost/libs/sort/example/boostrandomgen.cpp new file mode 100644 index 000000000..74f9b526f --- /dev/null +++ b/src/boost/libs/sort/example/boostrandomgen.cpp @@ -0,0 +1,69 @@ +// a random number generator supporting different distributions. +// +// Copyright Steven Ross 2009. +// +// 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/sort for library home page. + +#include <stdio.h> +#include "stdlib.h" +#include <fstream> +#include <iostream> +#include <vector> +#include <string> +#include <boost/random.hpp> + +using std::string; +using namespace boost; + +int main(int argc, const char ** argv) { + //Always seed with the same value, to get the same results + srand(1); + //defaults + int mod_shift = 32; + unsigned count = 1000000; + //Reading in user arguments + if (argc > 2) + count = atoi(argv[2]); + if (argc > 1) + mod_shift = atoi(argv[1]) - 1; + std::ofstream ofile; + ofile.open("input.txt", std::ios_base::out | std::ios_base::binary | + std::ios_base::trunc); + if (ofile.bad()) { + printf("could not open input.txt for writing!\n"); + return 1; + } + int min_int = (std::numeric_limits<int>::min)(); + int max_int = (std::numeric_limits<int>::max)(); + if (mod_shift < 31 && mod_shift >= 0) { + max_int %= 1 << mod_shift; + if (-max_int > min_int) + min_int = -max_int; + } + std::vector<int> result; + result.resize(count); + mt19937 rng; + if (argc > 3 && (string(argv[3]) == "-normal")) { + boost::normal_distribution<> everything(0, max_int/4); + variate_generator<mt19937&,normal_distribution<> > gen(rng, everything); + generate(result.begin(), result.end(), gen); + } + else if (argc > 3 && (string(argv[3]) == "-lognormal")) { + lognormal_distribution<> everything(max_int/2, max_int/4); + variate_generator<mt19937&,lognormal_distribution<> > gen(rng, everything); + generate(result.begin(), result.end(), gen); + } + else { + uniform_int<> everything(min_int, max_int); + variate_generator<mt19937&,uniform_int<> > gen(rng, everything); + generate(result.begin(), result.end(), gen); + } + ofile.write(reinterpret_cast<char *>(&(result[0])), result.size() * + sizeof(int)); + ofile.close(); + return 0; +} diff --git a/src/boost/libs/sort/example/caseinsensitive.cpp b/src/boost/libs/sort/example/caseinsensitive.cpp new file mode 100644 index 000000000..26d1c4f09 --- /dev/null +++ b/src/boost/libs/sort/example/caseinsensitive.cpp @@ -0,0 +1,101 @@ +// Example of sorting a struct using a case-insensitive string key. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/algorithm/string.hpp> +#include <boost/sort/spreadsort/string_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +struct DATA_TYPE { + string a; +}; + +struct lessthan { + inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const { + return boost::algorithm::ilexicographical_compare(x.a, y.a); + } +}; + +struct bracket { + inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const { + return toupper(x.a[offset]); + } +}; + +struct getsize { + inline size_t operator()(const DATA_TYPE &x) const{ return x.a.size(); } +}; + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (indata.bad()) { + printf("input.txt could not be opened\n"); + return 1; + } + DATA_TYPE inval; + indata >> inval.a; + while (!indata.eof() ) { + array.push_back(inval); + indata >> inval.a; + } + + indata.close(); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + std::sort(array.begin(), array.end(), lessthan()); + else + string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan()); + end = clock(); + elapsed = static_cast<double>(end - start); + if (stdSort) + outfile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + outfile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (outfile.good()) { + for (unsigned u = 0; u < array.size(); ++u) + outfile << array[u].a << "\n"; + outfile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/charstringsample.cpp b/src/boost/libs/sort/example/charstringsample.cpp new file mode 100644 index 000000000..4f4487d8a --- /dev/null +++ b/src/boost/libs/sort/example/charstringsample.cpp @@ -0,0 +1,101 @@ +// Example of sorting structs with a string key and indexing functors. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/string_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +struct DATA_TYPE { + string a; + inline bool operator<(const DATA_TYPE &y) const { return a < y.a;} +}; + + +struct bracket { + inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const { + return x.a[offset]; + } +}; + +struct getsize { + inline size_t operator()(const DATA_TYPE &x) const{ return x.a.size(); } +}; + + + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (indata.bad()) { + printf("input.txt could not be opened\n"); + return 1; + } + DATA_TYPE inval; + indata >> inval.a; + while (!indata.eof() ) { + array.push_back(inval); + indata >> inval.a; + } + + indata.close(); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) { + std::sort(array.begin(), array.end()); + } else { +//[bracket_1 + string_sort(array.begin(), array.end(), bracket(), getsize()); +//] [/bracket_1] + } + end = clock(); + elapsed = static_cast<double>(end - start); + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned u = 0; u < array.size(); ++u) + ofile << array[u].a << "\n"; + ofile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/double.cpp b/src/boost/libs/sort/example/double.cpp new file mode 100644 index 000000000..eff1295e7 --- /dev/null +++ b/src/boost/libs/sort/example/double.cpp @@ -0,0 +1,105 @@ +// spreadsort double sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE double +#define CAST_TYPE boost::int64_t + +//Pass in an argument to test std::sort +//Note that this converts NaNs and -0.0 to 0.0, so that sorting results are +//identical every time +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Using this to support compilers that don't support 64-bit constants + CAST_TYPE exponent_mask = 0x7ff00000; + exponent_mask <<= 32; + CAST_TYPE top_exponent_bit = 0x40000000; + top_exponent_bit <<= 32; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) { + input.read(reinterpret_cast<char *>(&(array[v])), uSize ); + //Checking for denormalized numbers + if (!(float_mem_cast<DATA_TYPE, CAST_TYPE>(array[v]) & exponent_mask)) { + //Make the top exponent bit high + CAST_TYPE temp = top_exponent_bit | + float_mem_cast<DATA_TYPE, CAST_TYPE>(array[v]); + memcpy(&(array[v]), &temp, sizeof(DATA_TYPE)); + } + //Testcase doesn't sort NaNs; they just cause confusion + if (!(array[v] < 0.0) && !(0.0 < array[v])) + array[v] = 0.0; + ++v; + } + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else + //float_sort(&(array[0]), &(array[0]) + uCount); + float_sort(array.begin(), array.end()); + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/floatfunctorsample.cpp b/src/boost/libs/sort/example/floatfunctorsample.cpp new file mode 100644 index 000000000..e930fee48 --- /dev/null +++ b/src/boost/libs/sort/example/floatfunctorsample.cpp @@ -0,0 +1,138 @@ +// spreadsort float functor sorting example. +// +// Copyright Steven Ross 2009. +// +// 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/sort for library home page. + +// Caution: this file contains Quickbook markup as well as code +// and comments, don't change any of the special comment markups! + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> + +using namespace boost::sort::spreadsort; + +//[float_functor_types +#define CAST_TYPE int +#define KEY_TYPE float +//] [/float_functor_types] + + +//[float_functor_datatypes +struct DATA_TYPE { + KEY_TYPE key; + std::string data; +}; +//] [/float_functor_datatypes] + + +//[float_functor_rightshift +// Casting to an integer before bitshifting +struct rightshift { + int operator()(const DATA_TYPE &x, const unsigned offset) const { + return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset; + } +}; +//] [/float_functor_rightshift] + +//[float_functor_lessthan +struct lessthan { + bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const { + return x.key < y.key; + } +}; +//] [/float_functor_lessthan] + +// Pass in an argument to test std::sort +// Note that this converts NaNs and -0.0 to 0.0, so that sorting results are +// identical every time +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) { + input.read(reinterpret_cast<char *>(&(array[v].key)), + sizeof(array[v].key)); + //Checking for denormalized numbers; float_sort looks too fast on them. + if (!(float_mem_cast<KEY_TYPE, CAST_TYPE>(array[v].key) & 0x7f800000)) { + //Make the top exponent bit high + CAST_TYPE temp = 0x40000000 | + float_mem_cast<KEY_TYPE, CAST_TYPE>(array[v].key); + memcpy(&(array[v].key), &temp, sizeof(KEY_TYPE)); + } + //Testcase doesn't sort NaNs; they just cause confusion + if (!(array[v].key < 0.0) && !(0.0 < array[v].key)) + array[v].key = 0.0; + //Adding the data, in this case a string + std::stringstream intstr; + intstr << array[v].key; + array[v].data = intstr.str(); + ++v; + } + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + std::sort(array.begin(), array.end(), lessthan()); + else + float_sort(array.begin(), array.end(), rightshift(), lessthan()); + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v].key)), + sizeof(array[v].key)); + ofile << array[v].data; + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/floatsample.cpp b/src/boost/libs/sort/example/floatsample.cpp new file mode 100644 index 000000000..1de3f650b --- /dev/null +++ b/src/boost/libs/sort/example/floatsample.cpp @@ -0,0 +1,100 @@ +// spreadsort float sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE float +#define CAST_TYPE int + +//Pass in an argument to test std::sort +//Note that this converts NaNs and -0.0 to 0.0, so that sorting results are +//identical every time +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) { + input.read(reinterpret_cast<char *>(&(array[v])), uSize ); + //Checking for denormalized numbers + if (!(float_mem_cast<float, int>(array[v]) & 0x7f800000)) { + //Make the top exponent bit high + CAST_TYPE temp = 0x40000000 | float_mem_cast<float, int>(array[v]); + memcpy(&(array[v]), &temp, sizeof(DATA_TYPE)); + } + //Testcase doesn't sort NaNs; they just cause confusion + if (!(array[v] < 0.0) && !(0.0 < array[v])) + array[v] = 0.0; + ++v; + } + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else + //boost::sort::spreadsort::spreadsort(&(array[0]), &(array[0]) + uCount); + boost::sort::spreadsort::spreadsort(array.begin(), array.end()); + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + input.close(); + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/generalizedstruct.cpp b/src/boost/libs/sort/example/generalizedstruct.cpp new file mode 100644 index 000000000..eed82c9e9 --- /dev/null +++ b/src/boost/libs/sort/example/generalizedstruct.cpp @@ -0,0 +1,192 @@ +// This example shows how to sort structs using complex multiple part keys using +// string_sort. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/string_sort.hpp> +#include <boost/sort/spreadsort/float_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +//[generalized_functors +struct DATA_TYPE { + time_t birth; + float net_worth; + string first_name; + string last_name; +}; + +static const int birth_size = sizeof(time_t); +static const int first_name_offset = birth_size + sizeof(float); +static const boost::uint64_t base_mask = 0xff; + +struct lessthan { + inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const { + if (x.birth != y.birth) { + return x.birth < y.birth; + } + if (x.net_worth != y.net_worth) { + return x.net_worth < y.net_worth; + } + if (x.first_name != y.first_name) { + return x.first_name < y.first_name; + } + return x.last_name < y.last_name; + } +}; + +struct bracket { + inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const { + // Sort date as a signed int, returning the appropriate byte. + if (offset < birth_size) { + const int bit_shift = 8 * (birth_size - offset - 1); + unsigned char result = (x.birth & (base_mask << bit_shift)) >> bit_shift; + // Handling the sign bit. Unnecessary if the data is always positive. + if (offset == 0) { + return result ^ 128; + } + + return result; + } + + // Sort a signed float. This requires reversing the order of negatives + // because of the way floats are represented in bits. + if (offset < first_name_offset) { + const int bit_shift = 8 * (first_name_offset - offset - 1); + unsigned key = float_mem_cast<float, unsigned>(x.net_worth); + unsigned char result = (key & (base_mask << bit_shift)) >> bit_shift; + // Handling the sign. + if (x.net_worth < 0) { + return 255 - result; + } + // Increasing positives so they are higher than negatives. + if (offset == birth_size) { + return 128 + result; + } + + return result; + } + + // Sort a string that is before the end. This approach supports embedded + // nulls. If embedded nulls are not required, then just delete the "* 2" + // and the inside of the following if just becomes: + // return x.first_name[offset - first_name_offset]; + const unsigned first_name_end_offset = + first_name_offset + x.first_name.size() * 2; + if (offset < first_name_end_offset) { + int char_offset = offset - first_name_offset; + // This signals that the string continues. + if (!(char_offset & 1)) { + return 1; + } + return x.first_name[char_offset >> 1]; + } + + // This signals that the string has ended, so that shorter strings come + // before longer ones. + if (offset == first_name_end_offset) { + return 0; + } + + // The final string needs no special consideration. + return x.last_name[offset - first_name_end_offset - 1]; + } +}; + +struct getsize { + inline size_t operator()(const DATA_TYPE &x) const { + return first_name_offset + x.first_name.size() * 2 + 1 + + x.last_name.size(); + } +}; +//] [/generalized_functors] + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (indata.bad()) { + printf("input.txt could not be opened\n"); + return 1; + } + + // Read in the data. + DATA_TYPE inval; + while (!indata.eof() ) { + indata >> inval.first_name; + indata >> inval.last_name; + indata.read(reinterpret_cast<char *>(&(inval.birth)), birth_size); + indata.read(reinterpret_cast<char *>(&(inval.net_worth)), sizeof(float)); + // Handling nan. + if (inval.net_worth != inval.net_worth) { + inval.net_worth = 0; + } + if (indata.eof()) + break; + array.push_back(inval); + } + indata.close(); + + // Sort the data. + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) { + std::sort(array.begin(), array.end(), lessthan()); + } else { +//[generalized_functors_call + string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan()); +//] [/generalized_functors_call] + } + end = clock(); + elapsed = static_cast<double>(end - start); + if (stdSort) { + outfile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + } else { + outfile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + } + if (outfile.good()) { + for (unsigned u = 0; u < array.size(); ++u) + outfile << array[u].birth << " " << array[u].net_worth << " " + << array[u].first_name << " " << array[u].last_name << "\n"; + outfile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) { + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + } else { + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + } + return 0; +} diff --git a/src/boost/libs/sort/example/int64.cpp b/src/boost/libs/sort/example/int64.cpp new file mode 100644 index 000000000..e01ce5c70 --- /dev/null +++ b/src/boost/libs/sort/example/int64.cpp @@ -0,0 +1,93 @@ +// spreadsort 64-bit integer sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +//[int64bit_1 +#define DATA_TYPE boost::int64_t +//] [/int64bit_1] + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) + input.read(reinterpret_cast<char *>(&(array[v++])), uSize ); + if (v < uCount) + array.resize(v); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else + //boost::sort::spreadsort::spreadsort(&(array[0]), &(array[0]) + uCount); +//[int64bit_2 + boost::sort::spreadsort::spreadsort(array.begin(), array.end()); +//] [/int64bit_2] + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + input.close(); + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/keyplusdatasample.cpp b/src/boost/libs/sort/example/keyplusdatasample.cpp new file mode 100644 index 000000000..bb6d30c6f --- /dev/null +++ b/src/boost/libs/sort/example/keyplusdatasample.cpp @@ -0,0 +1,107 @@ +// spreadsort key and data sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +struct DATA_TYPE { + int key; + std::string data; + }; +//functor example +struct lessthan { + inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const { + return x.key < y.key; + } +}; + +struct rightshift { + inline int operator()(const DATA_TYPE &x, const unsigned offset) { + return x.key >> offset; + } +}; + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + size_t uSize = sizeof(int); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + double total = 0.0; + std::vector<DATA_TYPE> array; + array.reserve(length/uSize); + unsigned uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + unsigned v = 0; + while (input.good() && v++ < uCount) { // EOF or failure stops the reading + DATA_TYPE element; + input.read(reinterpret_cast<char *>(&(element.key)), sizeof(element.key)); + std::stringstream intstr; + intstr << element.key; + element.data = intstr.str(); + array.push_back(element); + } + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + std::sort(array.begin(), array.end(), lessthan()); + else + integer_sort(array.begin(), array.end(), rightshift(), lessthan()); + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v].key)), + sizeof(array[v].key)); + ofile << array[v].data; + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + input.close(); + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/mostlysorted.cpp b/src/boost/libs/sort/example/mostlysorted.cpp new file mode 100644 index 000000000..b609cbdba --- /dev/null +++ b/src/boost/libs/sort/example/mostlysorted.cpp @@ -0,0 +1,100 @@ +// spreadsort on a mostly sorted array example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE int + +unsigned +get_index(unsigned count) +{ + unsigned result = unsigned((rand() % (1 << 16))*uint64_t(count)/(1 << 16)); + if (result >= count || result < 0) + result = count - 1; + return result; +} + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + srand(1); + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + //Sorts the data once, then times sorting of already-sorted data + loopCount += 1; + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) // EOF or failure stops the reading + input.read(reinterpret_cast<char *>(&(array[v++])), uSize ); + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + for (unsigned v = 0; v < uCount/10; ++v) + std::swap(array[get_index(uCount)], array[get_index(uCount)]); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else + //integer_sort(&(array[0]), &(array[0]) + uCount); + integer_sort(array.begin(), array.end()); + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + if (u) + total += elapsed; + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/parallelint.cpp b/src/boost/libs/sort/example/parallelint.cpp new file mode 100644 index 000000000..e7806617c --- /dev/null +++ b/src/boost/libs/sort/example/parallelint.cpp @@ -0,0 +1,115 @@ +// Benchmark for integer sorting speed across parallel threads. +// +// Copyright Steven Ross 2014 +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <boost/thread.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE int + +bool is_sorted(const std::vector<DATA_TYPE> &array) { + for (unsigned u = 0; u + 1 < array.size(); ++u) { + if (array[u] > array[u + 1]) { + return false; + } + } + return true; +} + +void sort_loop(const std::vector<DATA_TYPE> &base_array, bool stdSort, + unsigned loopCount) { + std::vector<DATA_TYPE> array(base_array); + for (unsigned u = 0; u < loopCount; ++u) { + for (unsigned v = 0; v < base_array.size(); ++v) { + array[v] = base_array[v]; + } + if (stdSort) + std::sort(array.begin(), array.end()); + else + boost::sort::spreadsort::spreadsort(array.begin(), array.end()); + if (!is_sorted(array)) { + fprintf(stderr, "sort failed!\n"); + exit(1); + } + } +} + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + int threadCount = -1; + unsigned loopCount = 0; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else if(threadCount < 0) + threadCount = atoi(argv[u]); + else + loopCount = atoi(argv[u]); + } + if (!loopCount) { + loopCount = 1; + } + printf("threads: %d loops: %d\n", threadCount, loopCount); + + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + std::vector<DATA_TYPE> base_array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + base_array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) + input.read(reinterpret_cast<char *>(&(base_array[v++])), uSize ); + input.close(); + if (v < uCount) + base_array.resize(v); + //Run multiple loops, if requested + clock_t start, end; + double elapsed; + std::vector<boost::thread *> workers; + start = clock(); + if (threadCount == 0) { + sort_loop(base_array, stdSort, loopCount); + } else { + for (int i = 0; i < threadCount; ++i) { + workers.push_back(new boost::thread(sort_loop, base_array, stdSort, + loopCount)); + } + for (int i = 0; i < threadCount; ++i) { + workers[i]->join(); + delete workers[i]; + } + } + end = clock(); + elapsed = static_cast<double>(end - start) ; + + if (stdSort) + printf("std::sort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount); + else + printf("spreadsort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount); + return 0; +} diff --git a/src/boost/libs/sort/example/parallelstring.cpp b/src/boost/libs/sort/example/parallelstring.cpp new file mode 100644 index 000000000..fb86604aa --- /dev/null +++ b/src/boost/libs/sort/example/parallelstring.cpp @@ -0,0 +1,143 @@ +// Benchmark for integer sorting speed across parallel threads. +// +// Copyright Steven Ross 2014 +// +// 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/sort for library home page. + +#include <boost/random/mersenne_twister.hpp> +#include <boost/random/uniform_int_distribution.hpp> +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <boost/thread.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +#define DATA_TYPE string + +static bool is_sorted(const std::vector<DATA_TYPE> &array) { + for (unsigned u = 0; u + 1 < array.size(); ++u) { + if (array[u] > array[u + 1]) { + return false; + } + } + return true; +} + +static void sort_core(std::vector<DATA_TYPE> &array, bool stdSort, + unsigned loopCount) { + if (stdSort) + std::sort(array.begin(), array.end()); + else + boost::sort::spreadsort::spreadsort(array.begin(), array.end()); + if (!is_sorted(array)) { + fprintf(stderr, "sort failed!\n"); + exit(1); + } +} + +static void sort_loop(const std::vector<DATA_TYPE> &base_array, bool stdSort, + unsigned loopCount) { + std::vector<DATA_TYPE> array(base_array); + for (unsigned u = 0; u < loopCount; ++u) { + for (unsigned v = 0; v < base_array.size(); ++v) { + array[v] = base_array[v]; + } + sort_core(array, stdSort, loopCount); + } +} + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + int constant_to_random_ratio = -1; + int threadCount = -1; + unsigned loopCount = 0; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else if(threadCount < 0) + threadCount = atoi(argv[u]); + else if (!loopCount) + loopCount = atoi(argv[u]); + else + constant_to_random_ratio = atoi(argv[u]); + } + if (!loopCount) { + loopCount = 1; + } + printf("threads: %d loops: %d\n", threadCount, loopCount); + + std::vector<DATA_TYPE> base_array; + if (constant_to_random_ratio >= 0) { + //Test for random data with gaps of identical data. + random::mt19937 generator; + random::uniform_int_distribution<int> distribution(0,255); + const int constant_to_random_count = 1000000; + const int string_length = 1000; + for (int i = 0; i < constant_to_random_count; ++i) { + DATA_TYPE temp(string_length, 'x'); // fill with default character. + for (int j = constant_to_random_ratio; j < string_length;) { + int val = distribution(generator); + temp[j] = val; + j += (val * constant_to_random_ratio)/128 + 1; + } + base_array.push_back(temp); + } + } else { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (indata.bad()) { + printf("input.txt could not be opened\n"); + return 1; + } + DATA_TYPE inval; + while (!indata.eof() ) { + indata >> inval; + base_array.push_back(inval); + } + } + + // Sort the input + clock_t start, end; + double elapsed; + std::vector<boost::thread *> workers; + start = clock(); + if (threadCount == 0) { + if (loopCount > 1) { + sort_loop(base_array, stdSort, loopCount); + } else { + sort_core(base_array, stdSort, loopCount); + } + threadCount = 1; + } else { + for (int i = 0; i < threadCount; ++i) { + workers.push_back(new boost::thread(sort_loop, base_array, stdSort, + loopCount)); + } + for (int i = 0; i < threadCount; ++i) { + workers[i]->join(); + delete workers[i]; + } + } + end = clock(); + elapsed = static_cast<double>(end - start) ; + + printf("for %lu strings\n", base_array.size()); + if (stdSort) + printf("std::sort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount); + else + printf("spreadsort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount); + return 0; +} diff --git a/src/boost/libs/sort/example/randomgen.cpp b/src/boost/libs/sort/example/randomgen.cpp new file mode 100644 index 000000000..aaa1f8505 --- /dev/null +++ b/src/boost/libs/sort/example/randomgen.cpp @@ -0,0 +1,69 @@ +// flexible random number generator providing multiple distributions. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/random/mersenne_twister.hpp> +#include <boost/random/uniform_int_distribution.hpp> +#include <stdio.h> +#include "stdlib.h" +#include <fstream> +#include <iostream> +using namespace boost; + +int main(int argc, const char ** argv) { + random::mt19937 generator; + random::uniform_int_distribution<unsigned> distribution; + //defaults + unsigned high_shift = 16; + unsigned low_shift = 16; + unsigned count = 1000000; + //Reading in user arguments + if (argc > 1) + high_shift = atoi(argv[1]); + if (argc > 2) + low_shift = atoi(argv[2]); + if (argc > 3) + count = atoi(argv[3]); + if (high_shift > 16) + high_shift = 16; + if (low_shift > 16) + low_shift = 16; + std::ofstream ofile; + ofile.open("input.txt", std::ios_base::out | std::ios_base::binary | + std::ios_base::trunc); + if (ofile.bad()) { + printf("could not open input.txt for writing!\n"); + return 1; + } + //buffering file output for speed + unsigned uDivideFactor = 1000; + //Skipping buffering for small files + if (count < uDivideFactor * 100) + uDivideFactor = count; + unsigned * pNumbers = static_cast<unsigned *>(malloc(uDivideFactor * + sizeof(unsigned))); + //Generating semirandom numbers + unsigned mask = 0; + unsigned one = 1; + for (unsigned u = 0; u < low_shift; ++u) { + mask += one << u; + } + for (unsigned u = 0; u < high_shift; ++u) { + mask += one << (16 + u); + } + for (unsigned u = 0; u < count/uDivideFactor; ++u) { + unsigned i = 0; + for (; i< uDivideFactor; ++i) { + pNumbers[i] = distribution(generator) & mask; + } + ofile.write(reinterpret_cast<char *>(pNumbers), uDivideFactor * 4 ); + } + ofile.close(); + return 0; +} diff --git a/src/boost/libs/sort/example/reverseintsample.cpp b/src/boost/libs/sort/example/reverseintsample.cpp new file mode 100644 index 000000000..c4777be93 --- /dev/null +++ b/src/boost/libs/sort/example/reverseintsample.cpp @@ -0,0 +1,101 @@ +//! \file +//! \brief integer sort with a rightshift functor reverse sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +// Caution: this file contains Quickbook markup as well as code +// and comments, don't change any of the special comment markups! + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <iostream> +#include <functional> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE int + +struct negrightshift { + inline int operator()(const int &x, const unsigned offset) { + return -(x >> offset); + } +}; + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) + input.read(reinterpret_cast<char *>(&(array[v++])), uSize ); + if (v < uCount) + array.resize(v); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + +//[reverse_int_1 + std::sort(array.begin(), array.end(), std::greater<DATA_TYPE>()); +//] [/reverse_int_1] + else +//[reverse_int_2 + integer_sort(array.begin(), array.end(), negrightshift(), std::greater<DATA_TYPE>()); +//] [/reverse_int_2] + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v])); + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/reversestringfunctorsample.cpp b/src/boost/libs/sort/example/reversestringfunctorsample.cpp new file mode 100644 index 000000000..6066f2814 --- /dev/null +++ b/src/boost/libs/sort/example/reversestringfunctorsample.cpp @@ -0,0 +1,112 @@ +// spreadsort string functor reverse sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/string_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +struct DATA_TYPE { + string a; + }; + +struct greaterthan { + inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const { + return x.a > y.a; + } +}; + +struct bracket { + inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const { + return x.a[offset]; + } +}; + +struct getsize { + inline size_t operator()(const DATA_TYPE &x) const{ return x.a.size(); } +}; + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (!indata) { + printf("input.txt could not be opened\n"); + return 1; + } + DATA_TYPE inval; + indata >> inval.a; + while (!indata.eof() ) { + array.push_back(inval); + //Inserting embedded nulls and empty strings + if (!(array.size() % 100)) { + if (inval.a.empty() || !(array.size() % 1000)) { + inval.a = ""; + array.push_back(inval); + } + else { + inval.a[0] = '\0'; + array.push_back(inval); + } + } + indata >> inval.a; + } + + indata.close(); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + std::sort(array.begin(), array.end(), greaterthan()); + else + reverse_string_sort(array.begin(), array.end(), bracket(), getsize(), + greaterthan()); + end = clock(); + elapsed = static_cast<double>(end - start); + if (stdSort) + outfile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + outfile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (outfile.good()) { + for (unsigned u = 0; u < array.size(); ++u) + outfile << array[u].a << "\n"; + outfile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/reversestringsample.cpp b/src/boost/libs/sort/example/reversestringsample.cpp new file mode 100644 index 000000000..9fa04c463 --- /dev/null +++ b/src/boost/libs/sort/example/reversestringsample.cpp @@ -0,0 +1,98 @@ +// spreadsort reverse string sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/string_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +#define DATA_TYPE string + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (!indata) { + printf("input.txt could not be opened\n"); + return 1; + } + DATA_TYPE inval; + indata >> inval; + while (!indata.eof() ) { + //testing substrings + if (!(array.size() % 2)) + inval = "prefix" + inval; + else + inval += "suffix"; + array.push_back(inval); + //Inserting embedded nulls and empty strings + if (!(array.size() % 100)) { + if (inval.empty() || !(array.size() % 1000)) + array.push_back(""); + else { + inval[0] = '\0'; + array.push_back(inval); + } + } + indata >> inval; + } + + indata.close(); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end(), std::greater<string>()); + else + //string_sort(&(array[0]), &(array[0]) + uCount); + reverse_string_sort(array.begin(), array.end(), std::greater<string>()); + end = clock(); + elapsed = static_cast<double>(end - start); + if (stdSort) + outfile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + outfile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (outfile.good()) { + for (unsigned u = 0; u < array.size(); ++u) + outfile << array[u] << "\n"; + outfile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/rightshiftsample.cpp b/src/boost/libs/sort/example/rightshiftsample.cpp new file mode 100644 index 000000000..33da64f73 --- /dev/null +++ b/src/boost/libs/sort/example/rightshiftsample.cpp @@ -0,0 +1,98 @@ +//! \brief Integer sort with a rightshift functor sorting example. +//! \file +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +// Caution: this file contains Quickbook markup as well as code +// and comments, don't change any of the special comment markups! + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE int + +//[rightshift_int_functor +struct rightshift { + inline int operator()(DATA_TYPE x, unsigned offset) { return x >> offset; } +}; +//] [/rightshift_int_functor] + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) + input.read(reinterpret_cast<char *>(&(array[v++])), uSize ); + if (v < uCount) + array.resize(v); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) { + std::sort(array.begin(), array.end()); + } else { +//[rightshift_1 + integer_sort(array.begin(), array.end(), rightshift()); +//] [/rightshift_1] + } + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/sample.cpp b/src/boost/libs/sort/example/sample.cpp new file mode 100644 index 000000000..1da89368b --- /dev/null +++ b/src/boost/libs/sort/example/sample.cpp @@ -0,0 +1,88 @@ +// spreadsort sorting example +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <sstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE int + + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) + input.read(reinterpret_cast<char *>(&(array[v++])), uSize ); + if (v < uCount) + array.resize(v); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + std::sort(array.begin(), array.end()); + else + boost::sort::spreadsort::spreadsort(array.begin(), array.end()); + end = clock(); + elapsed = static_cast<double>(end - start); + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + input.close(); + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/shiftfloatsample.cpp b/src/boost/libs/sort/example/shiftfloatsample.cpp new file mode 100644 index 000000000..5f752745d --- /dev/null +++ b/src/boost/libs/sort/example/shiftfloatsample.cpp @@ -0,0 +1,107 @@ +// float_sort rightshift functor sorting example +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <string> +#include <fstream> +#include <iostream> +using namespace boost::sort::spreadsort; + +#define DATA_TYPE float +#define CAST_TYPE int + +//Casting to an integer before bitshifting +struct rightshift { + inline int operator()(const DATA_TYPE &x, const unsigned offset) const { + return float_mem_cast<DATA_TYPE, int>(x) >> offset; + } +}; + + +//Pass in an argument to test std::sort +//Note that this converts NaNs and -0.0 to 0.0, so that sorting results are +//identical every time +int main(int argc, const char ** argv) { + size_t uCount,uSize=sizeof(DATA_TYPE); + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + std::ifstream input("input.txt", std::ios_base::in | std::ios_base::binary); + if (input.fail()) { + printf("input.txt could not be opened\n"); + return 1; + } + double total = 0.0; + std::vector<DATA_TYPE> array; + input.seekg (0, std::ios_base::end); + size_t length = input.tellg(); + uCount = length/uSize; + //Run multiple loops, if requested + for (unsigned u = 0; u < loopCount; ++u) { + input.seekg (0, std::ios_base::beg); + //Conversion to a vector + array.resize(uCount); + unsigned v = 0; + while (input.good() && v < uCount) { + input.read(reinterpret_cast<char *>(&(array[v])), uSize ); + //Testcase doesn't sort NaNs; they just cause confusion + if (!(array[v] < 0.0) && !(0.0 < array[v])) + array[v] = 0.0; + //Checking for denormalized numbers + if (!(float_mem_cast<float, int>(array[v]) & 0x7f800000)) { + //Make the top exponent bit high + CAST_TYPE temp = 0x40000000 | float_mem_cast<float, int>(array[v]); + memcpy(&(array[v]), &temp, sizeof(DATA_TYPE)); + } + ++v; + } + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else + //float_sort(&(array[0]), &(array[0]) + uCount, rightshift()); + float_sort(array.begin(), array.end(), rightshift()); + end = clock(); + elapsed = static_cast<double>(end - start) ; + std::ofstream ofile; + if (stdSort) + ofile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + ofile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (ofile.good()) { + for (unsigned v = 0; v < array.size(); ++v) { + ofile.write(reinterpret_cast<char *>(&(array[v])), sizeof(array[v]) ); + } + ofile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/example/stringfunctorsample.cpp b/src/boost/libs/sort/example/stringfunctorsample.cpp new file mode 100644 index 000000000..0ef9bf4e2 --- /dev/null +++ b/src/boost/libs/sort/example/stringfunctorsample.cpp @@ -0,0 +1,127 @@ +//! \brief spreadsort string functor sorting example. +//! \file +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +// Caution: this file contains Quickbook markup as well as code +// and comments, don't change any of the special comment markups! + +#include <boost/sort/spreadsort/string_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +struct DATA_TYPE { + string a; +}; + +//[lessthan_functor + +struct lessthan { + inline bool operator()(const DATA_TYPE &x, const DATA_TYPE &y) const { + return x.a < y.a; + } +}; +//] [/lessthan_functor] + +//[bracket_functor +struct bracket { + inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const { + return x.a[offset]; + } +}; +//] [/bracket_functor] + +//[getsize_functor +struct getsize { + inline size_t operator()(const DATA_TYPE &x) const{ return x.a.size(); } +}; +//] [/getsize_functor] + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (indata.bad()) { + printf("input.txt could not be opened\n"); + return 1; + } + DATA_TYPE inval; + indata >> inval.a; + while (!indata.eof() ) { + array.push_back(inval); + //Inserting embedded nulls and empty strings + if (!(array.size() % 100)) { + if (inval.a.empty() || !(array.size() % 1000)) { + inval.a = ""; + array.push_back(inval); + } + else { + inval.a[0] = '\0'; + array.push_back(inval); + } + } + indata >> inval.a; + } + + indata.close(); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) { + std::sort(array.begin(), array.end(), lessthan()); + } else { +//[stringsort_functors_call + string_sort(array.begin(), array.end(), bracket(), getsize(), lessthan()); +//] [/stringsort_functors_call] + } + end = clock(); + elapsed = static_cast<double>(end - start); + if (stdSort) { + outfile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + } else { + outfile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + } + if (outfile.good()) { + for (unsigned u = 0; u < array.size(); ++u) + outfile << array[u].a << "\n"; + outfile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) { + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + } else { + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + } + return 0; +} diff --git a/src/boost/libs/sort/example/stringsample.cpp b/src/boost/libs/sort/example/stringsample.cpp new file mode 100644 index 000000000..eb3003382 --- /dev/null +++ b/src/boost/libs/sort/example/stringsample.cpp @@ -0,0 +1,85 @@ +// spreadsort string sorting example. +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/string_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::string; +using namespace boost::sort::spreadsort; + +#define DATA_TYPE string + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (indata.bad()) { + printf("input.txt could not be opened\n"); + return 1; + } + DATA_TYPE inval; + while (!indata.eof() ) { + indata >> inval; + array.push_back(inval); + } + + indata.close(); + clock_t start, end; + double elapsed; + start = clock(); + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else + //string_sort(&(array[0]), &(array[0]) + uCount); + string_sort(array.begin(), array.end()); + end = clock(); + elapsed = static_cast<double>(end - start); + if (stdSort) + outfile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + outfile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (outfile.good()) { + for (unsigned u = 0; u < array.size(); ++u) + outfile << array[u] << "\n"; + outfile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} + + diff --git a/src/boost/libs/sort/example/wstringsample.cpp b/src/boost/libs/sort/example/wstringsample.cpp new file mode 100644 index 000000000..6775bbe7d --- /dev/null +++ b/src/boost/libs/sort/example/wstringsample.cpp @@ -0,0 +1,96 @@ +// spreadsort wstring sorting example +// +// Copyright Steven Ross 2009-2014. +// +// 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/sort for library home page. + +#include <boost/sort/spreadsort/string_sort.hpp> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include <algorithm> +#include <vector> +#include <iostream> +#include <fstream> +#include <string> +using std::wstring; +using namespace boost::sort::spreadsort; + +#define DATA_TYPE wstring + +//Pass in an argument to test std::sort +int main(int argc, const char ** argv) { + std::ifstream indata; + std::ofstream outfile; + bool stdSort = false; + unsigned loopCount = 1; + for (int u = 1; u < argc; ++u) { + if (std::string(argv[u]) == "-std") + stdSort = true; + else + loopCount = atoi(argv[u]); + } + double total = 0.0; + //Run multiple loops, if requested + std::vector<DATA_TYPE> array; + for (unsigned u = 0; u < loopCount; ++u) { + indata.open("input.txt", std::ios_base::in | std::ios_base::binary); + if (indata.bad()) { + printf("input.txt could not be opened\n"); + return 1; + } + unsigned short inval; + DATA_TYPE current; + while (indata.good()) { + indata.read(reinterpret_cast<char *>(&inval), sizeof(inval)); + current.push_back(inval); + //32 characters is a moderately long string + if (static_cast<int>(current.size()) > inval || current.size() >= 32) { + array.push_back(current); + current.clear(); + } + } + //adding the last string + if (!current.empty()) + array.push_back(current); + + indata.close(); + clock_t start, end; + double elapsed; + start = clock(); + wchar_t cast_type = 0; + if (stdSort) + //std::sort(&(array[0]), &(array[0]) + uCount); + std::sort(array.begin(), array.end()); + else + //string_sort(&(array[0]), &(array[0]) + uCount, cast_type); + string_sort(array.begin(), array.end(), cast_type); + end = clock(); + elapsed = static_cast<double>(end - start); + if (stdSort) + outfile.open("standard_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + else + outfile.open("boost_sort_out.txt", std::ios_base::out | + std::ios_base::binary | std::ios_base::trunc); + if (outfile.good()) { + for (unsigned u = 0; u < array.size(); ++u){ + for (unsigned v = 0; v < array[u].size(); ++v) + outfile << array[u][v]; + outfile << "\n"; + } + outfile.close(); + } + total += elapsed; + array.clear(); + } + if (stdSort) + printf("std::sort elapsed time %f\n", total / CLOCKS_PER_SEC); + else + printf("spreadsort elapsed time %f\n", total / CLOCKS_PER_SEC); + return 0; +} diff --git a/src/boost/libs/sort/index.html b/src/boost/libs/sort/index.html new file mode 100644 index 000000000..7d5f937b1 --- /dev/null +++ b/src/boost/libs/sort/index.html @@ -0,0 +1,15 @@ +<!-- Automatic redirection to Quickbook/Doxygen version of documentation. --> +<html> +<head> +<meta http-equiv="refresh" content="0; URL=doc/html/index.html"> +</head> +<body> +Automatic redirection failed, please go to +<a href="doc/html/index.html">doc/html/index.html</a> + <hr> +<p>© Copyright Steven Ross 2009-2014</p> +<p>Distributed under the Boost Software License, Version 1.0. (See accompanying +file <a href="../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or copy +at <a href="http://www.boost.org/LICENSE_1_0.txt">www.boost.org/LICENSE_1_0.txt</a>)</p> +</body> +</html> diff --git a/src/boost/libs/sort/meta/libraries.json b/src/boost/libs/sort/meta/libraries.json new file mode 100644 index 000000000..18c676de2 --- /dev/null +++ b/src/boost/libs/sort/meta/libraries.json @@ -0,0 +1,17 @@ +[ + { + "key": "sort", + "name": "Sort", + "authors": [ + "Steven Ross" + ], + "maintainers": [ + "Steven Ross <spreadsort -at- gmail.com>" + ], + "description": + "High-performance templated sort functions.", + "category": [ + "Algorithms" + ] + } +] diff --git a/src/boost/libs/sort/test/Jamfile.v2 b/src/boost/libs/sort/test/Jamfile.v2 new file mode 100644 index 000000000..1d581a8d4 --- /dev/null +++ b/src/boost/libs/sort/test/Jamfile.v2 @@ -0,0 +1,65 @@ +# Boost sorting_algo library test suite Jamfile ---------------------------- +# +# Copyright Steven Ross 2009. Use, modification and +# distribution is subject to 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/sort for library home page. + +import ../../config/checks/config : requires ; +import testing ; + +{ + test-suite "sort" + : [ run integer_sort_test.cpp + : : : : integer_sort ] + [ run float_sort_test.cpp + : : : : float_sort ] + [ run string_sort_test.cpp + : : : : string_sort ] + [ run sort_detail_test.cpp + : : : : sort_detail ] + + [ run test_pdqsort.cpp + : : : [ requires + cxx11_hdr_random ] <optimization>speed : test_pdqsort ] + + [ run test_flat_stable_sort.cpp + : : : [ requires + cxx11_constexpr + cxx11_noexcept ] <optimization>speed : test_flat_stable_sort ] + + [ run test_spinsort.cpp + : : : [ requires + cxx11_constexpr + cxx11_noexcept ] <optimization>speed : test_spinsort ] + + [ run test_insert_sort.cpp + : : : [ requires + cxx11_constexpr + cxx11_noexcept ] <optimization>speed : test_insert_sort ] + + + [ run test_block_indirect_sort.cpp + : : : [ requires + cxx11_constexpr + cxx11_noexcept + cxx11_thread_local + cxx11_lambdas ] <optimization>speed <threading>multi : test_block_indirect_sort ] + + [ run test_sample_sort.cpp + : : : [ requires + cxx11_constexpr + cxx11_noexcept + cxx11_thread_local + cxx11_lambdas ] <optimization>speed <threading>multi : test_sample_sort ] + + [ run test_parallel_stable_sort.cpp + : : : [ requires + cxx11_constexpr + cxx11_noexcept + cxx11_thread_local + cxx11_lambdas ] <optimization>speed <threading>multi : test_parallel_stable_sort ] + ; +} diff --git a/src/boost/libs/sort/test/float_sort_test.cpp b/src/boost/libs/sort/test/float_sort_test.cpp new file mode 100644 index 000000000..c562e00d6 --- /dev/null +++ b/src/boost/libs/sort/test/float_sort_test.cpp @@ -0,0 +1,155 @@ +// Boost Sort library float_sort_test.cpp file -----------------------------// + +// Copyright Steven Ross 2014. Use, modification and +// distribution is subject to 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/sort for library home page. + +#include <boost/sort/spreadsort/spreadsort.hpp> +// Include unit test framework +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> +#include <vector> + + +using namespace std; +using namespace boost::sort::spreadsort; + +//Casting to an integer before bitshifting +struct rightshift { + int operator()(const float &x, const unsigned offset) const { + return float_mem_cast<float, int>(x) >> offset; + } +}; + +struct rightshift_64 { + boost::int64_t operator()(const double &x, const boost::uint64_t offset) const + { + return float_mem_cast<double, boost::int64_t>(x) >> offset; + } +}; + +boost::int32_t +rand_32(bool sign = true) { + boost::int32_t result = rand() | (rand()<< 16); + if (rand() % 2) + result |= 1 << 15; + //Adding the sign bit + if (sign && (rand() % 2)) + result *= -1; + return result; +} + +static const unsigned input_count = 1000000; + +// Helper class to run tests across all float_sort interface variants. +template<class FloatType, class RightShift> +void test_vector(vector<FloatType> base_vec, RightShift shifter) { + vector<FloatType> sorted_vec = base_vec; + vector<FloatType> test_vec = base_vec; + std::sort(sorted_vec.begin(), sorted_vec.end()); + //Testing boost::sort::spreadsort version + test_vec = base_vec; + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec == sorted_vec); + //One functor + test_vec = base_vec; + float_sort(test_vec.begin(), test_vec.end(), shifter); + BOOST_CHECK(test_vec == sorted_vec); + //Both functors + test_vec = base_vec; + float_sort(test_vec.begin(), test_vec.end(), shifter, less<FloatType>()); + BOOST_CHECK(test_vec == sorted_vec); +} + +void float_test() +{ + // Prepare inputs + vector<float> base_vec; + + //Generating semirandom numbers that will work for basic testing + for (unsigned u = 0; u < input_count; ++u) { + float val = float(rand_32()); + //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0, treat all + //those as just 0.0 for testing + if (!(val < 0.0) && !(0.0 < val)) + base_vec.push_back(0.0); + else + base_vec.push_back(val); + } + test_vector(base_vec, rightshift()); + + // Trying both positive and negative sorted and reverse sorted data. + base_vec.clear(); + for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i); + test_vector(base_vec, rightshift()); + base_vec.clear(); + for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count); + test_vector(base_vec, rightshift()); + base_vec.clear(); + for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i); + test_vector(base_vec, rightshift()); + base_vec.clear(); + for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); + test_vector(base_vec, rightshift()); + base_vec.clear(); + for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); + for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1; + test_vector(base_vec, rightshift()); +} + +void double_test() { + vector<double> base_vec; + for (unsigned u = 0; u < input_count; ++u) { + double val = double + ((((boost::int64_t)rand_32()) << ((8 * sizeof(int)) -1)) + rand_32(false)); + //As std::sort gives arbitrary results for NaNs and 0.0 vs. -0.0, + //treat all those as just 0.0 for testing + if (!(val < 0.0) && !(0.0 < val)) + base_vec.push_back(0.0); + else + base_vec.push_back(val); + } + test_vector(base_vec, rightshift_64()); + + // Trying both positive and negative sorted and reverse sorted data. + base_vec.clear(); + for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(-i); + test_vector(base_vec, rightshift_64()); + base_vec.clear(); + for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(i - input_count); + test_vector(base_vec, rightshift_64()); + base_vec.clear(); + for (int i = 0; i < (int)input_count; ++i) base_vec.push_back(input_count - i); + test_vector(base_vec, rightshift_64()); + base_vec.clear(); + for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); + test_vector(base_vec, rightshift_64()); + base_vec.clear(); + for (size_t i = 0; i < input_count; ++i) base_vec.push_back(i); + for (size_t i = 0; i < input_count; i += 2) base_vec[i] *= -1; + test_vector(base_vec, rightshift_64()); +} + +// Verify that 0 and 1 elements work correctly. +void corner_test() { + vector<float> test_vec; + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + const float test_value = -0.0; + test_vec.push_back(test_value); + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec.size() == 1); + BOOST_CHECK(test_vec[0] == test_value); +} + +// test main +int test_main( int, char*[] ) +{ + srand(1); + float_test(); + double_test(); + corner_test(); + return 0; +} diff --git a/src/boost/libs/sort/test/integer_sort_test.cpp b/src/boost/libs/sort/test/integer_sort_test.cpp new file mode 100644 index 000000000..2a97de015 --- /dev/null +++ b/src/boost/libs/sort/test/integer_sort_test.cpp @@ -0,0 +1,131 @@ +// Boost Sort library int_test.cpp file ------------------------------------// + +// Copyright Steven Ross 2009-2014. Use, modification and +// distribution is subject to 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/sort for library home page. + +#include <boost/cstdint.hpp> +#include <boost/sort/spreadsort/spreadsort.hpp> +// Include unit test framework +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> +#include <vector> + +#include <iostream> + + +using namespace std; +using namespace boost::sort::spreadsort; + +struct rightshift { + int operator()(int x, unsigned offset) { return x >> offset; } +}; + +struct rightshift_max { + boost::intmax_t operator()(const boost::intmax_t &x, unsigned offset) { + return x >> offset; + } +}; + +struct negrightshift { + int operator()(const int &x, const unsigned offset) { return -(x >> offset); } +}; + +struct negrightshift_max { + boost::intmax_t operator()(const boost::intmax_t &x, const unsigned offset) { + return -(x >> offset); + } +}; + +boost::int32_t +rand_32(bool sign = true) { + boost::int32_t result = rand() | (rand()<< 16); + if (rand() % 2) + result |= 1 << 15; + //Adding the sign bit + if (sign && (rand() % 2)) + result *= -1; + return result; +} + +void int_test() +{ + // Prepare inputs + vector<int> base_vec; + unsigned count = 100000; + srand(1); + //Generating semirandom numbers + for (unsigned u = 0; u < count; ++u) + base_vec.push_back(rand_32()); + vector<int> sorted_vec = base_vec; + vector<int> test_vec = base_vec; + std::sort(sorted_vec.begin(), sorted_vec.end()); + //Testing basic call + integer_sort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec == sorted_vec); + //boost::sort::spreadsort variant + test_vec = base_vec; + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec == sorted_vec); + //One functor + test_vec = base_vec; + integer_sort(test_vec.begin(), test_vec.end(), rightshift()); + BOOST_CHECK(test_vec == sorted_vec); + //Both functors + test_vec = base_vec; + integer_sort(test_vec.begin(), test_vec.end(), rightshift(), less<int>()); + BOOST_CHECK(test_vec == sorted_vec); + //reverse order + std::sort(sorted_vec.begin(), sorted_vec.end(), greater<int>()); + integer_sort(test_vec.begin(), test_vec.end(), negrightshift(), + greater<int>()); + BOOST_CHECK(test_vec == sorted_vec); + + //Making sure we're correctly sorting boost::intmax_ts; should use std::sort + vector<boost::intmax_t> long_base_vec; + for (unsigned u = 0; u < base_vec.size(); ++u) + long_base_vec.push_back((((boost::intmax_t)rand_32()) << + ((8 * sizeof(int)) -1)) + rand_32(false)); + vector<boost::intmax_t> long_sorted_vec = long_base_vec; + vector<boost::intmax_t> long_test_vec = long_base_vec; + integer_sort(long_test_vec.begin(), long_test_vec.end()); + std::sort(long_sorted_vec.begin(), long_sorted_vec.end()); + BOOST_CHECK(long_test_vec == long_sorted_vec); + //One functor + long_test_vec = long_base_vec; + integer_sort(long_test_vec.begin(), long_test_vec.end(), rightshift_max()); + BOOST_CHECK(long_test_vec == long_sorted_vec); + //Both functors + long_test_vec = long_base_vec; + integer_sort(long_test_vec.begin(), long_test_vec.end(), rightshift_max(), + less<boost::intmax_t>()); + BOOST_CHECK(long_test_vec == long_sorted_vec); + //reverse order + std::sort(long_sorted_vec.begin(), long_sorted_vec.end(), + greater<boost::intmax_t>()); + integer_sort(long_test_vec.begin(), long_test_vec.end(), negrightshift_max(), + greater<boost::intmax_t>()); + BOOST_CHECK(long_test_vec == long_sorted_vec); +} + +// Verify that 0 and 1 elements work correctly. +void corner_test() { + vector<int> test_vec; + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + const int test_value = 42; + test_vec.push_back(test_value); + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec.size() == 1); + BOOST_CHECK(test_vec[0] == test_value); +} + +// test main +int test_main( int, char*[] ) +{ + int_test(); + corner_test(); + return 0; +} diff --git a/src/boost/libs/sort/test/list.txt b/src/boost/libs/sort/test/list.txt new file mode 100644 index 000000000..0162042fc --- /dev/null +++ b/src/boost/libs/sort/test/list.txt @@ -0,0 +1,15 @@ +CMakeLists.txt +float_sort_test.cpp +integer_sort_test.cpp +Jamfile.v2 +list.txt +sort_detail_test.cpp +string_sort_test.cpp +test_block_indirect_sort.cpp +test_flat_stable_sort.cpp +test_insert_sort.cpp +test.log +test_parallel_stable_sort.cpp +test_pdqsort.cpp +test_sample_sort.cpp +test_spinsort.cpp diff --git a/src/boost/libs/sort/test/sort_detail_test.cpp b/src/boost/libs/sort/test/sort_detail_test.cpp new file mode 100644 index 000000000..c7e7c5588 --- /dev/null +++ b/src/boost/libs/sort/test/sort_detail_test.cpp @@ -0,0 +1,294 @@ +// Boost Sort library tests for integer_sort and float_sort details. + +// Copyright Steven Ross 2014. Use, modification and +// distribution is subject to 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/sort for library home page. + +#include <boost/cstdint.hpp> +#include <boost/sort/spreadsort/detail/spreadsort_common.hpp> +#include <boost/sort/spreadsort/detail/integer_sort.hpp> +#include <boost/sort/spreadsort/detail/float_sort.hpp> +#include <boost/sort/spreadsort/detail/string_sort.hpp> +#include <boost/sort/spreadsort/float_sort.hpp> +// Include unit test framework +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> +#include <vector> + +#include <iostream> + + +using namespace std; +using namespace boost::sort::spreadsort; +using namespace boost::sort::spreadsort::detail; + +namespace { + +struct int_right_shift { + int operator()(const int x, const unsigned offset) const { + return x >> offset; + } +}; + +struct float_right_shift { + int operator()(const float x, const unsigned offset) const { + return float_mem_cast<float, int>(x) >> offset; + } +}; + +const int max_int_bits = sizeof(boost::uintmax_t) * 8; +const int max_size_bits = sizeof(size_t) * 8; +const boost::uintmax_t one = 1; + +// spreadsort won't recurse for inputs smaller than min_count. +const int int_min_log_count = + (std::min)((int)int_log_finishing_count, + (int)int_log_mean_bin_size + int_log_min_split_count); +const int float_min_log_count = + (std::min)((int)float_log_finishing_count, + (int)float_log_mean_bin_size + float_log_min_split_count); +const unsigned absolute_min_count = (std::min)(1 << int_min_log_count, + 1 << float_min_log_count); + +// Verify that roughlog2 is floor(log base 2) + 1. +void roughlog2_test() +{ + for (boost::uintmax_t i = 0; i < max_int_bits; ++i) { + BOOST_CHECK(detail::rough_log_2_size(one << i) == i + 1); + BOOST_CHECK(detail::rough_log_2_size((one << i) - 1) == i); + } +} + +// Test the worst-case performance handling, and assure that is using the +// correct formula for the worst-case number of radix iterations. +template<unsigned log_mean_bin_size, unsigned log_min_split_count, + unsigned log_finishing_count> +void get_min_count_test() +{ + const unsigned min_log_size = log_mean_bin_size + log_min_split_count; + size_t prev_min_count = absolute_min_count; + for (int log_range = 0; log_range <= max_int_bits; ++log_range) { + size_t min_count = get_min_count<log_mean_bin_size, log_min_split_count, + log_finishing_count>(log_range); + BOOST_CHECK(min_count >= prev_min_count); + prev_min_count = min_count; + // When the range is really small, the radix sort will complete in one + // iteration and worst-case handling doesn't apply. The code below + // guarantees the worst-case number of radix sorting iteration. + if (log_range > min_log_size) { + BOOST_CHECK(min_count >= (1 << min_log_size)); + int iterations = rough_log_2_size(min_count) - min_log_size; + BOOST_CHECK(iterations >= 1); + int base_iterations = max_splits - log_min_split_count; + int covered_log_range = 0; + if (iterations > base_iterations) { + covered_log_range += max_splits * (iterations - base_iterations); + } else { + base_iterations = iterations; + } + // sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size + covered_log_range += + (base_iterations * (log_min_split_count * 2 + base_iterations - 1))/2 + + log_mean_bin_size; + BOOST_CHECK(covered_log_range >= log_range); + BOOST_CHECK(covered_log_range - max_splits < log_range); + } + } +} + +// Test the decision of how many pieces to split up the radix sort into +// (roughly 2^(log_range - log_divisor)) to make sure the results are logical. +void get_log_divisor_test() +{ + for (int log_range = 0; log_range <= max_int_bits; ++log_range) { + int prev_log_divisor = max_int_bits + + (std::max)((int)int_log_mean_bin_size, (int)float_log_mean_bin_size); + for (int log_count = 0; log_count < max_size_bits; ++log_count) { + size_t count = (one << log_count) - 1; + BOOST_CHECK(rough_log_2_size(count) == (unsigned)log_count); + int log_divisor = + get_log_divisor<int_log_mean_bin_size>(count, log_range); + // Only process counts >= int_log_finishing_count in this function. + if (count >= absolute_min_count) + BOOST_CHECK(log_divisor <= log_range); + // More pieces should be used the larger count is. + BOOST_CHECK(log_divisor <= prev_log_divisor); + prev_log_divisor = log_divisor; + BOOST_CHECK(log_divisor >= 0); + if (log_range > log_count) { + BOOST_CHECK(log_range - log_divisor <= max_splits); + } else if (log_range <= max_finishing_splits) { + BOOST_CHECK(log_divisor == 0); + } + } + } +} + +// Verify that is_sorted_or_find_extremes returns true if the data is sorted, +// and otherwise returns the actual min and max. +void is_sorted_or_find_extremes_test() +{ + vector<int> input; + input.push_back(3); + input.push_back(5); + input.push_back(1); + // Test a sorted input. + vector<int> sorted_input(input); + std::sort(sorted_input.begin(), sorted_input.end()); + vector<int>::iterator max, min; + BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(), + sorted_input.end(), max, min)); + // Test an unsorted input. + BOOST_CHECK(!detail::is_sorted_or_find_extremes(input.begin(), input.end(), + max, min)); + BOOST_CHECK(*min == 1); + BOOST_CHECK(*max == 5); + // Test the comparison function version. + BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_input.begin(), + sorted_input.end(), max, min, + std::less<int>())); + BOOST_CHECK(!detail::is_sorted_or_find_extremes(sorted_input.begin(), + sorted_input.end(), + max, min, + std::greater<int>())); + BOOST_CHECK(*min == 5); + BOOST_CHECK(*max == 1); + + // Test with floats + vector<float> float_input; + float_input.push_back(.3f); + float_input.push_back(4.0f); + float_input.push_back(.1f); + vector<float> sorted_float_input(float_input); + std::sort(sorted_float_input.begin(), sorted_float_input.end()); + // Test cast_float_iter + int cast_min = detail::cast_float_iter<int, vector<float>::iterator>( + sorted_float_input.begin()); + int cast_max = detail::cast_float_iter<int, vector<float>::iterator>( + sorted_float_input.end() - 1); + BOOST_CHECK(cast_min == float_right_shift()(.1f, 0)); + BOOST_CHECK(cast_max == float_right_shift()(4.0f, 0)); + // Test a sorted input + int div_max, div_min; + BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(), + sorted_float_input.end(), + div_max, div_min)); + // Test an unsorted input. + BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(), + float_input.end(), + div_max, div_min)); + BOOST_CHECK(div_min == cast_min); + BOOST_CHECK(div_max == cast_max); + + // Test with a right_shift functor. + BOOST_CHECK(detail::is_sorted_or_find_extremes(sorted_float_input.begin(), + sorted_float_input.end(), + div_max, div_min, + float_right_shift())); + // Test an unsorted input. + BOOST_CHECK(!detail::is_sorted_or_find_extremes(float_input.begin(), + float_input.end(), div_max, + div_min, + float_right_shift())); + BOOST_CHECK(div_min == float_right_shift()(.1f, 0)); + BOOST_CHECK(div_max == float_right_shift()(4.0f, 0)); +} + +// Make sure bins are created correctly. +void size_bins_test() { + size_t bin_sizes[1 << detail::max_finishing_splits]; + bin_sizes[0] = 1; + bin_sizes[2] = 7; + const int old_bin_value = 7; + std::vector<int> old_bins; + old_bins.push_back(old_bin_value); + std::vector<vector<int>::iterator> bin_cache; + bin_cache.push_back(old_bins.begin()); + unsigned cache_offset = 1; + unsigned cache_end; + const unsigned bin_count = 2; + std::vector<int>::iterator *new_cache_start = + size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count); + BOOST_CHECK((new_cache_start - &bin_cache[0]) == cache_offset); + BOOST_CHECK(bin_sizes[0] == 0); + BOOST_CHECK(bin_sizes[1] == 0); + BOOST_CHECK(bin_sizes[2] == 7); // shouldn't modify past bin_count + BOOST_CHECK(cache_end == 3); + BOOST_CHECK(bin_cache.size() == cache_end); + BOOST_CHECK(old_bins[0] == old_bin_value); +} + +// Test the specialized 3-way swap loops. +void swap_loop_test() { + size_t bin_sizes[1 << detail::max_finishing_splits]; + bin_sizes[0] = bin_sizes[1] = 2; + bin_sizes[2] = 1; + + // test integer swap loop + vector<int> ints; + const int int_div_min = 3; + const int int_log_divisor = 1; + const unsigned int_offset = int_div_min << int_log_divisor; + ints.push_back(2 + int_offset); + ints.push_back(1 + int_offset); // stays in place + ints.push_back(4 + int_offset); + ints.push_back(3 + int_offset); + ints.push_back(0 + int_offset); + vector<vector<int>::iterator> int_bin_vector; + int_bin_vector.push_back(ints.begin()); + int_bin_vector.push_back(int_bin_vector[0] + bin_sizes[0]); + int_bin_vector.push_back(int_bin_vector[1] + bin_sizes[1]); + vector<int>::iterator next_int_bin_start = int_bin_vector[0]; + vector<int>::iterator *int_bins = &int_bin_vector[0]; + int_right_shift integer_right_shift; + swap_loop(int_bins, next_int_bin_start, 0, integer_right_shift, bin_sizes, + int_log_divisor, int_div_min); + for (unsigned i = 0; i < ints.size(); ++i) { + BOOST_CHECK(ints[i] == int(int_offset + i)); + } + BOOST_CHECK(next_int_bin_start == ints.begin() + bin_sizes[0]); + + // test float swap loop + vector<float> floats; + const int float_four_as_int = float_mem_cast<float, int>(4.0f); + const int float_log_divisor = + rough_log_2_size(float_mem_cast<float, int>(5.0f) - float_four_as_int); + const int float_div_min = float_four_as_int >> float_log_divisor; + floats.push_back(6.0f); + floats.push_back(5.0f); // stays in place + floats.push_back(8.0f); + floats.push_back(7.0f); + floats.push_back(4.0f); + vector<vector<float>::iterator> float_bin_vector; + float_bin_vector.push_back(floats.begin()); + float_bin_vector.push_back(float_bin_vector[0] + bin_sizes[0]); + float_bin_vector.push_back(float_bin_vector[1] + bin_sizes[1]); + vector<float>::iterator next_float_bin_start = float_bin_vector[0]; + vector<float>::iterator *float_bins = &float_bin_vector[0]; + float_swap_loop(float_bins, next_float_bin_start, 0, bin_sizes, + float_log_divisor, float_div_min); + for (unsigned i = 0; i < floats.size(); ++i) { + BOOST_CHECK(floats[i] == 4.0f + i); + } + BOOST_CHECK(next_float_bin_start == floats.begin() + bin_sizes[0]); +} + +} // end anonymous namespace + +// test main +int test_main( int, char*[] ) +{ + roughlog2_test(); + get_min_count_test<int_log_mean_bin_size, int_log_min_split_count, + int_log_finishing_count>(); + get_min_count_test<float_log_mean_bin_size, float_log_min_split_count, + float_log_finishing_count>(); + get_log_divisor_test(); + is_sorted_or_find_extremes_test(); + size_bins_test(); + swap_loop_test(); + return 0; +} diff --git a/src/boost/libs/sort/test/string_sort_test.cpp b/src/boost/libs/sort/test/string_sort_test.cpp new file mode 100644 index 000000000..5ccb1e645 --- /dev/null +++ b/src/boost/libs/sort/test/string_sort_test.cpp @@ -0,0 +1,162 @@ +// Boost Sort library string_sort_test.cpp file ----------------------------// + +// Copyright Steven Ross 2009. Use, modification and +// distribution is subject to 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/sort for library home page. + +#include <boost/sort/spreadsort/detail/string_sort.hpp> +#include <boost/sort/spreadsort/string_sort.hpp> +#include <boost/sort/spreadsort/spreadsort.hpp> +// Include unit test framework +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> +#include <vector> +#include <string> + + +using namespace std; +using namespace boost::sort::spreadsort; +using boost::sort::spreadsort::detail::offset_less_than; +using boost::sort::spreadsort::detail::offset_greater_than; +using boost::sort::spreadsort::detail::update_offset; + +struct bracket { + unsigned char operator()(const string &x, size_t offset) const { + return x[offset]; + } +}; + +struct wbracket { + wchar_t operator()(const wstring &x, size_t offset) const { + return x[offset]; + } +}; + +struct get_size { + size_t operator()(const string &x) const{ return x.size(); } +}; + +struct wget_size { + size_t operator()(const wstring &x) const{ return x.size(); } +}; + +static const unsigned input_count = 100000; + +// Test that update_offset finds the first character with a difference. +void update_offset_test() { + vector<string> input; + input.push_back("test1"); + input.push_back("test2"); + size_t char_offset = 1; + update_offset<vector<string>::iterator, unsigned char>(input.begin(), + input.end(), + char_offset); + BOOST_CHECK(char_offset == 4); + + // Functor version + char_offset = 1; + update_offset(input.begin(), input.end(), char_offset, bracket(), get_size()); + BOOST_CHECK(char_offset == 4); +} + +// Test that offset comparison operators only look after the offset. +void offset_comparison_test() { + string input1 = "ab"; + string input2 = "ba"; + string input3 = "aba"; + offset_less_than<string, unsigned char> less_than(0); + offset_greater_than<string, unsigned char> greater_than(0); + BOOST_CHECK(less_than(input1, input2)); + BOOST_CHECK(less_than(input1, input3)); + BOOST_CHECK(!less_than(input2, input1)); + BOOST_CHECK(!less_than(input1, input1)); + BOOST_CHECK(!greater_than(input1, input2)); + BOOST_CHECK(!greater_than(input1, input3)); + BOOST_CHECK(greater_than(input2, input1)); + BOOST_CHECK(!greater_than(input1, input1)); + + // Offset comparisons only check after the specified offset. + offset_less_than<string, unsigned char> offset_less(1); + offset_greater_than<string, unsigned char> offset_greater(1); + BOOST_CHECK(!offset_less(input1, input2)); + BOOST_CHECK(offset_less(input1, input3)); + BOOST_CHECK(offset_less(input2, input1)); + BOOST_CHECK(!offset_less(input1, input1)); + BOOST_CHECK(offset_greater(input1, input2)); + BOOST_CHECK(!offset_greater(input1, input3)); + BOOST_CHECK(!offset_greater(input2, input1)); + BOOST_CHECK(!offset_greater(input1, input1)); +} + +void string_test() +{ + // Prepare inputs + vector<string> base_vec; + const unsigned max_length = 32; + srand(1); + //Generating semirandom numbers + for (unsigned u = 0; u < input_count; ++u) { + unsigned length = rand() % max_length; + string result; + for (unsigned v = 0; v < length; ++v) { + result.push_back(rand() % 256); + } + base_vec.push_back(result); + } + vector<string> sorted_vec = base_vec; + vector<string> test_vec = base_vec; + std::sort(sorted_vec.begin(), sorted_vec.end()); + //Testing basic call + string_sort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec == sorted_vec); + //Testing boost::sort::spreadsort wrapper + test_vec = base_vec; + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec == sorted_vec); + //Character functors + test_vec = base_vec; + string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size()); + BOOST_CHECK(test_vec == sorted_vec); + //All functors + test_vec = base_vec; + string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size(), + less<string>()); + BOOST_CHECK(test_vec == sorted_vec); + //reverse order + std::sort(sorted_vec.begin(), sorted_vec.end(), greater<string>()); + reverse_string_sort(test_vec.begin(), test_vec.end(), greater<string>()); + BOOST_CHECK(test_vec == sorted_vec); + //reverse order with functors + test_vec = base_vec; + reverse_string_sort(test_vec.begin(), test_vec.end(), bracket(), get_size(), + greater<string>()); + BOOST_CHECK(test_vec == sorted_vec); +} + +// Verify that 0, 1, and input_count empty strings all sort correctly. +void corner_test() { + vector<string> test_vec; + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + test_vec.resize(1); + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec[0].empty()); + test_vec.resize(input_count); + boost::sort::spreadsort::spreadsort(test_vec.begin(), test_vec.end()); + BOOST_CHECK(test_vec.size() == input_count); + for (unsigned i = 0; i < test_vec.size(); ++i) { + BOOST_CHECK(test_vec[i].empty()); + } +} + +// test main +int test_main( int, char*[] ) +{ + update_offset_test(); + offset_comparison_test(); + string_test(); + corner_test(); + return 0; +} diff --git a/src/boost/libs/sort/test/test.log b/src/boost/libs/sort/test/test.log new file mode 100644 index 000000000..e529dcee0 --- /dev/null +++ b/src/boost/libs/sort/test/test.log @@ -0,0 +1,37 @@ + +Performing configuration checks + + - symlinks supported : yes (cached) +...patience... +...patience... +...found 2544 targets... +...updating 20 targets... +compile-c-c++ ..\..\..\bin.v2\libs\sort\test\integer_sort.test\msvc-12.0\debug\threading-multi\integer_sort_test.obj +integer_sort_test.cpp +msvc.link ..\..\..\bin.v2\libs\sort\test\integer_sort.test\msvc-12.0\debug\threading-multi\integer_sort.exe +msvc.manifest ..\..\..\bin.v2\libs\sort\test\integer_sort.test\msvc-12.0\debug\threading-multi\integer_sort.exe +testing.capture-output ..\..\..\bin.v2\libs\sort\test\integer_sort.test\msvc-12.0\debug\threading-multi\integer_sort.run + 1 file(s) copied. +**passed** ..\..\..\bin.v2\libs\sort\test\integer_sort.test\msvc-12.0\debug\threading-multi\integer_sort.test +compile-c-c++ ..\..\..\bin.v2\libs\sort\test\float_sort.test\msvc-12.0\debug\threading-multi\float_sort_test.obj +float_sort_test.cpp +msvc.link ..\..\..\bin.v2\libs\sort\test\float_sort.test\msvc-12.0\debug\threading-multi\float_sort.exe +msvc.manifest ..\..\..\bin.v2\libs\sort\test\float_sort.test\msvc-12.0\debug\threading-multi\float_sort.exe +testing.capture-output ..\..\..\bin.v2\libs\sort\test\float_sort.test\msvc-12.0\debug\threading-multi\float_sort.run + 1 file(s) copied. +**passed** ..\..\..\bin.v2\libs\sort\test\float_sort.test\msvc-12.0\debug\threading-multi\float_sort.test +compile-c-c++ ..\..\..\bin.v2\libs\sort\test\string_sort.test\msvc-12.0\debug\threading-multi\string_sort_test.obj +string_sort_test.cpp +msvc.link ..\..\..\bin.v2\libs\sort\test\string_sort.test\msvc-12.0\debug\threading-multi\string_sort.exe +msvc.manifest ..\..\..\bin.v2\libs\sort\test\string_sort.test\msvc-12.0\debug\threading-multi\string_sort.exe +testing.capture-output ..\..\..\bin.v2\libs\sort\test\string_sort.test\msvc-12.0\debug\threading-multi\string_sort.run + 1 file(s) copied. +**passed** ..\..\..\bin.v2\libs\sort\test\string_sort.test\msvc-12.0\debug\threading-multi\string_sort.test +compile-c-c++ ..\..\..\bin.v2\libs\sort\test\sort_detail.test\msvc-12.0\debug\threading-multi\sort_detail_test.obj +sort_detail_test.cpp +msvc.link ..\..\..\bin.v2\libs\sort\test\sort_detail.test\msvc-12.0\debug\threading-multi\sort_detail.exe +msvc.manifest ..\..\..\bin.v2\libs\sort\test\sort_detail.test\msvc-12.0\debug\threading-multi\sort_detail.exe +testing.capture-output ..\..\..\bin.v2\libs\sort\test\sort_detail.test\msvc-12.0\debug\threading-multi\sort_detail.run + 1 file(s) copied. +**passed** ..\..\..\bin.v2\libs\sort\test\sort_detail.test\msvc-12.0\debug\threading-multi\sort_detail.test +...updated 20 targets... diff --git a/src/boost/libs/sort/test/test_block_indirect_sort.cpp b/src/boost/libs/sort/test/test_block_indirect_sort.cpp new file mode 100644 index 000000000..b03f00feb --- /dev/null +++ b/src/boost/libs/sort/test/test_block_indirect_sort.cpp @@ -0,0 +1,186 @@ +//---------------------------------------------------------------------------- +/// @file test_block_indirect_sort.cpp +/// @brief Test program of the block_indirect_sort algorithm +/// +/// @author Copyright (c) 2016 Francisco Jose 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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <algorithm> +#include <random> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <vector> +#include <ciso646> +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> +#include <boost/sort/sort.hpp> + + +namespace bsc = boost::sort::common; +namespace bsp = boost::sort; +using boost::sort::block_indirect_sort; +using bsc::range; + +// ------------------- vector with 64 bits random numbers -------------------- +std::vector< uint64_t > Vrandom; +const uint64_t NELEM = 2000000; + +void test1 (void) +{ + const uint32_t NElem = 500000; + std::vector< uint64_t > V1; + V1.reserve (NElem); + + //------------------ sorted elements 4 threads -------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i); + + block_indirect_sort ( V1.begin ( ), V1.end ( ), 4); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //-------------------- reverse sorted elements 4 threads ------------------ + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i); + + block_indirect_sort ( V1.begin ( ), V1.end ( ), 4); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //-------------------- equal elements 4 threads --------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000); + + block_indirect_sort (V1.begin ( ), V1.end ( ), 4); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK (V1[ i - 1 ] == V1[ i ]); + }; + + //------------------ sorted elements 8 threads -------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i); + + block_indirect_sort ( V1.begin ( ), V1.end ( ), 8); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //-------------------- reverse sorted elements 8 threads ------------------ + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i); + + block_indirect_sort ( V1.begin ( ), V1.end ( ), 8); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //-------------------- equal elements 8 threads --------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000); + + block_indirect_sort (V1.begin ( ), V1.end ( ), 8); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK (V1[ i - 1 ] == V1[ i ]); + }; +}; + +void test2 (void) +{ + typedef std::less<uint64_t> compare; + std::vector< uint64_t > V1, V2; + V1.reserve ( NELEM ) ; + + V2 = Vrandom; + std::sort (V2.begin ( ), V2.end ( )); + + //------------------- random elements 0 threads --------------------------- + V1 = Vrandom; + block_indirect_sort (V1.begin ( ), V1.end ( ), compare(), 0); + for (unsigned i = 0; i < V1.size(); i++) + { BOOST_CHECK (V1[i] == V2[i]); + }; + + //------------------- random elements 4 threads --------------------------- + V1 = Vrandom; + block_indirect_sort (V1.begin ( ), V1.end ( ), compare(), 4); + for (unsigned i = 0; i < V1.size(); i++) + { BOOST_CHECK (V1[i] == V2[i]); + }; + + //------------------- random elements 8 threads --------------------------- + V1 = Vrandom; + block_indirect_sort (V1.begin ( ), V1.end ( ), compare(), 8); + for (unsigned i = 0; i < V1.size(); i++) + { BOOST_CHECK (V1[i] == V2[i]); + }; + + //------------------- random elements 16 threads --------------------------- + V1 = Vrandom; + block_indirect_sort ( V1.begin ( ), V1.end ( ), compare(), 16); + for (unsigned i = 0; i < V1.size(); i++) + { BOOST_CHECK (V1[i] == V2[i]); + }; + + //------------------- random elements 100 threads --------------------------- + V1 = Vrandom; + block_indirect_sort ( V1.begin ( ), V1.end ( ), compare(), 100); + for (unsigned i = 1; i < V1.size(); i++) + { BOOST_CHECK (V1[i] == V2[i]); + }; +}; + +template<uint32_t NN> +struct int_array +{ + uint64_t M[NN]; + + int_array(uint64_t number = 0) + { for (uint32_t i = 0; i < NN; ++i) M[i] = number; + }; + + bool operator<(const int_array<NN> &A) const + { return M[0] < A.M[0]; + }; +}; + +template<class IA> +void test_int_array(uint32_t NELEM) +{ + std::vector<IA> V1; + V1.reserve(NELEM); + + for (uint32_t i = 0; i < NELEM; ++i) + V1.emplace_back(Vrandom[i]); + + bsp::block_indirect_sort(V1.begin(), V1.end()); + for (unsigned i = 1; i < NELEM; i++) + { BOOST_CHECK(not (V1[i] < V1[i-1])); + }; +}; +void test3 (void) +{ + test_int_array<int_array<1> >(1u << 20); + test_int_array<int_array<2> >(1u << 19); + test_int_array<int_array<8> >(1u << 17); +} + +int test_main (int, char *[]) +{ + std::mt19937 my_rand (0); + Vrandom.reserve (NELEM); + for (uint32_t i = 0; i < NELEM; ++i) Vrandom.push_back (my_rand ( )); + + test1 ( ); + test2 ( ); + test3 ( ); + + return 0; +}; diff --git a/src/boost/libs/sort/test/test_flat_stable_sort.cpp b/src/boost/libs/sort/test/test_flat_stable_sort.cpp new file mode 100644 index 000000000..83aaaad5b --- /dev/null +++ b/src/boost/libs/sort/test/test_flat_stable_sort.cpp @@ -0,0 +1,140 @@ +//---------------------------------------------------------------------------- +/// @file test_flat_stable_sort.cpp +/// @brief test program of the flat_stable_sort algorithm +/// +/// @author Copyright (c) 2017 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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <algorithm> +#include <iostream> +#include <random> +#include <vector> +#include <ciso646> +#include <boost/sort/flat_stable_sort/flat_stable_sort.hpp> +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> + +using namespace boost::sort; + +void test1 ( ); +void test2 ( ); +void test3 ( ); + +//---------------- stability test ----------------------------------- +struct xk +{ + unsigned tail : 4; + unsigned num : 28; + xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){}; + bool operator< (xk A) const { return (num < A.num); }; +}; + +void test1 ( ) +{ + typedef typename std::vector< xk >::iterator iter_t; + typedef std::less< xk > compare_t; + std::mt19937_64 my_rand (0); + + const uint32_t NMAX = 100000; + + std::vector< xk > V1, V2; + V1.reserve (NMAX); + for (uint32_t i = 0; i < 8; ++i) { + for (uint32_t k = 0; k < NMAX; ++k) { + uint32_t NM = my_rand ( ); + xk G; + G.num = NM >> 3; + G.tail = i; + V1.push_back (G); + }; + }; + V2 = V1; + flat_stable_sort< iter_t, compare_t > (V1.begin ( ), V1.end ( ), compare_t ( )); + std::stable_sort (V2.begin ( ), V2.end ( )); + + BOOST_CHECK (V1.size ( ) == V2.size ( )); + for (uint32_t i = 0; i < V1.size ( ); ++i) { + BOOST_CHECK (V1[ i ].num == V2[ i ].num and + V1[ i ].tail == V2[ i ].tail); + }; +}; + +void test2 (void) +{ + typedef std::less< uint64_t > compare_t; + + const uint32_t NElem = 100000; + std::vector< uint64_t > V1,V2; + std::mt19937_64 my_rand (0); + compare_t comp; + + // ------------------------ random elements ------------------------------- + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (my_rand ( ) % NElem); + V2 = V1; + flat_stable_sort (V1.begin ( ), V1.end ( ), comp); + std::stable_sort (V2.begin ( ), V2.end ( ), comp); + for (unsigned i = 0; i < NElem; i++) { + BOOST_CHECK (V2[ i ] == V1[ i ]); + }; + + // --------------------------- sorted elements ---------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i); + flat_stable_sort (V1.begin ( ), V1.end ( ), comp); + for (unsigned i = 1; i < NElem; i++) { + BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //-------------------------- reverse sorted elements ---------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i); + flat_stable_sort (V1.begin ( ), V1.end ( ), comp); + for (unsigned i = 1; i < NElem; i++) { + BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //---------------------------- equal elements ---------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000); + flat_stable_sort (V1.begin ( ), V1.end ( ), comp); + for (unsigned i = 1; i < NElem; i++) { + BOOST_CHECK (V1[ i - 1 ] == V1[ i ]); + }; +}; + + +void test3 (void) +{ + typedef typename std::vector<xk>::iterator iter_t; + typedef std::less<xk> compare_t; + std::mt19937 my_rand (0); + std::vector<xk> V ; + const uint32_t NELEM = 100000; + V.reserve(NELEM * 10); + + + for (uint32_t k =0 ; k < 10 ; ++k) + { for ( uint32_t i =0 ; i < NELEM ; ++i) + { V.emplace_back(i , k); + }; + iter_t first = V.begin() + (k * NELEM); + iter_t last = first + NELEM ; + std::shuffle( first, last, my_rand); + }; + flat_stable_sort( V.begin() , V.end(), compare_t()); + for ( uint32_t i =0 ; i < ( NELEM * 10); ++i) + { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) ); + }; +} +int test_main (int, char *[]) +{ + test1 ( ); + test2 ( ); + test3 ( ); + return 0; +}; diff --git a/src/boost/libs/sort/test/test_insert_sort.cpp b/src/boost/libs/sort/test/test_insert_sort.cpp new file mode 100644 index 000000000..c2b93db87 --- /dev/null +++ b/src/boost/libs/sort/test/test_insert_sort.cpp @@ -0,0 +1,163 @@ +//---------------------------------------------------------------------------- +/// @file test_insert_sort.cpp +/// @brief Test program of the insert_sort algorithm +/// +/// @author Copyright (c) 2016 Francisco Jose 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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <ciso646> +#include <iostream> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include <vector> +#include <boost/sort/insert_sort/insert_sort.hpp> +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> + + +using namespace boost::sort; +using namespace std; +using boost::sort::common::util::insert_sorted; + +void test01 (void) +{ + unsigned A[] = {7, 4, 23, 15, 17, 2, 24, 13, 8, 3, 11, + 16, 6, 14, 21, 5, 1, 12, 19, 22, 25, 8}; + + std::less< unsigned > comp; + // Insertion Sort Unordered, not repeated + insert_sort (&A[ 0 ], &A[ 22 ], comp); + for (unsigned i = 0; i < 21; i++) { + BOOST_CHECK (A[ i ] <= A[ i + 1 ]); + }; + + unsigned B[] = {1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, + 13, 14, 15, 17, 18, 19, 20, 21, 23, 24, 25}; + // Insertion Sort Ordered, not repeated + insert_sort (&B[ 0 ], &B[ 22 ], comp); + for (unsigned i = 0; i < 21; i++) { + BOOST_CHECK (B[ i ] <= B[ i + 1 ]); + }; + + unsigned C[] = {27, 26, 25, 23, 22, 21, 19, 18, 17, 16, 15, + 14, 13, 11, 10, 9, 8, 7, 6, 5, 3, 2}; + // Insertion Sort reverse sorted, not repeated + insert_sort (&C[ 0 ], &C[ 22 ], comp); + for (unsigned i = 0; i < 21; i++) { + BOOST_CHECK (C[ i ] <= C[ i + 1 ]); + }; + + unsigned D[] = {4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, + 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}; + // Insertion Sort equal elements + insert_sort (&D[ 0 ], &D[ 22 ], comp); + for (unsigned i = 0; i < 21; i++) { + BOOST_CHECK (D[ i ] <= D[ i + 1 ]); + }; + + // Insertion Sort 100 random elements + unsigned F[ 100 ]; + for (unsigned i = 0; i < 100; i++) F[ i ] = rand ( ) % 1000; + insert_sort (&F[ 0 ], &F[ 100 ], comp); + for (unsigned i = 0; i < 99; i++) { + BOOST_CHECK (F[ i ] <= F[ i + 1 ]); + }; + + const unsigned NG = 10000; + // Insertion Sort "<<NG<<" random elements + unsigned G[ NG ]; + for (unsigned i = 0; i < NG; i++) G[ i ] = rand ( ) % 1000; + insert_sort (&G[ 0 ], &G[ NG ], comp); + for (unsigned i = 0; i < NG - 1; i++) { + BOOST_CHECK (G[ i ] <= G[ i + 1 ]); + }; +}; +void test02 (void) +{ + typedef typename std::vector< uint64_t >::iterator iter_t; + const uint32_t NELEM = 6667; + std::vector< uint64_t > A; + std::less< uint64_t > comp; + + for (uint32_t i = 0; i < 1000; ++i) A.push_back (0); + for (uint32_t i = 0; i < NELEM; ++i) A.push_back (NELEM - i); + for (uint32_t i = 0; i < 1000; ++i) A.push_back (0); + + insert_sort (A.begin ( ) + 1000, A.begin ( ) + (1000 + NELEM), comp); + + for (iter_t it = A.begin ( ) + 1000; it != A.begin ( ) + (1000 + NELEM); + ++it) + { + BOOST_CHECK ((*(it - 1)) <= (*it)); + }; + BOOST_CHECK (A[ 998 ] == 0 and A[ 999 ] == 0 and A[ 1000 + NELEM ] == 0 and + A[ 1001 + NELEM ] == 0); + + + A.clear ( ); + for (uint32_t i = 0; i < 1000; ++i) A.push_back (999999999); + for (uint32_t i = 0; i < NELEM; ++i) A.push_back (NELEM - i); + for (uint32_t i = 0; i < 1000; ++i) A.push_back (999999999); + + insert_sort (A.begin ( ) + 1000, A.begin ( ) + (1000 + NELEM), comp); + + for (iter_t it = A.begin ( ) + 1001; it != A.begin ( ) + (1000 + NELEM); + ++it) + { + BOOST_CHECK ((*(it - 1)) <= (*it)); + }; + BOOST_CHECK (A[ 998 ] == 999999999 and A[ 999 ] == 999999999 and + A[ 1000 + NELEM ] == 999999999 and + A[ 1001 + NELEM ] == 999999999); +}; + + +void test03 ( void) +{ + std::vector<uint32_t> V {1,3,5,2,4}; + std::less<uint32_t> comp ; + uint32_t aux[10] ; + + insert_sorted ( V.begin() , V.begin()+3, V.end(), comp, aux); + //insert_partial_sort ( V.begin() , V.begin()+3, V.end() , comp); + for ( uint32_t i =0 ; i < V.size() ; ++i) + std::cout<<V[i]<<", "; + std::cout<<std::endl; + + V ={3,5,7,9,11,13,15,17,19,8,6,10,4,2}; + insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux); + //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp); + for ( uint32_t i =0 ; i < V.size() ; ++i) + std::cout<<V[i]<<", "; + std::cout<<std::endl; + + V ={13,15,17,19,21,23,35,27,29,8,6,10,4,2}; + insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux); + //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp); + for ( uint32_t i =0 ; i < V.size() ; ++i) + std::cout<<V[i]<<", "; + std::cout<<std::endl; + + V ={3,5,7,9,11,13,15,17,19,28,26,30,24,22}; + insert_sorted ( V.begin() , V.begin()+9, V.end() , comp, aux); + //insert_partial_sort ( V.begin() , V.begin()+9, V.end() , comp); + for ( uint32_t i =0 ; i < V.size() ; ++i) + std::cout<<V[i]<<", "; + std::cout<<std::endl; + + + +} +int test_main (int, char *[]) +{ + test01 ( ); + test02 ( ); + test03 ( ); + return 0; +} diff --git a/src/boost/libs/sort/test/test_parallel_stable_sort.cpp b/src/boost/libs/sort/test/test_parallel_stable_sort.cpp new file mode 100644 index 000000000..6c1dace6f --- /dev/null +++ b/src/boost/libs/sort/test/test_parallel_stable_sort.cpp @@ -0,0 +1,183 @@ +//---------------------------------------------------------------------------- +/// @file test_parallel_stable_sort.cpp +/// @brief test program of the parallel_stable_sort algorithm +/// +/// @author Copyright (c) 2016 Francisco Jose 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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <ciso646> +#include <cstdio> +#include <cstdlib> +#include <ctime> +#include <vector> +#include <random> +#include <algorithm> +#include <boost/sort/parallel_stable_sort/parallel_stable_sort.hpp> +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> + +namespace bss = boost::sort; + + +struct xk +{ + unsigned tail : 4; + unsigned num : 28; + xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){}; + bool operator< (xk A) const { return (num < A.num); }; +}; +void test1() +{ + + std::mt19937_64 my_rand(0); + + const uint32_t NMAX = 100000; + + std::vector<xk> V1, V2, V3; + V1.reserve(NMAX); + for (uint32_t i = 0; i < 8; ++i) + { + for (uint32_t k = 0; k < NMAX; ++k) + { uint32_t NM = my_rand(); + xk G; + G.num = NM >> 3; + G.tail = i; + V1.push_back(G); + }; + }; + V3 = V2 = V1; + bss::parallel_stable_sort(V1.begin(), V1.end()); + std::stable_sort(V2.begin(), V2.end()); + bss::parallel_stable_sort(V3.begin(), V3.end(), 0); + + BOOST_CHECK(V1.size() == V2.size()); + for (uint32_t i = 0; i < V1.size(); ++i) + { BOOST_CHECK(V1[i].num == V2[i].num and V1[i].tail == V2[i].tail); + }; + + BOOST_CHECK(V3.size() == V2.size()); + for (uint32_t i = 0; i < V3.size(); ++i) + { BOOST_CHECK(V3[i].num == V2[i].num and V3[i].tail == V2[i].tail); + }; +}; + +void test2(void) +{ + const uint32_t NElem = 2000000; + std::vector<uint64_t> V1; + + // ----------------- sorted elements ------------------------------------ + V1.clear(); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(i); + bss::parallel_stable_sort(V1.begin(), V1.end()); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK(V1[i - 1] <= V1[i]); + }; + + // ------------- reverse sorted elements -------------------------------- + V1.clear(); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(NElem - i); + bss::parallel_stable_sort(V1.begin(), V1.end()); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK(V1[i - 1] <= V1[i]); + }; + + // -------------------- equals elements ----------------------------------- + V1.clear(); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(1000); + bss::parallel_stable_sort(V1.begin(), V1.end()); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK(V1[i - 1] == V1[i]); + }; +}; +void test3(void) +{ + const uint32_t NElem = 2000000; + std::vector<uint64_t> V1,V2,V3; + std::mt19937_64 my_rand(0); + + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(my_rand() % NElem); + V3 = V2 = V1; + std::stable_sort (V2.begin(), V2.end()); + + + // --------------- unsorted elements 0 threads ---------------------------- + V3 = V1; + bss::parallel_stable_sort(V3.begin(), V3.end(), 0); + for (unsigned i = 0; i < NElem; i++) + { BOOST_CHECK(V3[i] == V2[i]); + }; + + // --------------- unsorted elements ------------------------------------- + V3 = V1; + bss::parallel_stable_sort(V3.begin(), V3.end()); + for (unsigned i = 0; i < NElem; i++) + { BOOST_CHECK(V3[i] == V2[i]); + }; + + // --------------- unsorted elements 100 threads ---------------------------- + V3 = V1; + bss::parallel_stable_sort(V3.begin(), V3.end(), 100); + for (unsigned i = 0; i < NElem; i++) + { BOOST_CHECK(V3[i] == V2[i]); + }; +}; + +void test4(void) +{ + typedef std::less<uint64_t> compare; + const uint32_t KMax = 66000; + + std::vector<uint64_t> K, M; + std::mt19937_64 my_rand(0); + + for (uint32_t i = 0; i < KMax; ++i) + K.push_back(my_rand()); + M = K; + + bss::parallel_stable_sort(K.begin(), K.end(), compare(), 300); + + std::stable_sort(M.begin(), M.end(), compare()); + for (unsigned i = 0; i < KMax; i++) + BOOST_CHECK(M[i] == K[i]); +}; + +void test5 (void) +{ + typedef typename std::vector<xk>::iterator iter_t; + std::mt19937 my_rand (0); + std::vector<xk> V ; + const uint32_t NELEM = 100000; + V.reserve(NELEM * 10); + + + for (uint32_t k =0 ; k < 10 ; ++k) + { for ( uint32_t i =0 ; i < NELEM ; ++i) + { V.emplace_back(i , k); + }; + iter_t first = V.begin() + (k * NELEM); + iter_t last = first + NELEM ; + std::shuffle( first, last, my_rand); + }; + bss::parallel_stable_sort( V.begin() , V.end()); + for ( uint32_t i =0 ; i < ( NELEM * 10); ++i) + { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) ); + }; +} + + +int test_main(int, char *[]) +{ + test1(); + test2(); + test3(); + test4(); + test5(); + return 0; +}; + diff --git a/src/boost/libs/sort/test/test_pdqsort.cpp b/src/boost/libs/sort/test/test_pdqsort.cpp new file mode 100644 index 000000000..d82bf4eaf --- /dev/null +++ b/src/boost/libs/sort/test/test_pdqsort.cpp @@ -0,0 +1,163 @@ +// Boost Sort library test_pdqsort.cpp file ----------------------------// + +// Copyright Orson Peters 2017. Use, modification and +// distribution is subject to 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/sort for library home page. + + +#include <vector> +#include <string> +#include <random> + +#include <boost/sort/pdqsort/pdqsort.hpp> +// Include unit test framework +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> + + +// Gives a vector containing strings with the same order. +std::string u32_to_str(uint32_t n) { + std::string r; + for (int i = 0; i < 32; ++i) { + r = char('0' + (n & 1)) + r; + n >>= 1; + } + return r; +} + +std::vector<std::string> vec_u32_to_str(const std::vector<uint32_t>& v) { + std::vector<std::string> r; r.reserve(v.size()); + for (size_t i = 0; i < v.size(); ++i) { + r.push_back(u32_to_str(v[i])); + } + return r; +} + + +// Distributions. +std::vector<uint32_t> shuffled(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = 0; i < size; ++i) v.push_back(i); + std::shuffle(v.begin(), v.end(), rng); + return v; +} + +std::vector<uint32_t> shuffled_16_values(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = 0; i < size; ++i) v.push_back(i % 16); + std::shuffle(v.begin(), v.end(), rng); + return v; +} + +std::vector<uint32_t> all_equal(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = 0; i < size; ++i) v.push_back(0); + return v; +} + +std::vector<uint32_t> ascending(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = 0; i < size; ++i) v.push_back(i); + return v; +} + +std::vector<uint32_t> descending(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = size - 1; ; --i) { + v.push_back(i); + if (i == 0) break; + } + return v; +} + +std::vector<uint32_t> pipe_organ(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = 0; i < size/2; ++i) v.push_back(i); + for (uint32_t i = size/2; i < size; ++i) v.push_back(size - i); + return v; +} + +std::vector<uint32_t> push_front(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = 1; i < size; ++i) v.push_back(i); + v.push_back(0); + return v; +} + +std::vector<uint32_t> push_middle(size_t size, std::mt19937_64& rng) { + std::vector<uint32_t> v; v.reserve(size); + for (uint32_t i = 0; i < size; ++i) { + if (i != size/2) v.push_back(i); + } + v.push_back(size/2); + return v; +} + + +// Tests. +typedef std::vector<uint32_t> (*DistrF)(size_t, std::mt19937_64&); +void execute_test(DistrF distr, std::string distr_name, int repeats) { + // In C++14 we'd just use std::less<>(). + std::less<uint32_t> u32less; + std::greater<uint32_t> u32greater; + std::less<std::string> sless; + std::greater<std::string> sgreater; + + for (size_t sz = 1; sz <= 1000; sz *= 10) { + // Consistent but pseudorandom tests. + std::mt19937_64 rng; rng.seed(0); + + for (int i = 0; i < repeats; ++i) { + std::vector<uint32_t> u32l = distr(sz, rng); + std::vector<uint32_t> u32g = u32l; + std::vector<std::string> sl = vec_u32_to_str(u32l); + std::vector<std::string> sg = sl; + + boost::sort::pdqsort(u32l.begin(), u32l.end(), u32less); + boost::sort::pdqsort(u32g.begin(), u32g.end(), u32greater); + boost::sort::pdqsort(sl.begin(), sl.end(), sless); + boost::sort::pdqsort(sg.begin(), sg.end(), sgreater); + + BOOST_CHECK_MESSAGE( + std::is_sorted(u32l.begin(), u32l.end(), u32less), + "pdqsort<uint32_t, std::less> " + distr_name + " failed with size " + std::to_string(sz) + ); + + BOOST_CHECK_MESSAGE( + std::is_sorted(u32g.begin(), u32g.end(), u32greater), + "pdqsort<uint32_t, std::greater> " + distr_name + " failed with size " + std::to_string(sz) + ); + + BOOST_CHECK_MESSAGE( + std::is_sorted(sl.begin(), sl.end(), sless), + "pdqsort<std::string, std::less> " + distr_name + " failed with size " + std::to_string(sz) + ); + + BOOST_CHECK_MESSAGE( + std::is_sorted(sg.begin(), sg.end(), sgreater), + "pdqsort<std::string, std::greater> " + distr_name + " failed with size " + std::to_string(sz) + ); + } + } +} + + +// test main +int test_main(int argc, char** argv) { + // No unused warning. + (void) argc; (void) argv; + + execute_test(shuffled, "shuffled", 100); + execute_test(shuffled_16_values, "shuffled_16_values", 100); + execute_test(all_equal, "all_equal", 1); + execute_test(ascending, "ascending", 1); + execute_test(descending, "descending", 1); + execute_test(pipe_organ, "pipe_organ", 1); + execute_test(push_front, "push_front", 1); + execute_test(push_middle, "push_middle", 1); + + return 0; +} diff --git a/src/boost/libs/sort/test/test_sample_sort.cpp b/src/boost/libs/sort/test/test_sample_sort.cpp new file mode 100644 index 000000000..a83634f24 --- /dev/null +++ b/src/boost/libs/sort/test/test_sample_sort.cpp @@ -0,0 +1,181 @@ +//---------------------------------------------------------------------------- +/// @file test_sample_sort.cpp +/// @brief test sample_sort algorithm +/// +/// @author Copyright (c) 2016 Francisco Jose 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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <ciso646> +#include <cstdlib> +#include <ctime> +#include <algorithm> +#include <vector> +#include <random> +#include <boost/sort/sample_sort/sample_sort.hpp> +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> + +namespace bss = boost::sort; + + +struct xk +{ + unsigned tail : 4; + unsigned num : 28; + xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){}; + bool operator< (xk A) const { return (num < A.num); }; +}; +void test1() +{ + + std::mt19937_64 my_rand(0); + + const uint32_t NMAX = 100000; + + std::vector<xk> V1, V2, V3; + V1.reserve(NMAX); + for (uint32_t i = 0; i < 8; ++i) + { + for (uint32_t k = 0; k < NMAX; ++k) + { uint32_t NM = my_rand(); + xk G; + G.num = NM >> 3; + G.tail = i; + V1.push_back(G); + }; + }; + V3 = V2 = V1; + bss::sample_sort(V1.begin(), V1.end()); + std::stable_sort(V2.begin(), V2.end()); + bss::sample_sort(V3.begin(), V3.end(), 0); + + BOOST_CHECK(V1.size() == V2.size()); + for (uint32_t i = 0; i < V1.size(); ++i) + { BOOST_CHECK(V1[i].num == V2[i].num and V1[i].tail == V2[i].tail); + }; + + BOOST_CHECK(V3.size() == V2.size()); + for (uint32_t i = 0; i < V3.size(); ++i) + { BOOST_CHECK(V3[i].num == V2[i].num and V3[i].tail == V2[i].tail); + }; +}; + +void test2(void) +{ + const uint32_t NElem = 2000000; + std::vector<uint64_t> V1; + + // ----------------- sorted elements ------------------------------------ + V1.clear(); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(i); + bss::sample_sort(V1.begin(), V1.end()); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK(V1[i - 1] <= V1[i]); + }; + + // ------------- reverse sorted elements -------------------------------- + V1.clear(); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(NElem - i); + bss::sample_sort(V1.begin(), V1.end()); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK(V1[i - 1] <= V1[i]); + }; + + // -------------------- equals elements ----------------------------------- + V1.clear(); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(1000); + bss::sample_sort(V1.begin(), V1.end()); + for (unsigned i = 1; i < NElem; i++) + { BOOST_CHECK(V1[i - 1] == V1[i]); + }; +}; +void test3(void) +{ + typedef std::less<uint64_t> compare; + const uint32_t NElem = 2000000; + std::vector<uint64_t> V1,V2,V3; + std::mt19937_64 my_rand(0); + + for (uint32_t i = 0; i < NElem; ++i) V1.push_back(my_rand() % NElem); + V3 = V2 = V1; + std::stable_sort (V2.begin(), V2.end()); + + + // --------------- unsorted elements 0 threads ---------------------------- + V3 = V1; + bss::sample_sort(V3.begin(), V3.end(), compare(), 0); + for (unsigned i = 0; i < NElem; i++) + { BOOST_CHECK(V3[i] == V2[i]); + }; + + // --------------- unsorted elements ------------------------------------- + V3 = V1; + bss::sample_sort(V3.begin(), V3.end(), compare()); + for (unsigned i = 0; i < NElem; i++) + { BOOST_CHECK(V3[i] == V2[i]); + }; + + // --------------- unsorted elements 100 threads ---------------------------- + V3 = V1; + bss::sample_sort(V3.begin(), V3.end(), compare(), 100); + for (unsigned i = 0; i < NElem; i++) + { BOOST_CHECK(V3[i] == V2[i]); + }; +}; + +void test4(void) +{ + const uint32_t KMax = 66000; + + std::vector<uint64_t> K, M; + std::mt19937_64 my_rand(0); + + for (uint32_t i = 0; i < KMax; ++i) + K.push_back(my_rand()); + M = K; + + bss::sample_sort(K.begin(), K.end(), 300); + + std::stable_sort(M.begin(), M.end()); + for (unsigned i = 0; i < KMax; i++) + BOOST_CHECK(M[i] == K[i]); +}; + +void test5 (void) +{ + typedef typename std::vector<xk>::iterator iter_t; + std::mt19937 my_rand (0); + std::vector<xk> V ; + const uint32_t NELEM = 100000; + V.reserve(NELEM * 10); + + + for (uint32_t k =0 ; k < 10 ; ++k) + { for ( uint32_t i =0 ; i < NELEM ; ++i) + { V.emplace_back(i , k); + }; + iter_t first = V.begin() + (k * NELEM); + iter_t last = first + NELEM ; + std::shuffle( first, last, my_rand); + }; + bss::sample_sort( V.begin() , V.end()); + for ( uint32_t i =0 ; i < ( NELEM * 10); ++i) + { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) ); + }; +} + + +int test_main(int, char *[]) +{ + test1(); + test2(); + test3(); + test4(); + test5(); + return 0; +}; diff --git a/src/boost/libs/sort/test/test_spinsort.cpp b/src/boost/libs/sort/test/test_spinsort.cpp new file mode 100644 index 000000000..b8e2f268f --- /dev/null +++ b/src/boost/libs/sort/test/test_spinsort.cpp @@ -0,0 +1,180 @@ +//---------------------------------------------------------------------------- +/// @file test_spinsort.cpp +/// @brief test program of the spinsort algorithm +/// +/// @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 ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#include <ciso646> +#include <algorithm> +#include <iostream> +#include <cstdio> +#include <cstdlib> +#include <ctime> +#include <vector> +#include <random> +#include <boost/sort/spinsort/spinsort.hpp> +#include <boost/test/included/test_exec_monitor.hpp> +#include <boost/test/test_tools.hpp> + + +using namespace boost::sort; +using spin_detail::check_stable_sort; +using spin_detail::range_sort; +using common::range; + +void test1 ( ); +void test2 ( ); +void test3 ( ); +void test4 ( ); + +//---------------- stability test ----------------------------------- +struct xk +{ + unsigned tail : 4; + unsigned num : 28; + xk ( uint32_t n =0 , uint32_t t =0): tail (t), num(n){}; + bool operator< (xk A) const { return (num < A.num); }; +}; + +void test1 ( ) +{ + typedef std::less< xk > compare_t; + std::mt19937_64 my_rand (0); + + const uint32_t NMAX = 100000; + + std::vector< xk > V1, V2; + V1.reserve (NMAX); + for (uint32_t i = 0; i < 8; ++i) { + for (uint32_t k = 0; k < NMAX; ++k) { + uint32_t NM = my_rand ( ); + xk G; + G.num = NM >> 3; + G.tail = i; + V1.push_back (G); + }; + }; + V2 = V1; + spinsort (V1.begin ( ), V1.end ( ), compare_t ( )); + std::stable_sort (V2.begin ( ), V2.end ( )); + + BOOST_CHECK (V1.size ( ) == V2.size ( )); + for (uint32_t i = 0; i < V1.size ( ); ++i) { + BOOST_CHECK (V1[ i ].num == V2[ i ].num and + V1[ i ].tail == V2[ i ].tail); + }; +}; + +void test2 (void) +{ + typedef std::less< uint64_t > compare_t; + + const uint32_t NElem = 100000; + std::vector< uint64_t > V1,V2; + std::mt19937_64 my_rand (0); + compare_t comp; + + // ------------------------ random elements ------------------------------- + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (my_rand ( ) % NElem); + V2 = V1; + spinsort (V1.begin ( ), V1.end ( ), comp); + std::stable_sort (V2.begin ( ), V2.end ( ), comp); + for (unsigned i = 0; i < NElem; i++) { + BOOST_CHECK (V2[ i ] == V1[ i ]); + }; + + // --------------------------- sorted elements ---------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (i); + spinsort (V1.begin ( ), V1.end ( ), comp); + for (unsigned i = 1; i < NElem; i++) { + BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //-------------------------- reverse sorted elements ---------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (NElem - i); + spinsort (V1.begin ( ), V1.end ( ), comp); + for (unsigned i = 1; i < NElem; i++) { + BOOST_CHECK (V1[ i - 1 ] <= V1[ i ]); + }; + + //---------------------------- equal elements ---------------------------- + V1.clear ( ); + for (uint32_t i = 0; i < NElem; ++i) V1.push_back (1000); + spinsort (V1.begin ( ), V1.end ( ), comp); + for (unsigned i = 1; i < NElem; i++) { + BOOST_CHECK (V1[ i - 1 ] == V1[ i ]); + }; +}; + + +void test3 (void) +{ + typedef typename std::vector<uint64_t>::iterator iter_t ; + typedef range<iter_t> range_it ; + std::less<uint64_t> comp ; + + std::vector<uint64_t> V = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, + 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, + 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, + 14, 2, 4, 6, 8, 10, 12, 16, 18, 20}; + range_it rdata (V.begin() , V.end()); + std::vector<uint64_t> aux (40,0 ); + range_it raux ( aux.begin() , aux.end()); + + check_stable_sort ( rdata, raux, comp ); + for ( uint32_t i =0 ; i < V.size() ; ++i) + std::cout<<V[i]<<", "; + std::cout<<std::endl; + + V = {59, 57, 55, 53, 51, 49, 47, 45, 43, 41, + 39, 37, 35, 33, 31, 29, 27, 25, 23, 21, + 19, 17, 15, 13, 11, 9, 7, 5, 3, 1, + 14, 2, 6, 16, 18, 20, 12, 4, 8, 10}; + rdata = range_it (V.begin() , V.end()); + aux.assign (40,0); + raux = range_it ( aux.begin() , aux.end()); + check_stable_sort ( rdata, raux, comp ); + for ( uint32_t i =0 ; i < V.size() ; ++i) + std::cout<<V[i]<<", "; + std::cout<<std::endl; + +} +void test4 (void) +{ + typedef typename std::vector<xk>::iterator iter_t; + typedef std::less<xk> compare_t; + std::mt19937 my_rand (0); + std::vector<xk> V ; + const uint32_t NELEM = 100000; + V.reserve(NELEM * 10); + + + for (uint32_t k =0 ; k < 10 ; ++k) + { for ( uint32_t i =0 ; i < NELEM ; ++i) + { V.emplace_back(i , k); + }; + iter_t first = V.begin() + (k * NELEM); + iter_t last = first + NELEM ; + std::shuffle( first, last, my_rand); + }; + spinsort( V.begin() , V.end(), compare_t()); + for ( uint32_t i =0 ; i < ( NELEM * 10); ++i) + { BOOST_CHECK ( V[i].num == (i / 10) and V[i].tail == (i %10) ); + }; +} +int test_main (int, char *[]) +{ + test1 ( ); + test2 ( ); + test3 ( ); + test4 ( ); + return 0; +}; diff --git a/src/boost/libs/sort/tune.pl b/src/boost/libs/sort/tune.pl new file mode 100755 index 000000000..598f1a9ca --- /dev/null +++ b/src/boost/libs/sort/tune.pl @@ -0,0 +1,359 @@ +#!/usr/bin/perl -w +# Copyright Steven J. Ross 2008 - 2014 +# 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/sort for library home page. + +# A speed and accuracy testing and automated parameter tuning script. + +$usage = "usage: tune.pl [-tune] [-real] [-tune_verify] [-verbose] [-multiple_iterations] [-large] [-small] [-windows] [fileSize]\n"; +# testing sorting on 40 million elements by default +# don't test on below 2^22 (4 million) elements as that is the minimum +# for max_splits of 11 to be efficient +use File::Compare; +$defFileSize = 5000000; +$loopCount = 1; +$realtimes = 0; +$verifycorrect = 0; +$verbose = 0; +$exename = "spreadsort"; +$makename = "../../b2 \-\-tune"; +$all = ""; +$iter_count = 1; +$debug = 0; +$log = "> .tunelog"; +$log2 = "> .tunelog 2>&1"; +$diffopt = "-q"; +$tune = 0; +# have to change the path for UNIX +$prev_path = $ENV{'PATH'}; +$ENV{'PATH'} = '.:'.$prev_path; + +for (my $ii = 0; $ii < @ARGV; $ii++) { + my $currArg = $ARGV[$ii]; + if ($currArg =~ /^-help$/) { + print STDERR $usage; + exit(0); + } + # verification roughly doubles the runtime of this script, + # but it does make sure that results are correct during tuning + # verification always runs during speed comparisons with std::sort + if ($currArg =~ /^-tune_verify$/) { + $verifycorrect = 1; + # use real times only, don't use weighting and special-case tests + # this saves about 5/6 of the script runtime but results are different + } elsif ($currArg =~ /^-real$/) { + $realtimes = 1; + } elsif ($currArg =~ /^-verbose$/) { + $verbose = 1; + # runs until we converge on a precise set of values + # defaults off because of runtime + } elsif ($currArg =~ /^-multiple_iterations$/) { + $iter_count = 4; + } elsif ($currArg =~ /^-debug$/) { + $debug = 1; + $log = ""; + $diffopt = ""; + } elsif ($currArg =~ /^-large$/) { + $defFileSize = 20000000; + } elsif ($currArg =~ /^-small$/) { + $defFileSize = 100000; + } elsif ($currArg =~ /^-tune$/) { + $tune = 1; + } elsif ($currArg =~ /^-windows$/) { + $makename = "..\\..\\".$makename; + } elsif ($currArg =~ /^-/) { + print STDERR $usage; + exit(0); + } else { + $defFileSize = $currArg; + } +} +$fileSize = $defFileSize; + +print STDOUT "Tuning variables for $exename on vectors with $defFileSize elements\n"; + +# these are reasonable values +$max_splits = 11; +$log_finishing_count = 31; +$log_min_size = 11; +$log_mean_bin_size = 2; +$float_log_min_size = 10; +$float_log_mean_bin_size = 2; +$float_log_finishing_count = 4; + +# this value is a minimum to obtain decent file I/O performance +$min_sort_size = 1000; +$std = ""; + +print STDOUT "building randomgen\n"; +system("$makename randomgen $log"); +# Tuning to get convergence, maximum of 4 iterations with multiple iterations +# option set +$changed = 1; +my $ii = 0; +if ($tune) { + for ($ii = 0; $changed and $ii < $iter_count; $ii++) { + $changed = 0; + # Tuning max_splits is not recommended. + #print STDOUT "Tuning max_splits\n"; + #TuneVariable(\$max_splits, $log_min_size - $log_mean_bin_size, 17); + print STDOUT "Tuning log of the minimum count for recursion\n"; + TuneVariable(\$log_min_size, $log_mean_bin_size + 1, $max_splits + $log_mean_bin_size); + print STDOUT "Tuning log_mean_bin_size\n"; + TuneVariable(\$log_mean_bin_size, 0, $log_min_size - 1); + print STDOUT "Tuning log_finishing_size\n"; + TuneVariable(\$log_finishing_count, 1, $log_min_size); + # tuning variables for floats + $exename = "floatsort"; + print STDOUT "Tuning log of the minimum count for recursion for floats\n"; + TuneVariable(\$float_log_min_size, $float_log_mean_bin_size + 1, $max_splits + $float_log_mean_bin_size); + print STDOUT "Tuning float_log_mean_bin_size\n"; + TuneVariable(\$float_log_mean_bin_size, 0, $float_log_min_size - 1); + print STDOUT "Tuning float_log_finishing_size\n"; + TuneVariable(\$float_log_finishing_count, 1, $float_log_min_size); + $exename = "spreadsort"; + } + + # After optimizations for large datasets are complete, see how small of a + # dataset can be sped up + print STDOUT "Tuning minimum sorting size\n"; + TuneMinSize(); + print STDOUT "Writing results\n"; +} + +# Doing a final run with final settings to compare sort times +# also verifying correctness of results +$verifycorrect = 1; +$loopCount = 1; +$fileSize = $defFileSize; +system("$makename $all $log"); +$std = ""; +PerfTest("Verifying integer_sort", "spreadsort"); +PerfTest("Verifying float_sort", "floatsort"); +PerfTest("Verifying string_sort", "stringsort"); +PerfTest("Verifying integer_sort with mostly-sorted data", "mostlysorted"); +PerfTest("Timing integer_sort on already-sorted data", "alreadysorted"); +PerfTest("Verifying integer_sort with rightshift", "rightshift"); +PerfTest("Verifying integer_sort with 64-bit integers", "int64"); +PerfTest("Verifying integer_sort with separate key and data", "keyplusdata"); +PerfTest("Verifying reverse integer_sort", "reverseintsort"); +PerfTest("Verifying float_sort with doubles", "double"); +PerfTest("Verifying float_sort with shift functor", "shiftfloatsort"); +PerfTest("Verifying float_sort with functors", "floatfunctorsort"); +PerfTest("Verifying string_sort with indexing functors", "charstringsort"); +PerfTest("Verifying string_sort with all functors", "stringfunctorsort"); +PerfTest("Verifying reverse_string_sort", "reversestringsort"); +PerfTest("Verifying reverse_string_sort with functors", + "reversestringfunctorsort"); +PerfTest("Verifying generalized string_sort with multiple keys of different types", + "generalizedstruct"); +PerfTest("Verifying boost::sort on its custom-built worst-case distribution", + "binaryalrbreaker"); +# clean up once we finish +system("$makename clean $log"); +# WINDOWS +system("del spread_sort_out.txt $log2"); +system("del standard_sort_out.txt $log2"); +system("del input.txt $log2"); +system("del *.rsp $log2"); +system("del *.manifest $log2"); +system("del time.txt $log2"); +# UNIX +system("rm -f time.txt $log2"); +system("rm -f spread_sort_out.txt $log2"); +system("rm -f standard_sort_out.txt $log2"); +system("rm -f input.txt $log2"); + +$ENV{'PATH'} = $prev_path; + +# A simple speed test comparing std::sort to +sub PerfTest { + my ($message, $local_exe) = @_; + $exename = $local_exe; + print STDOUT "$message\n"; + $lastTime = SumTimes(); + print STDOUT "runtime: $lastTime\n"; + print STDOUT "std::sort time: $baseTime\n"; + $speedup = (($baseTime/$lastTime) - 1) * 100; + print STDOUT "speedup: ".sprintf("%.2f", $speedup)."%\n"; +} + +# Write an updated constants file as part of tuning. +sub WriteConstants { + # deleting the file + $const_file = 'include/boost/sort/spreadsort/detail/constants.hpp'; + @cannot = grep {not unlink} $const_file; + print "$0: could not unlink @cannot\n" if @cannot; + + # writing the results back to the original file name + unless(open(CONSTANTS, ">$const_file")) { + print STDERR "Can't open output file: $const_file: $!\n"; + exit; + } + print CONSTANTS "//constant definitions for the Boost Sort library\n\n"; + print CONSTANTS "// Copyright Steven J. Ross 2001 - 2014\n"; + print CONSTANTS "// Distributed under the Boost Software License, Version 1.0.\n"; + print CONSTANTS "// (See accompanying file LICENSE_1_0.txt or copy at\n"; + print CONSTANTS "// http://www.boost.org/LICENSE_1_0.txt)\n\n"; + print CONSTANTS "// See http://www.boost.org/libs/sort for library home page.\n"; + print CONSTANTS "#ifndef BOOST_SORT_SPREADSORT_DETAIL_CONSTANTS\n"; + print CONSTANTS "#define BOOST_SORT_SPREADSORT_DETAIL_CONSTANTS\n"; + print CONSTANTS "namespace boost {\n"; + print CONSTANTS "namespace sort {\n"; + print CONSTANTS "namespace spreadsort {\n"; + print CONSTANTS "namespace detail {\n"; + print CONSTANTS "//Tuning constants\n"; + print CONSTANTS "//This should be tuned to your processor cache;\n"; + print CONSTANTS "//if you go too large you get cache misses on bins\n"; + print CONSTANTS "//The smaller this number, the less worst-case memory usage.\n"; + print CONSTANTS "//If too small, too many recursions slow down spreadsort\n"; + print CONSTANTS "enum { max_splits = $max_splits,\n"; + print CONSTANTS "//It's better to have a few cache misses and finish sorting\n"; + print CONSTANTS "//than to run another iteration\n"; + print CONSTANTS "max_finishing_splits = max_splits + 1,\n"; + print CONSTANTS "//Sets the minimum number of items per bin.\n"; + print CONSTANTS "int_log_mean_bin_size = $log_mean_bin_size,\n"; + print CONSTANTS "//Used to force a comparison-based sorting for small bins, if it's faster.\n"; + print CONSTANTS "//Minimum value 1\n"; + $log_min_split_count = $log_min_size - $log_mean_bin_size; + print CONSTANTS "int_log_min_split_count = $log_min_split_count,\n"; + print CONSTANTS "//This is the minimum split count to use spreadsort when it will finish in one\n"; + print CONSTANTS "//iteration. Make this larger the faster std::sort is relative to integer_sort.\n"; + print CONSTANTS "int_log_finishing_count = $log_finishing_count,\n"; + print CONSTANTS "//Sets the minimum number of items per bin for floating point.\n"; + print CONSTANTS "float_log_mean_bin_size = $float_log_mean_bin_size,\n"; + print CONSTANTS "//Used to force a comparison-based sorting for small bins, if it's faster.\n"; + print CONSTANTS "//Minimum value 1\n"; + $float_log_min_split_count = $float_log_min_size - $float_log_mean_bin_size; + print CONSTANTS "float_log_min_split_count = $float_log_min_split_count,\n"; + print CONSTANTS "//This is the minimum split count to use spreadsort when it will finish in one\n"; + print CONSTANTS "//iteration. Make this larger the faster std::sort is relative to float_sort.\n"; + print CONSTANTS "float_log_finishing_count = $float_log_finishing_count,\n"; + print CONSTANTS "//There is a minimum size below which it is not worth using spreadsort\n"; + print CONSTANTS "min_sort_size = $min_sort_size };\n"; + print CONSTANTS "}\n}\n}\n}\n#endif\n"; + close CONSTANTS; + system("$makename $exename $log"); +} + +# Sort the file with both std::sort and boost::sort, verify the results are the +# same, update stdtime with std::sort time, and return boost::sort time. +sub CheckTime { + my $sort_time = 0.0; + my $time_file = "time.txt"; + # use the line below on systems that can't overwrite. + #system("rm -f $time_file"); + system("$exename $loopCount $std > $time_file"); + unless(open(CODE, $time_file)) { + print STDERR "Could not open file: $time_file: $!\n"; + exit; + } + while ($line = <CODE>) { + @parts = split("time", $line); + if (@parts > 1) { + $sort_time = $parts[1]; + last; + } + } + close(CODE); + # verifying correctness + if (not $std and $verifycorrect) { + system("$exename $loopCount -std > $time_file"); + unless(open(CODE, $time_file)) { + print STDERR "Could not open file: $time_file: $!\n"; + exit; + } + die "Difference in results\n" unless (compare("boost_sort_out.txt","standard_sort_out.txt") == 0) ; + while ($line = <CODE>) { + @parts = split("time", $line); + if (@parts > 1) { + $stdsingle = $parts[1]; + last; + } + } + close(CODE); + } + return $sort_time; +} + +# Sum up times for different data distributions. If realtimes is not set, +# larger ranges are given a larger weight. +sub SumTimes { + my $time = 0; + $baseTime = 0.0; + $stdsingle = 0.0; + my $ii = 1; + # if we're only using real times, don't bother with the corner-cases + if ($realtimes) { + $ii = 8; + } + for (; $ii <= 16; $ii++) { + system("randomgen $ii $ii $fileSize"); + if ($realtimes) { + $time += CheckTime(); + $baseTime += $stdsingle; + } else { + # tests with higher levels of randomness are given + # higher priority in timing results + print STDOUT "trying $ii $ii\n" if $debug; + $time += 2 * $ii * CheckTime(); + $baseTime += 2 * $ii * $stdsingle; + if ($ii > 1) { + print STDOUT "trying 1 $ii\n" if $debug; + system("randomgen 1 $ii $fileSize"); + $time += $ii * CheckTime(); + $baseTime += $ii * $stdsingle; + print STDOUT "trying $ii 1\n" if $debug; + system("randomgen $ii 1 $fileSize"); + $time += $ii * CheckTime(); + $baseTime += $ii * $stdsingle; + } + } + } + if ($time == 0.0) { + $time = 0.01; + } + return $time; +} + +# Tests a range of potential values for a variable, and sets it to the fastest. +sub TuneVariable { + my ($tunevar, $beginval, $endval) = @_; + my $best_val = $$tunevar; + my $besttime = 0; + my $startval = $$tunevar; + for ($$tunevar = $beginval; $$tunevar <= $endval; $$tunevar++) { + WriteConstants(); + $sumtime = SumTimes(); + # If this value is better, use it. If this is the start value + # and it's just as good, use the startval + if (not $besttime or ($sumtime < $besttime) or (($besttime == $sumtime) and ($$tunevar == $startval))) { + $besttime = $sumtime; + $best_val = $$tunevar; + } + print STDOUT "Value: $$tunevar Time: $sumtime\n" if $verbose; + } + $$tunevar = $best_val; + print STDOUT "Best Value: $best_val\n"; + if ($best_val != $startval) { + $changed = 1; + } +} + +# Determine the cutoff size below which std::sort is faster. +sub TuneMinSize { + for (; $min_sort_size <= $defFileSize; $min_sort_size *= 2) { + $loopCount = ($defFileSize/$min_sort_size)/10; + $fileSize = $min_sort_size; + WriteConstants(); + $std = ""; + $sumtime = SumTimes(); + $std = "-std"; + $stdtime = SumTimes(); + print STDOUT "Size: $min_sort_size boost::sort Time: $sumtime std::sort Time: $stdtime\n"; + last if ($stdtime > $sumtime); + } +} |