This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Fix __gnu_cxx::throw_allocator 2 * O(log(N)) complexity
- From: François Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>, gcc-patches <gcc-patches at gcc dot gnu dot org>
- Date: Mon, 12 Nov 2018 07:43:33 +0100
- Subject: 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