Стоит ли пытаться создать оптимизацию для sqrt () в C?

Question

Старые уловки (таблица поиска, приблизительные функции) для создания более быстрых реализаций sqrt () по-прежнему полезны, или же реализация по умолчанию так же быстро, как это происходит с современными компиляторами и оборудованием?

Answer 1

Правило 1: профиль перед оптимизацией

Прежде чем вкладывать какие-либо усилия в убеждение, что вы можете победить оптимизатор, вы должны профилировать все и выяснить, где на самом деле находится узкое место. В общем, маловероятно, что sqrt() само по себе является вашим узким местом.

Правило 2: замените алгоритм перед заменой стандартной функции

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

Что компилятор сделает для вас, если вы больше ничего не сделаете

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

В частности, я проверил MinGW gcc v3.4.5, и он заменил вызов sqrt() на встроенный код, который перетасовывал состояние FPU, и в ядре использовал инструкцию FSQRT. Благодаря тому, как стандарт C взаимодействует с плавающей точкой IEEE 754, он должен был следовать FSQRT с некоторым кодом для проверки исключительных условий и вызова реальной функции sqrt() из библиотеки времени выполнения, чтобы плавающая точка Исключения могут обрабатываться библиотекой в ​​соответствии с требованиями стандарта.

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

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

На практике любые хитрости сделают код менее понятным и, вероятно, менее обслуживаемым. В конце концов, вы бы предпочли сохранить (-b + sqrt(b*b - 4.*a*c)) / (2*a) или непрозрачный блок встроенных сборок и таблиц?

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

Однако в редких случаях можно добиться большего.

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

Редактировать: Я немного перестроил текст, чтобы сделать акцент на профилировании и алгоритмах, как это предлагал Джонатан Леффлер в комментариях. Спасибо, Джонатан.

Edit2: Исправлена ​​опечатка старшинства в квадратичном примере, замеченная острыми глазами kmm .

Answer 2

Sqrt практически не изменяется в большинстве систем. Это относительно медленная операция, но общая скорость системы улучшилась, поэтому, возможно, не стоит пытаться использовать «хитрости».

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

Я бы использовал профилирование, чтобы определить, является ли это "все еще полезным".

Answer 3

Если вы доказали, что вызов sqrt () в вашем коде является узким местом с профилировщиком, возможно, стоит попытаться создать оптимизированную версию. В противном случае это пустая трата времени.

Answer 4

Вероятно, это самый быстрый метод вычисления квадратного корня:

float fastsqrt(float val)  {
        union
        {
                int tmp;
                float val;
        } u;
        u.val = val;
        u.tmp -= 1<<23; /* Remove last bit so 1.0 gives 1.0 */
        /* tmp is now an approximation to logbase2(val) */
        u.tmp >>= 1; /* divide by 2 */
        u.tmp += 1<<29; /* add 64 to exponent: (e+127)/2 =(e/2)+63, */
        /* that represents (e/2)-64 but we want e/2 */
        return u.val;
}

статья в Википедии

---

Это, вероятно, самый быстрый метод вычисления обратного квадратного корня. Допустим, ошибка не более 0,00175228.

float InvSqrt (float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    return x*(1.5f - xhalf*x*x);
}

Это (очень приблизительно) примерно в 4 раза быстрее, чем (float)(1.0/sqrt(x))

статья в Википедии

Answer 5

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

Итак, возникает вопрос, знаете ли вы что-нибудь, что позволит вам лучше работать? Я не спрашиваю о специальных алгоритмах для вычисления квадратного корня (разработчики стандартной библиотеки тоже знают об этом, и если бы они вообще стояли, они бы их уже использовали), но есть ли у вас какая-либо конкретная информация о ваш вариант использования, который меняет ситуацию?

Вам нужна только ограниченная точность? Если это так, вы можете ускорить его по сравнению со стандартной версией библиотеки, которая должна быть точной.

Или вы знаете, что ваше приложение будет всегда работать на процессоре определенного типа? Затем вы можете посмотреть, насколько эффективна инструкция sqrt этого ЦП, и посмотреть, есть ли лучшие альтернативы. Конечно, недостатком этого является то, что если я запускаю ваше приложение на другом процессоре, ваш код может работать медленнее, чем стандартный sqrt ().

Можете ли вы сделать в своем коде предположения, которые разработчики стандартной библиотеки не смогли бы сделать?

Вам вряд ли удастся придумать лучшее решение проблемы "реализовать эффективную замену стандартной библиотеке sqrt".

Но, возможно, вам удастся найти решение проблемы «реализовать эффективную функцию квадратного корня для этой конкретной ситуации».

Answer 6

Почему бы и нет? Вы, наверное, многому научитесь!

Answer 7

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

Тем не менее, я обычно не создаю свои собственные оптимизации, а полагаюсь на грубое приближение обратного квадратного корня, предоставленного в качестве инструкции SIMD: rsqrtps. Это все еще действительно полезно для ускорения некоторых реальных случаев, если вы готовы пожертвовать точностью ради скорости. Использование rsqrtps может фактически сократить всю операцию, которая включает в себя деформацию и нормализацию нормалей вершин, почти вдвое, но ценой точности результатов (при этом способами, которые едва заметны человеческому глазу). ).

Я также все еще обнаружил, что быстрый обратный sqrt часто ошибочно приписывается Джону Кармаку, чтобы все еще улучшить производительность в скалярных случаях, хотя в настоящее время я не использую его много. Обычно естественно получить некоторое ускорение, если вы готовы пожертвовать точностью. Тем не менее, я бы даже не пытался побить C sqrt, если вы не пытаетесь жертвовать точностью ради скорости.

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

Answer 8

Мне очень трудно поверить, что функция sqrt является узким местом вашего приложения из-за того, как спроектированы современные компьютеры. Предполагая, что это не вопрос по отношению к какому-то сумасшедшему низкоуровневому процессору, вы получаете невероятное быстродействие, чтобы получить доступ к памяти вне кэшей вашего ЦП, поэтому, если ваш алгоритм не выполняет математику с очень небольшим числом (достаточно, чтобы они все в основном вписывается в кеши L1 и L2) вы не заметите ускорения оптимизации арифметики.