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