[PATCH v2 2/2] libstdc++: Simplify precomputed partial products in .

[Luc Grosheintz]

Prior to this commit, the partial products of static extents in <mdspan>
was done in a loop that calls a function that computes the partial
product. The complexity is quadratic in the rank.

This commit removes the quadratic complexity.

libstdc++-v3/ChangeLog:

        * include/std/mdspan (__static_prod): Delete.
        (__fwd_partial_prods): Compute at compile-time in O(rank), not
        O(rank**2).
        (__rev_partial_prods): Ditto.
        (__size): Inline __static_prod.

Signed-off-by: Luc Grosheintz <luc.groshei...@gmail.com>
---
 libstdc++-v3/include/std/mdspan | 44 +++++++++++++++++----------------
 1 file changed, 23 insertions(+), 21 deletions(-)

diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan
index 8f974257e96..4db4fd98b43 100644
--- a/libstdc++-v3/include/std/mdspan
+++ b/libstdc++-v3/include/std/mdspan
@@ -256,27 +256,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __static_extents() noexcept
       { return _Extents::_S_storage::_S_static_extents(); }
 
-    template<array _Extents>
-      consteval size_t
-      __static_prod(size_t __begin, size_t __end)
-      {
-       size_t __prod = 1;
-       for(size_t __i = __begin; __i < __end; ++__i)
-         {
-           auto __ext = _Extents[__i];
-           __prod *= __ext == dynamic_extent ? size_t(1) : __ext;
-         }
-       return __prod;
-      }
-
     // Pre-compute: \prod_{i = 0}^r _Extents[i], for r = 0,..., n (exclusive)
     template<array _Extents>
       constexpr auto __fwd_partial_prods = [] consteval
        {
          constexpr size_t __rank = _Extents.size();
          std::array<size_t, __rank> __ret;
-         for(size_t __r = 0; __r < __rank; ++__r)
-           __ret[__r] = __static_prod<_Extents>(0, __r);
+         size_t __prod = 1;
+         for (size_t __r = 0; __r < __rank; ++__r)
+           {
+             __ret[__r] = __prod;
+             if (size_t __ext = _Extents[__r]; __ext != dynamic_extent)
+               __prod *= __ext;
+           }
          return __ret;
        }();
 
@@ -286,8 +278,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
        {
          constexpr size_t __rank = _Extents.size();
          std::array<size_t, __rank> __ret;
-         for(size_t __r = 0; __r < __rank; ++__r)
-           __ret[__r] = __static_prod<_Extents>(__r + 1, __rank);
+         size_t __prod = 1;
+         for (size_t __r = __rank; __r > 0; --__r)
+           {
+             __ret[__r - 1] = __prod;
+             if (size_t __ext = _Extents[__r - 1]; __ext != dynamic_extent)
+               __prod *= __ext;
+           }
          return __ret;
        }();
 
@@ -517,10 +514,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       constexpr typename _Extents::index_type
       __size(const _Extents& __exts) noexcept
       {
-       constexpr auto& __sta_exts = __static_extents<_Extents>();
-       constexpr size_t __rank = _Extents::rank();
-       constexpr size_t __sta_prod = __static_prod<__sta_exts>(0, __rank);
-       return __extents_prod(__exts, __sta_prod, 0, __rank);
+       constexpr size_t __sta_prod = [] {
+         span<const size_t> __sta_exts = __static_extents<_Extents>();
+         size_t __ret = 1;
+         for(auto __ext : __sta_exts)
+           if (__ext != dynamic_extent)
+             __ret *= __ext;
+         return __ret;
+       }();
+       return __extents_prod(__exts, __sta_prod, 0, _Extents::rank());
       }
 
     template<typename _IndexType, size_t... _Counts>
-- 
2.50.0