"Fossies" - the Fresh Open Source Software Archive 
Member "snort3_extra-3.1.53.0/container_comparisons/src/string_key.cc" (20 Dec 2022, 7213 Bytes) of package /linux/misc/snort3_extra-3.1.53.0.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 "string_key.cc" see the
Fossies "Dox" file reference documentation.
1 //--------------------------------------------------------------------------
2 // Copyright (C) 2019-2022 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 // string_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
30 #include "common_key.h"
31
32 using namespace std;
33
34 static long double unordered_total_time;
35 static long double ordered_total_time;
36
37 //TODO: Read these keys from an input file (can be specified as a cmd arg) for a more scalable and generic approach
38 // all unique keys for evaluating performance against
39 static vector<string> unique_keys = {"appid-service", "appid-client", "appid-payload", "appid-misc", "appid-referred", "host", "tls-host", "url", "user-agent", "response-code", "referer", "xff", "client-version"};
40
41 void execute_test(DataUser& sink)
42 {
43 // containers to be compared
44 map<string, int> ordered_storage;
45 unordered_map<string, int> unordered_storage;
46
47 vector<int> function_ids;
48 vector<string> keys;
49
50 auto eng = std::default_random_engine(std::random_device()());
51
52 auto generate_new_key = [&]
53 {
54 int key_index = rand() % UNIQUE_KEYS_MAX;
55 return unique_keys[key_index];
56 };
57
58 for (size_t i = 0 ; i < KEYS_MAX ; ++i)
59 {
60 auto key = generate_new_key();
61 keys.push_back(key);
62
63 // 0: lookup operation
64 // 1: insert operation
65 // 2: clear the container
66 if( (i % 100) == 0)
67 function_ids.push_back(2);
68 else
69 function_ids.push_back(rand()%2);
70 }
71
72 // shuffle the keys to randomize access order
73 shuffle(begin(keys), end(keys), eng);
74
75 auto unordered_operation = [&](auto& key, int &id)
76 {
77 if(id == 0)
78 {
79 auto data = unordered_storage.find(key);
80 if (data != end(unordered_storage))
81 {
82 sink.sink(data->second);
83 }
84 }
85 else if(id == 1)
86 {
87 // does not matter what is the value here
88 unordered_storage[key] = 100;
89 }
90 else if(id == 2)
91 {
92 unordered_storage.clear();
93 }
94 };
95
96 auto ordered_operation = [&](auto& key, int &id)
97 {
98 if(id == 0)
99 {
100 auto data = ordered_storage.find(key);
101 if (data != end(ordered_storage))
102 {
103 sink.sink(data->second);
104 }
105 }
106 else if(id == 1)
107 {
108 // does not matter what is the value
109 ordered_storage[key] = 100;
110 }
111 else if(id == 2)
112 {
113 ordered_storage.clear();
114 }
115 };
116
117 // spawn threads to time access to unordered map
118 auto thread_unordered = async(launch::async,
119 [&]()
120 {
121 return time_test(unordered_operation, function_ids, keys);
122 });
123 auto unordered_time = thread_unordered.get();
124
125
126 // spawn threads to time access to ordered map
127 auto thread_ordered = async(launch::async, [&]
128 {
129 return time_test(ordered_operation, function_ids, keys);
130 });
131 auto ordered_time = thread_ordered.get();
132
133
134 ordered_total_time += ordered_time.count() * 1.0L / (SCALE_DOWN_FACTOR);
135 unordered_total_time += unordered_time.count() * 1.0L / (SCALE_DOWN_FACTOR);
136 }
137
138 int main(int argc, char **argv)
139 {
140 //TODO: output and input files can be sent as command line arguments
141 string output_file = "output_";
142
143 // remove "./" from beginning of the program name and append the remaining program name to output file name
144 output_file += &argv[0][2];
145 output_file += ".txt";
146 ofstream output(output_file);
147 if (output.fail())
148 {
149 cout << "Couldn't open output file!" << endl;
150 return 1;
151 }
152 else
153 {
154 cout << "Check "<< output_file << " for results" << endl;
155 }
156 output << std::fixed;
157 output << std::setprecision(2);
158
159 cout << "Running Tests..." << endl;
160
161 // provide different initial seed to rand() every time you run this program
162 srand(time(0));
163
164 // make a dummy sink, so that the optimizer wouldn't know what we are doing after searching into the container
165 auto user = make_sink(2);
166 long double final_ordered_time = 0, final_unordered_time = 0;
167
168 for(int i = 0; i < TOTAL_TEST_RUNS; i++)
169 {
170 ordered_total_time = 0; unordered_total_time = 0;
171
172 execute_test(*user);
173
174 final_ordered_time += ordered_total_time / TOTAL_TEST_RUNS;
175 final_unordered_time += unordered_total_time / TOTAL_TEST_RUNS;
176
177 output <<"---------------------------------------------------------------------"<<endl;
178 output << "Average Time for Ordered Map : " << setw(10) << (long long)ordered_total_time << " ticks"<<endl;
179 output << "Average Time for Unordered Map : " << setw(10) << (long long)unordered_total_time << " ticks"<<endl;
180 output <<"---------------------------------------------------------------------"<<endl;
181 output << endl << endl;
182 }
183 output << endl << endl;
184 output <<"Key: string" << ". #Test Runs: " << TOTAL_TEST_RUNS << ". Operations: " << KEYS_MAX << ". #Unique Keys: "<<UNIQUE_KEYS_MAX<<endl;
185 output <<"*********************************************************************"<<endl;
186 output << "Overall Time (scaled down by "<< SCALE_DOWN_FACTOR << "):" << endl;
187 output <<"*********************************************************************"<<endl;
188 output << "Avg. Time for Ordered Map : "<< setw(10) << (long long)final_ordered_time<< " ticks"<< endl;
189 output << "Avg. Time for Unordered Map : "<< setw(10) << (long long)final_unordered_time<< " ticks"<<endl<<endl;
190 output <<"---------------------------------------------------------------------"<<endl;
191 output << "\% Change from Ordered to Unordered : "<< setw(10) << (((final_ordered_time-final_unordered_time)/final_ordered_time) * 100) << endl;
192 output <<"*********************************************************************"<<endl;
193
194 output.close();
195
196 return 0;
197 }