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 
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:
57     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
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 
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