[Patch] Add the container_benchmark to the testsuite

[Paolo Carlini <pcarlini at suse dot de>]

Hi,

today I have received feedback from Bjarne Stroustrup, encouraging
us to add to the performance testsuite a version of the Standard
Container Benchmark: "... in the meantime, please use the benchmark.".
And we already had:

   http://gcc.gnu.org/ml/libstdc++/2003-06/msg00028.html

pointing out that there are no restrictions on the code.

Therefore, I have adapted it to our performance testsuite as you
can see below.

If nobody objects, I'd like to commit it soon, together with the
new, handy, 'report_header'.

Paolo.

////////////
2003-12-16  Paolo Carlini  <pcarlini@suse.de>

	* testsuite/performance/container_benchmark: New, a benchmark
	developed by Bjarne Stroustrup and Alexander Stepanov and
	made available with no restrictions.

	* testsuite/testsuite_performance.h (report_header): New,
	useful to produce header lines in the reports.

diff -urN libstdc++-v3-orig/testsuite/performance/container_benchmark.cc libstdc++-v3/testsuite/performance/container_benchmark.cc
--- libstdc++-v3-orig/testsuite/performance/container_benchmark.cc	1970-01-01 01:00:00.000000000 +0100
+++ libstdc++-v3/testsuite/performance/container_benchmark.cc	2003-12-16 22:21:27.000000000 +0100
@@ -0,0 +1,177 @@
+// Copyright (C) 2003 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
+// USA.
+
+// As a special exception, you may use this file as part of a free software
+// library without restriction.  Specifically, if other files instantiate
+// templates or use macros or inline functions from this file, or you compile
+// this file and link it with other files to produce an executable, this
+// file does not by itself cause the resulting executable to be covered by
+// the GNU General Public License.  This exception does not however
+// invalidate any other reasons why the executable file might be covered by
+// the GNU General Public License.
+
+#include <cmath>
+#include <cstdlib>
+
+#include <vector>
+#include <algorithm>
+#include <list>
+#include <deque>
+#include <set>
+
+#include <sstream>
+#include <testsuite_performance.h>
+
+using namespace std;
+
+typedef double element_t;
+typedef void(*test)(element_t*, element_t*);
+
+void array_test(element_t* first, element_t* last)
+{
+  element_t* array = new element_t[last - first];
+  copy(first, last, array);
+  sort(array, array + (last - first));
+  unique(array, array + (last - first));
+  delete [] array;	  
+}
+
+void vector_pointer_test(element_t* first, element_t* last)
+{ 
+  vector<element_t> container(first, last);
+  sort(&*container.begin(), &*container.end());
+  unique(&*container.begin(), &*container.end());
+}
+
+void vector_iterator_test(element_t* first, element_t* last)
+{
+  vector<element_t> container(first, last);
+  sort(container.begin(), container.end());
+  unique(container.begin(), container.end());
+}
+
+void deque_test(element_t* first, element_t* last)
+{  
+  deque<element_t> container(first, last);
+  copy(first, last, container.begin()); 
+  sort(container.begin(), container.end());
+  unique(container.begin(), container.end());
+}
+    
+void list_test(element_t* first, element_t* last)
+{ 
+  list<element_t> container(first, last);
+  container.sort();
+  container.unique();
+}
+ 
+void set_test(element_t* first, element_t* last)
+{
+  set<element_t> container(first, last);
+}
+
+void multiset_test(element_t* first, element_t* last)
+{
+  multiset<element_t> container(first, last);
+  typedef multiset<element_t>::iterator iterator;
+  {
+    iterator first = container.begin();
+    iterator last = container.end();
+    
+    while (first != last)
+      {
+	iterator next = first;
+	if (++next == last) break;
+	if (*first == *next)
+	  container.erase(next);
+	else
+	  ++first;
+      }
+  }
+}
+
+double logtwo(double x)
+{ return log(x)/log(2.0); }
+
+int number_of_tests(int size)
+{
+  double n = size;
+  double largest_n = 1000000;
+  return int(floor((largest_n * logtwo(largest_n))
+		   / (n * logtwo(n))));
+}
+
+void initialize(element_t* first, element_t* last)
+{
+  element_t value = 0.0;
+  while (first != last)
+    {
+      *first++ = value;
+      value += 1.;
+    }
+}
+
+void run_tests(int size, test* tests, const char** names,
+	       int ntests)
+{
+  using namespace __gnu_test;
+  time_counter time;
+  resource_counter resource;
+
+  const int n = number_of_tests(size);
+  const size_t length = 2 * size;
+
+  // make a random test set of the chosen size:
+  vector<element_t> buf(length);
+  element_t* buffer = &buf[0];
+  element_t* buffer_end = &buf[length];
+  initialize(buffer, buffer + size);	 // elements
+  initialize(buffer + size, buffer_end); // duplicate elements
+  random_shuffle(buffer, buffer_end);
+
+  // test the containers:
+  ostringstream oss;
+  oss << "size = " << size;
+  report_header(__FILE__, oss.str());
+  for (int i = 0; i < ntests; ++i)
+    {
+      start_counters(time, resource);
+      for (int j = 0; j < n; ++j)
+	tests[i](buffer, buffer_end);
+      stop_counters(time, resource);
+      report_performance(__FILE__, names[i], time, resource);
+      clear_counters(time, resource);
+    }
+}
+
+int main()
+{
+  test tests[] = { &array_test, &vector_pointer_test,
+                   &vector_iterator_test, &deque_test,
+                   &list_test, &set_test, &multiset_test };
+  const int n = sizeof(tests) / sizeof(test);
+  const char* names[n] = { "array", "vector (ptr)",
+			   "vector (iter)", "deque",
+			   "list", "set", "multiset" };
+
+  const int sizes[] = {100, 1000, 10000, 100000};
+  for (int i = 0; i < sizeof(sizes) / sizeof(int); ++i)
+    run_tests(sizes[i], tests, names, n);
+
+  return 0;
+}
diff -urN libstdc++-v3-orig/testsuite/testsuite_performance.h libstdc++-v3/testsuite/testsuite_performance.h
--- libstdc++-v3-orig/testsuite/testsuite_performance.h	2003-08-08 17:24:00.000000000 +0200
+++ libstdc++-v3/testsuite/testsuite_performance.h	2003-12-16 22:10:46.000000000 +0100
@@ -197,6 +197,25 @@
     out << std::endl;
     out.close();
   }
+
+  void
+  report_header(const std::string file, const std::string header)
+  {
+    const char space = ' ';
+    const char tab = '\t';
+    const char* name = "libstdc++-performance.sum";
+    std::string::const_iterator i = file.begin() + file.find_last_of('/') + 1;
+    std::string testname(i, file.end());
+
+    std::ofstream out(name, std::ios_base::app);
+
+    out.setf(std::ios_base::left);
+    out << std::setw(25) << testname << tab;
+    out << std::setw(10) << header << tab;
+
+    out << std::endl;
+    out.close();
+  }
 }; // namespace __gnu_test
 
 #endif // _GLIBCXX_PERFORMANCE_H