On 5/21/25 08:29, Tomasz Kaminski wrote:
On Tue, May 20, 2025 at 3:16 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++-v3/ChangeLog:
* include/std/mdspan (layout_left): New class.
Signed-off-by: Luc Grosheintz <luc.groshei...@gmail.com>
---
libstdc++-v3/include/std/mdspan | 309 +++++++++++++++++++++++++++++++-
1 file changed, 308 insertions(+), 1 deletion(-)
diff --git a/libstdc++-v3/include/std/mdspan
b/libstdc++-v3/include/std/mdspan
index 47cfa405e44..d90fed57a19 100644
--- a/libstdc++-v3/include/std/mdspan
+++ b/libstdc++-v3/include/std/mdspan
@@ -144,6 +144,20 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{ return __exts[__i]; });
}
+ static constexpr span<const size_t>
+ _S_static_subextents(size_t __begin, size_t __end) noexcept
+ {
+ return {_Extents.data() + __begin, _Extents.data() + __end};
+ }
+
+ constexpr span<const _IndexType>
+ _M_dynamic_subextents(size_t __begin, size_t __end) const noexcept
+ requires (_Extents.size() > 0)
+ {
+ return {_M_dynamic_extents + _S_dynamic_index[__begin],
+ _M_dynamic_extents + _S_dynamic_index[__end]};
+ }
+
private:
using _S_storage = __array_traits<_IndexType,
_S_rank_dynamic>::_Type;
[[no_unique_address]] _S_storage _M_dynamic_extents;
@@ -160,6 +174,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
|| _Extent <= numeric_limits<_IndexType>::max();
}
+ namespace __mdspan
+ {
+ template<typename _Extents>
+ constexpr span<const size_t>
+ __static_subextents(size_t __begin, size_t __end)
+ { return _Extents::_S_storage::_S_static_subextents(__begin,
__end); }
+
+ template<typename _Extents>
+ constexpr span<const typename _Extents::index_type>
+ __dynamic_subextents(const _Extents& __exts, size_t __begin, size_t
__end)
+ {
+ return __exts._M_dynamic_extents._M_dynamic_subextents(__begin,
__end);
+ }
+ }
+
template<typename _IndexType, size_t... _Extents>
class extents
{
@@ -251,7 +280,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
: _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())
@@ -276,6 +304,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
private:
+ friend span<const size_t>
+ __mdspan::__static_subextents<extents>(size_t, size_t);
+
+ friend span<const index_type>
+ __mdspan::__dynamic_subextents<extents>(const extents&, size_t,
size_t);
+
using _S_storage = __mdspan::_ExtentsStorage<
_IndexType, array<size_t, sizeof...(_Extents)>{_Extents...}>;
[[no_unique_address]] _S_storage _M_dynamic_extents;
@@ -286,6 +320,52 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace __mdspan
{
+ template<typename _Extents>
+ constexpr size_t
+ __static_extents_prod(size_t __begin, size_t __end)
+ {
+ auto __sta_exts = __static_subextents<_Extents>(__begin, __end);
+ size_t __ret = 1;
+ for(size_t __i = 0; __i < __sta_exts.size(); ++__i)
+ if (__sta_exts[__i] != dynamic_extent)
+ __ret *= __sta_exts[__i];
+ return __ret;
I wonder if we could perform some compile time caching of result here, like:
size_t __ret = 1;
switch (__end - __begin)
{
default:
break;
case 3:
if (__sta_exts[__begin + 2] != dynamic_extent)
_ret *= __sta_exts[__begin + 2];
[[ fallthrou ]];
case 2:
if (__sta_exts[__begin + 1] != dynamic_extent)
_ret *= __sta_exts[__begin + 1];
[[ fallthrou ]];
case 1:
if (__sta_exts[__begin] != dynamic_extent)
_ret *= __sta_exts[__begin];
[[ fallthrou ]];
case 0:
return __ret;
}
if constexpr ( _Extents::rank() >= 4 )
{
static constexpr std::array<size_t, _Extents::rank()> __partial_prods
= [] { return partial sums ;}
return __partial_prods[__end - 1] / __partial_prods[__begin];
}
return __ret;
Nice idea to trade N >= 4 multiplications for 1 division. Without
measuring how do we know that N >= 4 is the optimal choice?
Since we only ever need __exts_prod to compute __{fwd,rev}_prod, we
can instead cache __static_{fwd,rev}_prod(__r) separately and can skip
the divison entirely. Note that no layout uses both __fwd_prod and
__rev_prod with arguments that are not know at compile time.
When looking at __static_extents_prod I notice that it takes and
std::extents as template argument, since we don't use the index_type,
we could create fewer lookup tables by making it depend only on the
`size_t... Extents`.
We need to check that in required_span_size, where both __begin and __end
are known, the optimizer replaces all of __static_extents_prod with a
compile time constant; and in __dynamic_extents_prod doesn't do any
indirection and just multiplies everything.
Meaning there's a few options and things to check, but I'm wondering if
we should do those once we have enough of mdspan implemented to measure
something. It might also be nicer to have these optimizations in dedicated
commits.
However, if you prefer doing it now, I'm happy to dive in.
+ }
+
+ template<typename _Extents>
+ constexpr size_t
+ __dynamic_extents_prod(const _Extents& __exts, size_t __begin,
+ size_t __end)
+ {
+ auto __dyn_exts = __dynamic_subextents<_Extents>(__exts, __begin,
+ __end);
+ size_t __ret = 1;
+ for(size_t __i = 0; __i < __dyn_exts.size(); ++__i)
+ __ret *= __dyn_exts[__i];
+ return __ret;
+ }
+
+ template<typename _Extents>
+ constexpr typename _Extents::index_type
+ __exts_prod(const _Extents& __exts, size_t __begin, size_t __end)
noexcept
+ {
+ using _IndexType = typename _Extents::index_type;
And here doing something like:
size_t __ret = 1;
if constexpr (_Extents::rank_dynamic() != _Extents::rank())
__ret = __static_extents_prod<_Extents>(__begin, __end);;
Nice, I'd forgotten that it's not a compile time constant b/c of
the __begin and __end. This we should do regardless of the previous
optimization.
+ auto __ret = __static_extents_prod<_Extents>(__begin, __end);
+ if constexpr (_Extents::rank_dynamic() > 0)
+ __ret *= __dynamic_extents_prod(__exts, __begin, __end);
+ return __ret;
+ }
+
+ template<typename _Extents>
+ constexpr typename _Extents::index_type
+ __fwd_prod(const _Extents& __exts, size_t __r) noexcept
+ { return __exts_prod(__exts, 0, __r); }
+
+ template<typename _Extents>
+ constexpr typename _Extents::index_type
+ __rev_prod(const _Extents& __exts, size_t __r) noexcept
+ { return __exts_prod(__exts, __r + 1, __exts.rank()); }
+
template<typename _IndexType, size_t... _Counts>
auto __build_dextents_type(integer_sequence<size_t, _Counts...>)
-> extents<_IndexType, ((void) _Counts, dynamic_extent)...>;
@@ -304,6 +384,233 @@ _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<typename _Extents, typename... _Indices>
+ constexpr typename _Extents::index_type
+ __linear_index_left(const _Extents& __exts, _Indices... __indices)
+ {
+ using _IndexType = typename _Extents::index_type;
+ _IndexType __res = 0;
+ if constexpr (sizeof...(__indices) > 0)
+ {
+ _IndexType __mult = 1;
+ auto __update = [&, __pos = 0u](_IndexType __idx) mutable
+ {
+ __res += __idx * __mult;
+ __mult *= __exts.extent(__pos);
+ ++__pos;
+ };
+ (__update(__indices), ...);
+ }
+ return __res;
+ }
+
+ template<typename _Tp>
+ constexpr bool
+ __contains_zero(span<_Tp> __exts)
+ {
+ for (size_t __i = 0; __i < __exts.size(); ++__i)
+ if (__exts[__i] == 0)
+ return true;
+ return false;
+ }
+
+ template<typename _Extents>
+ consteval bool
+ __has_static_zero()
+ {
+ return __contains_zero(
+ __static_subextents<_Extents>(0, _Extents::rank()));
+ }
+
+ template<typename _Extents, typename _IndexType>
+ consteval _IndexType
+ __static_quotient(_IndexType __nom)
+ {
+ for(size_t __i = 0; __i < _Extents::rank(); ++__i)
+ {
+ auto __factor = _Extents::static_extent(__i);
+ if (__factor != dynamic_extent)
+ __nom /= _IndexType(__factor);
+ }
+ return __nom;
+ }
+
+ template<typename _Extents>
+ constexpr bool
+ __is_representable_extents(const _Extents& __exts)
+ {
+ using _IndexType = _Extents::index_type;
+ constexpr auto __rank = _Extents::rank();
+
+ constexpr auto __sta_quo = __static_quotient<_Extents, _IndexType>(
+ numeric_limits<_IndexType>::max());
+
+ if constexpr (__has_static_zero<_Extents>())
+ return true;
+ else if constexpr (_Extents::rank_dynamic() == 0)
+ return __sta_quo != 0;
+ else
+ {
+ auto __dyn_exts = __dynamic_subextents(__exts, 0, __rank);
+ if(__contains_zero(__dyn_exts))
+ return true;
+
+ if constexpr (__sta_quo == 0)
+ return false;
+ else
+ {
+ constexpr auto __dyn_rank = _Extents::rank_dynamic();
+ auto __dyn_quo = __sta_quo;
+ for(size_t __i = 0; __i < __dyn_rank && __dyn_quo > 0; ++__i)
+ __dyn_quo /= __dyn_exts[__i];
+ return __dyn_quo != 0;
+ }
+ }
+ }
+
+ template<typename _Extents, typename _IndexType>
+ concept __representable_size = _Extents::rank_dynamic() != 0
+ || __has_static_zero<_Extents>()
+ || (__static_quotient<_Extents, _IndexType>(
+ numeric_limits<_IndexType>::max()) != 0);
+
+ template<typename _Layout, typename _Mapping>
+ concept __mapping_of =
+ is_same_v<typename _Layout::mapping<typename
_Mapping::extents_type>,
+ _Mapping>;
+
+ template<typename _Mapping>
+ concept __standardized_mapping = __mapping_of<layout_left,
_Mapping>;
+
+ template<typename M>
+ concept __mapping_like = requires
+ {
+ requires __is_extents<typename M::extents_type>;
+ { M::is_always_strided() } -> same_as<bool>;
+ { M::is_always_exhaustive() } -> same_as<bool>;
+ { M::is_always_unique() } -> same_as<bool>;
+ bool_constant<M::is_always_strided()>::value;
+ bool_constant<M::is_always_exhaustive()>::value;
+ bool_constant<M::is_always_unique()>::value;
+ };
+
+ // A tag type to create internal ctors.
+ class __internal_ctor
+ { };
+ }
+
+ template<typename _Extents>
+ class layout_left::mapping
+ {
+ 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;
+
+ static_assert(__mdspan::__representable_size<_Extents, index_type>,
+ "The size of extents_type must be representable as index_type");
+
+ constexpr
+ mapping() noexcept = default;
+
+ constexpr
+ mapping(const mapping&) noexcept = default;
+
+ constexpr
+ mapping(const _Extents& __extents) noexcept
+ : _M_extents(__extents)
+ {
__glibcxx_assert(__mdspan::__is_representable_extents(_M_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
+ : mapping(__other.extents(), __mdspan::__internal_ctor{})
+ { }
+
+ constexpr mapping&
+ operator=(const mapping&) noexcept = default;
+
+ constexpr const _Extents&
+ extents() const noexcept { return _M_extents; }
+
+ constexpr index_type
+ required_span_size() const noexcept
+ { return __mdspan::__fwd_prod(_M_extents, extents_type::rank()); }
+
+ template<__mdspan::__valid_index_type<index_type>... _Indices>
+ requires (sizeof...(_Indices) == extents_type::rank())
+ constexpr index_type
+ operator()(_Indices... __indices) const noexcept
+ {
+ return __mdspan::__linear_index_left(
+ this->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:
+ template<typename _OExtents>
+ constexpr explicit
+ mapping(const _OExtents& __oexts, __mdspan::__internal_ctor)
noexcept
+ : _M_extents(extents_type(__oexts))
+ {
+ static_assert(__mdspan::__representable_size<_OExtents,
index_type>,
+ "The size of OtherExtents must be representable as
index_type");
+
__glibcxx_assert(__mdspan::__is_representable_extents(_M_extents));
+ }
+
+ public:
+ [[no_unique_address]] _Extents _M_extents;
+ };
+
_GLIBCXX_END_NAMESPACE_VERSION
}
#endif
--
2.49.0
