понедельник, 18 февраля 2013 г.

Быстрое округление вместо медленного floor()

    Заметка для начинающих пользователей math.h в высокопроизводительных вычислениях. Судя по гуглу проблема известная, но не смотря на то, что я себя новичком в этих вопросах не считаю, о таких неприятностях не догадывался.
    Речь пойдёт о floor. Вообще говоря, описанные проблемы производительности свойственны многим функциям, но я напоролся именно  на floor. Если коротко, то floor работает медленно. Настолько медленно, что в моём сеточном методе моделирования жидкости floor оказался в первых строках профайлера. Дело в том, что floor делает множество проверок на ситуации типа NaN, inf и может изменять глобальную переменную errno для сообщения о ошибке. Всё это занимает бОльшую часть времени работы функции. Во многих задачах всё это совершенно не нужно, а нужна только  скорость. Под катом пара вариантов решения проблемы: собственный fastFloor и настроки компилятора.


FastFloor


    Специфика моей задачи такова, что разные inf'ы мне обрабатывать не надо. Так же мне не нужен "честный" floor, но об этом позже. Одно из первых гуглящихся, да и приходящих в голову, решений является ручная реализация через приведение к инту и разным поведением на положительных и отрицательных значениях. Что-то вроде этого:

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

    Работает почти как обычный floor за исключением inf, NaN и прочее, а так же отрицательных целых чисел. С дробными всё так же как в "честном" floor, а вот целые обрабатываются с ошибкой. Так PSEUDO_FLOOR( -2 ) == -3. Поведение не как у floor, но принципиально такое же. График функции будет выглядеть так же, только непрерывность справа замениться на непрерывность слева в отрицательных целых значениях аргумента. Это может сыграть значимую  роль в многих задачах, но мне надо пространство бить на клетки, и поэтому с какой стороны непрерывен floor мне до лампочки. Главное везде использовать одну функцию. Так, забыв заменить floor на fastFloor в нескольких местах, я получил редкие непонятные падения, когда точка в разных частях метода относилась к разным ячейкам.
    Что мы получим взамен на эту неточность? Очень существенное ускорение. В конце статьи есть ссылки на тесты. Для сборки требуется Qt! Результаты

Pentium G530 2.4GHz 2GB RAM Win7 32-bit MinGW 4.5 Qt 4.7.3:
floor() - 755 ms, fastFloor - 50 ms, ускорение ~15 раз.

Core2 Duo E6600 2.4GHz 4GB RAM Win7 64-bit MinGW 4.4, Qt 4.7.4:
floor() - 859 ms, fastFloor - 79 ms, ускорение ~11 раз.

Core2 Duo E6600 2.4GHz 4GB RAM Win7 64-bit MinGW 4.7, Qt 5.01:
floor() - 332 ms, fastFloor - 92 ms, ускорение ~3.6 раз.

    Интересно, что результат сильно зависит от компилятора. Опции вроде как одни и те же, но MinGW 4.7 значительно лучше справляется с библиотечным floor(). В любом случае новая версия существенно опережает своего библиотечного предшественника.

Флаги компилятора


    Для GCC это -ffast-math и -fno-math-errno. Люди пишут, что помогает, но на результаты моих тестов эти флаги вообще не повлияли. Возможно MinGW их проигнорировал, предлагаю вам протестировать. Вообще польза должна быть, но для этого надо разбираться.

D language


    Для D эта проблема так же актуальна, как и для C#. Надо сказать, что встретил я её, программируя на D. Решение с PSEUDO_FLOOR так же хорошо подходит, разве что записать придётся в виде функции.

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

    Тот самый сеточный метод, с которого всё началось, я писал на D. В результате этой махинации получил ~70% ускорения вычислений. Вам эта цифра, конечно, ничего не говорит, ведь кроме злополучного floor там много кода, но зато это пример практической пользы.

ссылка на исходники (требуется Qt)
ссылка на бинарник (Windows Qt 4.7.4, библиотеки для запуска в комплекте)

Комментариев нет:

Отправить комментарий