libstdc++-v3/testsuite/performance/container_benchmark.cc

   1 // Copyright (C) 2003 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 2, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // You should have received a copy of the GNU General Public License along
  15 // with this library; see the file COPYING.  If not, write to the Free
  16 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  17 // USA.
  18
  19 // As a special exception, you may use this file as part of a free software
  20 // library without restriction.  Specifically, if other files instantiate
  21 // templates or use macros or inline functions from this file, or you compile
  22 // this file and link it with other files to produce an executable, this
  23 // file does not by itself cause the resulting executable to be covered by
  24 // the GNU General Public License.  This exception does not however
  25 // invalidate any other reasons why the executable file might be covered by
  26 // the GNU General Public License.
  27
  28 #include <cmath>
  29 #include <cstdlib>
  30
  31 #include <vector>
  32 #include <algorithm>
  33 #include <list>
  34 #include <deque>
  35 #include <set>
  36
  37 #include <sstream>
  38 #include <testsuite_performance.h>
  39
  40 using namespace std;
  41
  42 typedef double element_t;
  43 typedef void(*test)(element_t*, element_t*);
  44
  45 void array_test(element_t* first, element_t* last)
  46 {
  47   element_t* array = new element_t[last - first];
  48   copy(first, last, array);
  49   sort(array, array + (last - first));
  50   unique(array, array + (last - first));
  51   delete [] array;
  52 }
  53
  54 void vector_pointer_test(element_t* first, element_t* last)
  55 {
  56   vector<element_t> container(first, last);
  57   sort(&*container.begin(), &*container.end());
  58   unique(&*container.begin(), &*container.end());
  59 }
  60
  61 void vector_iterator_test(element_t* first, element_t* last)
  62 {
  63   vector<element_t> container(first, last);
  64   sort(container.begin(), container.end());
  65   unique(container.begin(), container.end());
  66 }
  67
  68 void deque_test(element_t* first, element_t* last)
  69 {
  70   deque<element_t> container(first, last);
  71   copy(first, last, container.begin());
  72   sort(container.begin(), container.end());
  73   unique(container.begin(), container.end());
  74 }
  75
  76 void list_test(element_t* first, element_t* last)
  77 {
  78   list<element_t> container(first, last);
  79   container.sort();
  80   container.unique();
  81 }
  82
  83 void set_test(element_t* first, element_t* last)
  84 { set<element_t> container(first, last); }
  85
  86 void multiset_test(element_t* first, element_t* last)
  87 {
  88   multiset<element_t> container(first, last);
  89   typedef multiset<element_t>::iterator iterator;
  90   {
  91     iterator first = container.begin();
  92     iterator last = container.end();
  93
  94     while (first != last)
  95       {
  96         iterator next = first;
  97         if (++next == last) break;
  98         if (*first == *next)
  99           container.erase(next);
 100         else
 101           ++first;
 102       }
 103   }
 104 }
 105
 106 double logtwo(double x)
 107 { return log(x)/log(2.0); }
 108
 109 int number_of_tests(int size)
 110 {
 111   const double n = size;
 112   const double largest_n = 1000000;
 113   return int(floor((largest_n * logtwo(largest_n))
 114                    / (n * logtwo(n))));
 115 }
 116
 117 void initialize(element_t* first, element_t* last)
 118 {
 119   element_t value = 0.0;
 120   while (first != last)
 121     {
 122       *first++ = value;
 123       value += 1.;
 124     }
 125 }
 126
 127 void run_tests(int size, const test* tests, const char** names,
 128                int ntests)
 129 {
 130   using namespace __gnu_test;
 131   time_counter time;
 132   resource_counter resource;
 133
 134   const int n = number_of_tests(size);
 135   const size_t length = 2 * size;
 136
 137   // make a random test set of the chosen size:
 138   vector<element_t> buf(length);
 139   element_t* buffer = &buf[0];
 140   element_t* buffer_end = &buf[length];
 141   initialize(buffer, buffer + size);     // elements
 142   initialize(buffer + size, buffer_end); // duplicate elements
 143   random_shuffle(buffer, buffer_end);
 144
 145   // test the containers:
 146   ostringstream oss;
 147   oss << "size = " << size << " :";
 148   report_header(__FILE__, oss.str());
 149   for (int i = 0; i < ntests; ++i)
 150     {
 151       start_counters(time, resource);
 152       for (int j = 0; j < n; ++j)
 153         tests[i](buffer, buffer_end);
 154       stop_counters(time, resource);
 155       report_performance(__FILE__, names[i], time, resource);
 156       clear_counters(time, resource);
 157     }
 158 }
 159
 160 int main()
 161 {
 162   const test tests[] = { &array_test, &vector_pointer_test,
 163                          &vector_iterator_test, &deque_test,
 164                          &list_test, &set_test, &multiset_test };
 165   const int ntests = sizeof(tests) / sizeof(test);
 166   const char* names[ntests] = { "array", "vector (pointer)",
 167                                 "vector (iterator)", "deque",
 168                                 "list", "set", "multiset" };
 169
 170   const int sizes[] = {100, 1000, 10000, 100000};
 171   for (int i = 0; i < sizeof(sizes) / sizeof(int); ++i)
 172     run_tests(sizes[i], tests, names, ntests);
 173
 174   return 0;
 175 }