On Wed, Apr 30, 2025 at 7:13 AM Tomasz Kaminski <tkami...@redhat.com> wrote:
> Hi, > > As we will be landing patches for extends, this will become a separate > patch series. > I would prefer, if you could commit per layout, and start with > layout_right (default) > I try to provide prompt responses, so if that works better for you, you > can post a patch > only with this layout first, as most of the comments will apply to all of > them. > > For the general design we have constructors that allow conversion between > rank-0 > and rank-1 layouts left and right. This is done because they essentially > represents > the same layout. I think we could benefit from that in code by having a > base classes > for rank0 and rank1 mapping: > template<typename _Extents> > _Rank0_mapping_base > { > static_assert(_Extents::rank() == 0); > > template<OtherExtents> > // explicit, requires goes here > _Rank0_mapping_base(_Rank0_mapping_base<OtherExtents>); > > // All members layout_type goes her > }; > > template<typename _Extents> > _Rank1_mapping_base > { > static_assert(_Extents::rank() == 1); > // Static assert for product is much simpler here, as we need to check > one > > template<OtherExtents> > // explicit, requires goes here > _Rank1_mapping_base(_Rank1_mapping_base<OtherExtents>); > > // Call operator can also be simplified > index_type operator()(index_type i) const // conversion happens at user > side > > // cosntructor from strided_layout of Rank1 goes here. > > // All members layout_type goes her > }; > Then we will specialize layout_left/right/stride to use > _Rank0_mapping_base as a base for rank() == 0 > and layout_left/right to use _Rank1_mapping as base for rank()1; > template<typename T, unsigned... Ids> > struct extents {}; > > struct layout > { > template<typename Extends> > struct mapping > { > // static assert that Extents mmyst be specialization of _Extents goes > here. > } > }; > > template<typename _IndexType> > struct layout::mapping<extents<_IndexType>> > : _Rank0_mapping_base<extents<_IndexType>> > { > using layout_type = layout_left; > // Provides converting constructor. > using _Rank0_mapping_base<extents<_IndexType>>::_Rank0_mapping_base; > // This one is implicit; > mapping(_Rank0_mapping_base<extents<_IndexType>> const&); > }; > > template<typename _IndexType, unsigned _Ext> > struct layout::mapping<extents<_IndexType, _Ext>> > : _Rank1_mapping_base<extents<_IndexType>> > > { > using layout_type = layout_left; > // Provides converting constructor. > using _Rank0_mapping_base<extents<_IndexType>>::_Rank0_mapping_base; > // This one is implicit, allows construction from layout_right > mapping(_Rank1_mapping_base<extents<_IndexType>> const&); > }; > }; > > template<typename _IndexType, unsigned... _Ext> > requires sizeof..(_Ext) > = 2 > struct layout::mapping<extents<_IndexType, _Ext>> > > The last one is a generic implementation that you can use in yours. > Please also include a comment explaining that we are deviating from > standard text here. > > > On Tue, Apr 29, 2025 at 2:56 PM Luc Grosheintz <luc.groshei...@gmail.com> > wrote: > >> Implements the parts of layout_left that don't depend on any of the >> other layouts. >> >> libstdc++/ChangeLog: >> >> * include/std/mdspan (layout_left): New class. >> >> Signed-off-by: Luc Grosheintz <luc.groshei...@gmail.com> >> --- >> libstdc++-v3/include/std/mdspan | 179 ++++++++++++++++++++++++++++++++ >> 1 file changed, 179 insertions(+) >> >> diff --git a/libstdc++-v3/include/std/mdspan >> b/libstdc++-v3/include/std/mdspan >> index 39ced1d6301..e05048a5b93 100644 >> --- a/libstdc++-v3/include/std/mdspan >> +++ b/libstdc++-v3/include/std/mdspan >> @@ -286,6 +286,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> >> namespace __mdspan >> { >> + template<typename _Extents> >> + constexpr typename _Extents::index_type >> + __fwd_prod(const _Extents& __exts, size_t __r) noexcept >> + { >> + typename _Extents::index_type __fwd = 1; >> + for(size_t __i = 0; __i < __r; ++__i) >> + __fwd *= __exts.extent(__i); >> + return __fwd; >> + } >> > As we are inside the standard library implementation, we can do some > tricks here, > and provide two functions: > // Returns the std::span(_ExtentsStorage::_Ext).substr(f, l); > // For extents forward to __static_exts > span<typename Extends::index_type> __static_exts(size_t f, size_t l); > // Returns the > std::span(_ExtentsStorage::_M_dynamic_extents).substr(_S_dynamic_index[f], > _S_dynamic_index[l); > span<typename Extends::index_type> __dynamic_exts(Extents const& c); > Then you can befriend this function both to extents and _ExtentsStorage. > Also add index_type members to _ExtentsStorage. > > Then instead of having fwd-prod and rev-prod I would have: > template<typename _Extents> > consteval size_t __static_ext_prod(size_t f, size_t l) > { > // multiply E != dynamic_ext from __static_exts > } > constexpr size __ext_prod(const _Extents& __exts, size_t f, size_t l) > { > // multiply __static_ext_prod<_Extents>(f, l) and each elements of > __dynamic_exts(__exts, f, l); > } > > Then fwd-prod(e, n) would be __ext_prod(e, 0, n), and rev_prod(e, n) would > be __ext_prod(e, __ext.rank() -n, n, __ext.rank()) > > >> + >> + template<typename _Extents> >> + constexpr typename _Extents::index_type >> + __rev_prod(const _Extents& __exts, size_t __r) noexcept >> + { >> + typename _Extents::index_type __rev = 1; >> + for(size_t __i = __r + 1; __i < __exts.rank(); ++__i) >> + __rev *= __exts.extent(__i); >> + return __rev; >> + } >> + >> template<typename _IndexType, size_t... _Counts> >> auto __build_dextents_type(integer_sequence<size_t, _Counts...>) >> -> extents<_IndexType, ((void) _Counts, dynamic_extent)...>; >> @@ -304,6 +324,165 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION >> explicit extents(_Integrals...) -> >> extents<size_t, __mdspan::__dynamic_extent<_Integrals>()...>; >> >> + struct layout_left >> + { >> + template<typename _Extents> >> + class mapping; >> + }; >> + >> + namespace __mdspan >> + { >> + template<typename _Tp> >> + constexpr bool __is_extents = false; >> + >> + template<typename _IndexType, size_t... _Extents> >> + constexpr bool __is_extents<extents<_IndexType, _Extents...>> = >> true; >> + >> + template<size_t _Count> >> + struct _LinearIndexLeft >> + { >> + template<typename _Extents, typename... _Indices> >> + static constexpr typename _Extents::index_type >> + _S_value(const _Extents& __exts, typename _Extents::index_type >> __idx, >> + _Indices... __indices) noexcept >> + { >> + return __idx + __exts.extent(_Count) >> + * _LinearIndexLeft<_Count + 1>::_S_value(__exts, >> __indices...); >> + } >> + >> + template<typename _Extents> >> + static constexpr typename _Extents::index_type >> + _S_value(const _Extents&) noexcept >> + { return 0; } >> + }; >> + >> + template<typename _Extents, typename... _Indices> >> + constexpr typename _Extents::index_type >> + __linear_index_left(const _Extents& __exts, _Indices... __indices) >> + { >> + return _LinearIndexLeft<0>::_S_value(__exts, __indices...); >> + } >> > This can be eliminated by fold expressions, see below. > >> + >> + template<typename _IndexType, typename _Tp, size_t _Nm> >> + consteval bool >> + __is_representable_product(array<_Tp, _Nm> __factors) >> + { >> + size_t __rest = numeric_limits<_IndexType>::max(); >> + for(size_t __i = 0; __i < _Nm; ++__i) >> + { >> + if (__factors[__i] == 0) >> + return true; >> + __rest /= _IndexType(__factors[__i]); >> + } >> + return __rest > 0; >> + } >> > I would replace that with > template<IndexType> > consteval size_t __div_reminder(span<const size_t, _Nm> __factors, size_t > __val) > { > size_t __rest = val; > for(size_t __i = 0; __i < _Nm; ++__i) > { > if (__factors[__i] == dynamic_extent) > continue; > if (__factors[__i] != 0) > return val; > __rest /= _IndexType(__factors[__i]); > if (__res == 0) > We cannot do early exit here, as when any of later factors is zero, we are still representable. > return 0; > } > return __rest; > } > > We can express the is presentable check as > static constexpr __dyn_reminder = __div_reminder(__static_exts<Extents>(0, > rank()), std::numeric_limits<Index>::max()); > static_assert(__dyn_reminder > 0); > However, with __dyn_reminder value, the precondition > https://eel.is/c++draft/mdspan.layout#left.cons-1, > can be checked by doing equivalent of __div_remainder for __dyn_extents > with __val being __dyn_reminder. > > >> + >> + template<typename _Extents> >> + consteval array<typename _Extents::index_type, _Extents::rank()> >> + __static_extents_array() >> + { >> + array<typename _Extents::index_type, _Extents::rank()> __exts; >> + for(size_t __i = 0; __i < _Extents::rank(); ++__i) >> + __exts[__i] = _Extents::static_extent(__i); >> + return __exts; >> + } >> > > Replaced by __static_exts accessor, as described above. > > >> + >> + template<typename _Extents, typename _IndexType> >> + concept __representable_size = _Extents::rank_dynamic() != 0 >> + || __is_representable_product<_IndexType>( >> + __static_extents_array<_Extents>()); >> + >> + template<typename _Extents> >> + concept __layout_extent = __representable_size< >> + _Extents, typename _Extents::index_type>; >> + } >> > + >> + template<typename _Extents> >> + class layout_left::mapping >> + { >> + static_assert(__mdspan::__layout_extent<_Extents>, >> + "The size of extents_type is not representable as index_type."); >> + public: >> + using extents_type = _Extents; >> + using index_type = typename extents_type::index_type; >> + using size_type = typename extents_type::size_type; >> + using rank_type = typename extents_type::rank_type; >> + using layout_type = layout_left; >> + >> + constexpr >> + mapping() noexcept = default; >> + >> + constexpr >> + mapping(const mapping&) noexcept = default; >> + >> + constexpr >> + mapping(const extents_type& __extents) noexcept >> + : _M_extents(__extents) >> + { >> > > > >> } >> + >> + template<typename _OExtents> >> + requires (is_constructible_v<extents_type, _OExtents>) >> + constexpr explicit(!is_convertible_v<_OExtents, extents_type>) >> + mapping(const mapping<_OExtents>& __other) noexcept >> + : _M_extents(__other.extents()) >> + { > > Here we could do checks at compile time: > if constexpr(_OExtents::rank_dynamic() == 0) > static_assert( __div_remainder(...) > 0); > } > > >> } >> + >> + constexpr mapping& >> + operator=(const mapping&) noexcept = default; >> + >> + constexpr const extents_type& >> + extents() const noexcept { return _M_extents; } >> + >> + constexpr index_type >> + required_span_size() const noexcept >> + { return __mdspan::__fwd_prod(_M_extents, _M_extents.rank()); } >> + >> + template<__mdspan::__valid_index_type<index_type>... _Indices> >> > // Because we extracted rank0 and rank1 specializations > >> + requires (sizeof...(_Indices) + 1 == extents_type::rank()) >> + constexpr index_type >> + operator()(index_type __idx, _Indices... __indices) const noexcept >> + { >> > This could be implemented as, please synchronize the names. > if constexpr (!is_same_v<_Indices, index_type> || ...) > // Reduce the number of instantations. > return operator()(index_type _idx0, > static_cast<index_type>(std::move(__indices))....); > else > { > // This can be used for layout stride, if you start with __res = 0; > index_type __res = _idx0; > index_type __mult = _M_extents.extent(0); > auto __update = [&__res, &__mult, __pos = 1u](index_type __idx) > mutable > { > __res += __idx * __mult; > __mult *= _M_extents.extent(__pos); > ++__pos; > }; > // Fold over invocation of lambda > (__update(_Indices), ....); > return __res; > } > > This could be even simpler and written as (use for layout stride): > size_t __pos = 0; > return (index_type(0) + ... + __indices * stride(__pos++)); > Here, I prefer to avoid multiplying multiple times. > > > + return __mdspan::__linear_index_left( >> + _M_extents, static_cast<index_type>(__indices)...); >> + } >> + >> + static constexpr bool >> + is_always_unique() noexcept { return true; } >> + >> + static constexpr bool >> + is_always_exhaustive() noexcept { return true; } >> + >> + static constexpr bool >> + is_always_strided() noexcept { return true; } >> + >> + static constexpr bool >> + is_unique() noexcept { return true; } >> + >> + static constexpr bool >> + is_exhaustive() noexcept { return true; } >> + >> + static constexpr bool >> + is_strided() noexcept { return true; } >> + >> + constexpr index_type >> + stride(rank_type __i) const noexcept >> + requires (extents_type::rank() > 0) >> + { >> + __glibcxx_assert(__i < extents_type::rank()); >> + return __mdspan::__fwd_prod(_M_extents, __i); >> + } >> + >> + template<typename _OExtents> >> + requires (extents_type::rank() == _OExtents::rank()) >> + friend constexpr bool >> + operator==(const mapping& __self, const mapping<_OExtents>& >> __other) >> + noexcept >> + { return __self.extents() == __other.extents(); } >> + >> + private: >> + [[no_unique_address]] extents_type _M_extents; >> + }; >> + >> _GLIBCXX_END_NAMESPACE_VERSION >> } >> #endif >> -- >> 2.49.0 >> >>