On Sat, May 3, 2025 at 2:39 PM Luc Grosheintz <luc.groshei...@gmail.com> wrote:
> > > On 4/30/25 7:13 AM, Tomasz Kaminski 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. > > > > Thank for reviewing and offering fast review cycles, I can't say I've > ever felt that they were anything but wonderfully fast and I appologise > for the delay (I've been away hiking for two days). > > The reason I implement all three is that I needed to see them all. > Otherwise, I can see and "feel" the impact of the duplication (or > efforts to reduce duplication). It's also to make sure I understand > precisely how the layouts are similar and different. The idea is that > you'd review one at a time; and by adding the others you can pick which > one and have a glance at the other if it's helpful during review. > > The review contains three topics. This email responds to the idea of > introducing a common base class. I believe I superficially understand > the request. However, it's not clear to me what we gain. > > The reorganization seems to stress the how rank 0 and rank 1 layouts are > similar; at the cost of making the uniformity of layout_left (regardless > of rank) and layout_right (regardless of rank) less obvious. Personally, > I quite like that we can express all layouts of one kind regardless of > their rank, without resorting to special cases via specialization. > > To me the standard reads like the layouts are three separate, > independent entities. However, because it would be too tedious to not > allow conversion between layouts of rank 0 and 1, a couple of ctors were > added. An example, of how the layouts are not consider related is that > we can't compare layout_left and layout_right mappings for equality. > > If I count, the current implementation has 3 copies: layout_left, > layout_right, layout_stride. The proposed changes add two (likely three) > base classes which, require three specializations of layout_right and > layout_left each. Therefore I end up with 6 copies of layout_left and > layout_right; and 2 (or 3) base classes. Or if we manage it use the base > classes for all layouts: 9 specialization, 2 (or 3) base classes. > Therefore, in terms of numbers the restructuring doesn't seem favourable > and I feel would require noticeably more repetition in the tests. > I think we can use a conditional base, to eliminate specializations, and have layout_left_base. > > While the rank zero and rank one versions are a lot simpler than the > generic copy, they aren't entirely empty either (we'll likely need to > use `using super::*` several times). Furthermore, I don't see any real > simplifications in the generic copy. Meaning we still have a copy that > has all the complexities and could (almost) handle the other two cases. > I think using a common bases, and allowing layout_left/layout_right to be constructed from the base classes, will automatically enable the conversions that are currently expressed via constructor: layout_left <-> layout_right for ranks 0 and 1, layout_stride <-> layout_left/right for rank 0 (because they are rank0) > > Since layout_stride is a little different, I'm not sure we can reuse the > base classes for it. For example it allows conversion more freely, but > is only implicit for rank 0; whereas the other two allow implicit > conversion between each other for rank 0 and 1. > This is why I said rank0_mapping_base should be used for layout_left, layout_rigth and layout_stride (and later layout_left_padeed, and layout_right_padded). For rank1 this would be shared between layout_left, laout_right, layout_left_paded and layout_right_paded. > > Most importantly though, the reorganization makes it very hard to > compare the implementation with the text of the standard. Therefore, > making it more likely that a discrepancy goes unnoticed. > > One example of the subtleties involved in restructuring the code is the > following: layout_right, layout_left support CTAD via the ctor > `mapping(extents_type)`. However, when using specialization, that stops > working and we'd need to add deduction guides to make the implementation > conforming. I suspect a Godbolt can explain the situation better: > https://godbolt.org/z/EdbE7ME6P We could use simple specializations, and derive from different base classes using conditional_t. This would require having > > > In summary: personally I feel using base classes adds repetition, > complexity and makes it hard (for me impossible) to check that the > implementation is conforming. > > Naturally, I can be convinced to change the implementation. Maybe you > could explain a little what and why you don't like the admittedly very > brute-force implementation. > There are a few things I had in mind. For rank 1 checking the precondition for the size of multidimensional index space is trivial, and we certainly could provide a __glibcxx_assert in such a case. This can be done for the separate implementation, but I think we will end up with repeated if constexpr checks in all mappings. This is why in my mind, the reduced rank0 and rank1 cases felt a bit special. For example, mdspan<T, extents<N>> can be seen as replacement for span<N>, which provides support for adjusting accessor and pointer type. My original request, however, was however driven by code size. The layout_left, layout_right, layout_left_padded, layout_right_padded with rank 0, have members with same semantics (operator(), stride, ...), and we could have only one definition for them, instead of four. > > > > > 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) > > 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 > >> > >> > > > >