LINUX.ORG.RU

Скалярное произведение - быстрее, ещё быстрее!

 , , ,


0

3

Попытался соптимизировать под SSE4/4.1/4.2 функцию вычисления скалярного произведения двух векторов 32-битных чисел с плавающей точкой. Длина векторов фиксирована - 28 чисел (=28*4=112 байт). %rsi указывает на первый вектор (загружается в %xmm1-7), %rdi - на второй, результат в %xmm0.

   0:   66 0f ef c0             pxor   %xmm0,%xmm0
   4:   0f 10 0e                movups (%rsi),%xmm1
   7:   0f 10 56 10             movups 0x10(%rsi),%xmm2
   b:   0f 10 5e 20             movups 0x20(%rsi),%xmm3
   f:   0f 10 66 30             movups 0x30(%rsi),%xmm4
  13:   0f 10 6e 40             movups 0x40(%rsi),%xmm5
  17:   0f 10 76 50             movups 0x50(%rsi),%xmm6
  1b:   0f 10 7e 60             movups 0x60(%rsi),%xmm7
  1f:   0f 59 0f                mulps  (%rdi),%xmm1
  22:   0f 59 57 10             mulps  0x10(%rdi),%xmm2
  26:   0f 59 5f 20             mulps  0x20(%rdi),%xmm3
  2a:   0f 59 67 30             mulps  0x30(%rdi),%xmm4
  2e:   0f 59 6f 40             mulps  0x40(%rdi),%xmm5
  32:   0f 59 77 50             mulps  0x50(%rdi),%xmm6
  36:   0f 59 7f 60             mulps  0x60(%rdi),%xmm7
  3a:   0f 58 d1                addps  %xmm1,%xmm2
  3d:   0f 58 e3                addps  %xmm3,%xmm4
  40:   0f 58 f5                addps  %xmm5,%xmm6
  43:   0f 58 c7                addps  %xmm7,%xmm0
  46:   0f 58 e2                addps  %xmm2,%xmm4
  49:   0f 58 c6                addps  %xmm6,%xmm0
  4c:   0f 58 c4                addps  %xmm4,%xmm0
  4f:   f2 0f 7c c0             haddps %xmm0,%xmm0
  53:   f2 0f 7c c0             haddps %xmm0,%xmm0

Кое-какой выигрыш получил, но хочется больше. Что тут можно ещё оптимизировать? Что-то по-другому сделать? Попробовал также на AVX, но оказалось сильно медленнее.

Ответ на: комментарий от onetoomany

С чего ты взял, что результат компиляции оставляет место для дальнейшей оптимизации? У тебя тривиальный код, любой современный компилятор и так производит оптимальный код для него.

И да, использовать URL shorteners - плохой тон. Здесь не твиттер.

godbolt.org в первый раз видишь штоле?

nonimous ()
Ответ на: комментарий от onetoomany

Здесь не твиттер.

Это годболт, он по другому не умеет. И даже если бы умел, то URL обычно получается слишком длинным чтобы им было удобно пользоваться.

pftBest ★★★★ ()
Ответ на: комментарий от nonimous

любой современный компилятор и так производит оптимальный код для него.

На самом деле тот же gcc производит субоптимальный код:

volatile float p; // чтобы компилятор не удалил весь код
int main() {
    float a[28];
    float b[28];
    int i;
    float product = 0;
    for (i=0; i<28; i++)
      product += a[i] * b[i];
    p = product;
}


$ gcc -O3 -msse -msse2 -msse3 -msse4 -msse4.1 -msse4.2 -c main.o main.c

$ objdump -d main.o

0000000000000000 <main>:
   0:   66 0f ef c9             pxor   %xmm1,%xmm1
   4:   48 83 ec 70             sub    $0x70,%rsp
   8:   31 c0                   xor    %eax,%eax
   a:   66 0f 1f 44 00 00       nopw   0x0(%rax,%rax,1)
  10:   f3 0f 10 44 04 88       movss  -0x78(%rsp,%rax,1),%xmm0
  16:   f3 0f 59 44 04 f8       mulss  -0x8(%rsp,%rax,1),%xmm0
  1c:   48 83 c0 04             add    $0x4,%rax
  20:   48 83 f8 70             cmp    $0x70,%rax
  24:   f3 0f 58 c8             addss  %xmm0,%xmm1
  28:   75 e6                   jne    10 <main+0x10>
  2a:   f3 0f 11 0d 00 00 00    movss  %xmm1,0x0(%rip)        # 32 <main+0x32>
  31:   00 
  32:   48 83 c4 70             add    $0x70,%rsp
  36:   c3                      retq   
onetoomany ()
Ответ на: комментарий от onetoomany

1. Зачем ты смотришь на результат компиляции кода с UB? Компилятор может сократить все до retq и будет прав. 2. Как ты определяешь «оптимальность» кода, на глаз?

nonimous ()
Ответ на: комментарий от onetoomany

Шланг вон размотал, но без бенчмарков это еще ничего не значит. Gcc умеет анроллить уже лет 20, если он этого не сделал, значит у него были на то основания.

nonimous ()
Ответ на: комментарий от nonimous

2. Как ты определяешь «оптимальность» кода, на глаз?

Я гонял тесты в размотанном и неразмотанном варианте.

onetoomany ()
Ответ на: комментарий от onetoomany

Как легко можно заметить, gcc даже не попытался размотать (unroll) цикл.

man gcc:

       -funroll-loops
           Unroll loops whose number of iterations can be determined at compile time or upon entry to the loop.  -funroll-loops implies -frerun-cse-after-loop, -fweb and -frename-registers.  It also turns on complete loop peeling (i.e. complete removal of loops with a small constant number of iterations).  This option makes code larger, and may or may not make it run faster.

           Enabled with -fprofile-use.
