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>
23using std::string;
24using namespace boost::sort::spreadsort;
25
26#define DATA_TYPE string
27
28static 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
37static void sort_core(std::vector<DATA_TYPE> &array, bool stdSort,
38 unsigned loopCount) {
39 if (stdSort)
40 std::sort(first: array.begin(), last: array.end());
41 else
42 boost::sort::spreadsort::spreadsort(first: array.begin(), last: array.end());
43 if (!is_sorted(array)) {
44 fprintf(stderr, format: "sort failed!\n");
45 exit(status: 1);
46 }
47}
48
49static 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
61int 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(nptr: argv[u]);
73 else if (!loopCount)
74 loopCount = atoi(nptr: argv[u]);
75 else
76 constant_to_random_ratio = atoi(nptr: argv[u]);
77 }
78 if (!loopCount) {
79 loopCount = 1;
80 }
81 printf(format: "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(x: temp);
98 }
99 } else {
100 indata.open(s: "input.txt", mode: std::ios_base::in | std::ios_base::binary);
101 if (indata.bad()) {
102 printf(format: "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(x: 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(array&: base_array, stdSort, loopCount);
122 }
123 threadCount = 1;
124 } else {
125 for (int i = 0; i < threadCount; ++i) {
126 workers.push_back(x: 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(format: "for %lu strings\n", base_array.size());
138 if (stdSort)
139 printf(format: "std::sort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount);
140 else
141 printf(format: "spreadsort clock time %lf\n", elapsed/CLOCKS_PER_SEC/threadCount);
142 return 0;
143}
144

source code of boost/libs/sort/example/parallelstring.cpp