Избежание звонков на этаж () - PullRequest
11 голосов
/ 28 февраля 2010

Я работаю над фрагментом кода, в котором мне нужно разобраться с uvs (2D текстурными координатами), которые не обязательно находятся в диапазоне от 0 до 1. Как пример, иногда я получаю уф с компонентом, который равен 1,2. Чтобы справиться с этим, я реализую упаковку, которая вызывает мозаику, выполнив следующее:

u -= floor(u)
v -= floor(v)

Это приводит к тому, что 1,2 становится 0,2, что является желаемым результатом. Он также обрабатывает отрицательные случаи, такие как -0,4 становится 0,6.

Однако, эти призывы к полу довольно медленные. Я профилировал свое приложение с помощью Intel VTune и трачу огромное количество циклов, просто выполняя эту базовую операцию.

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

int inline fasterfloor( const float x ) { return x > 0 ? (int) x : (int) x - 1; }

Я видел несколько уловок, которые выполняются с помощью встроенной сборки, но ничего, что, кажется, не работает точно правильно или имеет существенное улучшение скорости.

Кто-нибудь знает какие-нибудь хитрости для обработки такого сценария?

Ответы [ 9 ]

11 голосов
/ 01 марта 2010

Итак, вы хотите действительно быстрое преобразование с плавающей точкой -> int? AFAIK int-> float конвертируется быстро, но, по крайней мере, в MSVC ++ преобразование float-> int вызывает небольшую вспомогательную функцию ftol (), которая делает некоторые сложные вещи для обеспечения выполнения преобразования, соответствующего стандартам. Если вам не нужно такое строгое преобразование, вы можете взломать сборку, предполагая, что вы используете x86-совместимый процессор.

Вот функция для быстрого преобразования с плавающей точкой в ​​int, которая округляется с использованием синтаксиса встроенной сборки MSVC ++ (в любом случае она должна дать вам правильное представление):

inline int ftoi_fast(float f)
{
    int i;

    __asm
    {
        fld f
        fistp i
    }

    return i;
}

В MSVC ++ 64-bit вам понадобится внешний файл .asm, поскольку 64-битный компилятор отклоняет встроенную сборку. Эта функция в основном использует необработанные инструкции x87 FPU для load float (fld), а затем сохраняет float как целое число (fistp). (Примечание: вы можете изменить режим округления, используемый здесь, напрямую настраивая регистры на процессоре, но не делайте этого, вы сломаете много вещей, включая реализацию MSVC sin и cos!)

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

#include <emmintrin.h>

inline int ftoi_sse1(float f)
{
    return _mm_cvtt_ss2si(_mm_load_ss(&f));     // SSE1 instructions for float->int
}

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

Один из них должен охватывать дорогостоящий случай с плавающей точкой на int, и любые преобразования int-to-float по-прежнему должны быть дешевыми. Извините за специфичность для Microsoft, но именно здесь я проделал аналогичную работу по повышению производительности и таким образом получил большие выгоды. Если переносимость / другие компиляторы являются проблемой, вам придется взглянуть на что-то еще, но эти функции компилируются, возможно, в две инструкции, занимающие менее 5 часов, в отличие от вспомогательной функции, которая занимает более 100 часов.

10 голосов
/ 10 января 2017

Старый вопрос, но я натолкнулся на него, и меня слегка содрогнуло, что он не получил удовлетворительного ответа.

TL; DR: * Не используйте ** встроенную сборку, встроенные функции или любые другие решения для этого! Вместо этого выполните компиляцию с быстрой / небезопасной математической оптимизацией ("-ffast-math -funsafe-math-optimizations -fno-math-errno" в g ++). Причина, по которой floor () такой медленный, заключается в том, что он меняет глобальное состояние, если приведение будет переполнено (FLT_MAX не подходит для скалярного целочисленного типа любого размера), что также делает невозможным векторизацию, если вы не отключите строгую совместимость IEEE-754 на который вы, вероятно, не должны полагаться в любом случае. Компиляция с этими флагами отключает поведение проблемы.

