libstdc++: Speed up push_back
Jan Hubicka
hubicka@ucw.cz
Fri Nov 24 20:07:35 GMT 2023
> With my changes at -O3 we now inline push_back, so we could optimize the
> first loop to the second. However with
> ~/trunk-install/bin/gcc -O3 auto.C -S -fdump-tree-all-details -fno-exceptions -fno-store-merging -fno-tree-slp-vectorize
> the fist problem is right at the begining:
>
> <bb 2> [local count: 97603128]:
> MEM[(struct _Vector_impl_data *)x_4(D)]._M_start = 0B;
> MEM[(struct _Vector_impl_data *)x_4(D)]._M_finish = 0B;
> MEM[(struct _Vector_impl_data *)x_4(D)]._M_end_of_storage = 0B;
> _37 = operator new (40);
> _22 = x_4(D)->D.26019._M_impl.D.25320._M_finish;
> _23 = x_4(D)->D.26019._M_impl.D.25320._M_start;
Thinking of this problem, it is easy to adjust reserve to copy _M_start
and _M_finish to local variables across the call of new() which makes
the old values visible to compiler regardless of points-to-analysis.
In fact _M_realloc_insert already has such code:
// Make local copies of these members because the compiler thinks
// the allocator can alter them if 'this' is globally reachable.
pointer __old_start = this->_M_impl._M_start;
pointer __old_finish = this->_M_impl._M_finish;
So attached patch does that in reserve. The downside is that if things
are not inlined we may end up pushing extra copy to stack, but I believe
the benefit from inlining actually pays this back.
The testcase with loop still does not optimize it so I simplified it:
#include <vector>
auto
f()
{
std::vector<int> x;
x.reserve(10);
x.push_back(0);
x.push_back(0);
x.push_back(0);
x.push_back(0);
x.push_back(0);
x.push_back(0);
x.push_back(0);
x.push_back(0);
x.push_back(0);
return x;
}
auto
g()
{ return std::vector<int>(10, 0); }
This now compiles to less code but it is somewhat funny:
<bb 2> [local count: 1073741824]:
MEM <vector(2) long unsigned int> [(int * *)x_3(D)] = { 0, 0 };
MEM[(struct _Vector_impl_data *)x_3(D)]._M_end_of_storage = 0B;
_70 = operator new (40);
<bb 3> [local count: 1073741824]:
x_3(D)->D.26024._M_impl.D.25325._M_start = _70;
_65 = _70 + 40;
x_3(D)->D.26024._M_impl.D.25325._M_end_of_storage = _65;
_74 = _70 + 4;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _74;
MEM <unsigned long> [(int *)_70] = 0;
_80 = _70 + 8;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _80;
*_80 = 0;
_86 = _70 + 12;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _86;
*_86 = 0;
_92 = _70 + 16;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _92;
*_92 = 0;
_98 = _70 + 20;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _98;
*_98 = 0;
_104 = _70 + 24;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _104;
*_104 = 0;
_110 = _70 + 28;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _110;
*_110 = 0;
_116 = _70 + 32;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _116;
*_116 = 0;
_122 = _70 + 36;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _122;
return x_3(D);
The setup code in BB2 is useless and due to fake escape, as discussed in
PRR112653.
However it is funny that we miss dead store elimintation and repeately
set x_3(D)->D.26024._M_impl.D.25325._M_finish = _104;
The problem here is that until pushback.C.208t.forwprop4:std::vector we
do not optimize the reallocation code:
<bb 2> [local count: 1073741824]:
MEM <vector(2) long unsigned int> [(int * *)x_3(D)] = { 0, 0 };
MEM[(struct _Vector_impl_data *)x_3(D)]._M_end_of_storage = 0B;
_70 = operator new (40);
<bb 3> [local count: 1073741824]:
x_3(D)->D.26024._M_impl.D.25325._M_start = _70;
_65 = _70 + 40;
x_3(D)->D.26024._M_impl.D.25325._M_end_of_storage = _65;
*_70 = 0;
_74 = _70 + 4;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _74;
D.26115 = 0;
if (_65 != _74)
goto <bb 4>; [82.57%]
else
goto <bb 5>; [17.43%]
<bb 4> [local count: 886588624]:
*_74 = 0;
_80 = _70 + 8;
x_3(D)->D.26024._M_impl.D.25325._M_finish = _80;
goto <bb 8>; [100.00%]
<bb 5> [local count: 187153200]:
std::vector<int>::_M_realloc_append<int> (x_3(D), &D.26115);
goto <bb 7>; [100.00%]
<bb 6> [count: 0]:
<L12>:
goto <bb 44>; [100.00%]
<bb 7> [local count: 187153200]:
pretmp_127 = MEM[(int * const &)x_3(D) + 8];
pretmp_144 = MEM[(struct _Vector_base *)x_3(D)]._M_impl.D.25325._M_end_of_storage;
And after forwprop4 it is too late because DSE is no longer run.
I filled PR112706. For some reason FRE is missing to optimize:
int *ptr;
void link_error ();
void
test ()
{
int *ptr1 = ptr + 10;
int *ptr2 = ptr + 20;
if (ptr1 == ptr2)
link_error ();
}
The vector.tcc change was regtested on x86_64-linux, OK?
libstdc++-v3/ChangeLog:
* include/bits/vector.tcc (reserve): Copy _M_start and _M_finish
to local variables to allow propagation across call to
allocator.
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 0ccef7911b3..0a9db29c1c7 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -72,27 +72,30 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
if (this->capacity() < __n)
{
const size_type __old_size = size();
+ // Make local copies of these members because the compiler thinks
+ // the allocator can alter them if 'this' is globally reachable.
+ pointer __old_start = this->_M_impl._M_start;
+ pointer __old_finish = this->_M_impl._M_finish;
pointer __tmp;
#if __cplusplus >= 201103L
if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
{
__tmp = this->_M_allocate(__n);
- _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _S_relocate(__old_start, __old_finish,
__tmp, _M_get_Tp_allocator());
}
else
#endif
{
__tmp = _M_allocate_and_copy(__n,
- _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
- _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
- std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(__old_start),
+ _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(__old_finish));
+ std::_Destroy(__old_start, __old_finish,
_M_get_Tp_allocator());
}
_GLIBCXX_ASAN_ANNOTATE_REINIT;
- _M_deallocate(this->_M_impl._M_start,
- this->_M_impl._M_end_of_storage
- - this->_M_impl._M_start);
+ _M_deallocate(__old_start,
+ this->_M_impl._M_end_of_storage - __old_finish);
this->_M_impl._M_start = __tmp;
this->_M_impl._M_finish = __tmp + __old_size;
this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
More information about the Gcc-patches
mailing list