Re: [libstdc++] Improve M_check_len

[Jonathan Wakely <jwakely@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 4469 bytes --]

On Sun, 18 Jun 2023 at 19:37, Jan Hubicka <hubicka@ucw.cz> wrote:

> Hi,
> _M_check_len is used in vector reallocations. It computes __n + __s but
> does
> checking for case that (__n + __s) * sizeof (Tp) would overflow ptrdiff_t.
> Since we know that __s is a size of already allocated memory block if __n
> is
> not too large, this will never happen on 64bit systems since memory is not
> that
> large.  This patch adds __builtin_constant_p checks for this case.  This
> size
> of fully inlined push_back function that is critical for loops that are
> controlled by std::vector based stack.
>
> With the patch to optimize std::max and to handle SRA candidates, we
> fully now inline push_back with -O3 (not with -O2), however there are still
> quite few silly things for example:
>
>   //  _78 is original size of the allocated vector.
>
>   _76 = stack$_M_end_of_storage_177 - _142;
>   _77 = _76 /[ex] 8;
>   _78 = (long unsigned int) _77;
>   _79 = MAX_EXPR <_78, 1>;
>   _80 = _78 + _79; // this is result of _M_check_len doubling the
> allocated vector size.
>   if (_80 != 0)    // result will always be non-zero.
>     goto <bb 7>; [54.67%]
>   else
>     goto <bb 13>; [45.33%]
>
>   <bb 7> [local count: 30795011]:
>   if (_80 > 1152921504606846975)  // doubling succesfully allocated
> memmory will never get so large.
>     goto <bb 8>; [10.00%]
>   else
>     goto <bb 11>; [90.00%]
>
>   <bb 8> [local count: 3079501]:
>   if (_80 > 2305843009213693951)  // I wonder if we really want to have
> two different throws
>     goto <bb 9>; [50.00%]
>   else
>     goto <bb 10>; [50.00%]
>
>   <bb 9> [local count: 1539750]:
>   std::__throw_bad_array_new_length ();
>
>   <bb 10> [local count: 1539750]:
>   std::__throw_bad_alloc ();
>
>   <bb 11> [local count: 27715510]:
>   _108 = _80 * 8;
>   _109 = operator new (_108);
>
> Maybe we want to add assumption that result of the function is never
> greater than max_size to get rid of the two checks above.  However this
> will still be recongized only after inlining and will continue confusing
> inliner heuristics.
>
> Bootstrapped/regtested x86_64-linux.  I am not too familiar with libstdc++
> internals,
> so would welcome comments and ideas.
>
> libstdc++-v3/ChangeLog:
>
>         PR tree-optimization/110287
>         * include/bits/stl_vector.h: Optimize _M_check_len for constantly
> sized
>         types and allocations.
>
> diff --git a/libstdc++-v3/include/bits/stl_vector.h
> b/libstdc++-v3/include/bits/stl_vector.h
> index 70ced3d101f..3ad59fe3e2b 100644
> --- a/libstdc++-v3/include/bits/stl_vector.h
> +++ b/libstdc++-v3/include/bits/stl_vector.h
> @@ -1895,11 +1895,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
>        size_type
>        _M_check_len(size_type __n, const char* __s) const
>        {
> -       if (max_size() - size() < __n)
> -         __throw_length_error(__N(__s));
> +       // On 64bit systems vectors of small sizes can not
> +       // reach overflow by growing by small sizes; before
> +       // this happens, we will run out of memory.
> +       if (__builtin_constant_p (sizeof (_Tp))
>

This shouldn't be here, of course sizeof is a constant.

No space before the opening parens, libstdc++ doesn't follow GNU style.



> +           && __builtin_constant_p (__n)
> +           && sizeof (ptrdiff_t) >= 8
> +           && __n < max_size () / 2)
>

This check is not OK. As I said in Bugzilla just now, max_size() depends on
the allocator, which could return something much smaller than PTRDIFF_MAX.
You can't make this assumption for all specializations of std::vector.

If Alloc::max_size() == 100 and this->size() == 100 then this function
needs to throw length_error for *any* n. In the general case you cannot
remove size() from this condition.

For std::allocator<T> it's safe to assume that max_size() is related to
PTRDIFF_MAX/sizeof(T), but this patch would apply to all allocators.



> +         return size() + (std::max)(size(), __n);
>
+       else
> +         {
> +           if (max_size() - size() < __n)
> +             __throw_length_error(__N(__s));
>
> -       const size_type __len = size() + (std::max)(size(), __n);
> -       return (__len < size() || __len > max_size()) ? max_size() : __len;
> +           const size_type __len = size() + (std::max)(size(), __n);
> +           return (__len < size() || __len > max_size()) ? max_size() :
> __len;
> +         }
>        }
>
>        // Called by constructors to check initial size.
>
>