Типичное время выполнения элементарных функций

Question

Хорошо известно, что процессорная инструкция для умножения занимает в несколько раз больше времени, чем сложение, деление еще хуже (UPD: это уже не так, см. Ниже).А как насчет более сложных операций, таких как экспонента?Насколько они трудны?

Мотивация .Я заинтересован, потому что это помогло бы в разработке алгоритма оценить критические для производительности части алгоритмов на ранней стадии.Предположим, я хочу применить набор фильтров к изображению.Один из них оперирует по окрестности 3 × 3 каждого пикселя, суммирует их и принимает atan.Еще один суммирует больше соседних пикселей, но не использует сложные функции.Какой из них будет выполняться дольше?

Итак, в идеале я хочу иметь приблизительное относительное время выполнения элементарных операций, так как умножение обычно занимает в 5 раз больше времени, чем сложение, экспонента составляет около 100 умножений.Конечно, это дело порядков, а не точных значений.Я понимаю, что это зависит от аппаратного обеспечения и аргументов, поэтому предположим, что мы измеряем среднее время (в некотором смысле) для операций с плавающей запятой на современном x86 / x64.Для операций, которые не реализованы в аппаратном обеспечении, меня интересует типичное время выполнения для стандартных библиотек C ++.

Видели ли вы какие-либо источники, когда такие вещи анализировались?Этот вопрос имеет смысл вообще?Или никакие практические правила, подобные этому, не могут быть применены на практике?

Answer 1

Прежде всего, давайте прояснимся.Это:

Хорошо известно, что инструкция процессора для умножения занимает в несколько раз больше времени, чем сложение

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

Теперь, к вашему актуальному вопросу: это зависит как от архитектуры, так и отреализация.В недавней архитектуре с хорошо написанной математической библиотекой простые элементарные функции, такие как exp и log, обычно требуют нескольких десятков циклов (20-50 циклов - это разумная цифра с обратной стороны).С библиотекой низкого качества вы иногда увидите, что эти операции требуют нескольких сотен циклов.

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

Answer 2

Вы не должны беспокоиться об этом. Если я скажу вам, что типичная реализация трансцендентных функций в библиотеке C, как правило, занимает примерно 10 раз одно сложение / умножение с плавающей запятой (или 50 сложений / умножений с плавающей запятой) и примерно 5 раз деление с плавающей запятой, это не будет полезно для вас.

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

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

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

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

Кроме того, Intel Performance Primitives (если вы используете процессор Intel) - это что-то хорошее, если вы готовы обменять некоторую точность на скорость.

Answer 3

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