1 /* 2 Copyright (c) 2005-2020 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: 32 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; 84 Tally(StringTable& table_) : table(table_) {} 85 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 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 ", 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 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 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 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 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