"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 }