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

[Luc Grosheintz]

Prior to this commit, the partial producs 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 | 33 +++++++++++++++------------------
 1 file changed, 15 insertions(+), 18 deletions(-)

diff --git a/libstdc++-v3/include/std/mdspan b/libstdc++-v3/include/std/mdspan
index 8f974257e96..e68275e3807 100644
--- a/libstdc++-v3/include/std/mdspan
+++ b/libstdc++-v3/include/std/mdspan
@@ -256,27 +256,18 @@ _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
        {
+         auto __static_or_one = [](size_t __ext)
+         { return __ext == dynamic_extent ? size_t(1) : __ext; };
+
          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);
+         __ret[0] = 1;
+         for (size_t __r = 0; __r < __rank - 1; ++__r)
+           __ret[__r + 1] = __static_or_one(_Extents[__r]) * __ret[__r];
          return __ret;
        }();
 
@@ -284,10 +275,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     template<array _Extents>
       constexpr auto __rev_partial_prods = [] consteval
        {
+         auto __static_or_one = [](size_t __ext)
+         { return __ext == dynamic_extent ? size_t(1) : __ext; };
+
          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);
+         __ret[__rank-1] = 1;
+         for (size_t __r = __rank-1; __r > 0; --__r)
+           __ret[__r - 1] = __static_or_one(_Extents[__r]) * __ret[__r];
          return __ret;
        }();
 
@@ -519,7 +514,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       {
        constexpr auto& __sta_exts = __static_extents<_Extents>();
        constexpr size_t __rank = _Extents::rank();
-       constexpr size_t __sta_prod = __static_prod<__sta_exts>(0, __rank);
+       size_t __sta_prod = 1;
+       for(auto __ext : __sta_exts)
+         __sta_prod *= __ext == dynamic_extent ? size_t(1) : __ext;
        return __extents_prod(__exts, __sta_prod, 0, __rank);
       }
 
-- 
2.50.0