см.

xaizek ★★★★★ ()
Ответ на: комментарий от tim239

Сайт полезный, хотя я сомневаюсь, что автогенерированный код окажется быстрее затюненного вручную. Впрочем, надо проверить (и проверю).

onetoomany ()
Ответ на: комментарий от onetoomany
  9c:   f3 0f 58 c3             addss  %xmm3,%xmm0
  a0:   f3 0f 58 c4             addss  %xmm4,%xmm0
  a4:   f3 0f 58 c5             addss  %xmm5,%xmm0
  a8:   f3 0f 58 c6             addss  %xmm6,%xmm0
  ac:   f3 0f 58 c7             addss  %xmm7,%xmm0
  b0:   f3 41 0f 58 c0          addss  %xmm8,%xmm0
  b5:   f3 41 0f 58 c1          addss  %xmm9,%xmm0

Pipelining? Не, не слышали.

onetoomany ()
Ответ на: комментарий от onetoomany

1) Почему в цикле не ++i (или это тоже автоматом оптимизируется уже)?

2) Почему бы не запихнуть оба вектора в один вектор парами:

c = [a0, b0, a1, b1, ..., a27, b27]

а потом вычислять в цикле примерно такое?

for(i=0; i < 56; i+=2 ){ product += c[i]*c[i+1] }

?

Но кто его знает сколько займёт времени на копирование в новый массив.

grem ★★★★★ ()
Последнее исправление: grem (всего исправлений: 1)
Ответ на: комментарий от grem

1) Почему в цикле не ++i (или это тоже автоматом оптимизируется уже)?

Потому, что i это POD, а не stl-итератор.

andreyu ★★★★★ ()
Ответ на: комментарий от grem

Я не пишу на C, я пишу на ассемблере. Код на C был для непонятливого анонимуса.

А вектора - они отдельные, не вперехлёст, и даже трансформация в такой вид ничего не даст инструкциям SIMD.

onetoomany ()
Ответ на: комментарий от anonymous

Оно хорошо, если ты контролируешь выделение памяти под данные. Если нет, придётся копировать, и время сразу просядет.

Можно попробовать срезать невыровненный кусок сначала с помощью movups, а потом делать movaps.

onetoomany ()

Дальше остается оптимизация обрашения к памяти (заполнение кеша).

Память у нас медленная. Промах кеша получается дорогой.

Замерь время чтения данных из массивов в регистры. Быстрее этого уже никак.

Что используется профилирования? Без нее дальнейшая оптимизация невозможна.

Дальше остается выполнять вычисления этой функции для разных массивов на разных ядрах...

vel ★★★★★ ()
Последнее исправление: vel (всего исправлений: 1)
Ответ на: DPPS от d

Ага. Проблема в том, что она выполняет действия с регистрами, то есть надо загружать предварительно из памяти отдельной инструкцией. Инструкций получается больше, выполняется медленнее. Проверял уже.

Впрочем, буду рад, если кто-нибудь сможет меня опровергнуть и написать с dpps более быстрый код.

onetoomany ()
Ответ на: комментарий от anonymous

Вообще-то

For some history: yes, movaps versus movups used to make a difference in performance. But since Intel's Nehalem chips the difference in negligable. As a compiler targeting newer hardware, if we get to choose between movups and movaps we are generally going to choose movups as there is no risk of your program crashing.

https://connect.microsoft.com/VisualStudio/feedback/details/812192/inefficien...

onetoomany ()
Ответ на: комментарий от nonimous

Теперь сравни свои ссылки с результатом для gcc из транка (который не боится использовать movups и ему не обязательно выравнивать массивы) + -Ofast: https://godbolt.org/g/w2pSRq

И зачем там нужен был __restrict, если там только читается, а не пишется по указателям?

utf8nowhere ★★ ()
Последнее исправление: utf8nowhere (всего исправлений: 1)

Попробовал также на AVX, но оказалось сильно медленнее.

Не соответствует реальности.

Что-то по-другому сделать?

Не пытаться писать парашу?

Скалярное произведение

У тебя оно там не одно - вот и оптимизируй не одно.

rustonelove ()
Ответ на: комментарий от onetoomany

Ага. Проблема в том, что она выполняет действия с регистрами, то есть надо загружать предварительно из памяти отдельной инструкцией.

И что же из этого следует?

Инструкций получается больше, выполняется медленнее.

Никак второе из первого не следует, в твоём случае, да и в большинстве случаев.

Впрочем, буду рад, если кто-нибудь сможет меня опровергнуть и написать с dpps более быстрый код.

Если ты хочешь, что-бы кто-то тебе что-то написал, то ты должен предоставить экосистему - тесты и бенчмарки, желательно всё в рамках конечного юзкейса.

rustonelove ()
Ответ на: комментарий от vel

Дальше остается оптимизация обрашения к памяти (заполнение кеша).

Ахинея.

Память у нас медленная. Промах кеша получается дорогой.

Ахинея.

Замерь время чтения данных из массивов в регистры. Быстрее этого уже никак.

Ахинея.

Что используется профилирования? Без нее дальнейшая оптимизация невозможна.

Ахинея. Что ты собрался «профилировать»?

Дальше остается выполнять вычисления этой функции для разных массивов на разных ядрах...

Чё?

Я даже не знаю что на эту потужную ретрансляцию мифов и легенд из-за парты отвечать.

rustonelove ()

Опять царь забавляет публику срачём со своим виртуалом.

anonymous ()
Ответ на: комментарий от nonimous

Типа, если ты там увидел: vaddss/vmulss - это типа векторизация? Экспертные эксперты не перестают удивлять.

rustonelove ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.