1 /*
2 Copyright (c) 2005-2021 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15 */
16
17 #include <iostream>
18 #include <string>
19 #include <vector>
20 #include <algorithm> // std::max
21
22 #include "oneapi/tbb/parallel_for.h"
23 #include "oneapi/tbb/blocked_range.h"
24 #include "oneapi/tbb/tick_count.h"
25
26 static const std::size_t N = 22;
27
SerialSubStringFinder(const std::string & str,std::vector<std::size_t> & max_array,std::vector<std::size_t> & pos_array)28 void SerialSubStringFinder(const std::string &str,
29 std::vector<std::size_t> &max_array,
30 std::vector<std::size_t> &pos_array) {
31 for (std::size_t i = 0; i < str.size(); ++i) {
32 std::size_t max_size = 0, max_pos = 0;
33 for (std::size_t j = 0; j < str.size(); ++j)
34 if (j != i) {
35 std::size_t limit = str.size() - (std::max)(i, j);
36 for (std::size_t k = 0; k < limit; ++k) {
37 if (str[i + k] != str[j + k])
38 break;
39 if (k > max_size) {
40 max_size = k;
41 max_pos = j;
42 }
43 }
44 }
45 max_array[i] = max_size;
46 pos_array[i] = max_pos;
47 }
48 }
49
50 class SubStringFinder {
51 const char *str;
52 const std::size_t len;
53 std::size_t *max_array;
54 std::size_t *pos_array;
55
56 public:
operator ()(const oneapi::tbb::blocked_range<std::size_t> & r) const57 void operator()(const oneapi::tbb::blocked_range<std::size_t> &r) const {
58 for (std::size_t i = r.begin(); i != r.end(); ++i) {
59 std::size_t max_size = 0, max_pos = 0;
60 for (std::size_t j = 0; j < len; ++j) {
61 if (j != i) {
62 std::size_t limit = len - (std::max)(i, j);
63 for (std::size_t k = 0; k < limit; ++k) {
64 if (str[i + k] != str[j + k])
65 break;
66 if (k > max_size) {
67 max_size = k;
68 max_pos = j;
69 }
70 }
71 }
72 }
73 max_array[i] = max_size;
74 pos_array[i] = max_pos;
75 }
76 }
77 // We do not use std::vector for compatibility with offload execution
SubStringFinder(const char * s,const std::size_t s_len,std::size_t * m,std::size_t * p)78 SubStringFinder(const char *s, const std::size_t s_len, std::size_t *m, std::size_t *p)
79 : str(s),
80 len(s_len),
81 max_array(m),
82 pos_array(p) {}
83 };
84
main()85 int main() {
86 std::string str[N] = { std::string("a"), std::string("b") };
87 for (std::size_t i = 2; i < N; ++i)
88 str[i] = str[i - 1] + str[i - 2];
89 std::string &to_scan = str[N - 1];
90 const std::size_t num_elem = to_scan.size();
91
92 std::vector<std::size_t> max1(num_elem);
93 std::vector<std::size_t> pos1(num_elem);
94 std::vector<std::size_t> max2(num_elem);
95 std::vector<std::size_t> pos2(num_elem);
96
97 std::cout << " Done building string."
98 << "\n";
99
100 oneapi::tbb::tick_count serial_t0 = oneapi::tbb::tick_count::now();
101 SerialSubStringFinder(to_scan, max2, pos2);
102 oneapi::tbb::tick_count serial_t1 = oneapi::tbb::tick_count::now();
103 std::cout << " Done with serial version."
104 << "\n";
105
106 oneapi::tbb::tick_count parallel_t0 = oneapi::tbb::tick_count::now();
107 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<std::size_t>(0, num_elem, 100),
108 SubStringFinder(to_scan.c_str(), num_elem, &max1[0], &pos1[0]));
109 oneapi::tbb::tick_count parallel_t1 = oneapi::tbb::tick_count::now();
110 std::cout << " Done with parallel version."
111 << "\n";
112
113 for (std::size_t i = 0; i < num_elem; ++i) {
114 if (max1[i] != max2[i] || pos1[i] != pos2[i]) {
115 std::cout << "ERROR: Serial and Parallel Results are Different!"
116 << "\n";
117 break;
118 }
119 }
120 std::cout << " Done validating results."
121 << "\n";
122
123 std::cout << "Serial version ran in " << (serial_t1 - serial_t0).seconds() << " seconds"
124 << "\n"
125 << "Parallel version ran in " << (parallel_t1 - parallel_t0).seconds() << " seconds"
126 << "\n"
127 << "Resulting in a speedup of "
128 << (serial_t1 - serial_t0).seconds() / (parallel_t1 - parallel_t0).seconds() << "\n";
129
130 return 0;
131 }
132