Re: libstdc++: Speed up push_back

[Jonathan Wakely <jwakely.gcc@gmail.com>]

On Mon, 20 Nov 2023 at 15:44, Jan Hubicka <hubicka@ucw.cz> wrote:
>
> > > +           // RAII type to destroy initialized elements.
> >
> > There's only one initialized element, not "elements".
> >
> > > +           struct _Guard_elts
> > > +           {
> > > +             pointer _M_first, _M_last;  // Elements to destroy
> >
> > We only need to store one pointer here, call it _M_p.
> >
> > > +             _Tp_alloc_type& _M_alloc;
> > > +
> > > +             _GLIBCXX20_CONSTEXPR
> > > +             _Guard_elts(pointer __elt, _Tp_alloc_type& __a)
> > > +             : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a)
> > > +             { }
> > > +
> > > +             _GLIBCXX20_CONSTEXPR
> > > +             ~_Guard_elts()
> > > +             { std::_Destroy(_M_first, _M_last, _M_alloc); }
> >
> > This should be either:
> >
> >   std::_Destroy(_M_p, _M_p+1, _M_alloc);
> >
> > or avoid the loop that happens in that _Destroy function:
> >
> >   _Alloc_traits::destroy(_M_alloc, _M_p);
> >
> > > +
> > > +           private:
> > > +             _Guard_elts(const _Guard_elts&);
> > > +           };
> > > +
> > > +           // Guard the new element so it will be destroyed if anything throws.
> > > +           _Guard_elts __guard_elts(__new_start + __elems, _M_impl);
> > > +
> > > +           __new_finish = std::__uninitialized_move_if_noexcept_a(
> > > +                            __old_start, __old_finish,
> > > +                            __new_start, _M_get_Tp_allocator());
> > > +
> > > +           ++__new_finish;
> > > +           // Guard everything before the new element too.
> > > +           __guard_elts._M_first = __new_start;
> >
> > This seems redundant, we're not doing any more insertions now, and so
> > this store is dead.
>
> I removed this one.
> >
> > > +
> > > +           // New storage has been fully initialized, destroy the old elements.
> > > +           __guard_elts._M_first = __old_start;
> > > +           __guard_elts._M_last = __old_finish;
>
> However here I think I need __guard_elts supporting destruction of many
> elements in case the vector has moved to new location....

Ah yes.

> So I do not quite  see how to simplify the code as suggested above
> except that the constructor can be simplified to not require first and
> last argument since we always initialize it for 1 destruction but later
> we may update it.

We could just destroy the old ones manually at the end of this block,
it doesn't need to be done by the guard, e.g. update the guard to
destroy the first one, then loop to destroy the others:

__guard_elt._M_p = __old_start++;
std::_Destroy(__old_start, __old_finish, this->_M_impl);

But this would only improve codegen in the exceptional case when
something throws, and the guard destructor destroys a single element.
For the common case where we reach the end of the block, we're always
going to loop. So I agree with leaving __guard_elts in charge of two
pointers, and looping in its dtor.

So OK for trunk, with the dead store removed. Thanks!