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

[Tomasz Kaminski]

On Mon, Aug 11, 2025 at 3:29 PM Tomasz Kaminski <tkaminsk@redhat.com> 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...
>
>>           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.
>
To provide more motivation, I have also followed the approach in my
updates, where
when we care only about the __sta_exts values, I use a span of const
size_t, and only
preserve the fact that __static_extents<_Extents> produce reference to
array, when
we need to initialize NTTP with it. I would prefer to do that consistently.

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