Вращение 20 байт , точнее, 5 двойных слов

[Славян]

Есть 20 байт, точнее 5 двойных слов: int a[5] = {a,b,c,d,e};
Надо повернуть "влево", чтобы вышло: {b,c,d,e,a}
Но нашёл только u = _rotl64(v,32), что дало:

// вращаем 4*5 байт по 32 бита, влево
void
Rotat(unsigned long *p)
{
    *(unsigned long long*)p = _rotl64(*(unsigned long long*)p, 32);
    *(unsigned long long*)(p+1) = _rotl64(*(unsigned long long*)(p+1), 32);
    *(unsigned long long*)(p+2) = _rotl64(*(unsigned long long*)(p+2), 32);
    *(unsigned long long*)(p+3) = _rotl64(*(unsigned long long*)(p+3), 32);
}

Но компилятором на асме получилось много левого (и это со всеми оптимизациями!!!, вижуалка):

?Rotat@@YAXPEAK@Z PROC                  ; Rotat
 
; 364  :    *(unsigned long long*)p = _rotl64(*(unsigned long long*)p, 32);
 
  00000 48 8b 01     mov     rax, QWORD PTR [rcx]
  00003 48 c1 c0 20  rol     rax, 32            ; 00000020H
  00007 48 89 01     mov     QWORD PTR [rcx], rax
 
; 365  :    *(unsigned long long*)(p+1) = _rotl64(*(unsigned long long*)(p+1), 32);
 
  0000a 48 8b 41 04  mov     rax, QWORD PTR [rcx+4]
  0000e 48 c1 c0 20  rol     rax, 32            ; 00000020H
  00012 48 89 41 04  mov     QWORD PTR [rcx+4], rax
 
; 366  :    *(unsigned long long*)(p+2) = _rotl64(*(unsigned long long*)(p+2), 32);
 
  00016 48 8b 41 08  mov     rax, QWORD PTR [rcx+8]
  0001a 48 c1 c0 20  rol     rax, 32            ; 00000020H
  0001e 48 89 41 08  mov     QWORD PTR [rcx+8], rax
 
; 367  :    *(unsigned long long*)(p+3) = _rotl64(*(unsigned long long*)(p+3), 32);
 
  00022 48 8b 41 0c  mov     rax, QWORD PTR [rcx+12]
  00026 48 c1 c0 20  rol     rax, 32            ; 00000020H
  0002a 48 89 41 0c  mov     QWORD PTR [rcx+12], rax
 
; 368  : }

А хотелось бы:

rol  qw [rcx],32
rol  qw [rcx+4],32
rol  qw [rcx+8],32
rol  qw [rcx+12],32

Никак мне не ускорить мой Си-код?..

[grgdvo]

Предлагаю посмотреть векторные инструкции, а именно memmove

godbolt c -O2 показывает, что можно в пять инструкций уложиться над одним 128-битным регистром

https://www.godbolt.org/z/jG35KdMcW

[Qraizer]

Славян, во-первых, я бы поостерёгся называть короткий вариант быстрым. rol комплексная инструкция и довольно медленная, + обращения к памяти по пересекающимся адресам такая себе оптимизация. Сгенеренный код хотя бы пытается память распараллелить. Во-вторых, у тебя весьма частный случай, а вот если заглянуть внутрь std::rotate<>(), то там окажется много интересного. В реализации участвует несколько шаблонных классов с constexpr-методами, внутри которых всё на if constexpr (...), проверяющих возможность векторизации, тривиальность вращаемых объектов, выравнивание и их размер, возможность выброса исключений вращаемыми объектами и др, и if (std::is_constant_evaluated), который проверяет, а не выполнил ли уже вращение компилятор сам. В итоге в зависимости от кучи проверок вызываются другие вспомогательные функции. В общей сложности там сотни строк кода. (Правда следует отметить, что многие из этих функций используются в реализации и других алгоритмов, например, std::reverse<>(), std::stable_partition<>(), std::make_heap<>() итп.)
Конкретно твой пример, переписанный как

template <size_t N>
int a[5] = { 1, 2, 3, 4, 5 };
 
void Rotat(int (&p)[N])
{
  std::rotate(std::begin(p), std::begin(p) + 1, std::end(p));
}
/* ... */
  Rotat(a);
