math

Тригонометрия в бенчмарках

  • Дата публикации: 15.12.2024
  • /Метки: benchmark, d, ldc, math
  • /Комментарии: 0

“Неважно, что ты любишь больше:
косинус ли, синус ли…”

Тригонометрия – основа многих приложений, от компьютерной графики до научных симуляций. Все мы привыкли вызывать sin и cos, не задумываясь, как они реализованы. А реализации могут быть разные! Работая над математической библиотекой для dlib2, я провел интересное исследование – какая тригонометрия лучше? Конечно, есть функции из std.math, и в большинстве случаев подойдут именно они. Но не все так просто – все зависит от того, что именно вы разрабатываете.

Если вы собираете обычное приложение, то кажется, что беспокоиться не о чем. Но если вам, по тем или иным причинам, нельзя обращаться к Phobos? Тогда есть два основных пути – sin и cos из стандартной библиотеки C, либо кастомная реализация, если код собирается под голое железо (например, при создании ядра ОС или программировании встраиваемой электроники). Но если вы используете LDC, то ничто не мешает использовать интринсики LLVM – они, оказывается, работают быстрее, чем std.math!

Я провел ряд тестов для всех вариантов тригонометрии:

  • Тест на точность – вычисление синуса и косинуса для 200 аргументов от -π до +π. Замерялась максимальная погрешность – расхождение результата с std.math.sin и std.math.cos;
  • Тест на производительность – время вычисления синуса и косинуса 1000000 раз.

Во всех кейсах я использовал LDC 1.39.0 под Windows 10. Получилось следующее:

  • std.math.sin, std.math.cos:
    • Время выполнения: 4 мс
  • LLVM интринсики llvm_sin, llvm_cos:
    • Время выполнения: 2 мс
    • Точность: абсолютная (макс. погрешность для sin: 0, для cos: 0)
  • Функции sin, cos из стандартной библиотеки C:
    • Время выполнения: 21 мс
    • Точность: абсолютная (макс. погрешность для sin: 0, для cos: 0)
  • Моя кастомная реализация на таблицах:
    • Время выполнения: 33 мс
    • Точность: порядка 10-7 (макс. погрешность для sin: 2.97038e-07, для cos: 1.78188e-07)

Также я пробовал версию с ассемблерными вставками, но она получилась почему-то медленнее кастомной – видимо, при использовании инлайнового ассемблера компилятор не задействует какие-то оптимизации (а еще есть мнение, что x87 fsin, fcos на современных процессорах медленные сами по себе). Смысла в таком варианте реализации особо нет, так что я его не стал рассматривать для включения в библиотеку.

В итоге в dlib2 войдут четыре реализации с таким приоритетом:

  • Если используется LDC, то синус и косинус – это интринсики (то есть, кодогенератор сам выбирает оптимальную реализацию под нужную архитектуру);
  • Если используются другие компиляторы (DMD, GDC):
    • Если код компилируется с поддержкой Phobos, то используются функции из std.math;
    • Если код собирается в режиме version(NoPhobos), но не version(FreeStanding) (то есть, под Windows или Unix-подобную ОС), то используются функции рантайма C;
    • Если же идет компиляция в bare metal, то используется кастомная реализация на таблицах.

Обновления

dlib 1.3.0

Вышла новая версия dlib. В библиотеке появился новый пакет dlib.math.random с реализацией генератора псевдослучайных чисел на основе C-функции rand. Проделан ряд улучшений в математическом пакете: добавлена поддержка компилятора GDC в модуль dlib.math.sse, появилась новая функция интерполяции bezierQuadratic.

Количество скачиваний dlib в реестре DUB достигло 1400 в месяц – рекордный показатель за все время существования проекта!

Подготовка к релизу Dagon 0.16

Новая версия Dagon планируется к выпуску совсем скоро – на днях внес ряд багфиксов и улучшений в физику Newton (в частности, исправлен прыжок контроллера персонажа на плоских поверхностях), а также добавил встроенную функцию создания скриншотов – Application.takeScreenshot.

Интерполяция на основе сигмоиды

