Re: [libstdc++] Improve M_check_len

[Jan Hubicka <hubicka@ucw.cz>]

> > -       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.
OK :)
> 
> No space before the opening parens, libstdc++ doesn't follow GNU style.
Fixed.
> 
> 
> 
> > +           && __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.

Here is updated version.  I simply __builtin_constant_p max_size and
test it is large enough.  For that we need to copy it into temporary
variable since we fold-const __builtin_constant_p (function (x))
early, before function gets inlined.

I also added __builtin_unreachable to determine return value range
as discussed in PR.

Honza

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 70ced3d101f..7a1966405ca 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -1895,11 +1895,29 @@ _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));
+	const size_type __max_size = max_size();
+	// On 64bit systems vectors can not reach overflow by growing
+	// by small sizes; before this happens, we will run out of memory.
+	if (__builtin_constant_p(__n)
+	    && __builtin_constant_p(__max_size)
+	    && sizeof(ptrdiff_t) >= 8
+	    && __max_size * sizeof(_Tp) >= ((ptrdiff_t)1 << 60)
+	    && __n < __max_size / 2)
+	  {
+	    const size_type __len = size() + (std::max)(size(), __n);
+	    // let compiler know that __len has sane value range.
+	    if (__len < __n || __len >= __max_size)
+	      __builtin_unreachable();
+	    return __len;
+	  }
+	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.