On Thu, Apr 17, 2025 at 6:07 PM Luc Grosheintz <luc.groshei...@gmail.com>
wrote:
>
> On 4/17/25 2:31 PM, Tomasz Kaminski wrote:
>
>
>
> On Thu, Apr 17, 2025 at 2:21 PM Tomasz Kaminski <tkami...@redhat.com>
> wrote:
>
>>
>>
>> On Thu, Apr 17, 2025 at 1:44 PM Tomasz Kaminski <tkami...@redhat.com>
>> wrote:
>>
>>>
>>>
>>> On Thu, Apr 17, 2025 at 1:18 PM Luc Grosheintz <luc.groshei...@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.groshei...@gmail.com>
>>>>
>>> Looks really solid. Few very minor suggestions regarding naming, and use
>>> of
>>> consteval where function is not needed at runtime.
>>>
>>>> ---
>>>> libstdc++-v3/include/std/mdspan | 249 +++++++++++++++++++++++++++++++
>>>> libstdc++-v3/src/c++23/std.cc.in | 6 +-
>>>> 2 files changed, 254 insertions(+), 1 deletion(-)
>>>>
>>>> diff --git a/libstdc++-v3/include/std/mdspan
>>>> b/libstdc++-v3/include/std/mdspan
>>>> index 4094a416d1e..755c077f89c 100644
>>>> --- a/libstdc++-v3/include/std/mdspan
>>>> +++ b/libstdc++-v3/include/std/mdspan
>>>> @@ -33,6 +33,11 @@
>>>> #pragma GCC system_header
>>>> #endif
>>>>
>>>> +#include <span>
>>>> +#include <array>
>>>> +#include <type_traits>
>>>> +#include <limits>
>>>> +
>>>> #define __glibcxx_want_mdspan
>>>> #include <bits/version.h>
>>>>
>>>> @@ -41,6 +46,250 @@
>>>> namespace std _GLIBCXX_VISIBILITY(default)
>>>> {
>>>> _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>> + namespace __mdspan
>>>> + {
>>>> + template<typename _IndexType, array _Extents>
>>>> + class _ExtentsStorage
>>>> + {
>>>> + public:
>>>> + static constexpr bool
>>>>
>>> + _M_is_dyn(size_t __ext) noexcept
>>>>
>>> We use `_S_` prefix for static member functions, and `_M_` for instance
>>> member functions.
>>>
>>>> + { return __ext == dynamic_extent; }
>>>> +
>>>> + template<typename _OIndexType>
>>>> + static constexpr _IndexType
>>>> + _M_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 += _M_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 (_M_is_dyn(_Extents[__i]))
>>>> + __ret[__r++] = __i;
>>>> + return __ret;
>>>> + }();
>>>> +
>>>> + static constexpr size_t
>>>> + _M_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] =
>>>> _M_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](auto __i)
>>>>
>>> There is no need to be generic here, just use size_t as lambda
>>> parameter, instead of auto.
>>>
>>>> + { return __other._M_extent(__i); });
>>>> + }
>>>> +
>>>> + template<typename _OIndexType, size_t _Nm>
>>>> + constexpr
>>>> + _ExtentsStorage(const span<_OIndexType, _Nm>& __exts) noexcept
>>>>
>>> I think I would adjust the signature to span<const _OIndexType> and then
> insert the constructor of span into
> the extents constructor. This will guarantee that we do not create
> unnecessary instantiations for mutable spans here.
> (I have recently made mistake of forgetting about else if constexpr code
> https://gcc.gnu.org/cgit/gcc/commit/?id=843b273c6851b71407b116584982b0389be4d6fd
> ,
> and double instantiations instead of reducing them, so looking into a ways
> to make this guaranteed).
>
> Good idea, I'd like to make sure I'm not missing a subtlety: In this case
> here it's
> about reducing the number of template instantiations, with the intent of
> reducing compile time.
>
Each such constructor will have a separate symbol (mangled name) and code
emitted,
so this is not only compile time, but also binary size.
> If there's more to it please expand, since in that case I'm
> very likely unaware of something relevant.
>
> + {
>>>> + _M_init_dynamic_extents<_Nm>(
>>>> + [&__exts](auto __i) -> const _OIndexType&
>>>>
>>> Same as above.
>>>
>>>> + { 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();
>>>> +
>>>> + return _S_storage::_M_static_extent(__r);
>>>> + }
>>>> +
>>>> + constexpr index_type
>>>> + extent(rank_type __r) const noexcept
>>>> + {
>>>> + __glibcxx_assert(__r < rank());
>>>> + if constexpr (rank() == 0)
>>>> + __builtin_trap();
>>>> +
>>>> + return _M_dynamic_extents._M_extent(__r);
>>>> + }
>>>> +
>>>> + constexpr
>>>> + extents() noexcept = default;
>>>> +
>>>> + private:
>>>> + static constexpr bool
>>>>
>>> I think this can be made consteval, we do not need symbols emitted to
>>> binary.
>>>
>>>> + _M_is_less_dynamic(size_t __ext, size_t __oext)
>>>> + { return (__ext != dynamic_extent) && (__oext ==
>>>> dynamic_extent); }
>>>> +
>>>> + template<typename _OIndexType, size_t... _OExtents>
>>>> + static constexpr bool
>>>>
>>> I think this can be made consteval, we do not need symbols emitted to
>>> binary.
>>>
>>>> + _M_ctor_explicit()
>>>> + {
>>>> + return (_M_is_less_dynamic(_Extents, _OExtents) || ...)
>>>> + || (numeric_limits<index_type>::max()
>>>> + < numeric_limits<_OIndexType>::max());
>>>> + }
>>>> +
>>>> + public:
>>>> + template<typename _OIndexType, size_t... _OExtents>
>>>> + requires (sizeof...(_OExtents) == rank())
>>>> + && ((_OExtents == dynamic_extent || _Extents ==
>>>> dynamic_extent
>>>> + || _OExtents == _Extents) && ...)
>>>> + constexpr explicit(_M_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::_M_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(__exts)
>>>>
>>> I think we could pass span<const _OIndexType, _Nm>(__ext) here, to
>> reduce the number of instantiations for constructor.
>>
>>> + { }
>>>> +
>>>> +
>>>> + 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<add_const_t<_OIndexType>,
>>>> _Nm>(__exts))
>>>>
>>> We can say const _OIndexType here.
>>>
>>>> + { }
>>>> +
>>>> + template<typename _OIndexType, size_t... _OExtents>
>>>> + friend constexpr bool
>>>> + operator==(const extents& __self,
>>>> + const extents<_OIndexType, _OExtents...>& __other)
>>>> noexcept
>>>> + {
>>>> + if constexpr (__self.rank() != __other.rank())
>>>> + return false;
>>>> +
>>>> + for (size_t __i = 0; __i < __self.rank(); ++__i)
>>>> + if (__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, (_Counts, dynamic_extent)...>;
>>>> +
>>>> + template<typename _Tp>
>>>> + constexpr size_t
>>>>
>>> Make it consteval.
>>>
>>>> + __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 12253b95c5a..481e39b2821 100644
>>>> --- a/libstdc++-v3/src/c++23/std.cc.in
>>>> +++ b/libstdc++-v3/src/c++23/std.cc.in
>>>> @@ -1825,7 +1825,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
>>>>
>>>>
