> On 24/11/24 01:42 +0100, Jan Hubicka wrote:
> > Hi,
> > another common source of unnecesary throw_bad_alloc calls is
> > basic_string::_M_create.
> > basic_string<_CharT, _Traits, _Alloc>::
> > _M_create(size_type& __capacity, size_type __old_capacity)
> > {
> > // _GLIBCXX_RESOLVE_LIB_DEFECTS
> > // 83. String::npos vs. string::max_size()
> > if (__capacity > max_size())
> > std::__throw_length_error(__N("basic_string::_M_create"));
> >
> > // The below implements an exponential growth policy, necessary to
> > // meet amortized linear time requirements of the library: see
> > // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
> > if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
> > {
> > __capacity = 2 * __old_capacity;
> > // Never allocate a string bigger than max_size.
> > if (__capacity > max_size())
> > __capacity = max_size();
> > }
> >
> > // NB: Need an array of char_type[__capacity], plus a terminating
> > // null char_type() element.
> > return _S_allocate(_M_get_allocator(), __capacity + 1);
> > }
> >
> > The code makes it visible that string is never bigger then max_size,
> > however + 1
> > makes it one byte bigger than maximal size allowed by allocator. I believe
> > this is by miscounting the 0 at the end of string in max_size function:
> >
> > - { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
> > + { return _Alloc_traits::max_size(_M_get_allocator()) / 2 - 1; }
>
> Ah yes, good catch. That code was copied from ext/sso_string_base.h
> where it has been present since r0-76546-g3ad7074772808f in 2006!
it was caught by VRP :)
I was thinking to try to add warning attribute to that throw_bad_allocv
and see what comes out.
Thinking of that code, I am not sure it is correct, still. I see that
allocator's max_size returns full address space and / 2 is needed to get
to ptr_diff_t range. However I think allocator is not required to
return full address space and in case it returns something smaller,
diding by 2 is not necessary. In fact I think this already happen for
wstring.
Vector's max size is:
static _GLIBCXX20_CONSTEXPR size_type
_S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
{
// std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX,
// and realistically we can't store more than PTRDIFF_MAX/sizeof(T)
// (even if std::allocator_traits::max_size says we can).
const size_t __diffmax
= __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp);
const size_t __allocmax = _Alloc_traits::max_size(__a);
return (std::min)(__diffmax, __allocmax);
}
Perhaps we want to do the same here just add -1 for the trailing 0?
{
const size_t __diffmax
= __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_charT);
const size_t __allocmax = _Alloc_traits::max_size(_M_get_allocator());
return (std::min)(__diffmax, __allocmax) - 1;
}
> > I find it funny that the code special cases a.size () == 1 to copy single
> > byte
> > and a.size () == 0 to bypass memcpy call. I would say it is job of
> > middle-end
> > to optimize memcpy reasonably even for small blocks. Was this based on
> > some data
> > showing that many strings have size of 0 and 1 which is not visible to
> > compiler?
>
> That was added as _M_copy in 2004 by r0-62838-gec61e852bc917b and when
> I implemented the new std::__cxx11::basic_string I copied it, only
> renaming it to _S_copy because that's our convention for static member
> functions.
>
> There's no explanation in the ChangeLog (obviously, because ChangeLog
> files are useless at telling you *why* something happened), but this
> comment was added:
>
> + // When __n = 1 way faster than the general multichar
> + // traits_type::copy/move/assign.
>
> Back in 2004 char_traits<char>::copy called memcpy (not
> __builtin_memcpy) and maybe it was badly optimized.
>
> I think we can probably drop that "optimization" for __n == 1.
If size of string is not compile-time constant, gcc by default will call
memcpy (on x86 memcpy is faster for very large memory blocks) which does
have fast path for small blocks. So the code special casing _n == 1 may
get faster for variably sized strings that are very often of size 1, but
that observation applies to many other copy operations we have around.
>
> Please use __sz for these variables, as that's consistent with names
> used elsewhere.
Updated in my tree.
>
> > + if (__siz > max_size ())
> > + __builtin_unreachable ();
> > + return __siz;
> > + }
> >
> > /// Returns the number of characters in the string, not including any
> > /// null-termination.
> > _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
> > size_type
> > length() const _GLIBCXX_NOEXCEPT
> > - { return _M_string_length; }
> > + {
> > + size_type __siz = _M_string_length;
> > + if (__siz > max_size ())
> > + __builtin_unreachable ();
> > + return __siz;
>
> Should this just call size() instead of repeating the definition?
I also changed this to call.
>
> > + }
> >
> > /// Returns the size() of the largest possible %string.
> > _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
> > size_type
> > max_size() const _GLIBCXX_NOEXCEPT
> > - { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
> > + { return _Alloc_traits::max_size(_M_get_allocator()) / 2 - 1; }
> >
> > /**
> > * @brief Resizes the %string to the specified number of characters.
> > @@ -1184,8 +1194,11 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11
> > size_type
> > capacity() const _GLIBCXX_NOEXCEPT
> > {
> > - return _M_is_local() ? size_type(_S_local_capacity)
> > - : _M_allocated_capacity;
> > + size_t __siz = _M_is_local() ? size_type(_S_local_capacity)
>
> size_type __sz = ...
Also fixed
>
> > + : _M_allocated_capacity;
> > + if (__siz < _S_local_capacity || __siz > max_size () + 1)
>
> Is this +1 correct?
>
> I think it should be simply `__siz > max_size()`
>
> The largest allocation allowed is max_size()+1 but the value stored in
> _M_allocated_capacity will be just max_size() without the +1.
You are right. I misunderstood the code and tought capacity includes
also the trailing 0.
Honza
