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 <cstring>
18 #include <cctype>
19 #include <cstdlib>
20 #include <cstdio>
21
22 #include <string>
23
24 // Apple clang and MSVC defines their own specializations for std::hash<std::basic_string<T, Traits, Alloc>>
25 #if !(_LIBCPP_VERSION) && !(_CPPLIB_VER)
26
27 namespace std {
28
29 template <typename CharT, typename Traits, typename Allocator>
30 class hash<std::basic_string<CharT, Traits, Allocator>> {
31 public:
operator ()(const std::basic_string<CharT,Traits,Allocator> & s) const32 std::size_t operator()(const std::basic_string<CharT, Traits, Allocator>& s) const {
33 std::size_t h = 0;
34 for (const CharT* c = s.c_str(); *c; ++c) {
35 h = h * hash_multiplier ^ char_hash(*c);
36 }
37 return h;
38 }
39
40 private:
41 static constexpr std::size_t hash_multiplier = (std::size_t)(
42 (sizeof(std::size_t) == sizeof(unsigned)) ? 2654435769U : 11400714819323198485ULL);
43
44 std::hash<CharT> char_hash;
45 }; // strunt hash<std::basic_string>
46
47 } // namespace std
48
49 #endif // !(_LIBCPP_VERSION || _CPPLIB_VER)
50
51 #include "oneapi/tbb/concurrent_hash_map.h"
52 #include "oneapi/tbb/blocked_range.h"
53 #include "oneapi/tbb/parallel_for.h"
54 #include "oneapi/tbb/tick_count.h"
55 #include "oneapi/tbb/tbb_allocator.h"
56 #include "oneapi/tbb/global_control.h"
57
58 #include "common/utility/utility.hpp"
59 #include "common/utility/get_default_num_threads.hpp"
60
61 #include <map>
62
63 //! Count collisions
64 std::map<std::size_t, int> hashes;
65 int c = 0;
66
67 //! String type
68 typedef std::basic_string<char, std::char_traits<char>, oneapi::tbb::tbb_allocator<char>> MyString;
69
70 //! Set to true to counts.
71 static bool verbose = false;
72 static bool silent = false;
73 static bool count_collisions = false;
74 //! Problem size
75 long N = 1000000;
76 const int size_factor = 2;
77
78 //! A concurrent hash table that maps strings to ints.
79 typedef oneapi::tbb::concurrent_hash_map<MyString, int> StringTable;
80
81 //! Function object for counting occurrences of strings.
82 struct Tally {
83 StringTable& table;
TallyTally84 Tally(StringTable& table_) : table(table_) {}
operator ()Tally85 void operator()(const oneapi::tbb::blocked_range<MyString*> range) const {
86 for (MyString* p = range.begin(); p != range.end(); ++p) {
87 StringTable::accessor a;
88 table.insert(a, *p);
89 a->second += 1;
90 }
91 }
92 };
93
94 static MyString* Data;
95
CountOccurrences(int nthreads)96 static void CountOccurrences(int nthreads) {
97 StringTable table;
98
99 oneapi::tbb::tick_count t0 = oneapi::tbb::tick_count::now();
100 oneapi::tbb::parallel_for(oneapi::tbb::blocked_range<MyString*>(Data, Data + N, 1000),
101 Tally(table));
102 oneapi::tbb::tick_count t1 = oneapi::tbb::tick_count::now();
103
104 int n = 0;
105 for (StringTable::iterator i = table.begin(); i != table.end(); ++i) {
106 if (verbose && nthreads)
107 printf("%s %d\n", i->first.c_str(), i->second);
108 if (!silent && count_collisions) {
109 // it doesn't count real collisions in hash_map, a mask should be applied on hash value
110 hashes[std::hash<MyString>()(i->first) & 0xFFFF]++;
111 }
112 n += i->second;
113 }
114 if (!silent && count_collisions) {
115 for (auto i = hashes.begin(); i != hashes.end(); ++i)
116 c += i->second - 1;
117 printf("hashes = %d collisions = %d ", static_cast<int>(hashes.size()), c);
118 c = 0;
119 hashes.clear();
120 }
121
122 if (!silent)
123 printf(
124 "total = %d unique = %u time = %g\n", n, unsigned(table.size()), (t1 - t0).seconds());
125 }
126
127 /// Generator of random words
128
129 struct Sound {
130 const char* chars;
131 int rates[3]; // beginning, middle, ending
132 };
133 Sound Vowels[] = {
134 { "e", { 445, 6220, 1762 } }, { "a", { 704, 5262, 514 } }, { "i", { 402, 5224, 162 } },
135 { "o", { 248, 3726, 191 } }, { "u", { 155, 1669, 23 } }, { "y", { 4, 400, 989 } },
136 { "io", { 5, 512, 18 } }, { "ia", { 1, 329, 111 } }, { "ea", { 21, 370, 16 } },
137 { "ou", { 32, 298, 4 } }, { "ie", { 0, 177, 140 } }, { "ee", { 2, 183, 57 } },
138 { "ai", { 17, 206, 7 } }, { "oo", { 1, 215, 7 } }, { "au", { 40, 111, 2 } },
139 { "ua", { 0, 102, 4 } }, { "ui", { 0, 104, 1 } }, { "ei", { 6, 94, 3 } },
140 { "ue", { 0, 67, 28 } }, { "ay", { 1, 42, 52 } }, { "ey", { 1, 14, 80 } },
141 { "oa", { 5, 84, 3 } }, { "oi", { 2, 81, 1 } }, { "eo", { 1, 71, 5 } },
142 { "iou", { 0, 61, 0 } }, { "oe", { 2, 46, 9 } }, { "eu", { 12, 43, 0 } },
143 { "iu", { 0, 45, 0 } }, { "ya", { 12, 19, 5 } }, { "ae", { 7, 18, 10 } },
144 { "oy", { 0, 10, 13 } }, { "ye", { 8, 7, 7 } }, { "ion", { 0, 0, 20 } },
145 { "ing", { 0, 0, 20 } }, { "ium", { 0, 0, 10 } }, { "er", { 0, 0, 20 } }
146 };
147 Sound Consonants[] = {
148 { "r", { 483, 1414, 1110 } }, { "n", { 312, 1548, 1114 } }, { "t", { 363, 1653, 251 } },
149 { "l", { 424, 1341, 489 } }, { "c", { 734, 735, 260 } }, { "m", { 732, 785, 161 } },
150 { "d", { 558, 612, 389 } }, { "s", { 574, 570, 405 } }, { "p", { 519, 361, 98 } },
151 { "b", { 528, 356, 30 } }, { "v", { 197, 598, 16 } }, { "ss", { 3, 191, 567 } },
152 { "g", { 285, 430, 42 } }, { "st", { 142, 323, 180 } }, { "h", { 470, 89, 30 } },
153 { "nt", { 0, 350, 231 } }, { "ng", { 0, 117, 442 } }, { "f", { 319, 194, 19 } },
154 { "ll", { 1, 414, 83 } }, { "w", { 249, 131, 64 } }, { "k", { 154, 179, 47 } },
155 { "nd", { 0, 279, 92 } }, { "bl", { 62, 235, 0 } }, { "z", { 35, 223, 16 } },
156 { "sh", { 112, 69, 79 } }, { "ch", { 139, 95, 25 } }, { "th", { 70, 143, 39 } },
157 { "tt", { 0, 219, 19 } }, { "tr", { 131, 104, 0 } }, { "pr", { 186, 41, 0 } },
158 { "nc", { 0, 223, 2 } }, { "j", { 184, 32, 1 } }, { "nn", { 0, 188, 20 } },
159 { "rt", { 0, 148, 51 } }, { "ct", { 0, 160, 29 } }, { "rr", { 0, 182, 3 } },
160 { "gr", { 98, 87, 0 } }, { "ck", { 0, 92, 86 } }, { "rd", { 0, 81, 88 } },
161 { "x", { 8, 102, 48 } }, { "ph", { 47, 101, 10 } }, { "br", { 115, 43, 0 } },
162 { "cr", { 92, 60, 0 } }, { "rm", { 0, 131, 18 } }, { "ns", { 0, 124, 18 } },
163 { "sp", { 81, 55, 4 } }, { "sm", { 25, 29, 85 } }, { "sc", { 53, 83, 1 } },
164 { "rn", { 0, 100, 30 } }, { "cl", { 78, 42, 0 } }, { "mm", { 0, 116, 0 } },
165 { "pp", { 0, 114, 2 } }, { "mp", { 0, 99, 14 } }, { "rs", { 0, 96, 16 } },
166 { "rl", { 0, 97, 7 } }, { "rg", { 0, 81, 15 } }, { "pl", { 56, 39, 0 } },
167 { "sn", { 32, 62, 1 } }, { "str", { 38, 56, 0 } }, { "dr", { 47, 44, 0 } },
168 { "fl", { 77, 13, 1 } }, { "fr", { 77, 11, 0 } }, { "ld", { 0, 47, 38 } },
169 { "ff", { 0, 62, 20 } }, { "lt", { 0, 61, 19 } }, { "rb", { 0, 75, 4 } },
170 { "mb", { 0, 72, 7 } }, { "rc", { 0, 76, 1 } }, { "gg", { 0, 74, 1 } },
171 { "pt", { 1, 56, 10 } }, { "bb", { 0, 64, 1 } }, { "sl", { 48, 17, 0 } },
172 { "dd", { 0, 59, 2 } }, { "gn", { 3, 50, 4 } }, { "rk", { 0, 30, 28 } },
173 { "nk", { 0, 35, 20 } }, { "gl", { 40, 14, 0 } }, { "wh", { 45, 6, 0 } },
174 { "ntr", { 0, 50, 0 } }, { "rv", { 0, 47, 1 } }, { "ght", { 0, 19, 29 } },
175 { "sk", { 23, 17, 5 } }, { "nf", { 0, 46, 0 } }, { "cc", { 0, 45, 0 } },
176 { "ln", { 0, 41, 0 } }, { "sw", { 36, 4, 0 } }, { "rp", { 0, 36, 4 } },
177 { "dn", { 0, 38, 0 } }, { "ps", { 14, 19, 5 } }, { "nv", { 0, 38, 0 } },
178 { "tch", { 0, 21, 16 } }, { "nch", { 0, 26, 11 } }, { "lv", { 0, 35, 0 } },
179 { "wn", { 0, 14, 21 } }, { "rf", { 0, 32, 3 } }, { "lm", { 0, 30, 5 } },
180 { "dg", { 0, 34, 0 } }, { "ft", { 0, 18, 15 } }, { "scr", { 23, 10, 0 } },
181 { "rch", { 0, 24, 6 } }, { "rth", { 0, 23, 7 } }, { "rh", { 13, 15, 0 } },
182 { "mpl", { 0, 29, 0 } }, { "cs", { 0, 1, 27 } }, { "gh", { 4, 10, 13 } },
183 { "ls", { 0, 23, 3 } }, { "ndr", { 0, 25, 0 } }, { "tl", { 0, 23, 1 } },
184 { "ngl", { 0, 25, 0 } }, { "lk", { 0, 15, 9 } }, { "rw", { 0, 23, 0 } },
185 { "lb", { 0, 23, 1 } }, { "tw", { 15, 8, 0 } }, { "chr", { 18, 4, 0 } },
186 { "dl", { 0, 23, 0 } }, { "ctr", { 0, 22, 0 } }, { "nst", { 0, 21, 0 } },
187 { "lc", { 0, 22, 0 } }, { "sch", { 16, 4, 0 } }, { "ths", { 0, 1, 20 } },
188 { "nl", { 0, 21, 0 } }, { "lf", { 0, 15, 6 } }, { "ssn", { 0, 20, 0 } },
189 { "xt", { 0, 18, 1 } }, { "xp", { 0, 20, 0 } }, { "rst", { 0, 15, 5 } },
190 { "nh", { 0, 19, 0 } }, { "wr", { 14, 5, 0 } }
191 };
192 const int VowelsNumber = sizeof(Vowels) / sizeof(Sound);
193 const int ConsonantsNumber = sizeof(Consonants) / sizeof(Sound);
194 int VowelsRatesSum[3] = { 0, 0, 0 }, ConsonantsRatesSum[3] = { 0, 0, 0 };
195
CountRateSum(Sound sounds[],const int num,const int part)196 int CountRateSum(Sound sounds[], const int num, const int part) {
197 int sum = 0;
198 for (int i = 0; i < num; i++)
199 sum += sounds[i].rates[part];
200 return sum;
201 }
202
GetLetters(int type,const int part)203 const char* GetLetters(int type, const int part) {
204 Sound* sounds;
205 int rate, i = 0;
206 if (type & 1)
207 sounds = Vowels, rate = rand() % VowelsRatesSum[part];
208 else
209 sounds = Consonants, rate = rand() % ConsonantsRatesSum[part];
210 do {
211 rate -= sounds[i++].rates[part];
212 } while (rate > 0);
213 return sounds[--i].chars;
214 }
215
CreateData()216 static void CreateData() {
217 for (int i = 0; i < 3; i++) {
218 ConsonantsRatesSum[i] = CountRateSum(Consonants, ConsonantsNumber, i);
219 VowelsRatesSum[i] = CountRateSum(Vowels, VowelsNumber, i);
220 }
221 for (int i = 0; i < N; ++i) {
222 int type = rand();
223 Data[i] = GetLetters(type++, 0);
224 for (int j = 0; j < type % size_factor; ++j)
225 Data[i] += GetLetters(type++, 1);
226 Data[i] += GetLetters(type, 2);
227 }
228 MyString planet = Data[12];
229 planet[0] = toupper(planet[0]);
230 MyString helloworld = Data[0];
231 helloworld[0] = toupper(helloworld[0]);
232 helloworld += ", " + Data[1] + " " + Data[2] + " " + Data[3] + " " + Data[4] + " " + Data[5];
233 if (!silent)
234 printf("Message from planet '%s': %s!\nAnalyzing whole text...\n",
235 planet.c_str(),
236 helloworld.c_str());
237 }
238
main(int argc,char * argv[])239 int main(int argc, char* argv[]) {
240 StringTable table;
241 oneapi::tbb::tick_count mainStartTime = oneapi::tbb::tick_count::now();
242 srand(2);
243
244 //! Working threads count
245 // The 1st argument is the function to obtain 'auto' value; the 2nd is the default value
246 // The example interprets 0 threads as "run serially, then fully subscribed"
247 utility::thread_number_range threads(utility::get_default_num_threads, 0);
248
249 utility::parse_cli_arguments(
250 argc,
251 argv,
252 utility::cli_argument_pack()
253 //"-h" option for displaying help is present implicitly
254 .positional_arg(threads, "n-of-threads", utility::thread_number_range_desc)
255 .positional_arg(N, "n-of-strings", "number of strings")
256 .arg(verbose, "verbose", "verbose mode")
257 .arg(silent, "silent", "no output except elapsed time")
258 .arg(count_collisions, "count_collisions", "print the count of collisions"));
259
260 if (silent)
261 verbose = false;
262
263 Data = new MyString[N];
264 CreateData();
265
266 if (threads.first) {
267 for (int p = threads.first; p <= threads.last; p = threads.step(p)) {
268 if (!silent)
269 printf("threads = %d ", p);
270 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, p);
271 CountOccurrences(p);
272 }
273 }
274 else { // Number of threads wasn't set explicitly. Run serial and parallel version
275 { // serial run
276 if (!silent)
277 printf("serial run ");
278 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, 1);
279 CountOccurrences(1);
280 }
281 { // parallel run (number of threads is selected automatically)
282 if (!silent)
283 printf("parallel run ");
284 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism,
285 utility::get_default_num_threads());
286 CountOccurrences(0);
287 }
288 }
289
290 delete[] Data;
291
292 utility::report_elapsed_time((oneapi::tbb::tick_count::now() - mainStartTime).seconds());
293
294 return 0;
295 }
296