improve std::deque::_M_reallocate_map

Jonathan Wakely jwakely@redhat.com
Mon Nov 25 17:36:20 GMT 2024


On 24/11/24 16:26 +0100, Jan Hubicka wrote:
>> Hi,
>> looking into reason why we still do throw_bad_alloc in clang binary I noticed
>> that quite few calls come from deque::_M_reallocate_map.  This patch adds
>> unreachable to limit the size of realloc_map.  _M_reallocate_map is called only
>> if new size is smaller then max_size.  map is an array holding pointers to
>> entries of fixed size.
>>
>> Since rellocation is done by doubling the map size, I think the maximal size of
>> map allocated is max_size / deque_buf_size rounded up times two.  This should
>> be also safe for overflows since we have extra bit.
>>
>> map size is always at least 8. Theoretically this computation may be wrong for
>> very large T, but in that case callers should never reallocate.
>>
>> On the testcase I get:
>> jh@shroud:~> ~/trunk-install-new4/bin/g++ -O2 dq.C -c ; size -A dq.o | grep text
>> .text                                              284      0
>> .text._ZNSt5dequeIiSaIiEE17_M_reallocate_mapEmb    485      0
>> .text.unlikely                                      10      0
>> jh@shroud:~> ~/trunk-install-new5/bin/g++ -O2 dq.C -c ; size -A dq.o | grep text
>> .text                                              284      0
>> .text._ZNSt5dequeIiSaIiEE17_M_reallocate_mapEmb    465      0
>> .text.unlikely                                      10      0
>>
>> so this saves about 20 bytes of rellocate_map, which I think is worthwhile.
>> Curiously enough gcc14 does:
>>
>> jh@shroud:~> g++ -O2 dq.C -c ; size -A dq.o | grep text
>> .text                 604      0
>> .text.unlikely         10      0
>>
>> which is 145 bytes smaller. Obvoius difference is that _M_reallocate_map gets inlined.
>> Compiling gcc14 preprocessed file with trunk gives:
>>
>> jh@shroud:~> g++ -O2 dq.C -S ; size -A dq.o | grep text
>> .text                 762      0
>> .text.unlikely         10      0
>>
>> So inlining is due to changes at libstdc++ side, but code size growth is due to
>> something else.
>>
>> For clang this reduced number of thris_bad_new_array_length from 121 to 61.
>>
>> Regtested x86_64-linux, OK?
>>
>> libstdc++-v3/ChangeLog:
>>
>> 	* include/bits/deque.tcc: Compute maximal size of alloc_map.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 	* g++.dg/tree-ssa/deque.C: New test.
>>
>>
>> diff --git a/gcc/testsuite/g++.dg/tree-ssa/deque.C b/gcc/testsuite/g++.dg/tree-ssa/deque.C
>> new file mode 100644
>> index 00000000000..c79de9b2161
>> --- /dev/null
>> +++ b/gcc/testsuite/g++.dg/tree-ssa/deque.C
>> @@ -0,0 +1,9 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O1 -fdump-tree-optimized" } */
>> +#include <deque>
>> +void
>> +test(std::deque<int> &q, int v)
>> +{
>> +  q.push_back (v);
>> +}
>> +// { dg-final { scan-tree-dump-not "throw_bad_alloc" "optimized" } }
>> diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
>> index deb010a0ebb..653354f90a7 100644
>> --- a/libstdc++-v3/include/bits/deque.tcc
>> +++ b/libstdc++-v3/include/bits/deque.tcc
>> @@ -955,6 +955,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>>  	  size_type __new_map_size = this->_M_impl._M_map_size
>>  				     + std::max(this->_M_impl._M_map_size,
>>  						__nodes_to_add) + 2;
>> +	  size_type __max = __deque_buf_size(sizeof(_Tp));
>> +	  if (__new_map_size > ((max_size() + __deque_buf_size(sizeof(_Tp)) - 1)
>> +			        / __deque_buf_size(sizeof(_Tp))) * 2)
>> +	    __builtin_unreachable ();
>
>I forgot dead variable here which yields to -Wall warning.  Also I
>noticed that deque copy operation may be optimized if we know that
>size <= max_size.
>With this change we can now fully optimize away unused deque copies.  I
>am not sure how common it is in practice, but I think all the containers
>should be optimizable this way.
>
>Next interesting challenge (seen at llvm binary) is std::hash.
>
>Here is updated patch which got regtested&bootstrapped on x86_64-linux
>
>libstdc++-v3/ChangeLog:
>
>	* include/bits/deque.tcc (std::deque::_M_reallocate_map): Add
>	__builtin_unreachable check to declare that maps are not very large.
>	* include/bits/stl_deque.h (std::deque::size): Add __builtin_unreachable
>	to check for maximal size of map.
>
>gcc/testsuite/ChangeLog:
>
>	* g++.dg/tree-ssa/deque-1.C: New test.
>	* g++.dg/tree-ssa/deque-2.C: New test.
>
>diff --git a/gcc/testsuite/g++.dg/tree-ssa/deque-1.C b/gcc/testsuite/g++.dg/tree-ssa/deque-1.C
>new file mode 100644
>index 00000000000..c639ebb1a5f
>--- /dev/null
>+++ b/gcc/testsuite/g++.dg/tree-ssa/deque-1.C
>@@ -0,0 +1,9 @@
>+// { dg-do compile }
>+// { dg-options "-O1 -fdump-tree-optimized" }
>+#include <deque>
>+void
>+test(std::deque<int> &q, int v)
>+{
>+  q.push_back (v);
>+}
>+// { dg-final { scan-tree-dump-not "throw_bad_alloc" "optimized" } }
>diff --git a/gcc/testsuite/g++.dg/tree-ssa/deque-2.C b/gcc/testsuite/g++.dg/tree-ssa/deque-2.C
>new file mode 100644
>index 00000000000..7e268b3f018
>--- /dev/null
>+++ b/gcc/testsuite/g++.dg/tree-ssa/deque-2.C
>@@ -0,0 +1,10 @@
>+// { dg-do compile }
>+// { dg-options "-O3 -fdump-tree-optimized" }
>+#include <deque>
>+std::deque<int *>
>+test2(std::deque<int *> &q)
>+{
>+  return q;
>+}
>+// rethrow is OK, but throw is not.
>+// { dg-final { scan-tree-dump-not {[^e]throw} "optimized" } }
>diff --git a/libstdc++-v3/include/bits/deque.tcc b/libstdc++-v3/include/bits/deque.tcc
>index deb010a0ebb..e56cd0b9319 100644
>--- a/libstdc++-v3/include/bits/deque.tcc
>+++ b/libstdc++-v3/include/bits/deque.tcc
>@@ -955,6 +955,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> 	  size_type __new_map_size = this->_M_impl._M_map_size
> 				     + std::max(this->_M_impl._M_map_size,
> 						__nodes_to_add) + 2;
>+	  if (__new_map_size > ((max_size() + __deque_buf_size(sizeof(_Tp)) - 1)
>+			        / __deque_buf_size(sizeof(_Tp))) * 2)
>+	    __builtin_unreachable ();

I think it's worth avoiding the duplicate call, for -O0 -std=c++98.
It makes the line shorter too:

   const size_t __bufsz = __deque_buf_size(sizeof(_Tp));
   if (__new_map_size > ((max_size() + __bufsz - 1) / __bufsz) * 2)
     __builtin_unreachable();


>
> 	  _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
> 	  __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
>diff --git a/libstdc++-v3/include/bits/stl_deque.h b/libstdc++-v3/include/bits/stl_deque.h
>index c617933bd81..e47e7059330 100644
>--- a/libstdc++-v3/include/bits/stl_deque.h
>+++ b/libstdc++-v3/include/bits/stl_deque.h
>@@ -1266,7 +1266,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>       _GLIBCXX_NODISCARD
>       size_type
>       size() const _GLIBCXX_NOEXCEPT
>-      { return this->_M_impl._M_finish - this->_M_impl._M_start; }
>+      {
>+	size_type __siz = this->_M_impl._M_finish - this->_M_impl._M_start;

__sz here too please.

>+	if (__siz > max_size ())
>+	  __builtin_unreachable ();
>+	return __siz;
>+      }
>
>       /**  Returns the size() of the largest possible %deque.  */
>       _GLIBCXX_NODISCARD



More information about the Libstdc++ mailing list