1 // Benchmark for integer sorting speed across parallel threads.
2 //
3 // Copyright Steven Ross 2014
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 // See http://www.boost.org/libs/sort for library home page.
10
11 #include <boost/random/mersenne_twister.hpp>
12 #include <boost/random/uniform_int_distribution.hpp>
13 #include <boost/sort/spreadsort/spreadsort.hpp>
14 #include <boost/thread.hpp>
15 #include <time.h>
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <algorithm>
19 #include <vector>
20 #include <iostream>
21 #include <fstream>
22 #include <string>
23 using std::string;
24 using namespace boost::sort::spreadsort;
25
26 #define DATA_TYPE string
27
is_sorted(const std::vector<DATA_TYPE> & array)28 static bool is_sorted(const std::vector<DATA_TYPE> &array) {
29 for (unsigned u = 0; u + 1 < array.size(); ++u) {
30 if (array[u] > array[u + 1]) {
31 return false;
32 }
33 }
34 return true;
35 }
36
sort_core(std::vector<DATA_TYPE> & array,bool stdSort,unsigned loopCount)37 static void sort_core(std::vector<DATA_TYPE> &array, bool stdSort,
38 unsigned loopCount) {
39 if (stdSort)
40 std::sort(array.begin(), array.end());
41 else
42 boost::sort::spreadsort::spreadsort(array.begin(), array.end());
43 if (!is_sorted(array)) {
44 fprintf(stderr, "sort failed!\n");
45 exit(1);
46 }
47 }
48
sort_loop(const std::vector<DATA_TYPE> & base_array,bool stdSort,unsigned loopCount)49 static void sort_loop(const std::vector<DATA_TYPE> &base_array, bool stdSort,
50 unsigned loopCount) {
51 std::vector<DATA_TYPE> array(base_array);
52 for (unsigned u = 0; u < loopCount; ++u) {
53 for (unsigned v = 0; v < base_array.size(); ++v) {
54 array[v] = base_array[v];
55 }
56 sort_core(array, stdSort, loopCount);
57 }
58 }
59
60 //Pass in an argument to test std::sort
main(int argc,const char ** argv)61 int main(int argc, const char ** argv) {
62 std::ifstream indata;
63 std::ofstream outfile;
64 bool stdSort = false;
65 int constant_to_random_ratio = -1;
66 int threadCount = -1;
67 unsigned loopCount = 0;
68 for (int u = 1; u < argc; ++u) {
69 if (std::string(argv[u]) == "-std")
70 stdSort = true;
71 else if(threadCount < 0)
72 threadCount = atoi(argv[u]);
73 else if (!loopCount)
74 loopCount = atoi(argv[u]);
75 else
76 constant_to_random_ratio = atoi(argv[u]);
77 }
78 if (!loopCount) {
79 loopCount = 1;
80 }
81 printf("threads: %d loops: %d\n", threadCount, loopCount);
82
83 std::vector<DATA_TYPE> base_array;
84 if (constant_to_random_ratio >= 0) {
85 //Test for random data with gaps of identical data.
86 random::mt19937 generator;
87 random::uniform_int_distribution<int> distribution(0,255);
88 const int constant_to_random_count = 1000000;
89 const int string_length = 1000;
90 for (int i = 0; i < constant_to_random_count; ++i) {
91 DATA_TYPE temp(string_length, 'x'); // fill with default character.
92 for (int j = constant_to_random_ratio; j < string_length;) {
93 int val = distribution(generator);
94 temp[j] = val;
95 j += (val * constant_to_random_ratio)/128 + 1;
96 }
97 base_array.push_back(temp);
98 }
99 } else {
100 indata.open("input.txt", std::ios_base::in | std::ios_base::binary);
101 if (indata.bad()) {
102 printf("input.txt could not be opened\n");
103 return 1;
104 }
105 DATA_TYPE inval;
106 while (!indata.eof() ) {
107 indata >> inval;
108 base_array.push_back(inval);
109 }
110 }
111
112 // Sort the input
113 clock_t start, end;
114 double elapsed;
115 std::vector<boost::thread *> workers;
116 start = clock();
117 if (threadCount == 0) {
118 if (loopCount > 1) {
119 sort_loop(base_array, stdSort, loopCount);
120 } else {
121 sort_core(base_array, stdSort, loopCount);
122 }
123 threadCount = 1;
124 } else {
125 for (int i = 0; i < threadCount; ++i) {
126 workers.push_back(new boost::thread(sort_loop, base_array, stdSort,
127 loopCount));
128 }
129 for (int i = 0; i < threadCount; ++i) {
130 workers[i]->join();
131 delete workers[i];
132 }
133 }
134 end = clock();
135 elapsed = static_cast<double>(end - start) ;
136
137 printf("for %lu strings\n", base_array.size());
138 if (stdSort)
139 printf("std::sort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount);
140 else
141 printf("spreadsort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount);
142 return 0;
143 }
144