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

[Tomasz Kaminski]

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

>
>
> On 8/11/25 15:29, Tomasz Kaminski wrote:
> > 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...
>
> Because of the duplication of code? I was anticipating a review
> in that would ask to inline to reduce symbols. It also took a
> while until I found the almost passable name (and by that time I was
> already mentally stuck on two lambdas). More than happy to create a
> function __static_or_one.
>
And personally, I find an if (not dynamic) multiply much clearer way to
express
what we are computing there: only multiply extents that are static.
Multiplying by 1 is a bit roundabound way to express that.


> >
> >>            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./
>
> I'll change it, consistency is good.
>
> >
> >>          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;
> >
>
> The ternary is shorter and since its the product of all static extents,
> everything is known at compile time and the whole block is replaced by a
> constant.
>
I just find an if much more readable, and expressing the intent in both
cases,
I would also make sure that the computation is done at compile time, by
having:
constexpr size_t _sta_prod = [] {
   size_t __res;
   for(auto __ext : __static_extents<_Extents>())
       if (__ext != dynamic_extent)
         __res *= __ext;
    return __res;
}();


> >>          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/71e4b4d1/attachment.htm>