From: Luc Grosheintz <luc.groshei...@gmail.com>
In mdspan related code, for extents with no static extents, i.e. only
dynamic extents, the following simplifications can be made:
- The array of dynamic extents has size rank.
- The two arrays dynamic-index and dynamic-index-inv become
trivial, e.g. k[i] == i.
- All elements of the arrays __{fwd,rev}_partial_prods are 1.
This commits eliminates the arrays for dynamic-index, dynamic-index-inv
and __{fwd,rev}_partial_prods. It also removes the indirection k[i] == i
from the source code, which isn't as relevant because the optimizer is
(often) capable of eliminating the indirection.
To check if it's working we look at:
using E2 = std::extents<int, dyn, dyn, dyn, dyn>;
int stride_left_E2(const std::layout_left::mapping<E2>& m, size_t r)
{ return m.stride(r); }
which generates the following
0000000000000190 <stride_left_E2>:
190: 48 c1 e6 02 shl rsi,0x2
194: 74 22 je 1b8 <stride_left_E2+0x28>
196: 48 01 fe add rsi,rdi
199: b8 01 00 00 00 mov eax,0x1
19e: 66 90 xchg ax,ax
1a0: 48 63 17 movsxd rdx,DWORD PTR [rdi]
1a3: 48 83 c7 04 add rdi,0x4
1a7: 48 0f af c2 imul rax,rdx
1ab: 48 39 fe cmp rsi,rdi
1ae: 75 f0 jne 1a0 <stride_left_E2+0x10>
1b0: c3 ret
1b1: 0f 1f 80 00 00 00 00 nop DWORD PTR [rax+0x0]
1b8: b8 01 00 00 00 mov eax,0x1
1bd: c3 ret
We see that:
- There's no code to load the partial product of static extents.
- There's no indirection D[k[i]], it's just D[i] (as before).
On a test file which computes both mapping::stride(r) and
mapping::required_span_size, we check for static storage with
objdump -h
we don't see the NTTP _Extents, anything (anymore) related to
_StaticExtents, __fwd_partial_prods or __rev_partial_prods. We also
check that the size of the reference object file (described three
commits prior) reduced by a few percent from 41.9kB to 39.4kB.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__all_dynamic): New function.
(__mdspan::_StaticExtents::_S_dynamic_index): Convert to method.
(__mdspan::_StaticExtents::_S_dynamic_index_inv): Ditto.
(__mdspan::_StaticExtents): New specialization for fully dynamic
extents.
(__mdspan::__fwd_prod): New constexpr if branch to avoid
instantiating __fwd_partial_prods.
(__mdspan::__rev_prod): Ditto.
Reviewed-by: Tomasz Kamiński <tkami...@redhat.com>
Signed-off-by: Luc Grosheintz <luc.groshei...@gmail.com>
---
Patch v3 changes __all_dynamic to accept span.
libstdc++-v3/include/std/mdspan | 63 +++++++++++++++++++++++++++------
1 file changed, 53 insertions(+), 10 deletions(-)
diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan
index 3cbf922e78d..d98b91d4419 100644
--- a/libstdc++-v3/include/std/mdspan
+++ b/libstdc++-v3/include/std/mdspan
@@ -49,6 +49,15 @@ namespace std _GLIBCXX_VISIBILITY(default)
_GLIBCXX_BEGIN_NAMESPACE_VERSION
namespace __mdspan
{
+ consteval bool
+ __all_dynamic(std::span<const size_t> __extents)
+ {
+ for(auto __ext : __extents)
+ if (__ext != dynamic_extent)
+ return false;
+ return true;
+ }
+
template<array _Extents>
class _StaticExtents
{
@@ -59,13 +68,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
static constexpr size_t _S_rank = _Extents.size();
- // For __r in [0, _S_rank], _S_dynamic_index[__r] is the number
+ // 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_dyn_exts.
- static constexpr auto _S_dynamic_index = [] consteval
+ static constexpr size_t
+ _S_dynamic_index(size_t __r) noexcept
+ { return _S_dynamic_index_data[__r]; }
+
+ static constexpr auto _S_dynamic_index_data = [] consteval
{
array<size_t, _S_rank+1> __ret;
size_t __dyn = 0;
@@ -78,11 +91,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __ret;
}();
- static constexpr size_t _S_rank_dynamic = _S_dynamic_index[_S_rank];
+ 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
+ // 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
+ static constexpr size_t
+ _S_dynamic_index_inv(size_t __r) noexcept
+ { return _S_dynamic_index_inv_data[__r]; }
+
+ static constexpr auto _S_dynamic_index_inv_data = [] consteval
{
array<size_t, _S_rank_dynamic> __ret;
for (size_t __i = 0, __r = 0; __i < _S_rank; ++__i)
@@ -96,6 +113,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{ return _Extents[__r]; }
};
+ template<array _Extents>
+ requires (__all_dynamic<_Extents>())
+ class _StaticExtents<_Extents>
+ {
+ public:
+ static constexpr size_t _S_rank = _Extents.size();
+
+ static constexpr size_t
+ _S_dynamic_index(size_t __r) noexcept
+ { return __r; }
+
+ static constexpr size_t _S_rank_dynamic = _S_rank;
+
+ static constexpr size_t
+ _S_dynamic_index_inv(size_t __k) noexcept
+ { return __k; }
+
+ static constexpr size_t
+ _S_static_extent(size_t) noexcept
+ { return dynamic_extent; }
+ };
+
template<typename _IndexType, array _Extents>
class _ExtentsStorage : public _StaticExtents<_Extents>
{
@@ -107,6 +146,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
using _S_base::_S_rank_dynamic;
using _S_base::_S_dynamic_index;
using _S_base::_S_dynamic_index_inv;
+ using _S_base::_S_static_extent;
template<typename _OIndexType>
static constexpr _IndexType
@@ -118,7 +158,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __se = _Extents[__r];
if (__se == dynamic_extent)
- return _M_dyn_exts[_S_dynamic_index[__r]];
+ return _M_dyn_exts[_S_dynamic_index(__r)];
else
return __se;
}
@@ -144,7 +184,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
size_t __di = __i;
if constexpr (_OtherRank != _S_rank_dynamic)
- __di = _S_dynamic_index_inv[__i];
+ __di = _S_dynamic_index_inv(__i);
_M_dyn_exts[__i] = _S_int_cast(__get_extent(__di));
}
}
@@ -178,8 +218,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_dynamic_extents(size_t __begin, size_t __end) const noexcept
requires (_Extents.size() > 0)
{
- return {_M_dyn_exts + _S_dynamic_index[__begin],
- _M_dyn_exts + _S_dynamic_index[__end]};
+ return {_M_dyn_exts + _S_dynamic_index(__begin),
+ _M_dyn_exts + _S_dynamic_index(__end)};
}
private:
@@ -252,7 +292,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
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>;
@@ -430,6 +469,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 1;
else if constexpr (__rank == 2)
return __r == 0 ? 1 : __exts.extent(0);
+ else if constexpr (__all_dynamic(__sta_exts))
+ return __extents_prod(__exts, 1, 0, __r);
else
{
size_t __sta_prod = __fwd_partial_prods<__sta_exts>[__r];
@@ -448,6 +489,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return 1;
else if constexpr (__rank == 2)
return __r == 0 ? __exts.extent(1) : 1;
+ else if constexpr (__all_dynamic(__sta_exts))
+ return __extents_prod(__exts, 1, __r + 1, __rank);
else
{
size_t __sta_prod = __rev_partial_prods<__sta_exts>[__r];
--
2.49.0
