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

[Tomasz Kaminski]

On Mon, Aug 11, 2025 at 3:23 PM Luc Grosheintz <luc.grosheintz@gmail.com>
wrote:

> 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>
>
Thanks for submitting the patch. Few small suggestions below.

> ---
>  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];
>
Any reason for using an internal lambda here....

>           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];
>
...and here...

>           return __ret;
>         }();
>
> @@ -519,7 +514,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>        {
>         constexpr auto& __sta_exts = __static_extents<_Extents>();
>
I would change this type to span<const size_t>, we do not need a array
reference
in this case.
 constexpr span<const size_t>  __sta_exts./

>         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;
>
...and ternary operator here? I would prefer to use:
if (__ext != dynamic_extent)
  __sta_prod *= __ext;
And:
for(size_t __r = 0; __r < __rank; ++__r)
   if (size_t __ext = _Extents[__i]; __ext != dynamic_extent)
     __sta_prod *= __ext;

>         return __extents_prod(__exts, __sta_prod, 0, __rank);
>        }
>
> --
> 2.50.0
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20250811/7f754076/attachment-0001.htm>