优化线性序列的总和=n * (n+1)2 - 有什么比lea imul shrd更快的吗？

Question

这是我的汇编代码用于计算总和 rax = 1 + 2 + 3 + ...... + rdi 使用高斯方法 rax = (rdi + 1 ) * rdi 2. + 你们有什么想法或知道一个英特尔指令，以进一步减少所需的周期数吗？

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   

我得到了以下时钟数，每次定时循环的迭代（见下文）。

        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 途径 比这更早！

---

我的时间循环是这样的。

  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 += 收集一个结果，然后打印出来--这有助于说服编译器不要优化掉这个循环。

循环编译为

<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) 删除了依赖关系，但循环是:

<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>

这和有依赖关系的循环是一样的，但时间是：

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

这些设备很奇妙，还是什么？