Избегание вызовов на пол()

Ответ 1

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

Здесь используется функция быстрого float-to-int, которая округляется вниз, используя синтаксис встроенной сборки MSVС++ (она должна дать вам правильную идею в любом случае):

inline int ftoi_fast(float f)
{
    int i;

    __asm
    {
        fld f
        fistp i
    }

    return i;
}

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

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

#include <emmintrin.h>

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

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

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

Ответ 2

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

#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 перед выполнением условное инет-литье дает вам ускорение, потому что оно делает ваш условный предсказуемым. Или ваш компилятор может делать это с чем-то иным, чем условная ветвь, и в этом случае это не полезно, трудно сказать, не тестируя и не глядя на сгенерированную сборку.)

Ответ 3

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

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

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

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

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

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

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

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

Ответ 4

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

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

EDIT Я удалил это как "слишком глупо, плюс с + ve vs. -ve issue". Так или иначе, он был отменен, он был отменен, и я оставлю его другим, чтобы решить, насколько это глупо.

Ответ 5

Если вы используете Visual С++, проверьте настройку компилятора "Включить внутренние функции". Если он включен, он должен выполнять большинство математических функций быстрее (включая пол). Недостатком является то, что обработка краев (например, NaN) может быть неправильной, но для игры вам может быть безразлично.

Ответ 6

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

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

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

Ответ 7

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

Ответ 8

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

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

Ответ 9

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