Почему мой более сложный цикл C быстрее?

Я смотрю на производительность memchr -подобных функций и сделал интересное наблюдение.

Это check.c с тремя реализациями, чтобы найти смещение символа \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 us
• mem2: 12 us
• mem3: 25 us
• mem4: 16 us

(Я использую библиотеку criterion для измерения этих времен с статистической точностью.)

Я не могу объяснить это самому себе. Почему 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

Любое объяснение очень ценится!

Ответы

Ответ 1

Мое лучшее предположение заключается в том, что это связано с зависимостью регистра - если вы посмотрите на основной цикл с 3 командами в mem1, у вас есть круговая зависимость от rax. Naïvely, это означает, что каждая команда должна дождаться окончания последней - на практике это означает, что если инструкции не будут удалены достаточно быстро, микроархитектура может закончиться из регистров, чтобы переименовать и просто отказаться и свалиться на бит.

В mem2 факт, что в цикле есть 4 команды, а возможно, и тот факт, что больше явного конвейера при использовании как rax, так и edx/dl - вероятно, дает исключение - аппаратное обеспечение исполнения заказа легче, поэтому оно более эффективно конвейеризуется.

Я не претендую на роль эксперта, так что это может быть полная глупость, но на основе того, что я изучил Agner Fog абсолютное золото в оптимизации Intel детали, это не кажется совершенно необоснованной гипотезой.

Изменить: из интереса я тестировал mem1 и mem2 на моей машине (Core 2 Duo E7500), скомпилированный с -O2 -falign-functions = 64 на тот же самый ассемблерный код. Вызывая либо функцию с заданной строкой 1 000 000 раз в цикле, и используя Linux time, я получаю ~ 19 с для mem1 и ~ 18.8s для mem2 - намного меньше, чем разница 25% в новой микроархитектуре. Угадайте, что нужно купить i5...

Ответ 2

Ваш вход таков, что быстрее mem2. Каждая буква на входе, отличная от "\n", имеет значение больше, чем "$", поэтому условие if является ложным из первой части выражения (x <= '$') и второй части выражения ( x == '\n' || x == '\ 0') никогда не выполняется. Если вы будете использовать "####" вместо "abcd", я подозреваю, что выполнение будет медленнее.

Ответ 3

В кэше тест mem1() берет на себя основную нагрузку на кеш.

Запустите тест mem1() сначала и снова как последний, и используйте второй раз, поскольку он отражает загрунтованный кеш, как и другие тесты. Уверенно это будет быстрее и более справедливое сравнение времени.