From 4959739d83c25c37abdc19c3fda7067a70a751f0 Mon Sep 17 00:00:00 2001
From: Luc Grosheintz <luc.grosheintz@gmail.com>
Date: Mon, 11 Aug 2025 22:14:55 +0200
Subject: libstdc++: Simplify precomputed partial products in <mdspan>.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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.

Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@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 8f97425..4db4fd9 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>
-- 
cgit v1.1