ceph/src/boost/libs/sort/tune.pl

   1 #!/usr/bin/perl -w
   2 #          Copyright Steven J. Ross 2008 - 2014
   3 # Distributed under the Boost Software License, Version 1.0.
   4 #    (See accompanying file LICENSE_1_0.txt or copy at
   5 #          http://www.boost.org/LICENSE_1_0.txt)
   6 #
   7 # See http://www.boost.org/libs/sort for library home page.
   8
   9 # A speed and accuracy testing and automated parameter tuning script.
  10
  11 $usage = "usage: tune.pl [-tune] [-real] [-tune_verify] [-verbose] [-multiple_iterations] [-large] [-small] [-windows] [fileSize]\n";
  12 # testing sorting on 40 million elements by default
  13 # don't test on below 2^22 (4 million) elements as that is the minimum
  14 # for max_splits of 11 to be efficient
  15 use File::Compare;
  16 $defFileSize = 5000000;
  17 $loopCount = 1;
  18 $realtimes = 0;
  19 $verifycorrect = 0;
  20 $verbose = 0;
  21 $exename = "spreadsort";
  22 $makename = "../../b2 \-\-tune";
  23 $all = "";
  24 $iter_count = 1;
  25 $debug = 0;
  26 $log = "> .tunelog";
  27 $log2 = "> .tunelog 2>&1";
  28 $diffopt = "-q";
  29 $tune = 0;
  30 # have to change the path for UNIX
  31 $prev_path = $ENV{'PATH'};
  32 $ENV{'PATH'} = '.:'.$prev_path;
  33
  34 for (my $ii = 0; $ii < @ARGV; $ii++) {
  35         my $currArg = $ARGV[$ii];
  36         if ($currArg =~ /^-help$/) {
  37             print STDERR $usage;
  38             exit(0);
  39         }
  40         # verification roughly doubles the runtime of this script,
  41         # but it does make sure that results are correct during tuning
  42         # verification always runs during speed comparisons with std::sort
  43         if ($currArg =~ /^-tune_verify$/) {
  44             $verifycorrect = 1;
  45         # use real times only, don't use weighting and special-case tests
  46         # this saves about 5/6 of the script runtime but results are different
  47         } elsif ($currArg =~ /^-real$/) {
  48             $realtimes = 1;
  49         } elsif ($currArg =~ /^-verbose$/) {
  50             $verbose = 1;
  51         # runs until we converge on a precise set of values
  52         # defaults off because of runtime
  53         } elsif ($currArg =~ /^-multiple_iterations$/) {
  54             $iter_count = 4;
  55         } elsif ($currArg =~ /^-debug$/) {
  56             $debug = 1;
  57             $log = "";
  58             $diffopt = "";
  59         } elsif ($currArg =~ /^-large$/) {
  60             $defFileSize = 20000000;
  61         } elsif ($currArg =~ /^-small$/) {
  62             $defFileSize = 100000;
  63         } elsif ($currArg =~ /^-tune$/) {
  64             $tune = 1;
  65         } elsif ($currArg =~ /^-windows$/) {
  66             $makename = "..\\..\\".$makename;
  67         } elsif ($currArg =~ /^-/) {
  68             print STDERR $usage;
  69             exit(0);
  70         } else {
  71                 $defFileSize = $currArg;
  72         }
  73 }
  74 $fileSize = $defFileSize;
  75
  76 print STDOUT "Tuning variables for $exename on vectors with $defFileSize elements\n";
  77
  78 # these are reasonable values
  79 $max_splits = 11;
  80 $log_finishing_count = 31;
  81 $log_min_size = 11;
  82 $log_mean_bin_size = 2;
  83 $float_log_min_size = 10;
  84 $float_log_mean_bin_size = 2;
  85 $float_log_finishing_count = 4;
  86
  87 # this value is a minimum to obtain decent file I/O performance
  88 $min_sort_size = 1000;
  89 $std = "";
  90
  91 print STDOUT "building randomgen\n";
  92 system("$makename randomgen $log");
  93 # Tuning to get convergence, maximum of 4 iterations with multiple iterations
  94 # option set
  95 $changed = 1;
  96 my $ii = 0;
  97 if ($tune) {
  98     for ($ii = 0; $changed and $ii < $iter_count; $ii++) {
  99         $changed = 0;
 100         # Tuning max_splits is not recommended.
 101         #print STDOUT "Tuning max_splits\n";
 102         #TuneVariable(\$max_splits, $log_min_size - $log_mean_bin_size, 17);
 103         print STDOUT "Tuning log of the minimum count for recursion\n";
 104         TuneVariable(\$log_min_size, $log_mean_bin_size + 1, $max_splits + $log_mean_bin_size);
 105         print STDOUT "Tuning log_mean_bin_size\n";
 106         TuneVariable(\$log_mean_bin_size, 0, $log_min_size - 1);
 107         print STDOUT "Tuning log_finishing_size\n";
 108         TuneVariable(\$log_finishing_count, 1, $log_min_size);
 109         # tuning variables for floats
 110         $exename = "floatsort";
 111         print STDOUT "Tuning log of the minimum count for recursion for floats\n";
 112         TuneVariable(\$float_log_min_size, $float_log_mean_bin_size + 1, $max_splits + $float_log_mean_bin_size);
 113         print STDOUT "Tuning float_log_mean_bin_size\n";
 114         TuneVariable(\$float_log_mean_bin_size, 0, $float_log_min_size - 1);
 115         print STDOUT "Tuning float_log_finishing_size\n";
 116         TuneVariable(\$float_log_finishing_count, 1, $float_log_min_size);
 117         $exename = "spreadsort";
 118     }
 119
 120     # After optimizations for large datasets are complete, see how small of a
 121     # dataset can be sped up
 122     print STDOUT "Tuning minimum sorting size\n";
 123     TuneMinSize();
 124     print STDOUT "Writing results\n";
 125 }
 126
 127 # Doing a final run with final settings to compare sort times
 128 # also verifying correctness of results
 129 $verifycorrect = 1;
 130 $loopCount = 1;
 131 $fileSize = $defFileSize;
 132 system("$makename $all $log");
 133 $std = "";
 134 PerfTest("Verifying integer_sort", "spreadsort");
 135 PerfTest("Verifying float_sort", "floatsort");
 136 PerfTest("Verifying string_sort", "stringsort");
 137 PerfTest("Verifying integer_sort with mostly-sorted data", "mostlysorted");
 138 PerfTest("Timing integer_sort on already-sorted data", "alreadysorted");
 139 PerfTest("Verifying integer_sort with rightshift", "rightshift");
 140 PerfTest("Verifying integer_sort with 64-bit integers", "int64");
 141 PerfTest("Verifying integer_sort with separate key and data", "keyplusdata");
 142 PerfTest("Verifying reverse integer_sort", "reverseintsort");
 143 PerfTest("Verifying float_sort with doubles", "double");
 144 PerfTest("Verifying float_sort with shift functor", "shiftfloatsort");
 145 PerfTest("Verifying float_sort with functors", "floatfunctorsort");
 146 PerfTest("Verifying string_sort with indexing functors", "charstringsort");
 147 PerfTest("Verifying string_sort with all functors", "stringfunctorsort");
 148 PerfTest("Verifying reverse_string_sort", "reversestringsort");
 149 PerfTest("Verifying reverse_string_sort with functors",
 150          "reversestringfunctorsort");
 151 PerfTest("Verifying generalized string_sort with multiple keys of different types",
 152          "generalizedstruct");
 153 PerfTest("Verifying boost::sort on its custom-built worst-case distribution",
 154          "binaryalrbreaker");
 155 # clean up once we finish
 156 system("$makename clean $log");
 157 # WINDOWS
 158 system("del spread_sort_out.txt $log2");
 159 system("del standard_sort_out.txt $log2");
 160 system("del input.txt $log2");
 161 system("del *.rsp $log2");
 162 system("del *.manifest $log2");
 163 system("del time.txt $log2");
 164 # UNIX
 165 system("rm -f time.txt $log2");
 166 system("rm -f spread_sort_out.txt $log2");
 167 system("rm -f standard_sort_out.txt $log2");
 168 system("rm -f input.txt $log2");
 169
 170 $ENV{'PATH'} = $prev_path;
 171
 172 # A simple speed test comparing std::sort to
 173 sub PerfTest {
 174     my ($message, $local_exe) = @_;
 175     $exename = $local_exe;
 176     print STDOUT "$message\n";
 177     $lastTime = SumTimes();
 178     print STDOUT "runtime: $lastTime\n";
 179     print STDOUT "std::sort time: $baseTime\n";
 180     $speedup = (($baseTime/$lastTime) - 1) * 100;
 181     print STDOUT "speedup: ".sprintf("%.2f", $speedup)."%\n";
 182 }
 183
 184 # Write an updated constants file as part of tuning.
 185 sub WriteConstants {
 186     # deleting the file
 187     $const_file = 'include/boost/sort/spreadsort/detail/constants.hpp';
 188     @cannot = grep {not unlink} $const_file;
 189     print "$0: could not unlink @cannot\n" if @cannot;
 190
 191     # writing the results back to the original file name
 192     unless(open(CONSTANTS, ">$const_file")) {
 193       print STDERR "Can't open output file: $const_file: $!\n";
 194       exit;
 195     }
 196     print CONSTANTS "//constant definitions for the Boost Sort library\n\n";
 197     print CONSTANTS "//          Copyright Steven J. Ross 2001 - 2014\n";
 198     print CONSTANTS "// Distributed under the Boost Software License, Version 1.0.\n";
 199     print CONSTANTS "//    (See accompanying file LICENSE_1_0.txt or copy at\n";
 200     print CONSTANTS "//          http://www.boost.org/LICENSE_1_0.txt)\n\n";
 201     print CONSTANTS "//  See http://www.boost.org/libs/sort for library home page.\n";
 202     print CONSTANTS "#ifndef BOOST_SORT_SPREADSORT_DETAIL_CONSTANTS\n";
 203     print CONSTANTS "#define BOOST_SORT_SPREADSORT_DETAIL_CONSTANTS\n";
 204     print CONSTANTS "namespace boost {\n";
 205     print CONSTANTS "namespace sort {\n";
 206     print CONSTANTS "namespace spreadsort {\n";
 207     print CONSTANTS "namespace detail {\n";
 208     print CONSTANTS "//Tuning constants\n";
 209     print CONSTANTS "//This should be tuned to your processor cache;\n";
 210     print CONSTANTS "//if you go too large you get cache misses on bins\n";
 211     print CONSTANTS "//The smaller this number, the less worst-case memory usage.\n";
 212     print CONSTANTS "//If too small, too many recursions slow down spreadsort\n";
 213     print CONSTANTS "enum { max_splits = $max_splits,\n";
 214     print CONSTANTS "//It's better to have a few cache misses and finish sorting\n";
 215     print CONSTANTS "//than to run another iteration\n";
 216     print CONSTANTS "max_finishing_splits = max_splits + 1,\n";
 217     print CONSTANTS "//Sets the minimum number of items per bin.\n";
 218     print CONSTANTS "int_log_mean_bin_size = $log_mean_bin_size,\n";
 219     print CONSTANTS "//Used to force a comparison-based sorting for small bins, if it's faster.\n";
 220     print CONSTANTS "//Minimum value 1\n";
 221     $log_min_split_count = $log_min_size - $log_mean_bin_size;
 222     print CONSTANTS "int_log_min_split_count = $log_min_split_count,\n";
 223     print CONSTANTS "//This is the minimum split count to use spreadsort when it will finish in one\n";
 224     print CONSTANTS "//iteration.  Make this larger the faster std::sort is relative to integer_sort.\n";
 225     print CONSTANTS "int_log_finishing_count = $log_finishing_count,\n";
 226     print CONSTANTS "//Sets the minimum number of items per bin for floating point.\n";
 227     print CONSTANTS "float_log_mean_bin_size = $float_log_mean_bin_size,\n";
 228     print CONSTANTS "//Used to force a comparison-based sorting for small bins, if it's faster.\n";
 229     print CONSTANTS "//Minimum value 1\n";
 230     $float_log_min_split_count = $float_log_min_size - $float_log_mean_bin_size;
 231     print CONSTANTS "float_log_min_split_count = $float_log_min_split_count,\n";
 232     print CONSTANTS "//This is the minimum split count to use spreadsort when it will finish in one\n";
 233     print CONSTANTS "//iteration.  Make this larger the faster std::sort is relative to float_sort.\n";
 234     print CONSTANTS "float_log_finishing_count = $float_log_finishing_count,\n";
 235     print CONSTANTS "//There is a minimum size below which it is not worth using spreadsort\n";
 236     print CONSTANTS "min_sort_size = $min_sort_size };\n";
 237     print CONSTANTS "}\n}\n}\n}\n#endif\n";
 238     close CONSTANTS;
 239     system("$makename $exename $log");
 240 }
 241
 242 # Sort the file with both std::sort and boost::sort, verify the results are the
 243 # same, update stdtime with std::sort time, and return boost::sort time.
 244 sub CheckTime {
 245     my $sort_time = 0.0;
 246     my $time_file = "time.txt";
 247     # use the line below on systems that can't overwrite.
 248     #system("rm -f $time_file");
 249     system("$exename $loopCount $std > $time_file");
 250     unless(open(CODE, $time_file)) {
 251         print STDERR "Could not open file: $time_file: $!\n";
 252         exit;
 253     }
 254     while ($line = <CODE>) {
 255         @parts = split("time", $line);
 256         if (@parts > 1) {
 257             $sort_time = $parts[1];
 258             last;
 259         }
 260     }
 261     close(CODE);
 262     # verifying correctness
 263     if (not $std and $verifycorrect) {
 264         system("$exename $loopCount -std > $time_file");
 265         unless(open(CODE, $time_file)) {
 266             print STDERR "Could not open file: $time_file: $!\n";
 267             exit;
 268         }
 269         die "Difference in results\n" unless (compare("boost_sort_out.txt","standard_sort_out.txt") == 0) ;
 270         while ($line = <CODE>) {
 271             @parts = split("time", $line);
 272             if (@parts > 1) {
 273                 $stdsingle = $parts[1];
 274                 last;
 275             }
 276         }
 277         close(CODE);
 278     }
 279     return $sort_time;
 280 }
 281
 282 # Sum up times for different data distributions.  If realtimes is not set,
 283 # larger ranges are given a larger weight.
 284 sub SumTimes {
 285     my $time = 0;
 286     $baseTime = 0.0;
 287     $stdsingle = 0.0;
 288     my $ii = 1;
 289     # if we're only using real times, don't bother with the corner-cases
 290     if ($realtimes) {
 291         $ii = 8;
 292     }
 293     for (; $ii <= 16; $ii++) {
 294         system("randomgen $ii $ii $fileSize");
 295         if ($realtimes) {
 296             $time += CheckTime();
 297             $baseTime += $stdsingle;
 298         } else {
 299             # tests with higher levels of randomness are given
 300             # higher priority in timing results
 301             print STDOUT "trying $ii $ii\n" if $debug;
 302             $time += 2 * $ii * CheckTime();
 303             $baseTime += 2 * $ii * $stdsingle;
 304             if ($ii > 1) {
 305                 print STDOUT "trying 1 $ii\n" if $debug;
 306                 system("randomgen 1 $ii $fileSize");
 307                 $time += $ii * CheckTime();
 308                 $baseTime += $ii * $stdsingle;
 309                 print STDOUT "trying $ii 1\n" if $debug;
 310                 system("randomgen $ii 1 $fileSize");
 311                 $time += $ii * CheckTime();
 312                 $baseTime += $ii * $stdsingle;
 313             }
 314         }
 315     }
 316     if ($time == 0.0) {
 317         $time = 0.01;
 318     }
 319     return $time;
 320 }
 321
 322 # Tests a range of potential values for a variable, and sets it to the fastest.
 323 sub TuneVariable {
 324     my ($tunevar, $beginval, $endval) = @_;
 325     my $best_val = $$tunevar;
 326     my $besttime = 0;
 327     my $startval = $$tunevar;
 328     for ($$tunevar = $beginval; $$tunevar <= $endval; $$tunevar++) {
 329         WriteConstants();
 330         $sumtime = SumTimes();
 331         # If this value is better, use it.  If this is the start value
 332         # and it's just as good, use the startval
 333         if (not $besttime or ($sumtime < $besttime) or (($besttime == $sumtime) and ($$tunevar == $startval))) {
 334             $besttime = $sumtime;
 335             $best_val = $$tunevar;
 336         }
 337         print STDOUT "Value: $$tunevar Time: $sumtime\n" if $verbose;
 338     }
 339     $$tunevar = $best_val;
 340     print STDOUT "Best Value: $best_val\n";
 341     if ($best_val != $startval) {
 342         $changed = 1;
 343     }
 344 }
 345
 346 # Determine the cutoff size below which std::sort is faster.
 347 sub TuneMinSize {
 348     for (; $min_sort_size <= $defFileSize; $min_sort_size *= 2) {
 349         $loopCount = ($defFileSize/$min_sort_size)/10;
 350         $fileSize = $min_sort_size;
 351         WriteConstants();
 352         $std = "";
 353         $sumtime = SumTimes();
 354         $std = "-std";
 355         $stdtime = SumTimes();
 356         print STDOUT "Size: $min_sort_size boost::sort Time: $sumtime std::sort Time: $stdtime\n";
 357         last if ($stdtime > $sumtime);
 358     }
 359 }