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

Message ID 876fff41-adec-4e17-b311-e8c8be5ea54b@gmail.com
State New
Headers show
Series
  • Fix __gnu_cxx::throw_allocator 2 * O(log(N)) complexity
Related show

Commit Message

François Dumont Nov. 12, 2018, 6:43 a.m.
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

Comments

François Dumont Nov. 13, 2018, 6:15 a.m. | #1
Oops, it was not the tested patch. Here it is.

On 11/12/18 7:43 AM, François Dumont wrote:
> 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..3a5670e3454 100644
--- a/libstdc++-v3/include/ext/throw_allocator.h
+++ b/libstdc++-v3/include/ext/throw_allocator.h
@@ -87,6 +87,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
    */
   struct annotate_base
   {
+  private:
+    typedef std::pair<size_t, size_t>		data_type;
+    typedef std::map<void*, data_type>		map_alloc_type;
+    typedef map_alloc_type::value_type		entry_type;
+    typedef map_alloc_type::const_iterator	const_iterator;
+    typedef map_alloc_type::const_reference	const_reference;
+#if __cplusplus >= 201103L
+    typedef std::map<void*, size_t>		map_construct_type;
+#endif
+
+  public:
     annotate_base()
     {
       label();
@@ -104,31 +115,28 @@ _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())
+      std::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 +148,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 map_alloc_type::iterator
     check_allocated(void* p, size_t size)
     {
-      const_iterator found = map_alloc().find(p);
+      map_alloc_type::iterator found = map_alloc().find(p);
       if (found == map_alloc().end())
 	{
 	  std::string error("annotate_base::check_allocated by value "
@@ -181,6 +184,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 +261,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     }
 
 #if __cplusplus >= 201103L
-    inline void
+    inline map_construct_type::iterator
     check_constructed(void* p)
     {
       auto found = map_construct().find(p);
@@ -267,6 +272,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
@@ -292,15 +299,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #endif
 
   private:
-    typedef std::pair<size_t, size_t>		data_type;
-    typedef std::map<void*, data_type> 		map_alloc_type;
-    typedef map_alloc_type::value_type 		entry_type;
-    typedef map_alloc_type::const_iterator 		const_iterator;
-    typedef map_alloc_type::const_reference 		const_reference;
-#if __cplusplus >= 201103L
-    typedef std::map<void*, size_t>		map_construct_type;
-#endif
-
     friend std::ostream&
     operator<<(std::ostream&, const annotate_base&);
Jonathan Wakely Nov. 19, 2018, 12:41 p.m. | #2
On 13/11/18 07:15 +0100, François Dumont wrote:
>Oops, it was not the tested patch. Here it is.

>

>On 11/12/18 7:43 AM, François Dumont wrote:

>>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 ?


OK, thanks.

Patch

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