[PATCH] libstdc++: Fix reserve of size_t(-1) elements in piecewise_constant_distribution. [PR113761]
Jonathan Wakely
jwakely@redhat.com
Wed May 13 16:26:20 GMT 2026
On Wed, 13 May 2026 at 15:04, Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>
>
>
> On Wed, May 13, 2026 at 3:37 PM Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> On Thu, 30 Apr 2026 at 13:03 +0200, Tomasz Kamiński wrote:
>> >The piecewise_constant_distribution constructor from std::initializer_list il,
>> >unconditionally _M_den reserved il.size()-1 elements. In case when the il.size()
>>
>> It looks like "_M_den" is not meant to be in this sentence?
>
> It was meant to say, unconditionally reserve _M_den for il.size() - 1 elements.
>
>>
>>
>> >was zero, this led to unsigned overflow, and attempt to allocate size_t(-1)
>> >elements.
>> >
>> >This patch addresses above, by refactoring the constructors of param_type for
>> >both piecewise_constant_distribution and piecewise_linear_distribution, to
>> >exit early (and do not populate internal vectors) if number of intervals range is
>> >smaller than two. For the constructor accepting pair of iterators, this is done
>> >by checking result of __detail::__load_first2, that extracts up to two elements,
>> >and returns false, if less than two is found.
>> >
>> >Futhremore, we if the number of intervals is equal to two (for iterator __bbegin
>>
>> Furthermore
>>
>> >is at __bend after __load_first2), we store densities value on stack, and call
>> >newly introduced an _M_initialize2 helper, that does not popluate internal vector
>>
>> populate
>>
>> >if __ints and __dens values correspond to default configuration.
>> >
>> >With both of above changes, we no longer populate _M_int and _M_den with default
>> >values, and corresponding code that clears them in _M_initialize is not necessary.
>> >This avoids any uncessary memory allocatos.
>> >
>> >Finally, for constructor accepting two iterators, we reserve required space
>> >in _M_int vector, if the iterators are forward (or model sized_sentinel in C++20).
>> >The _M_den initialization is performed afterwards, so _M_ints size is already
>>
>> _M_int's instead of _M_ints maybe?
>
> Yes.
>>
>>
>> >determined (even for input iterators) and it can be used for call to reserve.
>> >
>> > PR libstdc++/113761
>> >
>> >libstdc++-v3/ChangeLog:
>> >
>> > * include/bits/random.h
>> > (piecewise_constant_distribution::param_type::_M_initialize2)
>> > (piecewise_linear_distribution::param_type::_M_initialize2): Declare.
>> > * include/bits/random.tcc (__detail::__load_first2): Define.
>> > (piecewise_constant_distribution::param_type::_M_initialize)
>> > (piecewise_linear_distribution::param_type::_M_initialize):
>> > Remove checks for default values.
>> > (piecewise_constant_distribution::param_type::_M_initialize2)
>> > (piecewise_linear_distribution::param_type::_M_initialize2): Define.
>> > (piecewise_constant_distribution::param_type::param_type)
>> > (piecewise_linear_distribution::param_type::param_type):
>> > Exit early for less that two intervals. Use _M_initialize2 to handle
>> > two intervals case. Reserve _M_int for iterators case.
>> > * testsuite/26_numerics/random/piecewise_constant_distribution/cons/range.cc:
>> > Test input and forward iterators, in addition to random_access ones.
>> > * testsuite/26_numerics/random/piecewise_linear_distribution/cons/range.cc:
>> > Likewise.
>> > * testsuite/26_numerics/random/piecewise_constant_distribution/cons/fallback.cc:
>> > New test.
>> > * testsuite/26_numerics/random/piecewise_linear_distribution/cons/fallback.cc:
>> > New test.
>> >---
>> >Tested on x86_64-linux locally. *piecewise* tests additionally tested
>> >with all standard modes and modules. OK for trunk?
>> >
>> > libstdc++-v3/include/bits/random.h | 6 +
>> > libstdc++-v3/include/bits/random.tcc | 208 ++++++++++++++----
>> > .../cons/fallback.cc | 108 +++++++++
>> > .../cons/range.cc | 17 +-
>> > .../cons/fallback.cc | 127 +++++++++++
>> > .../cons/range.cc | 17 +-
>> > 6 files changed, 429 insertions(+), 54 deletions(-)
>> > create mode 100644 libstdc++-v3/testsuite/26_numerics/random/piecewise_constant_distribution/cons/fallback.cc
>> > create mode 100644 libstdc++-v3/testsuite/26_numerics/random/piecewise_linear_distribution/cons/fallback.cc
>> >
>> >diff --git a/libstdc++-v3/include/bits/random.h b/libstdc++-v3/include/bits/random.h
>> >index 3fda69c4399..d8125bb0f62 100644
>> >--- a/libstdc++-v3/include/bits/random.h
>> >+++ b/libstdc++-v3/include/bits/random.h
>> >@@ -6468,6 +6468,9 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
>> > void
>> > _M_initialize();
>> >
>> >+ void
>> >+ _M_initialize2(const _RealType* __ints, _RealType __den);
>> >+
>> > std::vector<_RealType> _M_int;
>> > std::vector<double> _M_den;
>> > std::vector<double> _M_cp;
>> >@@ -6748,6 +6751,9 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
>> > void
>> > _M_initialize();
>> >
>> >+ void
>> >+ _M_initialize2(const _RealType* __ints, const _RealType *__dens);
>>
>> Please move the * to the type instead of the parameter name.
>>
>> >+
>> > std::vector<_RealType> _M_int;
>> > std::vector<double> _M_den;
>> > std::vector<double> _M_cp;
>> >diff --git a/libstdc++-v3/include/bits/random.tcc b/libstdc++-v3/include/bits/random.tcc
>> >index 4475e365c2d..8d4e46c5168 100644
>> >--- a/libstdc++-v3/include/bits/random.tcc
>> >+++ b/libstdc++-v3/include/bits/random.tcc
>> >@@ -2947,16 +2947,6 @@ namespace __detail
>> > piecewise_constant_distribution<_RealType>::param_type::
>> > _M_initialize()
>> > {
>> >- if (_M_int.size() < 2
>> >- || (_M_int.size() == 2
>> >- && _M_int[0] == _RealType(0)
>> >- && _M_int[1] == _RealType(1)))
>> >- {
>> >- _M_int.clear();
>> >- _M_den.clear();
>> >- return;
>> >- }
>>
>> I'm wondering about the ABI impact of removing this chunk.
>>
>> If we have an object file which inlines the old definition of the
>> constructor and so still calls _M_initialize(), then if the linker
>> picks a new definition of _M_initialize() then we could get here with
>> _M_den.size() == 0 and the assertion below would fail.
>
> I would rename this function to _M_initialize_vecs; that should solve this
> bypass this completely. Forgot ABI break caused by moving checks to
> different function.
>>
>>
>> Do we need to preserve that code, but mark it as [[__unlikely__]] ?
>>
>> You could surround it with:
>> #if ! _GLIBCXX_INLINE_VERSION
>> so that for the unstable ABI we don't need the check and the early
>> return.
>>
>> >-
>> > const double __sum = std::accumulate(_M_den.begin(),
>> > _M_den.end(), 0.0);
>> > __glibcxx_assert(__sum > 0);
>> >@@ -2975,6 +2965,46 @@ namespace __detail
>> > _M_den[__k] /= _M_int[__k + 1] - _M_int[__k];
>> > }
>> >
>> >+ template<typename _RealType>
>> >+ void
>> >+ piecewise_constant_distribution<_RealType>::param_type::
>> >+ _M_initialize2(const _RealType *__ints, _RealType __den)
>>
>> Same here.
>
> You mean, move * here.
Ah yes, sorry. I went back and added the comment about ABI for
_M_initialize later, so this was no longer the "same" as the previous
comment.
>>
>>
>> >+ {
>> >+ if (__ints[0] == _RealType(0) && __ints[1] == _RealType(1))
>> >+ return;
>> >+
>> >+ _M_int.reserve(2);
>> >+ _M_int.push_back(__ints[0]);
>> >+ _M_int.push_back(__ints[1]);
>> >+
>> >+ _M_den.reserve(1);
>> >+ _M_den.push_back(__den);
>> >+ _M_initialize();
>> >+ }
>> >+
>> >+namespace __detail
>> >+{
>> >+ template<typename _InputIterator, typename _RealType>
>> >+ bool
>> >+ __load_first2(_InputIterator& __first, _InputIterator __last,
>> >+ _RealType* __out)
>> >+ {
>> >+ if (__first == __last)
>> >+ return false;
>> >+
>> >+ *__out = *__first;
>> >+ ++__first;
>> >+ if (__first == __last)
>> >+ return false;
>> >+
>> >+ ++__out;
>> >+ *__out = *__first;
>> >+ ++__first;
>> >+ return true;
>> >+ }
>> >+} // namespace __detail
>> >+
>> >+
>> > template<typename _RealType>
>> > template<typename _InputIteratorB, typename _InputIteratorW>
>> > piecewise_constant_distribution<_RealType>::param_type::
>> >@@ -2983,20 +3013,38 @@ namespace __detail
>> > _InputIteratorW __wbegin)
>> > : _M_int(), _M_den(), _M_cp()
>> > {
>> >- if (__bbegin != __bend)
>> >- {
>> >- for (;;)
>> >- {
>> >- _M_int.push_back(*__bbegin);
>> >- ++__bbegin;
>> >- if (__bbegin == __bend)
>> >- break;
>> >+ _RealType __ints[2];
>> >+ if (!__detail::__load_first2(__bbegin, __bend, __ints))
>> >+ return;
>> >
>> >- _M_den.push_back(*__wbegin);
>> >- ++__wbegin;
>> >- }
>> >+ if (__bbegin == __bend)
>> >+ {
>> >+ _M_initialize2(__ints, *__wbegin);
>> >+ return;
>> > }
>> >
>> >+#if __glibcxx_concepts // C++ >= C++20
>> >+ if constexpr (sized_sentinel_for<_InputIteratorB, _InputIteratorB>
>> >+ || forward_iterator<_InputIteratorB>)
>> >+ _M_int.reserve(2 + size_t(ranges::distance(__bbegin, __bend)));
>>
>> I think we get ranges::distance via <numeric>, right?
>
> We are getting it via #include <vector> in bits/random.h
ack
>>
>>
>> >+#else
>> >+#pragma GCC diagnostic push
>> >+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
>> >+ if constexpr (is_convertible<__iter_category_t<_InputIteratorB>,
>> >+ forward_iterator_tag>::value)
>> >+ _M_int.reserve(2 + size_t(std::distance(__bbegin, __bend)));
>> >+#pragma GCC diagnostic pop
>> >+#endif
>> >+
>> >+ _M_int.push_back(__ints[0]);
>> >+ _M_int.push_back(__ints[1]);
>> >+ for (; __bbegin != __bend; ++__bbegin)
>> >+ _M_int.push_back(*__bbegin);
>> >+
>> >+ _M_den.reserve(_M_int.size() - 1);
>> >+ for (size_t __k = 0; __k < _M_int.size() - 1; (void)++__k, ++__wbegin)
>> >+ _M_den.push_back(*__wbegin);
>>
>> If _InputIteratorW is contiguous it's possible that we'd get better
>> code using _M_den.assign(__wbegin, __wbegin + _M_int.size() - 1)
>> because it could be turned into a memcpy inside uninitialized_copy.
>
> I could. I used a loop, because I may want to convert (*__wbegin) to
> RealType before converting to double, see https://cplusplus.github.io/LWG/issue4052.
That makes sense.
>>
>>
>> But I think it's unlikely that the sequence will be long enough that
>> it matters, so this loop is ok.
>>
>> >+
>> > _M_initialize();
>> > }
>> >
>> >@@ -3006,10 +3054,18 @@ namespace __detail
>> > param_type(initializer_list<_RealType> __bl, _Func __fw)
>> > : _M_int(), _M_den(), _M_cp()
>> > {
>> >- _M_int.reserve(__bl.size());
>> >- for (auto __biter = __bl.begin(); __biter != __bl.end(); ++__biter)
>> >- _M_int.push_back(*__biter);
>> >+ if (__bl.size() < 2)
>> >+ return;
>> >+
>> >+ if (__bl.size() == 2)
>> >+ {
>> >+ const _RealType *__ints = __bl.begin();
>> >+ _RealType __den = __fw(0.5 * (__ints[1] + __ints[0]));
>> >+ _M_initialize2(__ints, __den);
>> >+ return;
>> >+ }
>> >
>> >+ _M_int = __bl;
>> > _M_den.reserve(_M_int.size() - 1);
>> > for (size_t __k = 0; __k < _M_int.size() - 1; ++__k)
>> > _M_den.push_back(__fw(0.5 * (_M_int[__k + 1] + _M_int[__k])));
>> >@@ -3025,6 +3081,13 @@ namespace __detail
>> > {
>> > const size_t __n = __nw == 0 ? 1 : __nw;
>> > const _RealType __delta = (__xmax - __xmin) / __n;
>> >+ if (__n == 1)
>> >+ {
>> >+ _RealType __ints[2] = { __xmin, __xmin + __delta };
>> >+ _RealType __den = __fw(__xmin * 0.5 * __delta);
>> >+ _M_initialize2(__ints, __den);
>> >+ return;
>> >+ }
>> >
>> > _M_int.reserve(__n + 1);
>> > for (size_t __k = 0; __k <= __nw; ++__k)
>> >@@ -3161,17 +3224,6 @@ namespace __detail
>> > piecewise_linear_distribution<_RealType>::param_type::
>> > _M_initialize()
>> > {
>> >- if (_M_int.size() < 2
>> >- || (_M_int.size() == 2
>> >- && _M_int[0] == _RealType(0)
>> >- && _M_int[1] == _RealType(1)
>> >- && _M_den[0] == _M_den[1]))
>> >- {
>> >- _M_int.clear();
>> >- _M_den.clear();
>> >- return;
>> >- }
>>
>> As before, can we end up calling the new definition of _M_initialize()
>> from an old object file, where _M_int is empty, and so the reserve
>> calls below still wrap to SIZE_MAX?
>
> Will rename this function.
>>
>>
>> >-
>> > double __sum = 0.0;
>> > _M_cp.reserve(_M_int.size() - 1);
>> > _M_m.reserve(_M_int.size() - 1);
>> >@@ -3194,7 +3246,27 @@ namespace __detail
>> >
>> > // Make sure the last cumulative probablility is one.
>> > _M_cp[_M_cp.size() - 1] = 1.0;
>> >- }
>> >+ }
>> >+
>> >+ template<typename _RealType>
>> >+ void
>> >+ piecewise_linear_distribution<_RealType>::param_type::
>> >+ _M_initialize2(const _RealType *__ints, const _RealType* __dens)
>> >+ {
>> >+ if (__ints[0] == _RealType(0)
>> >+ && __ints[1] == _RealType(1)
>> >+ && __dens[0] == __dens[1])
>> >+ return;
>> >+
>> >+ _M_int.reserve(2);
>> >+ _M_int.push_back(__ints[0]);
>> >+ _M_int.push_back(__ints[1]);
>> >+
>> >+ _M_den.reserve(2);
>> >+ _M_den.push_back(__dens[0]);
>> >+ _M_den.push_back(__dens[1]);
>> >+ _M_initialize();
>> >+ }
>> >
>> > template<typename _RealType>
>> > template<typename _InputIteratorB, typename _InputIteratorW>
>> >@@ -3204,12 +3276,42 @@ namespace __detail
>> > _InputIteratorW __wbegin)
>> > : _M_int(), _M_den(), _M_cp(), _M_m()
>> > {
>> >- for (; __bbegin != __bend; ++__bbegin, (void) ++__wbegin)
>> >+ _RealType __ints[2];
>> >+ if (!__detail::__load_first2(__bbegin, __bend, __ints))
>> >+ return;
>> >+
>> >+ if (__bbegin == __bend)
>> > {
>> >- _M_int.push_back(*__bbegin);
>> >- _M_den.push_back(*__wbegin);
>> >+ _RealType __dens[2];
>> >+ __dens[0] = *__wbegin;
>> >+ ++__wbegin;
>> >+ __dens[1] = *__wbegin;
>> >+ _M_initialize2(__ints, __dens);
>> >+ return;
>> > }
>> >
>> >+#if __glibcxx_concepts // C++ >= C++20
>> >+ if constexpr (sized_sentinel_for<_InputIteratorB, _InputIteratorB>
>> >+ || forward_iterator<_InputIteratorB>)
>> >+ _M_int.reserve(2 + size_t(ranges::distance(__bbegin, __bend)));
>> >+#else
>> >+#pragma GCC diagnostic push
>> >+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
>> >+ if constexpr (is_convertible<__iter_category_t<_InputIteratorB>,
>> >+ forward_iterator_tag>::value)
>> >+ _M_int.reserve(2 + size_t(std::distance(__bbegin, __bend)));
>> >+#pragma GCC diagnostic pop
>> >+#endif
>> >+
>> >+ _M_int.push_back(__ints[0]);
>> >+ _M_int.push_back(__ints[1]);
>> >+ for (; __bbegin != __bend; ++__bbegin)
>> >+ _M_int.push_back(*__bbegin);
>> >+
>> >+ _M_den.reserve(_M_int.size());
>> >+ for (size_t __i = 0; __i < _M_int.size(); (void)++__i, ++__wbegin)
>> >+ _M_den.push_back(*__wbegin);
>> >+
>> > _M_initialize();
>> > }
>> >
>> >@@ -3219,14 +3321,23 @@ namespace __detail
>> > param_type(initializer_list<_RealType> __bl, _Func __fw)
>> > : _M_int(), _M_den(), _M_cp(), _M_m()
>> > {
>> >- _M_int.reserve(__bl.size());
>> >- _M_den.reserve(__bl.size());
>> >- for (auto __biter = __bl.begin(); __biter != __bl.end(); ++__biter)
>> >+ if (__bl.size() < 2)
>> >+ return;
>> >+
>> >+ if (__bl.size() == 2)
>> > {
>> >- _M_int.push_back(*__biter);
>> >- _M_den.push_back(__fw(*__biter));
>> >+ const _RealType *__ints = __bl.begin();
>> >+ _RealType __den[2];
>> >+ __den[0] = __fw(__ints[0]);
>> >+ __den[1] = __fw(__ints[1]);
>> >+ _M_initialize2(__ints, __den);
>> >+ return;
>> > }
>> >
>> >+ _M_int = __bl;
>> >+ _M_den.reserve(__bl.size());
>> >+ for (auto __biter = __bl.begin(); __biter != __bl.end(); ++__biter)
>> >+ _M_den.push_back(__fw(*__biter));
>>
>> This would be simpler to read as:
>>
>> for (auto __b : __bl)
>> _M_den.push_back(__fw(__b));
>>
>> (no need to check the bounds or care about whether it uses
>> pre-increment or post-increment, or whether it caches __bl.end(),
>> etc.)
>
> I will change auto to _RealType in for-each. In general done this
> due being scared of what I can actually do with the result type,
> but here we got plain RealTypes.
ack
More information about the Libstdc++
mailing list