/* ... */

превращается в

        lea     rdx, OFFSET FLAT:?a@@3PAHA+4
        lea     rbx, OFFSET FLAT:?a@@3PAHA              ; a
        mov     rcx, rbx
        call    __std_reverse_trivially_swappable_4
        lea     rdi, OFFSET FLAT:?a@@3PAHA+20
        mov     rdx, rdi
        lea     rcx, OFFSET FLAT:?a@@3PAHA+4
        call    __std_reverse_trivially_swappable_4
        mov     rdx, rdi
        mov     rcx, rbx
        call    __std_reverse_trivially_swappable_4
/* ... */

__declspec(noalias) void __cdecl __std_reverse_trivially_swappable_4(void* _First, void* _Last) noexcept {
#if !defined(_M_ARM64EC)
    if (_Byte_length(_First, _Last) >= 64 && _bittest(&__isa_enabled, __ISA_AVAILABLE_AVX2)) {
        const void* _Stop_at = _First;
        _Advance_bytes(_Stop_at, _Byte_length(_First, _Last) >> 6 << 5);
        do {
            _Advance_bytes(_Last, -32);
            const __m256i _Left  = _mm256_permute4x64_epi64(_mm256_loadu_si256(static_cast<__m256i*>(_First)), 78);
            const __m256i _Right = _mm256_permute4x64_epi64(_mm256_loadu_si256(static_cast<__m256i*>(_Last)), 78);
            const __m256i _Left_reversed  = _mm256_shuffle_epi32(_Left, 27);
            const __m256i _Right_reversed = _mm256_shuffle_epi32(_Right, 27);
            _mm256_storeu_si256(static_cast<__m256i*>(_First), _Right_reversed);
            _mm256_storeu_si256(static_cast<__m256i*>(_Last), _Left_reversed);
            _Advance_bytes(_First, 32);
        } while (_First != _Stop_at);
    }
#endif // !defined(_M_ARM64EC)
 
    if (_Byte_length(_First, _Last) >= 32
#ifdef _M_IX86
        && _bittest(&__isa_enabled, __ISA_AVAILABLE_SSE2)
#endif // _M_IX86
    ) {
        const void* _Stop_at = _First;
        _Advance_bytes(_Stop_at, _Byte_length(_First, _Last) >> 5 << 4);
        do {
            _Advance_bytes(_Last, -16);
            const __m128i _Left           = _mm_loadu_si128(static_cast<__m128i*>(_First));
            const __m128i _Right          = _mm_loadu_si128(static_cast<__m128i*>(_Last));
            const __m128i _Left_reversed  = _mm_shuffle_epi32(_Left, 27);
            const __m128i _Right_reversed = _mm_shuffle_epi32(_Right, 27);
            _mm_storeu_si128(static_cast<__m128i*>(_First), _Right_reversed);
            _mm_storeu_si128(static_cast<__m128i*>(_Last), _Left_reversed);
            _Advance_bytes(_First, 16);
        } while (_First != _Stop_at);
    }
 
    _Reverse_tail(static_cast<unsigned long*>(_First), static_cast<unsigned long*>(_Last));
}
/* ... */
template <class _BidIt>
static void _Reverse_tail(_BidIt _First, _BidIt _Last) noexcept {
    for (; _First != _Last && _First != --_Last; ++_First) {
        const auto _Temp = *_First;
        *_First          = *_Last;
        *_Last           = _Temp;
    }
}

и если интересно, как выглядит эта самая _Reverse_tail<>(), то вот из отладчика:

Цитата

_Reverse_tail(static_cast<unsigned long*>(_First), static_cast<unsigned long*>(_Last));
00007FF60B968D95 sub rdx,4
00007FF60B968D99 cmp r8,rdx
00007FF60B968D9C je __std_reverse_trivially_swappable_4+0C1h (07FF60B968DB1h)
00007FF60B968D9E mov ecx,dword ptr [r8]
00007FF60B968DA1 mov eax,dword ptr [rdx]
00007FF60B968DA3 mov dword ptr [r8],eax
00007FF60B968DA6 add r8,4
00007FF60B968DAA mov dword ptr [rdx],ecx
00007FF60B968DAC cmp r8,rdx
00007FF60B968DAF jne __std_reverse_trivially_swappable_4+0A5h (07FF60B968D95h)
}
00007FF60B968DB1 ret

