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

https://stackoverflow.com/questions/824118

05-07-2019
|

Вопрос

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

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

VC:  0.10
ICL: 0.20

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

VC:  0.04
ICL: 0.04

Как можно floor() это намного медленнее, чем простое приведение?!Он делает по сути то же самое (за исключением отрицательных чисел).2-й вопрос:Кто-нибудь знает о сверхбыстром 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]);
        }
    }
}

Решение

Пара вещей делает floor медленнее, чем приведение, и предотвращает векторизацию.

Самый важный из них:

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

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

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

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

Другие советы

Если вы собираетесь преобразовать результат операции 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 на округление в сторону бесконечности (он же floor).В C это должно быть возможно с помощью fenv материал, или _mm_getcsr / _mm_setcsr.
выполните цикл над массивом, выполняя _mm_cvtps_epi32 на SIMD-векторах, преобразующих 4 floatпреобразуется в 32-разрядное целое число с использованием текущего режима округления.(И сохранение результирующих векторов в пункт назначения.)

cvtps2dq xmm0, [rdi] представляет собой единый микропроцессорный 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 или -msse4 опции, компиляторы могут быть встроенными floor используя roundps, или скалярный эквивалент и/или эквивалент двойной точности, например roundsd xmm1, xmm0, 1, но это стоит 2 uops и имеет пропускную способность 1 на 2 такта в Haswell для скалярных или векторных данных.На самом деле, gcc8.2 будет встроенным roundsd для floor даже без каких-либо опций быстрой математики, как вы можете видеть в проводнике компилятора Godbolt.Но это с -march=haswell.К сожалению, это не базовая версия для x86-64, поэтому вам нужно включить ее, если ваш компьютер ее поддерживает.)

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

Иногда я использую макрос для аппроксимации floor ():

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

Он ведет себя не так, как floor(-1) == -1: например, 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 -

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;
}

<Ол>

Они не делают то же самое. Этаж () является функцией. Поэтому его использование вызывает вызов функции, выделение кадра стека, копирование параметров и получение результата. Приведение не является вызовом функции, поэтому оно использует более быстрые механизмы (я полагаю, что оно может использовать регистры для обработки значений).

Возможно, floor () уже оптимизирован.

Можете ли вы увеличить производительность своего алгоритма? Может быть, переключение строк и столбцов может помочь? Можете ли вы кешировать общие значения? Все ли оптимизации вашего компилятора включены? Можете ли вы переключить операционную систему? компилятор? «Жемчужины программирования» Джона Бентли содержит отличный обзор возможных оптимизаций.

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

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

Журнал регистрации терминала

тест custom_1 8.3837

тест native_1 18.4989

тест custom_2 8.36333

тест native_2 18.5001

тест custom_3 8.37316

тест native_3 18.5012

Тест

void test(char* name, double (*f)(double))
{
    int it = std::numeric_limits<int>::max();

    clock_t begin = clock();

    for(int i=0; i<it; i++)
    {
        f(double(i)/1000.0);
    }
    clock_t end = clock();

    cout << "test " << name << " " << double(end - begin) / CLOCKS_PER_SEC << endl;

}

int main(int argc, char **argv)
{

    test("custom_1",round);
    test("native_1",std::round);
    test("custom_2",round);
    test("native_2",std::round);
    test("custom_3",round);
    test("native_3",std::round);
    return 0;
}

Результат

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow