On Mon, Aug 11, 2025 at 3:29 PM Tomasz Kaminski <tkami...@redhat.com> wrote:
>
>
> On Mon, Aug 11, 2025 at 3:23 PM Luc Grosheintz <luc.groshei...@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.groshei...@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
>>
>>
