2 Copyright 2005-2009 Intel Corporation. All Rights Reserved.
4 This file is part of Threading Building Blocks.
6 Threading Building Blocks is free software; you can redistribute it
7 and/or modify it under the terms of the GNU General Public License
8 version 2 as published by the Free Software Foundation.
10 Threading Building Blocks is distributed in the hope that it will be
11 useful, but WITHOUT ANY WARRANTY; without even the implied warranty
12 of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with Threading Building Blocks; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 As a special exception, you may use this file as part of a free software
20 library without restriction. Specifically, if other files instantiate
21 templates or use macros or inline functions from this file, or you compile
22 this file and link it with other files to produce an executable, this
23 file does not by itself cause the resulting executable to be covered by
24 the GNU General Public License. This exception does not however
25 invalidate any other reasons why the executable file might be covered by
26 the GNU General Public License.
33 #include "tbb/parallel_for.h"
34 #include "tbb/blocked_range.h"
35 #include "tbb/tick_count.h"
39 static const size_t N = 22;
41 void SerialSubStringFinder ( const string &str, size_t *max_array, size_t *pos_array) {
42 for ( size_t i = 0; i < str.size(); ++i ) {
43 size_t max_size = 0, max_pos = 0;
44 for (size_t j = 0; j < str.size(); ++j)
46 size_t limit = str.size()-( i > j ? i : j );
47 for (size_t k = 0; k < limit; ++k) {
48 if (str[i + k] != str[j + k]) break;
55 max_array[i] = max_size;
56 pos_array[i] = max_pos;
60 class SubStringFinder {
65 void operator() ( const blocked_range<size_t>& r ) const {
66 for ( size_t i = r.begin(); i != r.end(); ++i ) {
67 size_t max_size = 0, max_pos = 0;
68 for (size_t j = 0; j < str.size(); ++j)
70 size_t limit = str.size()-( i > j ? i : j );
71 for (size_t k = 0; k < limit; ++k) {
72 if (str[i + k] != str[j + k]) break;
79 max_array[i] = max_size;
80 pos_array[i] = max_pos;
83 SubStringFinder(string &s, size_t *m, size_t *p) :
84 str(s), max_array(m), pos_array(p) { }
87 int main(int argc, char *argv[]) {
90 string str[N] = { string("a"), string("b") };
91 for (size_t i = 2; i < N; ++i) str[i] = str[i-1]+str[i-2];
92 string &to_scan = str[N-1];
94 size_t *max = new size_t[to_scan.size()];
95 size_t *max2 = new size_t[to_scan.size()];
96 size_t *pos = new size_t[to_scan.size()];
97 size_t *pos2 = new size_t[to_scan.size()];
98 cout << " Done building string." << endl;
101 tick_count serial_t0 = tick_count::now();
102 SerialSubStringFinder(to_scan, max2, pos2);
103 tick_count serial_t1 = tick_count::now();
104 cout << " Done with serial version." << endl;
106 tick_count parallel_t0 = tick_count::now();
107 parallel_for(blocked_range<size_t>(0, to_scan.size(), 100),
108 SubStringFinder( to_scan, max, pos ) );
109 tick_count parallel_t1 = tick_count::now();
110 cout << " Done with parallel version." << endl;
112 for (size_t i = 0; i < to_scan.size(); ++i) {
113 if (max[i] != max2[i] || pos[i] != pos2[i]) {
114 cout << "ERROR: Serial and Parallel Results are Different!" << endl;
117 cout << " Done validating results." << endl;
119 cout << "Serial version ran in " << (serial_t1 - serial_t0).seconds() << " seconds" << endl
120 << "Parallel version ran in " << (parallel_t1 - parallel_t0).seconds() << " seconds" << endl
121 << "Resulting in a speedup of " << (serial_t1 - serial_t0).seconds() / (parallel_t1 - parallel_t0).seconds() << endl;
In the beginning the Universe was created. This has made a lot of
people very angry and has been widely regarded as a bad move.
Douglas Adams