Re: Enhance performance test

[François Dumont <frs dot dumont at gmail dot com>]

Attached patch applied.

2011-11-06  François Dumont <fdumont@gcc.gnu.org>

        * testsuite/performance/23_containers/insert_erase/41975.cc: Add
        tests to check performance with or without cache of hash code 
and with
        string type that has a costlier hash functor than int type.

François


On 11/05/2011 12:56 AM, Paolo Carlini wrote:
> On 11/04/2011 10:32 PM, François Dumont wrote:
> > Hi
> >
> >     Here is a patch to enhance the performance test introduced 
> > recently for hashtable. It shows more clearly the 41975 performance 
> > issue. I also introduced a bench using unordered_set<string> so that 
> > we have a tests involving a type with costlier hash functor than the 
> > one used for int. And lastly the bench are run twice, with and 
> > without hash code cached.
> >
> > 2011-11-04  François Dumont <fdumont@gcc.gnu.org>
> >
> >         * testsuite/performance/23_containers/insert_erase/41975.cc: Add
> >         tests to check performance with or without cache of hash code 
> > and with
> >         string type that has a costlier hash functor than int type.
> >
> > Ok to commit ?
> Looks Ok, but, as usual, watch overlong lines!
>
> Paolo.

Index: testsuite/performance/23_containers/insert_erase/41975.cc
===================================================================
--- testsuite/performance/23_containers/insert_erase/41975.cc	(revision 181036)
+++ testsuite/performance/23_containers/insert_erase/41975.cc	(working copy)
@@ -17,56 +17,167 @@
 // with this library; see the file COPYING3.  If not see
 // <http://www.gnu.org/licenses/>.
 
-#include <cassert>
+#include <sstream>
 #include <unordered_set>
 #include <testsuite_performance.h>
 
-int main()
+namespace
 {
-  using namespace __gnu_test;
+  // Bench using an unordered_set<int>. Hash functor for int is quite
+  // predictable so it helps bench very specific use cases.
+  template<bool use_cache>
+    void bench()
+    {
+      using namespace __gnu_test;
+      std::ostringstream ostr;
+      ostr << "unordered_set<int> " << (use_cache ? "with" : "without")
+	   << " cache";
+      const std::string desc = ostr.str();
 
-  time_counter time;
-  resource_counter resource;
+      time_counter time;
+      resource_counter resource;
 
-  start_counters(time, resource);
+      const int nb = 200000;
+      start_counters(time, resource);
 
-  std::unordered_set<int> us;
-  for (int i = 0; i != 5000000; ++i)
-    us.insert(i);
+      std::__unordered_set<int, std::hash<int>, std::equal_to<int>,
+			   std::allocator<int>, use_cache> us;
+      for (int i = 0; i != nb; ++i)
+	us.insert(i);
 
-  stop_counters(time, resource);
-  report_performance(__FILE__, "Container generation", time, resource);
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": first insert";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
 
-  start_counters(time, resource);
+      start_counters(time, resource);
 
-  for (int j = 100; j != 0; --j)
-    {
-      auto it = us.begin();
-      while (it != us.end())
+      // Here is the worst erase use case when hashtable implementation was
+      // something like vector<forward_list<>>. Erasing from the end was very
+      // costly because we need to return the iterator following the erased
+      // one, as the hashtable is getting emptier at each step there are
+      // more and more empty bucket to loop through to reach the end of the
+      // container and find out that it was in fact the last element.
+      for (int j = nb - 1; j >= 0; --j)
 	{
-	  if ((*it % j) == 0)
-	    it = us.erase(it);
-	  else
-	    ++it;
+	  auto it = us.find(j);
+	  if (it != us.end())
+	    us.erase(it);
 	}
+
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": erase from iterator";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+      start_counters(time, resource);
+
+      // This is a worst insertion use case for the current implementation as
+      // we insert an element at the begining of the hashtable and then we
+      // insert starting at the end so that each time we need to seek up to the
+      // first bucket to find the first non-empty one.
+      us.insert(0);
+      for (int i = nb - 1; i >= 0; --i)
+	us.insert(i);
+
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": second insert";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+      start_counters(time, resource);
+
+      for (int j = nb - 1; j >= 0; --j)
+	us.erase(j);
+
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": erase from key";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
     }
 
-  stop_counters(time, resource);
-  report_performance(__FILE__, "Container erase", time, resource);
+  // Bench using unordered_set<string> that show how important it is to cache
+  // hash code as computing string hash code is quite expensive compared to
+  // computing it for int.
+  template<bool use_cache>
+    void bench_str()
+    {
+      using namespace __gnu_test;
+      std::ostringstream ostr;
+      ostr << "unordered_set<string> " << (use_cache ? "with" : "without")
+	   << " cache";
+      const std::string desc = ostr.str();
 
-  start_counters(time, resource);
+      time_counter time;
+      resource_counter resource;
 
-  us.insert(0);
+      const int nb = 200000;
+      // First generate once strings that are going to be used throughout the
+      // bench:
+      std::vector<std::string> strs;
+      strs.reserve(nb);
+      for (int i = 0; i != nb; ++i)
+      {
+	ostr.str("");
+	ostr << "string #" << i;
+	strs.push_back(ostr.str());
+      }
 
-  for (int i = 0; i != 500; ++i)
-    {
-      auto it = us.begin();
-      ++it;
-      assert( it == us.end() );
+      start_counters(time, resource);
+
+      std::__unordered_set<std::string, std::hash<std::string>,
+			   std::equal_to<std::string>,
+			   std::allocator<std::string>, use_cache> us;
+      for (int i = 0; i != nb; ++i)
+	us.insert(strs[i]);
+
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": first insert";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+      start_counters(time, resource);
+
+      for (int j = nb - 1; j >= 0; --j)
+	{
+	  auto it = us.find(strs[j]);
+	  if (it != us.end())
+	    us.erase(it);
+	}
+
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": erase from iterator";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+      start_counters(time, resource);
+
+      us.insert(strs[0]);
+      for (int i = nb - 1; i >= 0; --i)
+	us.insert(strs[i]);
+
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": second insert";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
+
+      start_counters(time, resource);
+
+      for (int j = nb - 1; j >= 0; --j)
+	us.erase(strs[j]);
+
+      stop_counters(time, resource);
+      ostr.str("");
+      ostr << desc << ": erase from key";
+      report_performance(__FILE__, ostr.str().c_str(), time, resource);
     }
+}
 
-  stop_counters(time, resource);
-  report_performance(__FILE__, "Container iteration", time, resource);
-
+int main()
+{
+  bench<false>();
+  bench<true>();
+  bench_str<false>();
+  bench_str<true>();
   return 0;
 }