On 8/11/25 15:29, Tomasz Kaminski 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...
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.
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.
return __extents_prod(__exts, __sta_prod, 0, __rank); } -- 2.50.0
