[PATCH v4 3/4] libstdc++: Implement std::extents [PR107761].
Tomasz Kaminski
tkaminsk@redhat.com
Tue Apr 22 07:02:47 GMT 2025
On Fri, Apr 18, 2025 at 7:48 PM Luc Grosheintz <luc.grosheintz@gmail.com>
wrote:
>
> On 4/18/25 2:00 PM, Tomasz Kaminski wrote:
> >
> >
> >
> > On Fri, Apr 18, 2025 at 1:43 PM Luc Grosheintz <luc.grosheintz@gmail.com
> > <mailto: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 <http://std.cc.in>: Add 'using
> > std::extents'.
> >
> > Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com
> > <mailto:luc.grosheintz@gmail.com>>
> > ---
> >
> > LGTM.
> > Below, I shared one idea that I found interesting, and you could look
> into,
> > but not necessary.
> >
> > libstdc++-v3/include/std/mdspan | 249
> +++++++++++++++++++++++++++++++
> > libstdc++-v3/src/c++23/std.cc.in <http://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..f7a47552485 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
> > + _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();
> > +
> > + 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();
> > +
> > + 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());
> > + }
> > +
> > + public:
> > + template<typename _OIndexType, size_t... _OExtents>
> > + requires (sizeof...(_OExtents) == rank())
> > + && ((_OExtents == dynamic_extent || _Extents ==
> > dynamic_extent
> > + || _OExtents == _Extents) && ...)
> >
> > Let's imagine that we have a _S_is_compatible_function(e1, e2) that
> > encapsulates this condition.
> > return e1 == dynamic_extent || e2 == dynamic_extent || e1 == e2.
> > Then ...
> >
> > + 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 (__self.rank() != __other.rank())
> > + return false;
> >
> > .. in operator== we could add check:
> > if constexpr (!(_S_is_compatible(_OExtents, _Extends) && ...))
> > return false;
> > This would avoid doing any runtime checks in some cases.
>
> Very nice observation. I was hoping that in the cases where
> everything could be determined at compile time, e.g.
>
> std::extents<int, 1, 2>{} == std::extents<short, 1, 2>{}
>
> the compiler would be able to reduce the expression to `true`.
>
We could add:
if constexpr (__self.rank() != __other.rank())
return ralse;
else if constexpr (!(_S_is_compatible(_OExtents, _Extends) && ...))
return false;
// N.B. Extents are compatible, so they are dynamic or static and equal
else if (((_Extends != dynamic_extent) && ...))
return true;
else
{
/// for each loop
}
>
> I'd like to check the code the compiler generates in some of
> these cases. Taken literally, I think the proposal doesn't go
> far enough, because there's also cases in which we know at
> compile time that the answer is `true` (not just `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>
> > + 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 <http://std.cc.in> b/
> > libstdc++-v3/src/c++23/std.cc.in <http://std.cc.in>
> > index 5e18ad73908..e42f54df20e 100644
> > --- a/libstdc++-v3/src/c++23/std.cc.in <http://std.cc.in>
> > +++ b/libstdc++-v3/src/c++23/std.cc.in <http://std.cc.in>
> > @@ -1831,7 +1831,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
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20250422/9b02b1e1/attachment-0001.htm>
More information about the Libstdc++
mailing list