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