]>
git.proxmox.com Git - ceph.git/blob - ceph/src/boost/libs/sort/tune.pl
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)
7 # See http://www.boost.org/libs/sort for library home page.
9 # A speed and accuracy testing and automated parameter tuning script.
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
16 $defFileSize = 5000000;
21 $exename = "spreadsort";
22 $makename = "../../b2 \-\-tune";
27 $log2 = "> .tunelog 2>&1";
30 # have to change the path for UNIX
31 $prev_path = $ENV{'PATH'};
32 $ENV{'PATH'} = '.:'.$prev_path;
34 for (my $ii = 0; $ii < @ARGV; $ii++) {
35 my $currArg = $ARGV[$ii];
36 if ($currArg =~ /^-help$/) {
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$/) {
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$/) {
49 } elsif ($currArg =~ /^-verbose$/) {
51 # runs until we converge on a precise set of values
52 # defaults off because of runtime
53 } elsif ($currArg =~ /^-multiple_iterations$/) {
55 } elsif ($currArg =~ /^-debug$/) {
59 } elsif ($currArg =~ /^-large$/) {
60 $defFileSize = 20000000;
61 } elsif ($currArg =~ /^-small$/) {
62 $defFileSize = 100000;
63 } elsif ($currArg =~ /^-tune$/) {
65 } elsif ($currArg =~ /^-windows$/) {
66 $makename = "..\\..\\".$makename;
67 } elsif ($currArg =~ /^-/) {
71 $defFileSize = $currArg;
74 $fileSize = $defFileSize;
76 print STDOUT
"Tuning variables for $exename on vectors with $defFileSize elements\n";
78 # these are reasonable values
80 $log_finishing_count = 31;
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;
87 # this value is a minimum to obtain decent file I/O performance
88 $min_sort_size = 1000;
91 print STDOUT
"building randomgen\n";
92 system("$makename randomgen $log");
93 # Tuning to get convergence, maximum of 4 iterations with multiple iterations
98 for ($ii = 0; $changed and $ii < $iter_count; $ii++) {
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";
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";
124 print STDOUT
"Writing results\n";
127 # Doing a final run with final settings to compare sort times
128 # also verifying correctness of results
131 $fileSize = $defFileSize;
132 system("$makename $all $log");
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",
155 # clean up once we finish
156 system("$makename clean $log");
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");
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");
170 $ENV{'PATH'} = $prev_path;
172 # A simple speed test comparing std::sort to
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";
184 # Write an updated constants file as part of tuning.
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;
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";
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";
239 system("$makename $exename $log");
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.
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";
254 while ($line = <CODE
>) {
255 @parts = split("time", $line);
257 $sort_time = $parts[1];
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";
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);
273 $stdsingle = $parts[1];
282 # Sum up times for different data distributions. If realtimes is not set,
283 # larger ranges are given a larger weight.
289 # if we're only using real times, don't bother with the corner-cases
293 for (; $ii <= 16; $ii++) {
294 system("randomgen $ii $ii $fileSize");
296 $time += CheckTime
();
297 $baseTime += $stdsingle;
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;
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;
322 # Tests a range of potential values for a variable, and sets it to the fastest.
324 my ($tunevar, $beginval, $endval) = @_;
325 my $best_val = $$tunevar;
327 my $startval = $$tunevar;
328 for ($$tunevar = $beginval; $$tunevar <= $endval; $$tunevar++) {
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;
337 print STDOUT
"Value: $$tunevar Time: $sumtime\n" if $verbose;
339 $$tunevar = $best_val;
340 print STDOUT
"Best Value: $best_val\n";
341 if ($best_val != $startval) {
346 # Determine the cutoff size below which std::sort is faster.
348 for (; $min_sort_size <= $defFileSize; $min_sort_size *= 2) {
349 $loopCount = ($defFileSize/$min_sort_size)/10;
350 $fileSize = $min_sort_size;
353 $sumtime = SumTimes
();
355 $stdtime = SumTimes
();
356 print STDOUT
"Size: $min_sort_size boost::sort Time: $sumtime std::sort Time: $stdtime\n";
357 last if ($stdtime > $sumtime);