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

[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.grosheintz@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