divide non impera

[netch80]

Числовое деление в современных процессорах - это какой-то странный забытый всеми пасынок. Я понимаю, что для лайкания котиков или раскодировки видео его скорость, скорее всего, не важна. Но когда пытаешься выжать ещё полпроцента из программы и видишь кучу делений на неконстанту(!) в методах std::deque или std::unordered_map, начинаешь задумываться. А тут показывают проблемы от деления в хэшмапе, которая самая что ни на есть базовая структура, и тоже никто не оптимизирует под константу даже при постоянном размере хэша - и эти чудеса от деления вылазят в полный рост.

Беру тестовый пример (код ниже) и сравниваю скорость одного и того же 32-битного деления в вариантах собственно нацело и - перевести оба числа в double, разделить, перевести обратно в int. Далее усреднённые (5 проб на все первичные значения, два крайних отброшены, оставшиеся 3 усреднены) времена (меньше - лучше), длина массива подобрана так, чтобы переключения задач в процессе одного замера не происходило. Все компиляции с gcc 4.8, -O; -march=native, если не уточнено. (-O2, -O3 дают все результаты чуть медленнее.)

AMD FX-8150 (3.6GHz), -march=k8:

Integer time: 121991
Float64/FPU time: 79405
Float64/SSE time: 44578
SSE2-packed time: 35827

Ускорение от упакованного SSE2 по сравнению с одиночным очевидно, но меньше, чем ожидалось. А вот от FPU и SSE в целом при дополнительной конверсии(!) по сравнению с целочисленным - очень удивительно.

(То же самое с -march=native на gcc-4.8 плохо: включается AVX, но верхние части регистров не зачищаются, и Float64/SSE время удваивается(!) - 90-91k вместо 44k. А вот в gcc5 это уже исправили - vxorps перед vmovsd возвращает время в нормальное.)

AMD Athlon 64 3500+ (2.2GHz):

Integer time: 245093
Float64/FPU time: 87644
Float64/SSE time: 82745
SSE2-packed time: 83360

Тут уже упаковывать нет смысла, а вот целочисленное по-прежнему в загоне.

Переключаем вендора.

Intel Pentium G860 (3GHz):

Integer time: 58324
Float64/FPU time: 82303
Float64/SSE time: 88143
SSE2-packed time: 38742

SSE неупакованное медленнее FPU! А целочисленное деление вдруг быстрее плавающего. Самое смешное, что packed спасает, почему-то, быстрее, чем в 2 раза - разные АЛУ с разными принципами?

Intel Xeon X5690 (3.45GHz), типа крутой, но архитектурно на поколение-два древнее предыдущего домашнего зверя. (Для него пришлось из-за переключения задач сократить выборку в 10 раз, так что времена в показе после усреднения обратно умножены на 10.)

Integer time: 76947
Float64/FPU time: 150687
Float64/SSE time: 163263
SSE2-packed time: 69380

Та же фигня - от упаковки ускорение в 2.3 раза?

Кстати, у agner@ фокус с делением через плавучку не описан. Посоветовать, что ли...

#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>

#define NDIVS 10000002

#define unlikely(x) __builtin_expect(x, 0)
#define likely(x) __builtin_expect(x, 1)

long tvdiff(const struct timeval *t1, const struct timeval *t0) {
  return 1000000L * (t1->tv_sec - t0->tv_sec) + (t1->tv_usec - t0->tv_usec);
}

volatile int divres;
int nums[NDIVS], dens[NDIVS], quots[NDIVS];

int main(int argc, char *argv[])
{
  struct timeval tv0, tv1;
  unsigned ix;
#if !defined(NO_COMPARE)
  unsigned cw;
#endif
  long time_int, time_float64;
  if (argc >= 2) {
    srand(strtoul(argv[1], NULL, 0));
  }
  for (ix = 0; ix < NDIVS; ++ix) {
    nums[ix] = 1 + (rand() & 0x3FFFFFFF);
    dens[ix] = 1 + (rand() & 0x3FFFFFFF);
  }
  gettimeofday(&tv0, NULL);
  for (ix = 0; ix < NDIVS; ++ix) {
    divres = quots[ix] = nums[ix] / dens[ix];
  }
  gettimeofday(&tv1, NULL);
  time_int = tvdiff(&tv1, &tv0);
  printf("Integer time: %ld\n", time_int);
  gettimeofday(&tv0, NULL);
#if !defined(NO_COMPARE)
  cw = 0;
#endif
  for (ix = 0; ix < NDIVS; ++ix) {
    divres = (int) ((double) nums[ix] / (double) dens[ix]);
#if !defined(NO_COMPARE)
    if (unlikely(divres != quots[ix])) { ++cw; }
#endif
  }
  gettimeofday(&tv1, NULL);
  time_float64 = tvdiff(&tv1, &tv0);
  printf("Float64 time: %ld\n", time_float64);
  printf("I/F ratio: %g\n", (double) time_int / (double) time_float64);
#if !defined(NO_COMPARE)
  printf("cw=%u\n", cw);
#endif

#if defined(WITH_SSE2)
  gettimeofday(&tv0, NULL);
#if !defined(NO_COMPARE)
  cw = 0;
#endif
  for (ix = 0; ix < NDIVS; ix += 2) {
    int tmp_quots[2];
    asm(
      "cvtpi2pd %[nums], %%xmm4\n\t"
      "cvtpi2pd %[dens], %%xmm5\n\t"
      "divpd %%xmm5, %%xmm4\n\t"
      "cvttpd2dq %%xmm4, %%xmm5\n\t"
      "movq %%xmm5, %[quots]"
      : [quots] "=m" (tmp_quots)
      : [nums] "m" (nums[ix]), [dens] "m" (dens[ix])
      : "xmm4", "xmm5");
#if !defined(NO_COMPARE)
    if (unlikely(tmp_quots[0] != quots[ix])) {
      if (cw < 16) {
        printf("%d/%d=%d(%d)\n", nums[ix], dens[ix], quots[ix], tmp_quots[0]);
      }
      ++cw;
    }
    if (unlikely(tmp_quots[1] != quots[ix+1])) {
      ++cw;
    }
#endif
  }
  gettimeofday(&tv1, NULL);
  long time_sse2 = tvdiff(&tv1, &tv0);
  printf("SSE2-packed time: %ld\n", time_sse2);
  printf("I/S ratio: %g\n", (double) time_int / (double) time_sse2);
  printf("F/S ratio: %g\n", (double) time_float64 / (double) time_sse2);
#if !defined(NO_COMPARE)
  printf("cw=%u\n", cw);
#endif // NO_COMPARE
#endif // WITH_SSE2

  printf("F/S ratio: %g\n", (double) time_float64 / (double) time_sse2);
#if !defined(NO_COMPARE)
  printf("cw=%u\n", cw);
#endif // NO_COMPARE
#endif // WITH_SSE2

  return 0;
}

P.S[1]. Intel со своей любовью к SRT однозначно извращенцы. Но AMD, что, использует его же в целочисленном варианте? (Про плавучий известно, что Goldschmidt.)

P.S[2]. Везде было cw=0, можно доверять :)

P.S[3]. В упомянутом видео предполагают, что это проблемы шедулера, на основании того, что плавучее деление на AMD в одном железном треде (hart, по терминологии авторов RISC-V) тормозит целочисленное в соседнем. Боюсь, тут сложнее.

P.S[4]. Надо не лениться таки менять железо даже на очень автопилотных машинах. Железо уровня 10-летней давности даже x86 это уже паршиво.