Intereting Posts

Почему floor () так медленно?

Недавно я написал некоторый код (ISO / ANSI C) и был удивлен низкой плотностью, которую он достиг. Короче говоря, оказалось, что виновником была функция floor() . Он не только медленный, но и не векторизованный (с компилятором Intel, иначе ICL).

Вот несколько эталонных тестов для выполнения пол для всех ячеек в 2D-матрице:

 VC: 0.10 ICL: 0.20 

Сравните это с простым произведением:

 VC: 0.04 ICL: 0.04 

Как может floor() быть намного медленнее, чем простой литой ?! Это по сути то же самое (кроме отрицательных чисел). Второй вопрос: знает ли кто-нибудь о сверхбыстрой реализации floor() ?

PS: Вот цикл, который я сравнивал:

 void Floor(float *matA, int *intA, const int height, const int width, const int width_aligned) { float *rowA=NULL; int *intRowA=NULL; int row, col; for(row=0 ; row<height ; ++row){ rowA = matA + row*width_aligned; intRowA = intA + row*width_aligned; #pragma ivdep for(col=0 ; col<width; ++col){ /*intRowA[col] = floor(rowA[col]);*/ intRowA[col] = (int)(rowA[col]); } } } 

Несколько вещей делают слово медленнее, чем литье, и предотвращают векторизация.

Самый важный:

пол может изменить глобальное состояние. Если вы передадите слишком большое значение, чтобы быть представленным как целое число в формате float, переменная errno получает значение EDOM . Также выполняется специальная обработка для NaN. Все это относится к приложениям, которые хотят обнаружить случай переполнения и как-то справиться с ситуацией (не спрашивайте меня, как).

Обнаружение этих проблемных условий непросто и составляет более 90% времени исполнения пола. Фактическое округление является дешевым и может быть вложенным / векторизованным. Также очень много кода, поэтому включение всей функции пола сделает вашу программу медленнее.

Некоторые компиляторы имеют специальные флаги компилятора, которые позволяют компилятору оптимизировать некоторые из редко используемых правил c-стандарта. Например, GCC может сказать, что вы вообще не интересуетесь ошибкой. Для этого передайте -fno-math-errno или -ffast-math . ICC и VC могут иметь аналогичные флаги компилятора.

Btw – Вы можете катить свою собственную функцию пола, используя простые приведения. Вам просто нужно обращаться с отрицательными и положительными случаями по-разному. Это может быть намного быстрее, если вам не нужна специальная обработка переполнений и NaN.

Если вы собираетесь преобразовать результат операции floor() в int, и если вас не беспокоит переполнение, следующий код намного быстрее, чем (int)floor(x) :

 inline int int_floor(double x) { int i = (int)x; /* truncate */ return i - ( i > x ); /* convert trunc to floor */ } 

Безпоточный пол и потолок (лучше использовать пипилин) без проверки ошибок

 int f(double x) { return (int) x - (x < (int) x); // as dgobbi above, needs less than for floor } int c(double x) { return (int) x + (x > (int) x); } 

или с использованием пола

 int c(double x) { return -(f(-x)); } 

Самая быстрая реализация для большого массива на современных процессорах x86 была бы

  • измените режим округления MXCSR FP на раунд в направлении -Infinity (aka floor ) . В C это должно быть возможно с fenv или _mm_getcsr / _mm_setcsr .
  • цикл над массивом, выполняющий _mm_cvtps_epi32 на SIMD-векторах, преобразование 4 float в 32-разрядное целое с использованием текущего режима округления. (И сохранение векторов результатов в пункт назначения.)

    cvtps2dq xmm0, [rdi] – это один микро-fused uop на любом процессоре Intel или AMD с K10 или Core 2. ( https://agner.org/optimize/ ) То же самое для 256-битной версии AVX с векторами YMM.

  • верните текущий режим округления в обычный режим IEEE по умолчанию, используя исходное значение MXCSR. (от округлой до ближайшей, даже в случае тай-брейка)

Это позволяет загрузить + преобразование + сохранение 1 SIMD-вектора результатов за такт, так же быстро, как и усечение . (SSE2 имеет специальную инструкцию преобразования FP-> int для усечения, именно потому, что это очень часто необходимо компиляторам C. В плохие старые дни с x87, даже (int)x требуется изменить режим округления x87 на усечение, а затем обратно. cvttps2dq для упакованного float-> int с усечением (обратите внимание на дополнительный t в мнемонике). Или для скалярного перехода из XMM в целые регистры cvttss2si или cvttsd2si для скалярного double целочисленного значения.

С некоторой разверткой цикла и / или хорошей оптимизацией это должно быть возможно без узких мест в интерфейсе, только с пропускной способностью 1 в час, при условии отсутствия узких мест в кэше. (И на Intel перед Skylake, также узким местом с пропускной способностью упакованного конвертирования с пропускной способностью 1 кбит / с ), то есть 16, 32 или 64 байта за цикл, используя SSE2, AVX или AVX512.


Не меняя текущий режим округления, вам нужны SSE4.1 roundps для округления float до ближайшего целочисленного float используя ваш выбор режимов округления. Или вы можете использовать один из трюков в других ответах, которые работают для поплавков с малой достаточной величиной, чтобы соответствовать подписанному 32-битовому целому числу, поскольку это ваш конечный формат назначения в любом случае.)


(С правильными параметрами компилятора, такими как -fno-math-errno и правыми параметрами -march или -march , компиляторы могут использовать встроенный floor с использованием roundps или эквивалент скалярной и / или двойной точности, например roundsd xmm1, xmm0, 1 , но это стоит 2 часа и имеет 1 пропускную способность в 2 часа на Haswell для скаляра или векторов. Фактически, gcc8.2 будет roundsd для floor даже без каких-либо быстрых математических вариантов, как вы можете видеть в проводнике компилятора Godbolt . с -march=haswell . К сожалению, это не базовый уровень для x86-64, поэтому вам нужно включить его, если ваша машина поддерживает его.)

Да, floor() очень медленный на всех платформах, так как он должен реализовывать много поведения из спецификации IEEE fp. Вы не можете использовать его во внутренних циклах.

Я иногда использую макрос для приближения к полу ():

 #define PSEUDO_FLOOR( V ) ((V) >= 0 ? (int)(V) : (int)((V) - 1)) 

Он не ведет себя точно так же, как floor() : например, floor(-1) == -1 но PSEUDO_FLOOR(-1) == -2 , но он PSEUDO_FLOOR(-1) == -2 для большинства целей.

Фактически разветвленная версия, которая требует единственного преобразования между доменами с плавающей запятой и целым числом, перенесет значение x во все положительные или все отрицательные диапазоны, затем сбрасывает / усекает и переносит их обратно.

 long fast_floor(double x) { const unsigned long offset = ~(ULONG_MAX >> 1); return (long)((unsigned long)(x + offset) - offset); } long fast_ceil(double x) { const unsigned long offset = ~(ULONG_MAX >> 1); return (long)((unsigned long)(x - offset) + offset ); } 

Как указано в комментариях, эта реализация основана на временном значении x +- offset не переполняется.

На 64-битных платформах исходный код с промежуточным значением int64_t приведет к созданию трех ящиков команд, то же самое доступно для int32_t уменьшенного диапазона floor / ceil, где |x| < 0x40000000 |x| < 0x40000000 -

 inline int floor_x64(double x) { return (int)((int64_t)(x + 0x80000000UL) - 0x80000000LL); } inline int floor_x86_reduced_range(double x) { return (int)(x + 0x40000000) - 0x40000000; } 
  1. Они не делают то же самое. floor () – это функция. Поэтому использование этого метода вызывает вызов функции, распределение кадра стека, копирование параметров и получение результата. Кастинг не является вызовом функции, поэтому он использует более быстрые механизмы (я считаю, что он может использовать регистры для обработки значений).
  2. Вероятно, floor () уже оптимизирован.
  3. Можете ли вы выжать больше производительности из своего алгоритма? Может быть, могут помочь переключения строк и столбцов? Можете ли вы кэшировать общие значения? Включены ли все возможности вашего компилятора? Можете ли вы переключить операционную систему? компилятор? Программирование Pearls Джона Бентли имеет большой обзор возможных оптимизаций.

Быстрый двойной раунд

 double round(double x) { return double((x>=0.5)?(int(x)+1):int(x)); } 

Журнал терминалов

test custom_1 8.3837

test native_1 18.4989

test custom_2 8.36333

test native_2 18.5001

test custom_3 8.37316

test native_3 18.5012


Тестовое задание

 void test(char* name, double (*f)(double)) { int it = std::numeric_limits::max(); clock_t begin = clock(); for(int i=0; i 

Результат

Тип литья и использование вашего мозга в ~ 3 раза быстрее, чем использование собственных функций.