"Fossies" - the Fresh Open Source Software Archive 
Member "snort3_extra-3.0.3-1/container_comparisons/src/int_key.cc" (23 Sep 2020, 9841 Bytes) of package /linux/misc/snort3_extra-3.0.3-1.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "int_key.cc" see the
Fossies "Dox" file reference documentation.
1 //--------------------------------------------------------------------------
2 // Copyright (C) 2019-2020 Cisco and/or its affiliates. All rights reserved.
3 //
4 // This program is free software; you can redistribute it and/or modify it
5 // under the terms of the GNU General Public License Version 2 as published
6 // by the Free Software Foundation. You may not use, modify or distribute
7 // this program under any other version of the GNU General Public License.
8 //
9 // This program is distributed in the hope that it will be useful, but
10 // WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 // General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License along
15 // with this program; if not, write to the Free Software Foundation, Inc.,
16 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17 //--------------------------------------------------------------------------
18
19 // int_key.cc author Devendra Dahiphale <ddahipha@cisco.com>
20 #include <iostream>
21 #include <random>
22 #include <algorithm>
23 #include <string>
24 #include <map>
25 #include <unordered_map>
26 #include <unordered_set>
27 #include <future>
28 #include <fstream>
29 #include <cstring>
30
31 #include "common_key.h"
32
33 using namespace std;
34
35 static long double unordered_total_time;
36 static long double ordered_total_time;
37 static long double array_total_time;
38 static long double vector_total_time;
39
40 void execute_test(DataUser& sink)
41 {
42 // containers to be compared
43 map<int, int> ordered_storage;
44 unordered_map<int, int> unordered_storage;
45 int array_storage[UNIQUE_KEYS_MAX] = {0};
46 vector<int> vector_storage(UNIQUE_KEYS_MAX, 0);
47
48 vector<int> function_ids;
49 // a vector of all keys to be tested, which we can shuffle in order to randomize input
50 vector<int> keys;
51
52 // for uniform probability distribution
53 auto eng = std::default_random_engine(std::random_device()());
54
55 auto generate_new_key = [&]
56 {
57 int key = rand() % UNIQUE_KEYS_MAX;
58 return key;
59 };
60
61 for (size_t i = 0 ; i < KEYS_MAX ; ++i)
62 {
63 auto key = generate_new_key();
64 keys.push_back(key);
65
66 // 0: lookup operation
67 // 1: insert operation
68 // 2: clear the container
69 if( (i % 100) == 0)
70 function_ids.push_back(2);
71 else
72 function_ids.push_back(rand()%2);
73 }
74
75 // shuffle the keys to randomize access order
76 shuffle(begin(keys), end(keys), eng);
77
78 auto unordered_operation = [&](auto& key, int &id)
79 {
80 if(id == 0)
81 {
82 auto data = unordered_storage.find(key);
83 if (data != end(unordered_storage))
84 {
85 sink.sink(data->second);
86 }
87 }
88 else if(id == 1)
89 {
90 unordered_storage[key] = key;
91 }
92 else if(id == 2)
93 {
94 unordered_storage.clear();
95 }
96 };
97
98 auto ordered_operation = [&](auto& key, int &id)
99 {
100 if(id == 0)
101 {
102 auto data = ordered_storage.find(key);
103 if (data != end(ordered_storage))
104 {
105 sink.sink(data->second);
106 }
107 }
108 else if(id == 1)
109 {
110 ordered_storage[key] = key;
111 }
112 else if(id == 2)
113 {
114 ordered_storage.clear();
115 }
116 };
117
118 auto array_operation = [&](auto& key, int &id)
119 {
120 if(id == 0)
121 {
122 auto data = array_storage[key];
123 sink.sink(data);
124 }
125 else if(id == 1)
126 {
127 array_storage[key] = key;
128 }
129 else if(id == 2)
130 {
131 memset(array_storage, 0, UNIQUE_KEYS_MAX);
132 }
133 };
134
135 auto vector_operation = [&](auto& key, int &id)
136 {
137 if(id == 0)
138 {
139 auto data = vector_storage[key];
140 sink.sink(data);
141 }
142 else if(id == 1)
143 {
144 vector_storage[key] = key;
145 }
146 else if(id == 2)
147 {
148 vector_storage.clear();
149 }
150 };
151
152 // spawn threads to time access to unordered map
153 auto thread_unordered = async(launch::async,
154 [&]()
155 {
156 return time_test(unordered_operation, function_ids, keys);
157 });
158 auto unordered_time = thread_unordered.get();
159
160
161 // spawn threads to time access to ordered map
162 auto thread_ordered = async(launch::async, [&]
163 {
164 return time_test(ordered_operation, function_ids, keys);
165 });
166 auto ordered_time = thread_ordered.get();
167
168
169 // spawn threads to time access to array
170 auto thread_array = async(launch::async, [&]
171 {
172 return time_test(array_operation, function_ids, keys);
173 });
174 auto array_time = thread_array.get();
175
176
177 // spawn threads to time access to vector
178 auto thread_vector = async(launch::async, [&]
179 {
180 return time_test(vector_operation, function_ids, keys);
181 });
182 auto vector_time = thread_vector.get();
183
184
185 ordered_total_time += ordered_time.count() * 1.0L/ (SCALE_DOWN_FACTOR);
186 unordered_total_time += unordered_time.count() * 1.0L/ (SCALE_DOWN_FACTOR);
187 array_total_time += array_time.count() * 1.0L/ (SCALE_DOWN_FACTOR);
188 vector_total_time += vector_time.count() * 1.0L/ (SCALE_DOWN_FACTOR);
189 }
190
191 int main(int argc, char **argv)
192 {
193 //TODO: output and input files can be sent as command line arguments
194 string output_file = "output_";
195 // remove "./" from beginning of the program name and append the remaining program name to output file name
196 output_file += &argv[0][2];
197 output_file += ".txt";
198
199 ofstream output(output_file);
200 if (output.fail())
201 {
202 cout << "Couldn't open output file! : " << output_file << endl;
203 return 1;
204 }
205 else
206 {
207 cout << "Check "<< output_file << " for results" << endl;
208 }
209 output << std::fixed;
210 output << std::setprecision(2);
211
212 cout << "Running Tests..." << endl;
213
214 // provide different initial seed to rand() every time you run this program
215 srand(time(0));
216
217 // To hide from optimizing container accesses
218 auto user = make_sink(2);
219 long double final_ordered_time = 0, final_unordered_time = 0, final_array_time = 0, final_vector_time = 0;
220
221 for(int i = 0; i < TOTAL_TEST_RUNS; i++)
222 {
223 // reset vars used for a test
224 ordered_total_time = 0; unordered_total_time = 0; array_total_time = 0; vector_total_time = 0;
225
226 execute_test(*user);
227
228 final_ordered_time += ordered_total_time / TOTAL_TEST_RUNS;
229 final_unordered_time += unordered_total_time / TOTAL_TEST_RUNS;
230 final_array_time += array_total_time / TOTAL_TEST_RUNS;
231 final_vector_time += vector_total_time / TOTAL_TEST_RUNS;
232
233 output <<"---------------------------------------------------------------------"<<endl;
234 output << "Average Time for Ordered Map : " << setw(10) << (long long)ordered_total_time << " ticks"<< endl;
235 output << "Average Time for Unordered Map : " << setw(10) << (long long)unordered_total_time << " ticks"<<endl;
236 output << "Average Time for Array : " << setw(10) << (long long)array_total_time << " ticks"<<endl;
237 output << "Average Time for Vector : " << setw(10) << (long long)vector_total_time << " ticks"<<endl;
238 output <<"---------------------------------------------------------------------"<<endl;
239 output << endl << endl;
240 }
241 output << endl << endl;
242 output <<"Key: int" << ". #Test Runs: " << TOTAL_TEST_RUNS << ". Operations: " << KEYS_MAX << ". #Unique Keys: "<<UNIQUE_KEYS_MAX<<endl;
243 output <<"*********************************************************************"<<endl;
244 output << "Overall Time (scaled down by "<< SCALE_DOWN_FACTOR << "):" << endl;
245 output <<"*********************************************************************"<<endl;
246 output << "Avg. Time for Ordered Map : "<< setw(10)<< (long long)(final_ordered_time) << " ticks"<< endl;
247 output << "Avg. Time for Unordered Map : "<< setw(10)<< (long long)(final_unordered_time) << " ticks"<< endl;
248 output << "Avg. Time for Array : "<< setw(10)<< (long long)(final_array_time) << " ticks"<<endl;
249 output << "Avg. Time for Vector : "<< setw(10)<< (long long)(final_vector_time) << " ticks"<<endl << endl;
250 output <<"---------------------------------------------------------------------"<<endl;
251 output << "\% Change Ordered to Unordered : "<< setw(10)<< (((final_ordered_time-final_unordered_time)/final_ordered_time) * 100) << endl;
252 output << "\% Change Ordered to Array : "<< setw(10)<< (((final_ordered_time-final_array_time)/final_ordered_time) * 100) << endl;
253 output << "\% Change Ordered to Vector : "<< setw(10)<< (((final_ordered_time-final_vector_time)/final_ordered_time) * 100) << endl;
254 output << "\% Change Unordered to Array : "<< setw(10)<< (((final_unordered_time-final_array_time)/final_unordered_time) * 100) << endl;
255 output << "\% Change Unordered to Vector : "<< setw(10)<< (((final_unordered_time-final_vector_time)/final_unordered_time) * 100) << endl;
256 output << "\% Change Array to Vector : "<< setw(10)<< (((final_array_time-final_vector_time)/final_array_time) * 100) << endl;
257 output <<"*********************************************************************"<<endl;
258
259 output.close();
260
261 return 0;
262 }