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