netch80: (bird)
[personal profile] 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 это уже паршиво.



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

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

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

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

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

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

Profile

netch80: (Default)
netch80

August 2017

S M T W T F S
  12345
67 89101112
13141516171819
20212223242526
2728293031  

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Aug. 18th, 2017 06:26 pm
Powered by Dreamwidth Studios