ceph/src/boost/libs/sort/benchmark/single/benchmark_numbers.cpp

   1 //----------------------------------------------------------------------------
   2 /// @file benchmark_numbers.cpp
   3 /// @brief Benchmark of several sort methods with integer objects
   4 ///
   5 /// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n
   6 ///         Distributed under the Boost Software License, Version 1.0.\n
   7 ///         ( See accompanying file LICENSE_1_0.txt or copy at
   8 ///           http://www.boost.org/LICENSE_1_0.txt )
   9 ///
  10 ///         This program use for comparison purposes, the Threading Building
  11 ///         Blocks which license is the GNU General Public License, version 2
  12 ///         as  published  by  the  Free Software Foundation.
  13 ///
  14 /// @version 0.1
  15 ///
  16 /// @remarks
  17 //-----------------------------------------------------------------------------
  18 #include <algorithm>
  19
  20 #include <iostream>
  21 #include <iomanip>
  22 #include <random>
  23 #include <stdlib.h>
  24 #include <vector>
  25
  26 #include <boost/sort/common/time_measure.hpp>
  27 #include <boost/sort/common/file_vector.hpp>
  28 #include <boost/sort/common/int_array.hpp>
  29
  30 #include <boost/sort/sort.hpp>
  31
  32 #define NELEM 100000000
  33
  34 using namespace std;
  35 namespace bsort = boost::sort;
  36 namespace bsc = boost::sort::common;
  37
  38 using bsc::time_point;
  39 using bsc::now;
  40 using bsc::subtract_time;
  41 using bsc::fill_vector_uint64;
  42 using bsc::write_file_uint64;
  43
  44 using bsort::spinsort;
  45 using bsort::flat_stable_sort;
  46 using bsort::spreadsort::spreadsort;
  47 using bsort::pdqsort;
  48
  49 void Generator_random (void);
  50 void Generator_sorted (void);
  51 void Generator_sorted_end (size_t n_last);
  52 void Generator_sorted_middle (size_t n_last);
  53 void Generator_reverse_sorted (void);
  54 void Generator_reverse_sorted_end (size_t n_last);
  55 void Generator_reverse_sorted_middle (size_t n_last);
  56
  57 template<class IA, class compare>
  58 int Test (std::vector<IA> &B, compare comp = compare ());
  59
  60 int main (int argc, char *argv[])
  61 {
  62     cout << "\n\n";
  63     cout << "************************************************************\n";
  64     cout << "**                                                        **\n";
  65     cout << "**               B O O S T      S O R T                   **\n";
  66     cout << "**              S I N G L E    T H R E A D                **\n";
  67     cout << "**          I N T E G E R    B E N C H M A R K            **\n";
  68     cout << "**                                                        **\n";
  69     cout << "**        SORT OF 100 000 000 NUMBERS OF 64 BITS          **\n";
  70     cout << "**                                                        **\n";
  71     cout << "************************************************************\n";
  72     cout << std::endl;
  73
  74     cout<<"[ 1 ] std::sort   [ 2 ] pdqsort          [ 3 ] std::stable_sort \n";
  75     cout<<"[ 4 ] spinsort    [ 5 ] flat_stable_sort [ 6 ] spreadsort\n\n";
  76     cout<<"                    |      |      |      |      |      |      |\n";
  77     cout<<"                    | [ 1 ]| [ 2 ]| [ 3 ]| [ 4 ]| [ 5 ]| [ 6 ]|\n";
  78     cout<<"--------------------+------+------+------+------+------+------+\n";
  79     std::string empty_line =
  80            "                    |      |      |      |      |      |      |\n";
  81     cout<<"random              |";
  82     Generator_random ();
  83     cout<<empty_line;
  84     cout<<"sorted              |";
  85     Generator_sorted ();
  86
  87     cout<<"sorted + 0.1% end   |";
  88     Generator_sorted_end (NELEM / 1000);
  89
  90     cout<<"sorted +   1% end   |";
  91     Generator_sorted_end (NELEM / 100);
  92
  93     cout<<"sorted +  10% end   |";
  94     Generator_sorted_end (NELEM / 10);
  95
  96     cout<<empty_line;
  97     cout<<"sorted + 0.1% mid   |";
  98     Generator_sorted_middle (NELEM / 1000);
  99
 100     cout<<"sorted +   1% mid   |";
 101     Generator_sorted_middle (NELEM / 100);
 102
 103     cout<<"sorted +  10% mid   |";
 104     Generator_sorted_middle (NELEM / 10);
 105
 106     cout<<empty_line;
 107     cout<<"reverse sorted      |";
 108     Generator_reverse_sorted ();
 109
 110     cout<<"rv sorted + 0.1% end|";
 111     Generator_reverse_sorted_end (NELEM / 1000);
 112
 113     cout<<"rv sorted +   1% end|";
 114     Generator_reverse_sorted_end (NELEM / 100);
 115
 116     cout<<"rv sorted +  10% end|";
 117     Generator_reverse_sorted_end (NELEM / 10);
 118
 119     cout<<empty_line;
 120     cout<<"rv sorted + 0.1% mid|";
 121     Generator_reverse_sorted_middle (NELEM / 1000);
 122
 123     cout<<"rv sorted +   1% mid|";
 124     Generator_reverse_sorted_middle (NELEM / 100);
 125
 126     cout<<"rv sorted +  10% mid|";
 127     Generator_reverse_sorted_middle (NELEM / 10);
 128     cout<<"--------------------+------+------+------+------+------+------+\n";
 129     cout<<endl<<endl ;
 130     return 0;
 131 }
 132 void
 133 Generator_random (void)
 134 {
 135     vector<uint64_t> A;
 136     A.reserve (NELEM);
 137     A.clear ();
 138     if (fill_vector_uint64 ("input.bin", A, NELEM) != 0)
 139     {
 140         std::cout << "Error in the input file\n";
 141         return;
 142     };
 143     Test<uint64_t, std::less<uint64_t>> (A);
 144 }
 145 ;
 146 void
 147 Generator_sorted (void)
 148 {
 149     vector<uint64_t> A;
 150
 151     A.reserve (NELEM);
 152     A.clear ();
 153     for (size_t i = 0; i < NELEM; ++i)
 154         A.push_back (i);
 155     Test<uint64_t, std::less<uint64_t>> (A);
 156
 157 }
 158
 159 void Generator_sorted_end (size_t n_last)
 160 {
 161     vector<uint64_t> A;
 162     A.reserve (NELEM);
 163     A.clear ();
 164     if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
 165     {
 166         std::cout << "Error in the input file\n";
 167         return;
 168     };
 169     std::sort (A.begin (), A.begin () + NELEM);
 170
 171     Test<uint64_t, std::less<uint64_t>> (A);
 172
 173 }
 174 ;
 175 void Generator_sorted_middle (size_t n_last)
 176 {
 177     vector<uint64_t> A, B, C;
 178     A.reserve (NELEM);
 179     A.clear ();
 180     if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
 181     {
 182         std::cout << "Error in the input file\n";
 183         return;
 184     };
 185     for (size_t i = NELEM; i < A.size (); ++i)
 186         B.push_back (std::move (A[i]));
 187     A.resize ( NELEM);
 188     for (size_t i = 0; i < (NELEM >> 1); ++i)
 189         std::swap (A[i], A[NELEM - 1 - i]);
 190
 191     std::sort (A.begin (), A.end ());
 192     size_t step = NELEM / n_last + 1;
 193     size_t pos = 0;
 194
 195     for (size_t i = 0; i < B.size (); ++i, pos += step)
 196     {
 197         C.push_back (B[i]);
 198         for (size_t k = 0; k < step; ++k)
 199             C.push_back (A[pos + k]);
 200     };
 201     while (pos < A.size ())
 202         C.push_back (A[pos++]);
 203     A = C;
 204     Test<uint64_t, std::less<uint64_t>> (A);
 205 }
 206 ;
 207 void Generator_reverse_sorted (void)
 208 {
 209     vector<uint64_t> A;
 210
 211     A.reserve (NELEM);
 212     A.clear ();
 213     for (size_t i = NELEM; i > 0; --i)
 214         A.push_back (i);
 215     Test<uint64_t, std::less<uint64_t>> (A);
 216 }
 217 void Generator_reverse_sorted_end (size_t n_last)
 218 {
 219     vector<uint64_t> A;
 220     A.reserve (NELEM);
 221     A.clear ();
 222     if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
 223     {
 224         std::cout << "Error in the input file\n";
 225         return;
 226     };
 227     std::sort (A.begin (), A.begin () + NELEM);
 228     for (size_t i = 0; i < (NELEM >> 1); ++i)
 229         std::swap (A[i], A[NELEM - 1 - i]);
 230
 231     Test<uint64_t, std::less<uint64_t>> (A);
 232 }
 233 void Generator_reverse_sorted_middle (size_t n_last)
 234 {
 235     vector<uint64_t> A, B, C;
 236     A.reserve (NELEM);
 237     A.clear ();
 238     if (fill_vector_uint64 ("input.bin", A, NELEM + n_last) != 0)
 239     {
 240         std::cout << "Error in the input file\n";
 241         return;
 242     };
 243     for (size_t i = NELEM; i < A.size (); ++i)
 244         B.push_back (std::move (A[i]));
 245     A.resize ( NELEM);
 246     for (size_t i = 0; i < (NELEM >> 1); ++i)
 247         std::swap (A[i], A[NELEM - 1 - i]);
 248
 249     std::sort (A.begin (), A.end ());
 250     size_t step = NELEM / n_last + 1;
 251     size_t pos = 0;
 252
 253     for (size_t i = 0; i < B.size (); ++i, pos += step)
 254     {
 255         C.push_back (B[i]);
 256         for (size_t k = 0; k < step; ++k)
 257             C.push_back (A[pos + k]);
 258     };
 259     while (pos < A.size ())
 260         C.push_back (A[pos++]);
 261     A = C;
 262     Test<uint64_t, std::less<uint64_t>> (A);
 263 };
 264
 265
 266 template<class IA, class compare>
 267 int Test (std::vector<IA> &B,  compare comp)
 268 {   //---------------------------- begin --------------------------------
 269     double duration;
 270     time_point start, finish;
 271     std::vector<IA> A (B);
 272     std::vector<double> V;
 273
 274     //--------------------------------------------------------------------
 275     A = B;
 276     start = now ();
 277     std::sort (A.begin (), A.end (), comp);
 278     finish = now ();
 279     duration = subtract_time (finish, start);
 280     V.push_back (duration);
 281
 282     A = B;
 283     start = now ();
 284     pdqsort (A.begin (), A.end (), comp);
 285     finish = now ();
 286     duration = subtract_time (finish, start);
 287     V.push_back (duration);
 288
 289     A = B;
 290     start = now ();
 291     std::stable_sort (A.begin (), A.end (), comp);
 292     finish = now ();
 293     duration = subtract_time (finish, start);
 294     V.push_back (duration);
 295
 296     A = B;
 297     start = now ();
 298     spinsort(A.begin (), A.end (), comp);
 299     finish = now ();
 300     duration = subtract_time (finish, start);
 301     V.push_back (duration);
 302
 303     A = B;
 304     start = now ();
 305     flat_stable_sort (A.begin (), A.end (), comp);
 306     finish = now ();
 307     duration = subtract_time (finish, start);
 308     V.push_back (duration);
 309
 310
 311     A = B;
 312     start = now ();
 313     spreadsort (A.begin (), A.end ());
 314     finish = now ();
 315     duration = subtract_time (finish, start);
 316     V.push_back (duration);
 317
 318     //-----------------------------------------------------------------------
 319     // printing the vector
 320     //-----------------------------------------------------------------------
 321     std::cout<<std::setprecision(2)<<std::fixed;
 322     for ( uint32_t i =0 ; i < V.size() ; ++i)
 323     {   std::cout<<std::right<<std::setw(5)<<V[i]<<" |";
 324     };
 325     std::cout<<std::endl;
 326     return 0;
 327 };
 328