为什么我的更复杂的C循环更快？

Question

我正在研究memchr类似函数的性能并做了一个有趣的观察.

这是check.c通过3种实现来查找\n字符串中字符的偏移量:

#include <stdlib.h>

size_t mem1(const char *s)
{
  const char *p = s;
  while (1)
  {
    const char x = *p;
    if (x == '\n') return (p - s);
    p++;
  }
}

size_t mem2(const char *s)
{
  const char *p = s;
  while (1)
  {
    const char x = *p;
    if (x <= '$' && (x == '\n' || x == '\0')) return (p - s);
    p++;
  }
}

size_t mem3(const char *s)
{
  const char *p = s;
  while (1)
  {
    const char x = *p;
    if (x == '\n' || x == '\0') return (p - s);
    p++;
  }
}

size_t mem4(const char *s)
{
  const char *p = s;
  while (1)
  {
    const char x = *p;
    if (x <= '$' && (x == '\n')) return (p - s);
    p++;
  }
}

我在一个字节字符串上运行这些函数,这些字节可以用Haskell表达式描述(concat $ replicate 10000 "abcd") ++ "\n" ++ "hello"- 即10000次asdf,然后是新行找到,然后hello.当然,所有3个实现都返回相同的偏移量:40000如预期的那样.

有趣的是,在编译时gcc -O2,该字符串的运行时间为:

• mem1:16我们
• mem2:12我们
• mem3:25我们
• mem4:16我们

(我正在使用标准库来统计准确度来测量这些时间.)

我无法向自己解释这一点.为什么mem2比其他两个快得多？

-

由以下组件生成的程序集gcc -S -O2 -o check.asm check.c:

mem1:
.LFB14:
  cmpb  $10, (%rdi)
  movq  %rdi, %rax
  je  .L9
.L6:
  addq  $1, %rax
  cmpb  $10, (%rax)
  jne .L6
  subq  %rdi, %rax
  ret
.L9:
  xorl  %eax, %eax
  ret


mem2:
.LFB15:
  movq  %rdi, %rax
  jmp .L13
.L19:
  cmpb  $10, %dl
  je  .L14
.L11:
  addq  $1, %rax
.L13:
  movzbl  (%rax), %edx
  cmpb  $36, %dl
  jg  .L11
  testb %dl, %dl
  jne .L19
.L14:
  subq  %rdi, %rax
  ret


mem3:
.LFB16:
  movzbl  (%rdi), %edx
  testb %dl, %dl
  je  .L26
  cmpb  $10, %dl
  movq  %rdi, %rax
  jne .L27
  jmp .L26
.L30:
  cmpb  $10, %dl
  je  .L23
.L27:
  addq  $1, %rax
  movzbl  (%rax), %edx
  testb %dl, %dl
  jne .L30
.L23:
  subq  %rdi, %rax
  ret
.L26:
  xorl  %eax, %eax
  ret


mem4:
.LFB17:
  cmpb  $10, (%rdi)
  movq  %rdi, %rax
  je  .L38
.L36:
  addq  $1, %rax
  cmpb  $10, (%rax)
  jne .L36
  subq  %rdi, %rax
  ret
.L38:
  xorl  %eax, %eax
  ret

任何解释都非常感谢!

Answer 1

我最好的猜测是它与寄存器依赖有关 - 如果您查看 中的 3 指令主循环mem1，您会发现对 的循环依赖rax。Na\xc3\xafvely，这意味着每条指令都必须等待最后一条指令完成 - 实际上，这意味着如果指令没有足够快地退出，微体系结构可能会用完寄存器来重命名，然后放弃并停止运行一点点。

\n

事实上mem2，循环中有 4 条指令，而且可能还有更多使用 和 的显式管道这一事实，rax这edx/dl可能使乱序执行硬件更容易，因此它最终使流水线更加有效。

\n

我并不自称是专家，所以这可能完全是无稽之谈，但根据我对Agner Fog 的英特尔优化细节的绝对金矿的研究，这似乎并不是一个完全不合理的假设。

\n

编辑：出于兴趣，我已经在我的机器（Core 2 Duo E7500）上进行了测试mem1，mem2并使用 -O2 -falign-functions=64 编译为完全相同的汇编代码。在循环中使用给定字符串调用任一函数 1,000,000 次并使用 Linux 的time，我得到 ~19s formem1和 ~18.8s for mem2- 远小于较新微架构上 25% 的差异。看来是时候买个i5了...

\n