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
>>
>>

Reply via email to