Оптимизация суммы линейной последовательности = n * (n + 1) / 2 - что-нибудь быстрее, чем lea / imul / shrd?

Question

это мой ассемблерный код, используемый для вычисления суммы rax = 1 + 2 + 3 + .... + rdi с использованием метода Гаусса rax = (rdi + 1) * rdi / 2. Есть ли у кого-нибудь из вас идея или знаете инструкцию intel для дальнейшего уменьшения количества необходимых циклов? примечание: ноп для выравнивания

nop
lea rax, [rdi + 1] 
imul rdi
shrd rax, rdx, 1
ret 

Answer 1

К сожалению, shrd ужасно медленный (3 такта на ряде устройств).

Принимая sn_a в качестве версии shrd:

   lea    0x1(%rdi),%rax       # sn_a
   imul   %rdi
   shrd   $0x1,%rdx,%rax
# if you want %rdx:%rax need shr $1, $rdx here
   retq   

и sn_b в качестве предложенной мной альтернативы:

   lea    0x1(%rdi),%rax       # sn_b
   or     $0x1,%rdi
   shr    %rax
   imul   %rdi                 # %rdx:%rax is 128 bit result
   retq   

И (в основном) пустое sn_e:

   mov    %rdi,%rax            # sn_e
   retq   

Я получил следующие значения тактов на одну итерацию времени l oop (см. ниже):

        Ryzen 7   i7 (Coffee-Lake)
  sn_a:  11.00     11.00
  sn_b:   8.05      8.27      -- yay :-)
  sn_e:   5.00      5.00

Я считаю, что:

            Ryzen 7             i7 Coffee-Lake
        latency throughput   latency throughput  
  shrd     3       1/3          3       1/3
  imul     3       1/2          3       1/1  -- 128 bit result
  imul     2       1/2          3       1/1  --  64 bit result

где пропускная способность - это команды / часы. Я полагаю, что 128-битное значение imul доставляет ls 64 бита на 1 такт раньше или ms 64 бита на один такт позже.

Я думаю, что мы видим в моментах времени -3 такта, удаляя shrd, +1 часы для shr $1 и or $1 (параллельно), -1 часы не используют %rdx.

Кстати, и sn_a, и sn_b возвращают 0 для UINT64_MAX! Имейте в виду, результат переполняется uint64_t путь раньше, чем это!

---

FWIW, моя синхронизация l oop выглядит следующим образом:

  uint64_t  n ;
  uint64_t  r ;
  uint64_t  m ;

  m = zz ;                      // static volatile uint64_t zz = 0
  r = 0 ;
  n = 0 ;

  qpmc_read_start(...) ;        // magic to read rdpmc 
  do
    {
      n += 1 ;
      r += sigma_n(n + (r & m)) ;
    }
  while (n < 1000000000) ;

  qpmc_read_stop(....) ;        // magic to read rdpmc 

Где + (r & m) устанавливает зависимость так, что вход для функции, которая синхронизируется, зависит от результат предыдущего звонка. r += собирает результат, который позже печатается - что помогает убедить компилятор не оптимизировать l oop.

l oop компилируется в:

<sigma_timing_run+64>:          // 64 byte aligned
   mov    %r12,%rdi
   inc    %rbx
   and    %r13,%rdi
   add    %rbx,%rdi
   callq  *%rbp
   add    %rax,%r12
   cmp    $0x3b9aca00,%rbx
   jne    <sigma_timing_run+64>

Замена + (r & m) на + (n & m) удаляет зависимость, но l oop равно:

<sigma_timing_run+64>:          // 64 byte aligned
   inc    %rbx
   mov    %r13,%rdi
   and    %rbx,%rdi
   add    %rbx,%rdi
   callq  *%rbp
   add    %rax,%r12
   cmp    $0x3b9aca00,%rbx
   jne    0x481040 <sigma_timing_run+64>

, что совпадает с l oop с зависимостью, но время:

        Ryzen 7   i7 (Coffee-Lake)
  sn_a:   5.56      5.00
  sn_b:   5.00      5.00
  sn_e:   5.00      5.00

Прекрасны ли эти устройства или как?