This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Fix __gnu_cxx::throw_allocator 2 * O(log(N)) complexity


When doing some debugging session I noticed that the __gnu_cxx::throw_allocator doubles all lookup on both insert and erase.

Using map::insert result and erasing the found iterator avoids this double lookup.

    * include/ext/throw_allocator.h
    (annotate_base::insert(void*, size_t)): Use insert result to check for
    double insert attempt.
    (annotate_base::insert_construct(void*)): Likewise.
    (annotate_base::check_allocated(void*, size_t)): Return found iterator.
    (annotate_base::erase(void*, size_t)): Use latter method returned
    iterator.
    (annotate_base::check_constructed(void*, size_t)): Return found iterator.
    (annotate_base::erase_construct(void*)): Use latter method returned
    iterator.

Tested under linux x86_64.

Ok to commit ?

François

diff --git a/libstdc++-v3/include/ext/throw_allocator.h b/libstdc++-v3/include/ext/throw_allocator.h
index dd7c692222e..e513571b766 100644
--- a/libstdc++-v3/include/ext/throw_allocator.h
+++ b/libstdc++-v3/include/ext/throw_allocator.h
@@ -104,31 +104,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     void
     insert(void* p, size_t size)
     {
+      entry_type entry = make_entry(p, size);
       if (!p)
 	{
 	  std::string error("annotate_base::insert null insert!\n");
-	  log_to_string(error, make_entry(p, size));
+	  log_to_string(error, entry);
 	  std::__throw_logic_error(error.c_str());
 	}
 
-      const_iterator found = map_alloc().find(p);
-      if (found != map_alloc().end())
+      pair<map_alloc_type::iterator, bool> inserted = map_alloc().insert(entry);
+      if (!inserted.second)
 	{
 	  std::string error("annotate_base::insert double insert!\n");
-	  log_to_string(error, make_entry(p, size));
-	  log_to_string(error, *found);
+	  log_to_string(error, entry);
+	  log_to_string(error, *inserted.first);
 	  std::__throw_logic_error(error.c_str());
 	}
-
-      map_alloc().insert(make_entry(p, size));
     }
 
     void
     erase(void* p, size_t size)
-    {
-      check_allocated(p, size);
-      map_alloc().erase(p);
-    }
+    { map_alloc().erase(check_allocated(p, size)); }
 
 #if __cplusplus >= 201103L
     void
@@ -140,31 +136,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  std::__throw_logic_error(error.c_str());
 	}
 
-      auto found = map_construct().find(p);
-      if (found != map_construct().end())
+      auto inserted = map_construct().insert(std::make_pair(p, get_label()));
+      if (!inserted.second)
 	{
 	  std::string error("annotate_base::insert_construct double insert!\n");
 	  log_to_string(error, std::make_pair(p, get_label()));
-	  log_to_string(error, *found);
+	  log_to_string(error, *inserted.first);
 	  std::__throw_logic_error(error.c_str());
 	}
-
-      map_construct().insert(std::make_pair(p, get_label()));
     }
 
     void
     erase_construct(void* p)
-    {
-      check_constructed(p);
-      map_construct().erase(p);
-    }
+    { map_construct().erase(check_constructed(p)); }
 #endif
 
     // See if a particular address and allocation size has been saved.
-    inline void
+    inline typename map_alloc_type::iterator
     check_allocated(void* p, size_t size)
     {
-      const_iterator found = map_alloc().find(p);
+      iterator found = map_alloc().find(p);
       if (found == map_alloc().end())
 	{
 	  std::string error("annotate_base::check_allocated by value "
@@ -181,6 +172,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  log_to_string(error, *found);
 	  std::__throw_logic_error(error.c_str());
 	}
+
+      return found;
     }
 
     // See if a given label has been allocated.
@@ -256,7 +249,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
 #if __cplusplus >= 201103L
-    inline void
+    inline typename map_construct_type::iterator
     check_constructed(void* p)
     {
       auto found = map_construct().find(p);
@@ -267,6 +260,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  log_to_string(error, std::make_pair(p, get_label()));
 	  std::__throw_logic_error(error.c_str());
 	}
+
+      return found;
     }
 
     inline void

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]