optimize std::vector move assignment

[Marc Glisse]

Hello,

I talked about this last year 
(https://gcc.gnu.org/ml/gcc-patches/2017-04/msg01063.html and thread), 
this tweaks std::vector move assignment to help gcc generate better code 
for it.

For this code

#include <vector>
#include <utility>
typedef std::vector<int> V;
void f(V&a,V&b){a=std::move(b);}

with -O2 -fdump-tree-optimized on powerpc64le-unknown-linux-gnu, we 
currently have

   _5 = MEM[(int * &)a_3(D)];
   MEM[(int * &)a_3(D)] = 0B;
   MEM[(int * &)a_3(D) + 8] = 0B;
   MEM[(int * &)a_3(D) + 16] = 0B;
   _6 = MEM[(int * &)b_2(D)];
   MEM[(int * &)a_3(D)] = _6;
   MEM[(int * &)b_2(D)] = 0B;
   _7 = MEM[(int * &)a_3(D) + 8];
   _8 = MEM[(int * &)b_2(D) + 8];
   MEM[(int * &)a_3(D) + 8] = _8;
   MEM[(int * &)b_2(D) + 8] = _7;
   _9 = MEM[(int * &)a_3(D) + 16];
   _10 = MEM[(int * &)b_2(D) + 16];
   MEM[(int * &)a_3(D) + 16] = _10;
   MEM[(int * &)b_2(D) + 16] = _9;
   if (_5 != 0B)

with the patch, we go down to

   _3 = MEM[(const struct _Vector_impl_data &)a_4(D)]._M_start;
   _5 = MEM[(const struct _Vector_impl_data &)b_2(D)]._M_start;
   MEM[(struct _Vector_impl_data *)a_4(D)]._M_start = _5;
   _6 = MEM[(const struct _Vector_impl_data &)b_2(D)]._M_finish;
   MEM[(struct _Vector_impl_data *)a_4(D)]._M_finish = _6;
   _7 = MEM[(const struct _Vector_impl_data &)b_2(D)]._M_end_of_storage;
   MEM[(struct _Vector_impl_data *)a_4(D)]._M_end_of_storage = _7;
   MEM[(struct _Vector_impl_data *)b_2(D)]._M_start = 0B;
   MEM[(struct _Vector_impl_data *)b_2(D)]._M_finish = 0B;
   MEM[(struct _Vector_impl_data *)b_2(D)]._M_end_of_storage = 0B;
   if (_3 != 0B)

removing 2 reads and 3 writes. At -O3 we also get more vectorization.

The main idea is to give the compiler more type information. Currently, 
the only type information the compiler cares about is the type used for a 
memory read/write. Using std::swap as before, the reads/writes are done on 
int&. Doing it directly, they are done on _Vector_impl_data::_M_start, a 
more precise information. Maybe some day the compiler will get stricter 
and be able to deduce the same information, but not yet.

The second point is to rotate { new, old, tmp } in an order that's simpler 
for the compiler. I was going to remove the swaps and use _M_copy_data 
directly, but since doing the swaps in a different order works...

_M_copy_data is not really needed, we could add a defaulted assignment 
operator, or remove the move constructor (and call a new _M_clear() from 
the 2 users), etc. However, it seemed the least intrusive, the least 
likely to have weird consequences.

I didn't add a testcase because I don't see any dg-final scan-tree-dump in 
the libstdc++ testsuite. The closest would be g++.dg/pr83239.C, 
g++.dg/vect/pr64410.cc, g++.dg/vect/pr33426-ivdep-4.cc that include 
<vector>, but from previous experience (already with vector), adding 
libstdc++ testcases to the C++ testsuite is not very popular.

Bootstrap+regtest on powerpc64le-unknown-linux-gnu.

2018-07-25  Marc Glisse  <marc.glisse@inria.fr>

 	* include/bits/stl_vector.h (_Vector_impl_data::_M_copy_data): New.
 	(_Vector_impl_data::_M_swap_data): Use _M_copy_data.
 	(vector::_M_move_assign): Reorder the swaps.

-- 
Marc Glisse
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vmove.patch
Type: text/x-diff
Size: 2376 bytes
Desc: 
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20180725/8bdb420c/attachment.bin>