netch80: (bird)
netch80 ([personal profile] netch80) wrote2016-01-14 12:35 pm

divide non impera

Числовое деление в современных процессорах - это какой-то странный забытый всеми пасынок. Я понимаю, что для лайкания котиков или раскодировки видео его скорость, скорее всего, не важна. Но когда пытаешься выжать ещё полпроцента из программы и видишь кучу делений на неконстанту(!) в методах 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 это уже паршиво.



[identity profile] filonov.livejournal.com 2016-01-14 11:12 am (UTC)(link)
Сдается мне вероятность того, что результаты целочисленного деления и деления через плавучку не совпадут, отлична от нуля.

[identity profile] netch80.livejournal.com 2016-01-14 11:21 am (UTC)(link)
Эта вероятность нулевая. Во-первых, код сравнивает все результаты, во-вторых, это подтверждает теория. Делим мы 32-битные числа, а у double мантисса - 53 бита, денормализованных и бесконечностей не может быть при такой операции по определению.

Кстати, при отладке этого кода я таки нарвался на несовпадение - теперь cvttpd2dq вместо наивного и округляющего cvtpd2dq :)

(Случай делитель=0, естественно, не рассматривается - его надо проверять отдельно или исключать логически.)
Edited 2016-01-14 11:21 (UTC)

[identity profile] http://users.livejournal.com/_slw/ 2016-01-14 11:22 am (UTC)(link)
если под линухом гонять, то там есть возможность сделать (при загрузке) CPU-only ядра, на которых не будет ни прерываний, ни шедулинга других задач.
с учетом того, что контекст плавучки надо бы дополнительно сохранять могут быть изменения.

[identity profile] netch80.livejournal.com 2016-01-14 11:26 am (UTC)(link)
Я специально выбрал минимально загруженные машины, убирал лишнюю загрузку (на десктопах - начиная с firefox'ов) и отсекал крайние значения (точнее, даже все варианты, когда времена заметно разные). Поэтому уверен, что переключения задач при этих измерениях не происходили. Операции сами по себе очень длинные, кэш если влияет, то равномерно на все действия.

[identity profile] http://users.livejournal.com/_slw/ 2016-01-14 11:33 am (UTC)(link)
а у меня нет такой уверенности, все же в системе постоянно болтается чертова куча даже user-land процессов, не говоря уж о кернельных тредах и тех же таймерных и сетевых прерываниях.
netch: (Default)

[personal profile] netch 2016-01-14 07:46 pm (UTC)(link)
Если такие есть, они действуют равномерно на все измерения, так что соотношение времён не должно меняться.

[identity profile] http://users.livejournal.com/_slw/ 2016-01-14 07:49 pm (UTC)(link)
соотношение времен может меняться между интом и флоатом.
особенно если запускать чисто интовую программу без флотатовского кода вообще. ну теоретически.

[identity profile] netch80.livejournal.com 2016-01-14 08:28 pm (UTC)(link)
Доли процента. Не в счёт.

[identity profile] http://users.livejournal.com/_slw/ 2016-01-14 11:24 am (UTC)(link)
и это ты еще деления на тилере о 64 ядрах не щупал (как и на текоторых других процах)!

[identity profile] netch80.livejournal.com 2016-01-14 11:27 am (UTC)(link)
что такое "тилер"?

[identity profile] netch80.livejournal.com 2016-01-14 12:19 pm (UTC)(link)
Ну, его ещё найти в доступе надо. А x86 - его вокруг везде и всегда, и разнообразный до не могу.
Вот решусь сломать какой-нибудь старый раутер ради openwrt, будет ещё другой рахитектуры...