线性序列的总和= n *（n + 1）/ 2-比lea / imul / shrd好吗？

Question

这是我用于计算总和的汇编代码rax = 1 + 2 + 3 + .... +使用高斯方法的rdi rax =（rdi + 1）* rdi /2。你们中有人有想法或知道intel指令以进一步减少所需的循环数？备注：nop用于对齐

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可以提前1个时钟提供ls 64位，或者更晚1个时钟提供ms 64位。

[我认为，通过删除shrd，我们看到的是-3个时钟，shr $1和or $1的+1个时钟（并行），-1个时钟未使用%rdx。

顺便说一下，sn_a和sn_b都为UINT64_MAX返回0！请注意，结果比该时间早uint64_t way溢出！

---

FWIW，我的计时循环看起来像这样：

  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

这些设备很棒吗，还是什么？