причём точка входа стоит на отмеченной строке, а не на начале функции.
Собстна, вопрос: ты пробовал профилировать код? Или тебе-таки важен размер, а не скорость?

Сообщение отредактировано: Qraizer - 04.11.26, 19:38

[Славян]

Цитата grgdvo @ 04.11.26, 14:33

Предлагаю посмотреть векторные инструкции

Точно, спасибо, глянул!
Переделал на SSE:

// вращаем 4*5 байт по 32 бита, влево
void
Rotat(int *p)
{
    int b = *p;
    __m128 a = _mm_loadu_ps((float*)(p+1));
    p[4] = b;
    _mm_store_ps((float*)p, a);
}

И получил на выходе:

?Rotat@@YAXPEAH@Z PROC                  ; Rotat
; 372  :    int b = *p;
; 373  :    __m128 a = _mm_loadu_ps((float*)(p+1));
  00000 0f 10 41 04  movups  xmm0, XMMWORD PTR [rcx+4]
; 374  :    p[4] = b;
  00004 8b 01        mov     eax, DWORD PTR [rcx]
  00006 89 41 10     mov     DWORD PTR [rcx+16], eax
; 375  :    _mm_store_ps((float*)p, a);
  00009 0f 11 01     movups  XMMWORD PTR [rcx], xmm0
; 376  : }
  0000c c3       ret     0

Вообще без вращений, чистые mov'ы!!

Цитата Qraizer @ 04.11.26, 19:32

обращения к памяти по пересекающимся адресам

Подразумевалось при двух соседних инструкциях? Ну да, есть такой косяк, без него трудно...

Цитата Qraizer @ 04.11.26, 19:32

пробовал профилировать код? Или тебе-таки важен размер, а не скорость?

Скорость на первом месте, но краткость тоже прекрасна и часто на скорость намекает. Но пока не занимался ею. Будет время...

[ЫукпШ]

Цитата Славян @ 05.11.26, 07:09

Вообще без вращений, чистые mov'ы!!

Может оказаться, что самое простое решение окажется
самым быстрым:

void rot_(int* pArray, int iSize)
{
 int iSize1 = iSize-1;
 int tmp;
 tmp = pArray[0];
 for(int i=0;i<iSize1;++i)
 {
  pArray[i]=pArray[i+1];
 }
 pArray[iSize1]=tmp;
}

ассемблерный листинг:

?rot_@@YGXPAHH@Z PROC                   ; rot_, COMDAT
; _pArray$ = eax
 
; 9586 : яю/
; 9587 :
; 9588 :
 
  00000 8b 08        mov     ecx, DWORD PTR [eax]
 
; 9589 :
; 9590 :
; 9591 :
 
  00002 8b 50 04     mov     edx, DWORD PTR [eax+4]
  00005 89 10        mov     DWORD PTR [eax], edx
  00007 8b 50 08     mov     edx, DWORD PTR [eax+8]
  0000a 89 50 04     mov     DWORD PTR [eax+4], edx
  0000d 8b 50 0c     mov     edx, DWORD PTR [eax+12]
  00010 89 50 08     mov     DWORD PTR [eax+8], edx
  00013 8b 50 10     mov     edx, DWORD PTR [eax+16]
  00016 89 50 0c     mov     DWORD PTR [eax+12], edx
 
; 9592 :
; 9593 :
 
  00019 89 48 10     mov     DWORD PTR [eax+16], ecx
 
; 9594 :
 
  0001c c3       ret     0
?rot_@@YGXPAHH@Z ENDP

[Славян]

Цитата ЫукпШ @ 05.11.26, 12:55

Может оказаться, что самое простое решение окажется самым быстрым

1. Технически, может, конечно, но см. далее;
2. У меня 1 и 2 строки могут быть распараллелены (как и 3-я с 4-ой!);
3. В вашем же (классическом) каждые две соседние строки увязаны друг на друге - печаль для ЦП.
4. Сейчашняя увлечённость SSE может служить тому, что ЦП-производители стараются сделать эти инструкции быстрыми, что и вселяет в меня оптимизм и надежду!