<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Mon, Jul 28, 2025 at 10:13 AM Luc Grosheintz <<a href="mailto:luc.grosheintz@gmail.com">luc.grosheintz@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
<br>
On 7/28/25 08:32, Tomasz Kaminski wrote:<br>
> In the __fwd_prod, __rev_prod I would also add the case for all-dynamic<br>
> extents, so we do not instantiate an array with all 1, i.e. we would have:<br>
> constexpr size_t __rank = _Extents::rank();<br>
> + size_t __sta_prod = _RevProd<_Extents>::_S_value[__r];<br>
> + return __extents_prod(__exts, __sta_prod, __r + 1, __rank);<br>
> if constexpr (__rank == 1)<br>
> return 1;<br>
> else if constexpr (__rank == 2)<br>
> return __i == 0 ? _M_extents.extent(1) : 1;<br>
> else if constexpr (Extents::rank_dynamic() == __rank)<br>
> return __extents_prod(__exts, __1u, __r + 1, __rank);<br>
> else<br>
> {<br>
> size_t __sta_prod = _RevProd<_Extents>::_S_value[__r];<br>
> return __extents_prod(__exts, __sta_prod, __r + 1, __rank);<br>
> }<br>
<br>
True, purely dynamic extents, is another interesting case to optimize,<br>
I suspect there's more potential in that case. For example the<br>
indirection E[i] := D[k[i]] is not needed because k[i] == i.<br></blockquote><div>I am not concerned about optimization that much, just in avoiding creating</div><div>storage for arrays with all 1. This two suggestion are independent, so I will </div><div>still add:</div><div>if constexpr (Extents::rank_dynamic() == __rank)<br> return __extents_prod(__exts, __1u, __r + 1, __rank);<br>else<br> {<br> size_t __sta_prod = _RevProd<_Extents>::_S_value[__r];<br> return __extents_prod(__exts, __sta_prod, __r + 1, __rank);<br> }</div><div>// So the __RevProd is no longer instantiated.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
Therefore, since the series already had several commits, I chose<br>
to leave it for later.<br>
<br>
> <br>
> <br>
> On Mon, Jul 28, 2025 at 8:02 AM Tomasz Kaminski <<a href="mailto:tkaminsk@redhat.com" target="_blank">tkaminsk@redhat.com</a>> wrote:<br>
> <br>
>><br>
>><br>
>> On Sun, Jul 27, 2025 at 2:47 PM Luc Grosheintz <<a href="mailto:luc.grosheintz@gmail.com" target="_blank">luc.grosheintz@gmail.com</a>><br>
>> wrote:<br>
>><br>
>>> The methods layout_{left,right}::mapping::stride are defined<br>
>>> as<br>
>>><br>
>>> \prod_{i = 0}^r E[i]<br>
>>> \prod_{i = r+1}^n E[i]<br>
>>><br>
>>> This is computed as the product of a pre-comupted static product and the<br>
>>> product of the required dynamic extents.<br>
>>><br>
>>> Disassembly shows that even for low-rank extents, i.e. rank == 1 and<br>
>>> rank == 2, with at least one dynamic extent, the generated code loads<br>
>>> two values; and then runs the loop over at most one element, e.g.<br>
>>><br>
>>> 220: 48 8b 0c f5 00 00 00 mov rcx,QWORD PTR [rsi*8+0x0]<br>
>>> 227: 00<br>
>>> 228: 48 8b 04 f5 00 00 00 mov rax,QWORD PTR [rsi*8+0x0]<br>
>>> 22f: 00<br>
>>> 230: 48 c1 e1 02 shl rcx,0x2<br>
>>> 234: 74 1a je 250 <stride_left_d5+0x30><br>
>>> 236: 48 01 f9 add rcx,rdi<br>
>>> 239: 0f 1f 80 00 00 00 00 nop DWORD PTR [rax+0x0]<br>
>>> 240: 48 63 17 movsxd rdx,DWORD PTR [rdi]<br>
>>> 243: 48 83 c7 04 add rdi,0x4<br>
>>> 247: 48 0f af c2 imul rax,rdx<br>
>>> 24b: 48 39 f9 cmp rcx,rdi<br>
>>> 24e: 75 f0 jne 240 <stride_left_d5+0x20><br>
>>> 250: c3 ret<br>
>>><br>
>>> If there's no dynamic extents, it simply loads the precomputed product<br>
>>> of static extents.<br>
>>><br>
>>> For rank == 1 the answer is constant `1`; for rank == 2 it's either 1 or<br>
>>> extents.extent(k), with k == 0 for layout_left and k == 1 for<br>
>>> layout_right.<br>
>>><br>
>>> Consider,<br>
>>><br>
>>> using Ed = std::extents<int, dyn>;<br>
>>> int stride_left_d(const std::layout_left::mapping<Ed>& m, size_t r)<br>
>>> { return m.stride(r); }<br>
>>><br>
>>> using E3d = std::extents<int, 3, dyn>;<br>
>>> int stride_left_3d(const std::layout_left::mapping<E3d>& m, size_t r)<br>
>>> { return m.stride(r); }<br>
>>><br>
>>> using Ed5 = std::extents<int, dyn, 5>;<br>
>>> int stride_left_d5(const std::layout_left::mapping<Ed5>& m, size_t r)<br>
>>> { return m.stride(r); }<br>
>>><br>
>>> The optimized code for these three cases is:<br>
>>><br>
>>> 0000000000000060 <stride_left_d>:<br>
>>> 60: b8 01 00 00 00 mov eax,0x1<br>
>>> 65: c3 ret<br>
>>><br>
>>> 0000000000000090 <stride_left_3d>:<br>
>>> 90: 48 83 fe 01 cmp rsi,0x1<br>
>>> 94: 19 c0 sbb eax,eax<br>
>>> 96: 83 e0 fe and eax,0xfffffffe<br>
>>> 99: 83 c0 03 add eax,0x3<br>
>>> 9c: c3 ret<br>
>>><br>
>>> 00000000000000a0 <stride_left_d5>:<br>
>>> a0: b8 01 00 00 00 mov eax,0x1<br>
>>> a5: 48 85 f6 test rsi,rsi<br>
>>> a8: 74 02 je ac <stride_left_d5+0xc><br>
>>> aa: 8b 07 mov eax,DWORD PTR [rdi]<br>
>>> ac: c3 ret<br>
>>><br>
>>> For rank == 1 it simply returns 1 (as expected). For rank == 2, it<br>
>>> either implements a branchless formula, or conditionally loads one<br>
>>> value. In all cases involving a dynamic extent this seems like it's<br>
>>> always doing clearly less work, both in terms of computation and loads.<br>
>>><br>
>>> For rank == 2, it trades loading one value for a branchless sequence of<br>
>>> four instructions that don't require loading any values.<br>
>>><br>
>> I will put this optimization into the __fwd_prod and __rev_pord functions,<br>
>> so it will be applied for all uses. This will also avoid us creating this<br>
>> caching<br>
>> tables for such small ranks.<br>
>><br>
>>><br>
>>> libstdc++-v3/ChangeLog:<br>
>>><br>
>>> * include/std/mdspan (layout_left::mapping::stride): Optimize<br>
>>> for rank <= 2.<br>
>>> (layout_right::mapping::stride): Ditto.<br>
>>><br>
>>> Signed-off-by: Luc Grosheintz <<a href="mailto:luc.grosheintz@gmail.com" target="_blank">luc.grosheintz@gmail.com</a>><br>
>>> ---<br>
>>> libstdc++-v3/include/std/mdspan | 14 ++++++++++++--<br>
>>> 1 file changed, 12 insertions(+), 2 deletions(-)<br>
>>><br>
>>> diff --git a/libstdc++-v3/include/std/mdspan<br>
>>> b/libstdc++-v3/include/std/mdspan<br>
>>> index 06ccf3e3827..f288af96cdb 100644<br>
>>> --- a/libstdc++-v3/include/std/mdspan<br>
>>> +++ b/libstdc++-v3/include/std/mdspan<br>
>>> @@ -652,7 +652,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION<br>
>>> requires (extents_type::rank() > 0)<br>
>>> {<br>
>>> __glibcxx_assert(__i < extents_type::rank());<br>
>>> - return __mdspan::__fwd_prod(_M_extents, __i);<br>
>>> + if constexpr (extents_type::rank() == 1)<br>
>>> + return 1;<br>
>>> + else if constexpr (extents_type::rank() == 2)<br>
>>> + return __i == 0 ? 1 : _M_extents.extent(0);<br>
>>> + else<br>
>>> + return __mdspan::__fwd_prod(_M_extents, __i);<br>
>>> }<br>
>>><br>
>>> template<typename _OExtents><br>
>>> @@ -797,7 +802,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION<br>
>>> requires (extents_type::rank() > 0)<br>
>>> {<br>
>>> __glibcxx_assert(__i < extents_type::rank());<br>
>>> - return __mdspan::__rev_prod(_M_extents, __i);<br>
>>> + if constexpr (extents_type::rank() == 1)<br>
>>> + return 1;<br>
>>> + else if constexpr (extents_type::rank() == 2)<br>
>>> + return __i == 0 ? _M_extents.extent(1) : 1;<br>
>>> + else<br>
>>> + return __mdspan::__rev_prod(_M_extents, __i);<br>
>>> }<br>
>>><br>
>>> template<typename _OExtents><br>
>>> --<br>
>>> 2.50.0<br>
>>><br>
>>><br>
> <br>
<br>
</blockquote></div></div>