Некоторые замечания:

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

  2. Встроенная сборка с использованием SSE cvttss2si с методом, который вы описали, на моей машине на самом деле медленнее, чем простой цикл for с оптимизацией компилятора. Это вероятно потому, что ваш компилятор будет распределять регистры и лучше избегать остановок конвейера, если вы позволите ему векторизовать целые блоки кода вместе. Для такого короткого фрагмента кода, как этот, с несколькими внутренними зависимыми цепочками и практически без шансов на утечку регистров, у него очень мало шансов сделать хуже, чем оптимизированный вручную код, окруженный asm ().

  3. Встроенная сборка непереносима, не поддерживается в 64-разрядных сборках Visual Studio и безумно трудна для чтения. Внутренние особенности страдают от тех же предостережений, что и перечисленные выше.

  4. Все остальные перечисленные способы просто неверны, что, вероятно, хуже, чем медленный, и они дают в каждом случае такое незначительное улучшение производительности, что это не оправдывает грубость подхода. (int) (x + 16.0) -16.0 настолько плохо, что я даже не буду его трогать, но ваш метод также неверен, потому что он дает floor (-1) как -2. Также очень плохая идея включать ветки в математический код, когда это настолько критично для производительности, что стандартная библиотека не сделает эту работу за вас. Таким образом, ваш (неправильный) путь должен выглядеть больше как ((int) x) - (x <0.0), возможно, с промежуточным звеном, чтобы вам не приходилось выполнять перемещение fpu дважды. Ветви могут вызвать пропадание кэша, что полностью сведет на нет любое увеличение производительности; также, если math errno отключен, то приведение к int является самым большим остающимся узким местом любой реализации floor (). Если вы / действительно / не хотите получать правильные значения для отрицательных целых чисел, это может быть разумным приближением, но я бы не стал рисковать, если вы не очень хорошо знаете свой вариант использования. </p>

  5. Я пытался использовать побитовое приведение и округление через битовую маску, как это делает реализация newlib от SUN в fmodf, но это заняло очень много времени, и на моей машине было в несколько раз медленнее, даже без соответствующей флаги оптимизации компилятора. Весьма вероятно, что они написали этот код для какого-то древнего процессора, где операции с плавающей запятой были сравнительно очень дорогими и не было никаких векторных расширений, не говоря уже об операциях преобразования векторов; это больше не относится к любым распространенным архитектурам AFAIK. SUN также является местом рождения быстрой обратной подпрограммы sqrt (), используемой в Quake 3; теперь есть инструкция для большинства архитектур. Одна из самых больших ошибок микрооптимизации в том, что они быстро устаревают.

3 голосов
/ 01 марта 2010

Требуемую операцию можно выразить с помощью функции fmod (fmodf для float, а не double):

#include <math.h>
u = fmodf(u, 1.0f);

Вполне вероятно, что ваш компилятор сделает это наиболее эффективным способом, который работает.

С другой стороны, насколько вас беспокоит точность последнего бита? Можете ли вы поставить нижнюю границу для ваших отрицательных значений, например, что-то, зная, что они никогда не ниже -16,0? Если это так, что-то вроде этого избавит вас от условия, которое весьма вероятно будет полезно, если это не то, что может быть надежно предсказано ветвлением с вашими данными:

u = (u + 16.0);  // Does not affect fractional part aside from roundoff errors.
u -= (int)u;     // Recovers fractional part if positive.

(В этом отношении, в зависимости от того, как выглядят ваши данные и от процессора, который вы используете, если большая их часть отрицательна, а очень малая ниже 16.0, вы можете обнаружить, что добавление 16.0f перед выполнением условное int-приведение дает вам ускорение, потому что оно делает ваше условное предсказуемым, или ваш компилятор может делать это с чем-то другим, кроме условного перехода, и в этом случае это бесполезно; трудно сказать без тестирования и просмотра сгенерированной сборки.)

2 голосов
/ 28 февраля 2010

Если вы используете Visual C ++, проверьте настройку компилятора «Enable Intrinsic Functions». Если включено, это должно сделать большинство математических функций быстрее (включая пол). Недостатком является то, что обработка крайних случаев (например, NaN) может быть неправильной, но для игры вам может быть все равно.

2 голосов
/ 28 февраля 2010

Еще одна глупая идея, которая может сработать, если диапазон маленький ...

Извлеките экспоненту из числа с плавающей запятой, используя побитовые операции, затем используйте таблицу поиска, чтобы найти маску, которая стирает ненужные биты из мантиссы. Используйте это, чтобы найти слово (протрите биты ниже точки), чтобы избежать перенормировки.

РЕДАКТИРОВАТЬ Я удалил это как "слишком глупо, плюс с проблемой + ve против -ve". Так как за него проголосовали в любом случае, он был восстановлен, и я оставлю это другим, чтобы решить, насколько это глупо.

1 голос
/ 28 февраля 2010

Если диапазон значений, которые могут возникнуть, достаточно мал, возможно, вы можете выполнить двоичный поиск значения минимума. Например, если возможны значения -2 <= x <2 ... </p>

if (u < 0.0)
{
  if (u < 1.0)
  {
    //  floor is 0
  }
  else
  {
    //  floor is 1
  }
}
else
{
  if (u < -1.0)
  {
    //  floor is -2
  }
  else
  {
    //  floor is -1
  }
}

Я не даю никаких гарантий по этому поводу - я не знаю, как эффективность сравнения сравнивается с минимальной - но, возможно, стоит попробовать.

0 голосов
/ 23 апреля 2014

Если вы зациклились и используете u и v в качестве индексных координат, вместо того чтобы указывать плавающее число для получения координат, сохраняйте и float, и int одного и того же значения и увеличивайте их вместе. Это даст вам соответствующее целое число для использования при необходимости.

0 голосов
/ 10 января 2011

это не решает стоимость каста, но должно быть математически правильно:

int inline fasterfloor( const float x ) { return x < 0 ? (int) x == x ? (int) x : (int) x -1 : (int) x; }
0 голосов
/ 28 февраля 2010

Каков максимальный диапазон ввода ваших значений u, v? Если это довольно маленький диапазон, например От -5,0 до +5,0, тогда будет быстрее многократно добавлять / вычитать 1,0, пока вы не окажетесь в пределах диапазона, вместо того, чтобы вызывать дорогие функции, такие как floor.

...