From: Jonathan Wakely <jwakely@redhat.com>
To: Jan Hubicka <hubicka@ucw.cz>
Cc: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org
Subject: Re: libstdc++: Speed up push_back
Date: Tue, 21 Nov 2023 13:07:52 +0000 [thread overview]
Message-ID: <CACb0b4k=VW4FJdckeXmNFDuzoF1X-gcHkuOgtdJjjymGThD+aA@mail.gmail.com> (raw)
In-Reply-To: <ZVynpY5Sz5+DZAKR@kam.mff.cuni.cz>
On Tue, 21 Nov 2023 at 12:50, 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 am attaching patch with this check removed. However I still think
> Guard_elts needs to stay to be able to destroy the old ellements
> >
> > > +
> > > + // New storage has been fully initialized, destroy the old elements.
> > > + __guard_elts._M_first = __old_start;
> > > + __guard_elts._M_last = __old_finish;
> ... here
>
> Does it look better? (I am not really that confidend with libstdc++).
Yes, looks good, thanks.
>
> I also was wondering if we do have some data on what libstdc++ functions
> are perofrmance critical in practice. Given that the push_back can be
> sped up very noticeably, I wonder if we don't have problems elsewhere?
We don't have that data, no.
It's possible that we could do similar things for insert(iterator pos,
...) for the case where pos==end(), i.e. inserting multiple elements
at the end.
>
> Thank you,
> Honza
>
> diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
> index 5e18f6eedce..973f4d7e2e9 100644
> --- a/libstdc++-v3/include/bits/stl_vector.h
> +++ b/libstdc++-v3/include/bits/stl_vector.h
> @@ -1288,7 +1288,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> _GLIBCXX_ASAN_ANNOTATE_GREW(1);
> }
> else
> - _M_realloc_insert(end(), __x);
> + _M_realloc_append(__x);
> }
>
> #if __cplusplus >= 201103L
> @@ -1822,6 +1822,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>
> void
> _M_realloc_insert(iterator __position, const value_type& __x);
> +
> + void
> + _M_realloc_append(const value_type& __x);
> #else
> // A value_type object constructed with _Alloc_traits::construct()
> // and destroyed with _Alloc_traits::destroy().
> @@ -1871,6 +1874,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> void
> _M_realloc_insert(iterator __position, _Args&&... __args);
>
> + template<typename... _Args>
> + _GLIBCXX20_CONSTEXPR
> + void
> + _M_realloc_append(_Args&&... __args);
> +
> // Either move-construct at the end, or forward to _M_insert_aux.
> _GLIBCXX20_CONSTEXPR
> iterator
> diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
> index 80631d1e2a1..0ccef7911b3 100644
> --- a/libstdc++-v3/include/bits/vector.tcc
> +++ b/libstdc++-v3/include/bits/vector.tcc
> @@ -120,7 +120,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> _GLIBCXX_ASAN_ANNOTATE_GREW(1);
> }
> else
> - _M_realloc_insert(end(), std::forward<_Args>(__args)...);
> + _M_realloc_append(std::forward<_Args>(__args)...);
> #if __cplusplus > 201402L
> return back();
> #endif
> @@ -459,6 +459,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> #endif
> {
> const size_type __len = _M_check_len(1u, "vector::_M_realloc_insert");
> + if (__len <= 0)
> + __builtin_unreachable ();
> pointer __old_start = this->_M_impl._M_start;
> pointer __old_finish = this->_M_impl._M_finish;
> const size_type __elems_before = __position - begin();
> @@ -571,6 +573,127 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> this->_M_impl._M_end_of_storage = __new_start + __len;
> }
>
> +#if __cplusplus >= 201103L
> + template<typename _Tp, typename _Alloc>
> + template<typename... _Args>
> + _GLIBCXX20_CONSTEXPR
> + void
> + vector<_Tp, _Alloc>::
> + _M_realloc_append(_Args&&... __args)
> +#else
> + template<typename _Tp, typename _Alloc>
> + void
> + vector<_Tp, _Alloc>::
> + _M_realloc_append(const _Tp& __x)
> +#endif
> + {
> + const size_type __len = _M_check_len(1u, "vector::_M_realloc_append");
> + if (__len <= 0)
> + __builtin_unreachable ();
> + pointer __old_start = this->_M_impl._M_start;
> + pointer __old_finish = this->_M_impl._M_finish;
> + const size_type __elems = end() - begin();
> + pointer __new_start(this->_M_allocate(__len));
> + pointer __new_finish(__new_start);
> +
> + // RAII guard for allocated storage.
> + struct _Guard
> + {
> + pointer _M_storage; // Storage to deallocate
> + size_type _M_len;
> + _Tp_alloc_type& _M_alloc;
> +
> + _GLIBCXX20_CONSTEXPR
> + _Guard(pointer __s, size_type __l, _Tp_alloc_type& __a)
> + : _M_storage(__s), _M_len(__l), _M_alloc(__a)
> + { }
> +
> + _GLIBCXX20_CONSTEXPR
> + ~_Guard()
> + {
> + if (_M_storage)
> + __gnu_cxx::__alloc_traits<_Tp_alloc_type>::
> + deallocate(_M_alloc, _M_storage, _M_len);
> + }
> +
> + private:
> + _Guard(const _Guard&);
> + };
> +
> + {
> + _Guard __guard(__new_start, __len, _M_impl);
> +
> + // The order of the three operations is dictated by the C++11
> + // case, where the moves could alter a new element belonging
> + // to the existing vector. This is an issue only for callers
> + // taking the element by lvalue ref (see last bullet of C++11
> + // [res.on.arguments]).
> +
> + // If this throws, the existing elements are unchanged.
> +#if __cplusplus >= 201103L
> + _Alloc_traits::construct(this->_M_impl,
> + std::__to_address(__new_start + __elems),
> + std::forward<_Args>(__args)...);
> +#else
> + _Alloc_traits::construct(this->_M_impl,
> + __new_start + __elems,
> + __x);
> +#endif
> +
> +#if __cplusplus >= 201103L
> + if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
> + {
> + // Relocation cannot throw.
> + __new_finish = _S_relocate(__old_start, __old_finish,
> + __new_start, _M_get_Tp_allocator());
> + ++__new_finish;
> + }
> + else
> +#endif
> + {
> + // RAII type to destroy initialized elements.
> + struct _Guard_elts
> + {
> + pointer _M_first, _M_last; // Elements to destroy
> + _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); }
> +
> + 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;
> +
> + // New storage has been fully initialized, destroy the old elements.
> + __guard_elts._M_first = __old_start;
> + __guard_elts._M_last = __old_finish;
> + }
> + __guard._M_storage = __old_start;
> + __guard._M_len = this->_M_impl._M_end_of_storage - __old_start;
> + }
> + // deallocate should be called before assignments to _M_impl,
> + // to avoid call-clobbering
> +
> + this->_M_impl._M_start = __new_start;
> + this->_M_impl._M_finish = __new_finish;
> + this->_M_impl._M_end_of_storage = __new_start + __len;
> + }
> +
> template<typename _Tp, typename _Alloc>
> _GLIBCXX20_CONSTEXPR
> void
>
next prev parent reply other threads:[~2023-11-21 13:08 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-11-19 21:53 Jan Hubicka
2023-11-20 12:09 ` Jonathan Wakely
2023-11-20 15:44 ` Jan Hubicka
2023-11-20 16:46 ` Jonathan Wakely
2023-11-21 12:50 ` Jan Hubicka
2023-11-21 13:07 ` Jonathan Wakely [this message]
2023-11-23 8:15 ` Matthias Kretz
2023-11-23 15:07 ` Jan Hubicka
2023-11-23 15:33 ` Jan Hubicka
2023-11-23 15:43 ` Jan Hubicka
2023-11-23 16:26 ` Jonathan Wakely
2023-11-23 16:20 ` Jonathan Wakely
2023-11-24 10:21 ` Martin Jambor
2023-11-24 10:23 ` Richard Biener
2023-11-24 19:45 ` Marc Glisse
2023-11-24 20:07 ` Jan Hubicka
2023-11-24 21:55 ` Jonathan Wakely
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CACb0b4k=VW4FJdckeXmNFDuzoF1X-gcHkuOgtdJjjymGThD+aA@mail.gmail.com' \
--to=jwakely@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=libstdc++@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).