[PATCH v5 03/10] libstdc++: Implement std::extents [PR107761].
Luc Grosheintz
luc.grosheintz@gmail.com
Wed Apr 30 08:55:29 GMT 2025
On 4/30/25 4:37 AM, Tomasz Kaminski wrote:
> On Tue, Apr 29, 2025 at 11:52 PM Jonathan Wakely <jwakely@redhat.com> wrote:
>
>> On Tue, 29 Apr 2025 at 14:55, Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>>>
>>>
>>>
>>> On Tue, Apr 29, 2025 at 2:55 PM Luc Grosheintz <luc.grosheintz@gmail.com>
>> wrote:
>>>>
>>>> This implements std::extents from <mdspan> according to N4950 and
>>>> contains partial progress towards PR107761.
>>>>
>>>> If an extent changes its type, there's a precondition in the standard,
>>>> that the value is representable in the target integer type. This
>>>> precondition is not checked at runtime.
>>>>
>>>> The precondition for 'extents::{static_,}extent' is that '__r < rank()'.
>>>> For extents<T> this precondition is always violated and results in
>>>> calling __builtin_trap. For all other specializations it's checked via
>>>> __glibcxx_assert.
>>>>
>>>> PR libstdc++/107761
>>>>
>>>> libstdc++-v3/ChangeLog:
>>>>
>>>> * include/std/mdspan (extents): New class.
>>>> * src/c++23/std.cc.in: Add 'using std::extents'.
>>>>
>>>> Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
>>>> ---
>>>> libstdc++-v3/include/std/mdspan | 262 +++++++++++++++++++++++++++++++
>>>> libstdc++-v3/src/c++23/std.cc.in | 6 +-
>>>> 2 files changed, 267 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/libstdc++-v3/include/std/mdspan
>> b/libstdc++-v3/include/std/mdspan
>>>> index 4094a416d1e..39ced1d6301 100644
>>>> --- a/libstdc++-v3/include/std/mdspan
>>>> +++ b/libstdc++-v3/include/std/mdspan
>>>> @@ -33,6 +33,12 @@
>>>> #pragma GCC system_header
>>>> #endif
>>>>
>>>> +#include <span>
>>>> +#include <array>
>>>> +#include <type_traits>
>>>> +#include <limits>
>>>> +#include <utility>
>>>> +
>>>> #define __glibcxx_want_mdspan
>>>> #include <bits/version.h>
>>>>
>>>> @@ -41,6 +47,262 @@
>>>> namespace std _GLIBCXX_VISIBILITY(default)
>>>> {
>>>> _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>> + namespace __mdspan
>>>> + {
>>>> + template<typename _IndexType, array _Extents>
>>>> + class _ExtentsStorage
>>>> + {
>>>> + public:
>>>> + static consteval bool
>>>> + _S_is_dyn(size_t __ext) noexcept
>>>> + { return __ext == dynamic_extent; }
>>>> +
>>>> + template<typename _OIndexType>
>>>> + static constexpr _IndexType
>>>> + _S_int_cast(const _OIndexType& __other) noexcept
>>>> + { return _IndexType(__other); }
>>>> +
>>>> + static constexpr size_t _S_rank = _Extents.size();
>>>> +
>>>> + // For __r in [0, _S_rank], _S_dynamic_index[__r] is the number
>>>> + // of dynamic extents up to (and not including) __r.
>>>> + //
>>>> + // If __r is the index of a dynamic extent, then
>>>> + // _S_dynamic_index[__r] is the index of that extent in
>>>> + // _M_dynamic_extents.
>>>> + static constexpr auto _S_dynamic_index = [] consteval
>>>> + {
>>>> + array<size_t, _S_rank+1> __ret;
>>>> + size_t __dyn = 0;
>>>> + for(size_t __i = 0; __i < _S_rank; ++__i)
>>>> + {
>>>> + __ret[__i] = __dyn;
>>>> + __dyn += _S_is_dyn(_Extents[__i]);
>>>> + }
>>>> + __ret[_S_rank] = __dyn;
>>>> + return __ret;
>>>> + }();
>>>> +
>>>> + static constexpr size_t _S_rank_dynamic =
>> _S_dynamic_index[_S_rank];
>>>> +
>>>> + // For __r in [0, _S_rank_dynamic), _S_dynamic_index_inv[__r]
>> is the
>>>> + // index of the __r-th dynamic extent in _Extents.
>>>> + static constexpr auto _S_dynamic_index_inv = [] consteval
>>>> + {
>>>> + array<size_t, _S_rank_dynamic> __ret;
>>>> + for (size_t __i = 0, __r = 0; __i < _S_rank; ++__i)
>>>> + if (_S_is_dyn(_Extents[__i]))
>>>> + __ret[__r++] = __i;
>>>> + return __ret;
>>>> + }();
>>>> +
>>>> + static constexpr size_t
>>>> + _S_static_extent(size_t __r) noexcept
>>>> + { return _Extents[__r]; }
>>>> +
>>>> + constexpr _IndexType
>>>> + _M_extent(size_t __r) const noexcept
>>>> + {
>>>> + auto __se = _Extents[__r];
>>>> + if (__se == dynamic_extent)
>>>> + return _M_dynamic_extents[_S_dynamic_index[__r]];
>>>> + else
>>>> + return __se;
>>>> + }
>>>> +
>>>> + template<size_t _OtherRank, typename _GetOtherExtent>
>>>> + constexpr void
>>>> + _M_init_dynamic_extents(_GetOtherExtent __get_extent) noexcept
>>>> + {
>>>> + for(size_t __i = 0; __i < _S_rank_dynamic; ++__i)
>>>> + {
>>>> + size_t __di = __i;
>>>> + if constexpr (_OtherRank != _S_rank_dynamic)
>>>> + __di = _S_dynamic_index_inv[__i];
>>>> + _M_dynamic_extents[__i] =
>> _S_int_cast(__get_extent(__di));
>>>> + }
>>>> + }
>>>> +
>>>> + constexpr
>>>> + _ExtentsStorage() noexcept = default;
>>>> +
>>>> + template<typename _OIndexType, array _OExtents>
>>>> + constexpr
>>>> + _ExtentsStorage(const _ExtentsStorage<_OIndexType, _OExtents>&
>>>> + __other) noexcept
>>>> + {
>>>> + _M_init_dynamic_extents<_S_rank>([&__other](size_t __i)
>>>> + { return __other._M_extent(__i); });
>>>> + }
>>>> +
>>>> + template<typename _OIndexType, size_t _Nm>
>>>> + constexpr
>>>> + _ExtentsStorage(span<const _OIndexType, _Nm> __exts) noexcept
>>>> + {
>>>> + _M_init_dynamic_extents<_Nm>(
>>>> + [&__exts](size_t __i) -> const _OIndexType&
>>>> + { return __exts[__i]; });
>>>> + }
>>>> +
>>>> + private:
>>>> + using _S_storage = __array_traits<_IndexType,
>> _S_rank_dynamic>::_Type;
>>>> + [[no_unique_address]] _S_storage _M_dynamic_extents;
>>>> + };
>>>> +
>>>> + template<typename _OIndexType, typename _SIndexType>
>>>> + concept __valid_index_type =
>>>> + is_convertible_v<_OIndexType, _SIndexType> &&
>>>> + is_nothrow_constructible_v<_SIndexType, _OIndexType>;
>>>> +
>>>> + template<size_t _Extent, typename _IndexType>
>>>> + concept
>>>> + __valid_static_extent = _Extent == dynamic_extent
>>>> + || _Extent <= numeric_limits<_IndexType>::max();
>>>> + }
>>>> +
>>>> + template<typename _IndexType, size_t... _Extents>
>>>> + class extents
>>>> + {
>>>> + static_assert(is_integral_v<_IndexType>, "_IndexType must be
>> integral.");
>>>> + static_assert(
>>>> + (__mdspan::__valid_static_extent<_Extents, _IndexType> &&
>> ...),
>>>> + "Extents must either be dynamic or representable as
>> _IndexType");
>>>> +
>>>> + public:
>>>> + using index_type = _IndexType;
>>>> + using size_type = make_unsigned_t<index_type>;
>>>> + using rank_type = size_t;
>>>> +
>>>> + static constexpr rank_type
>>>> + rank() noexcept { return _S_storage::_S_rank; }
>>>> +
>>>> + static constexpr rank_type
>>>> + rank_dynamic() noexcept { return _S_storage::_S_rank_dynamic; }
>>>> +
>>>> + static constexpr size_t
>>>> + static_extent(rank_type __r) noexcept
>>>> + {
>>>> + __glibcxx_assert(__r < rank());
>>>> + if constexpr (rank() == 0)
>>>> + __builtin_trap();
>>>> + else
>>>> + return _S_storage::_S_static_extent(__r);
>>>> + }
>>>> +
>>>> + constexpr index_type
>>>> + extent(rank_type __r) const noexcept
>>>> + {
>>>> + __glibcxx_assert(__r < rank());
>>>> + if constexpr (rank() == 0)
>>>> + __builtin_trap();
>>>> + else
>>>> + return _M_dynamic_extents._M_extent(__r);
>>>> + }
>>>> +
>>>> + constexpr
>>>> + extents() noexcept = default;
>>>> +
>>>> + private:
>>>> + static consteval bool
>>>> + _S_is_less_dynamic(size_t __ext, size_t __oext)
>>>> + { return (__ext != dynamic_extent) && (__oext ==
>> dynamic_extent); }
>>>> +
>>>> + template<typename _OIndexType, size_t... _OExtents>
>>>> + static consteval bool
>>>> + _S_ctor_explicit()
>>>> + {
>>>> + return (_S_is_less_dynamic(_Extents, _OExtents) || ...)
>>>> + || (numeric_limits<index_type>::max()
>>>> + < numeric_limits<_OIndexType>::max());
>>>> + }
>>>> +
>>>> + template<size_t... _OExtents>
>>>> + static consteval bool
>>>> + _S_is_compatible_extents()
>>>> + {
>>>> + if constexpr (sizeof...(_OExtents) != rank())
>>>> + return false;
>>>> + else {
>>>
>>> We do not need braces here.
>>>>
>>>> + return ((_OExtents == dynamic_extent || _Extents ==
>> dynamic_extent
>>>> + || _OExtents == _Extents) && ...);
>>>> + }
>>>> + }
>>>> +
>>>> + public:
>>>> + template<typename _OIndexType, size_t... _OExtents>
>>>> + requires (_S_is_compatible_extents<_OExtents...>())
>>>> + constexpr explicit(_S_ctor_explicit<_OIndexType,
>> _OExtents...>())
>>>> + extents(const extents<_OIndexType, _OExtents...>& __other)
>> noexcept
>>>> + : _M_dynamic_extents(__other._M_dynamic_extents)
>>>> + { }
>>>> +
>>>> + template<__mdspan::__valid_index_type<index_type>...
>> _OIndexTypes>
>>>> + requires (sizeof...(_OIndexTypes) == rank()
>>>> + || sizeof...(_OIndexTypes) == rank_dynamic())
>>>> + constexpr explicit extents(_OIndexTypes... __exts) noexcept
>>>> + : _M_dynamic_extents(span<const _IndexType,
>> sizeof...(_OIndexTypes)>(
>>>> + initializer_list{_S_storage::_S_int_cast(__exts)...}))
>>>> + { }
>>>> +
>>>> + template<__mdspan::__valid_index_type<index_type> _OIndexType,
>> size_t _Nm>
>>>> + requires (_Nm == rank() || _Nm == rank_dynamic())
>>>> + constexpr explicit(_Nm != rank_dynamic())
>>>> + extents(span<_OIndexType, _Nm> __exts) noexcept
>>>> + : _M_dynamic_extents(span<const _OIndexType, _Nm>(__exts))
>>>> + { }
>>>> +
>>>> +
>>>> + template<__mdspan::__valid_index_type<index_type> _OIndexType,
>> size_t _Nm>
>>>> + requires (_Nm == rank() || _Nm == rank_dynamic())
>>>> + constexpr explicit(_Nm != rank_dynamic())
>>>> + extents(const array<_OIndexType, _Nm>& __exts) noexcept
>>>> + : _M_dynamic_extents(span<const _OIndexType, _Nm>(__exts))
>>>> + { }
>>>> +
>>>> + template<typename _OIndexType, size_t... _OExtents>
>>>> + friend constexpr bool
>>>> + operator==(const extents& __self,
>>>> + const extents<_OIndexType, _OExtents...>& __other)
>> noexcept
>>>> + {
>>>> + if constexpr (!_S_is_compatible_extents<_OExtents...>())
>>>> + return false;
>>>
>>> We can add here:
>>> // N.B. if extents are compatible and static, it implies
>> that they are equal
>>> else if constexpr ((_Extents != dynamic_extent) && ...)
>>> return true;
>>
>> Can't we have a case where _OExtents==dynamic_extent and
>> _Extents!=dynamic_extents, which would mean they're compatible, but
>> not equal?
>>
> Ah, indeed the conditions needs to be:
> (_Extents != dynamic_extent && _Extents == _OExtents) && ...
>
The reason I didn't follow through with this is because when looking
at the generated code I saw no advantage of the additional constexpr
branch. Therefore, I preferred the simplicity of Tomasz first proposal,
i.e. the current implementation.
Would you still like me to add the additional `else if constexpr`
branch?
Here's the output of objdump when compiling with `-O2`:
bool same1(const std::extents<int, 1, 2, 3>& e1,
const std::extents<int, 1, 2, 3>& e2)
{ return e1 == e2; }
0: b8 01 00 00 00 mov $0x1,%eax
5: c3 ret
bool same2(const std::extents<int, 2, 2, 3>& e1,
const std::extents<int, 1, 2, 3>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
bool same3(const std::extents<int, 2, dyn, 3>& e1,
const std::extents<int, 1, 2, 3>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
bool same4(const std::extents<int, 2, dyn, 3>& e1,
const std::extents<int, dyn, 2, 4>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
bool same5(const std::extents<int, dyn>& e1,
const std::extents<int, dyn, dyn>& e2)
{ return e1 == e2; }
0: 31 c0 xor %eax,%eax
2: c3 ret
>>
>>
>>>>
>>>> + else
>>>> + {
>>>> + for (size_t __i = 0; __i < __self.rank(); ++__i)
>>>> + if (!cmp_equal(__self.extent(__i), __other.extent(__i)))
>>>> + return false;
>>>> + return true;
>>>> + }
>>>> + }
>>>> +
>>>> + private:
>>>> + using _S_storage = __mdspan::_ExtentsStorage<
>>>> + _IndexType, array<size_t, sizeof...(_Extents)>{_Extents...}>;
>>>> + [[no_unique_address]] _S_storage _M_dynamic_extents;
>>>> +
>>>> + template<typename _OIndexType, size_t... _OExtents>
>>>> + friend class extents;
>>>> + };
>>>> +
>>>> + namespace __mdspan
>>>> + {
>>>> + template<typename _IndexType, size_t... _Counts>
>>>> + auto __build_dextents_type(integer_sequence<size_t, _Counts...>)
>>>> + -> extents<_IndexType, ((void) _Counts, dynamic_extent)...>;
>>>> +
>>>> + template<typename _Tp>
>>>> + consteval size_t
>>>> + __dynamic_extent() { return dynamic_extent; }
>>>> + }
>>>> +
>>>> + template<typename _IndexType, size_t _Rank>
>>>> + using dextents =
>> decltype(__mdspan::__build_dextents_type<_IndexType>(
>>>> + make_index_sequence<_Rank>()));
>>>> +
>>>> + template<typename... _Integrals>
>>>> + requires (is_convertible_v<_Integrals, size_t> && ...)
>>>> + explicit extents(_Integrals...) ->
>>>> + extents<size_t, __mdspan::__dynamic_extent<_Integrals>()...>;
>>>>
>>>> _GLIBCXX_END_NAMESPACE_VERSION
>>>> }
>>>> diff --git a/libstdc++-v3/src/c++23/std.cc.in b/libstdc++-v3/src/c++23/
>> std.cc.in
>>>> index 930a489ff44..0df27cd7e7d 100644
>>>> --- a/libstdc++-v3/src/c++23/std.cc.in
>>>> +++ b/libstdc++-v3/src/c++23/std.cc.in
>>>> @@ -1833,7 +1833,11 @@ export namespace std
>>>> }
>>>> }
>>>>
>>>> -// FIXME <mdspan>
>>>> +// <mdspan>
>>>> +{
>>>> + using std::extents;
>>>> + // FIXME layout_*, default_accessor and mdspan
>>>> +}
>>>>
>>>> // 20.2 <memory>
>>>> export namespace std
>>>> --
>>>> 2.49.0
>>>>
>>
>>
>
More information about the Libstdc++
mailing list