Для одного из шейдеров на GLSL мне потребовалась “умная” интерполяция цветов с возможностью изменять резкость перехода от одного значения к другому – от полностью плавного (линейного) до дискретного. В итоге получилась вот такая функция, которую я вывел на основе рациональной сигмоиды – может быть, кому-то пригодится:

float sigmoid(float x, float k)
{
    return (x + x * k - k * 0.5 - 0.5) / 
        (abs(x * k * 4.0 - k * 2.0) - k + 1.0) + 0.5;
}

При k = 0 функция обращается в линейную, при k = 1 – разрывается в точке 0,5. Вы можете увидеть, как это работает, при помощи интерактивного графика на Desmos: https://www.desmos.com/calculator/s0cwcrtzvs.

Результат этой функции передается в привычный mix – то есть, вместо mix(c1, c2, t) пишем mix(c1, c2, sigmoid(t, k)). Получится, например, такое:

(градиенты гамма-скорректированы)

dlib 0.9.0 beta

Вышла бета-версия коллекции библиотек dlib 0.9.0. Из основных нововведений стоит отметить новый модуль dlib.math.tensor – реализацию тензоров с поддержкой как статического, так и динамического выделения памяти (еще один шаг, приближающий dlib к NumPy и Matlab). Также значительно улучшен пакет dlib.image: появился экспорт в BMP и TGA, двумерный foreach для изображений, диапазоны для окон и произвольных прямоугольных регионов. Новый пакет dlib.network, как планируется, будет содержать независимую от Phobos поддержку сети и веб-функциональность (пока в нем есть только парсер URL).

А еще Atrium был успешно портирован под FreeBSD.

dlib 0.5

Не так давно состоялось очередное крупное обновление коллекции библиотек dlib – вышла версия 0.5, наиболее значительным нововведением которой стала поддержка ручного управления памятью (РУП). Но – обо всем по порядку…

  • Новый модуль dlib.core.memory предоставляет средства для ручного выделения и высвобождения динамической памяти, независимые от сборщика мусора и основанные на malloc/free. Имеется поддержка структур, классов и массивов. При использовании классов рекомендуется использовать интерфейс ManuallyAllocatable и перегружать метод free, который ответственен за удаление объекта – в противном случае корректное удаление в некоторых случаях не гарантировано (например, при доступе через интерфейс или родительский класс).
  • Началась работа по переводу всей dlib на РУП. Так, загрузчики изрбражений (PNG, JPEG, TGA, BMP) в новой версии полностью независимы от сборщика мусора. Для этого активно используется паттерн абстрактной фабрики, ответственный за создание изображений  в памяти. Кстати, в загрузчике PNG значительно улучшена поддержка индексированных изображений, для них добавлена поддержка альфа-канала.
  • Кроме того, на РУП переведены некоторые контейнеры из dlib.container – BST, ассоциативный массив. Реализован полностью ручной динамический массив (dlib.container.array).
  • Еще одна новинка – ООП для структур (dlib.core.oop). Это экспериментальный модуль, реализующий для структур прототипный стиль ООП с поддержкой множественного наследования и параметрического полиморфизма. Полностью заменить классы он, конечно, не может, но окажется весьма полезен, если нужно создавать объекты с наследованием в стеке. В будущем планируется переписать некоторые внутренние механизмы dlib с использованием этой легковесной объектной системы.
  • В пакете dlib.math появилась поддержка дуальных кватернионов. Это частный случай алгербы Клиффорда, обобщение кватернионов на поле дуальных чисел. Их можно использовать, например, для описания движения тел в кинематике – один дуальный кватернион охватывает и перенос, и вращение. Кстати, реализация обычных кватернионов через инкапсуляцию теперь совместима с векторами.
  • Изменения коснулись и пакета вычислительной геометрии. Усеченная пирамида (dlib.geometry.frustum) теперь задается с нормалями ограничивающих плоскостей, указывающими наружу пирамиды. Подвергся изменению API проверки пересечения Frustum с AABB. Исправлены ошибки в реализации AABB и плоскости.